Vcsn  2.4
Be Rational
sparse-set.hh
Go to the documentation of this file.
1 #pragma once
2 
3 #include <vector>
4 
5 namespace vcsn
6 {
11  template <typename T>
12  class sparse_set
13  {
15  static_assert(std::is_unsigned<T>::value,
16  "sparse-set: requires unsigned indexes");
17 
18  public:
19  sparse_set(size_t max_size = 0)
20  : dense_{}
21  , sparse_{}
22  {
23  set_max_size(max_size);
24  }
25 
30  template <template <typename Elt> class Container,
31  typename = decltype(std::declval<Container<T>>().size())>
32  sparse_set(const Container<T>& cont)
33  : dense_{}
34  , sparse_{}
35  {
36  set_max_size(cont.size());
37  for (const auto& elt : cont)
38  insert(elt);
39  }
40 
42  void set_max_size(size_t max_size)
43  {
44  sparse_.resize(max_size);
45  }
46 
47  bool emplace(T e)
48  {
49  return insert(e);
50  }
51 
55  // already present in the set.
56  bool insert(T e)
57  {
58  if (has(e))
59  return false;
60  if (sparse_.size() <= e)
61  sparse_.resize(e + 1);
62  if (curr_ < dense_.size())
63  dense_[curr_] = e;
64  else
65  dense_.push_back(e);
66  sparse_[e] = curr_;
67  ++curr_;
68  return true;
69  }
70 
71  bool has(T e) const
72  {
73  return e < sparse_.capacity()
74  && sparse_[e] < curr_
75  && dense_[sparse_[e]] == e;
76  }
77 
81  void erase(T e)
82  {
83  if (has(e))
84  {
85  T last = dense_[curr_ - 1];
86  dense_[sparse_[e]] = last;
87  sparse_[last] = sparse_[e];
88  --curr_;
89  }
90  }
91 
93  void clear()
94  {
95  curr_ = 0;
96  }
97 
98  auto begin()
99  {
100  return dense_.begin();
101  }
102 
103  auto end()
104  {
105  return dense_.begin() + curr_;
106  }
107 
108  auto begin() const
109  {
110  return dense_.begin();
111  }
112 
113  auto end() const
114  {
115  return dense_.begin() + curr_;
116  }
117 
118  private:
120  std::vector<T> dense_;
122  std::vector<T> sparse_;
124  T curr_ = 0;
125  };
126 
127  template <typename T>
128  bool
129  has(const sparse_set<T>& s, T e)
130  {
131  return s.has(e);
132  }
133 }
void erase(T e)
Erase an element.
Definition: sparse-set.hh:81
auto end() const
Definition: sparse-set.hh:113
sparse_set(size_t max_size=0)
The template parameter corresponds to indexes so it has to be unsigned.
Definition: sparse-set.hh:19
Sparse Set implementation.
Definition: sparse-set.hh:12
std::vector< T > sparse_
Indexes of elements in the dense_ vector.
Definition: sparse-set.hh:122
bool insert(T e)
Insert new value.
Definition: sparse-set.hh:56
bool emplace(T e)
Definition: sparse-set.hh:47
auto begin() const
Definition: sparse-set.hh:108
Definition: a-star.hh:8
size_t size(const ExpSet &rs, const typename ExpSet::value_t &r)
bool has(T e) const
Definition: sparse-set.hh:71
std::vector< T > dense_
Actual elements of the set, not sorted.
Definition: sparse-set.hh:120
void clear()
Flush all elements from the set.
Definition: sparse-set.hh:93
T curr_
Current number of elements.
Definition: sparse-set.hh:124
void set_max_size(size_t max_size)
Set current vector size.
Definition: sparse-set.hh:42
ATTRIBUTE_PURE bool has(const boost::container::flat_set< Key, Compare, Allocator > &s, const Key &e)
Whether e is member of s.
Definition: setalpha.hh:25
sparse_set(const Container< T > &cont)
Construct with a container.
Definition: sparse-set.hh:32