libdballe  9.11
smallset.h
1 #ifndef DBALLE_CORE_SMALLSET_H
2 #define DBALLE_CORE_SMALLSET_H
3 
4 #include <vector>
5 #include <algorithm>
6 
7 namespace dballe {
8 namespace core {
9 
10 template<typename T> inline const T& smallset_default_get_value(const T& val) { return val; }
11 
15 template<typename Item, typename Value=Item, const Value& (*get_value)(const Item&)=smallset_default_get_value>
16 struct SmallSet
17 {
18  mutable std::vector<Item> items;
19  mutable size_t dirty = 0;
20 
21  typedef typename std::vector<Item>::const_iterator const_iterator;
22  typedef typename std::vector<Item>::iterator iterator;
23  typedef typename std::vector<Item>::const_reverse_iterator const_reverse_iterator;
24  typedef typename std::vector<Item>::reverse_iterator reverse_iterator;
25 
26  iterator begin() { return items.begin(); }
27  iterator end() { return items.end(); }
28  const_iterator begin() const { return items.begin(); }
29  const_iterator end() const { return items.end(); }
30  reverse_iterator rbegin() { return items.rbegin(); }
31  reverse_iterator rend() { return items.rend(); }
32  const_reverse_iterator rbegin() const { return items.rbegin(); }
33  const_reverse_iterator rend() const { return items.rend(); }
34  size_t size() const { return items.size(); }
35  bool empty() const { return items.empty(); }
36 
37  bool operator==(const SmallSet& o) const
38  {
39  if (dirty) rearrange_dirty();
40  if (o.dirty) o.rearrange_dirty();
41  return items == o.items;
42  }
43 
44  bool operator!=(const SmallSet& o) const
45  {
46  if (dirty) rearrange_dirty();
47  if (o.dirty) o.rearrange_dirty();
48  return items == o.items;
49  }
50 
51  void clear()
52  {
53  items.clear();
54  dirty = 0;
55  }
56 
57  int binary_search(const Value& value) const
58  {
59  int begin, end;
60  begin = -1, end = items.size();
61  while (end - begin > 1)
62  {
63  int cur = (end + begin) / 2;
64  if (value < get_value(items[cur]))
65  end = cur;
66  else
67  begin = cur;
68  }
69  if (begin == -1 || get_value(items[begin]) != value)
70  return -1;
71  else
72  return begin;
73  }
74 
75  const_iterator find(const Value& value) const
76  {
77  if (items.empty()) return end();
78 
79  // Stick to linear search if the vector size is small
80  if (items.size() < 6)
81  {
82  for (auto it = std::begin(items); it != std::end(items); ++it)
83  if (get_value(*it) == value)
84  return it;
85  return end();
86  }
87 
88  // Use binary search for larger vectors
89 
90  if (dirty > 16)
91  {
92  std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
93  return get_value(a) < get_value(b);
94  });
95  dirty = 0;
96  } else if (dirty) {
97  // Use insertion sort, if less than 16 new elements appeared since the
98  // last sort
99  rearrange_dirty();
100  }
101 
102  int pos = binary_search(value);
103  if (pos == -1)
104  return items.end();
105  else
106  return items.begin() + pos;
107  }
108 
109  iterator find(const Value& value)
110  {
111  if (items.empty()) return end();
112 
113  // Stick to linear search if the vector size is small
114  if (items.size() < 6)
115  {
116  for (auto it = std::begin(items); it != std::end(items); ++it)
117  if (get_value(*it) == value)
118  return it;
119  return end();
120  }
121 
122  // Use binary search for larger vectors
123 
124  if (dirty > 16)
125  {
126  std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
127  return get_value(a) < get_value(b);
128  });
129  dirty = 0;
130  } else if (dirty) {
131  // Use insertion sort, if less than 16 new elements appeared since the
132  // last sort
133  rearrange_dirty();
134  }
135 
136  int pos = binary_search(value);
137  if (pos == -1)
138  return items.end();
139  else
140  return items.begin() + pos;
141  }
142 
143  Item& add(const Item& item)
144  {
145  ++dirty;
146  items.emplace_back(item);
147  return items.back();
148  }
149 
150  // static const Value& _smallset_get_value(const Item&);
151 
152  void rearrange_dirty() const
153  {
154  // Rearrange newly inserted items by insertion sort
155  for (size_t i = items.size() - dirty; i < items.size(); ++i)
156  for (size_t j = i; j > 0 && get_value(items[j]) < get_value(items[j - 1]); --j)
157  std::swap(items[j], items[j - 1]);
158  dirty = 0;
159  }
160 };
161 
162 
163 template<typename Value>
164 struct SmallUniqueValueSet : protected SmallSet<Value>
165 {
171  using SmallSet<Value>::end;
173  using SmallSet<Value>::rend;
175  using SmallSet<Value>::size;
177  bool operator==(const SmallUniqueValueSet& o) const { return SmallSet<Value>::operator==(o); }
178  bool operator!=(const SmallUniqueValueSet& o) const { return SmallSet<Value>::operator!=(o); }
179 
180  void add(const Value& val)
181  {
182  auto i = this->find(val);
183  if (i != this->end()) return;
185  }
186 
187  bool has(const Value& val) const
188  {
189  return this->find(val) != this->end();
190  }
191 };
192 
193 
194 template<typename Value>
196 {
197  typedef typename SmallUniqueValueSet<Value>::iterator iterator;
198  typedef typename SmallUniqueValueSet<Value>::const_iterator const_iterator;
199  typedef typename SmallUniqueValueSet<Value>::reverse_iterator reverse_iterator;
200  typedef typename SmallUniqueValueSet<Value>::const_reverse_iterator const_reverse_iterator;
208 
209  iterator begin()
210  {
211  if (this->dirty) this->rearrange_dirty();
213  }
214  const_iterator begin() const
215  {
216  if (this->dirty) this->rearrange_dirty();
218  }
219  reverse_iterator rbegin()
220  {
221  if (this->dirty) this->rearrange_dirty();
223  }
224  const_reverse_iterator rbegin() const
225  {
226  if (this->dirty) this->rearrange_dirty();
228  }
229 
230  void add(const Value& val)
231  {
232  auto i = this->find(val);
233  if (i != this->end()) return;
235  }
236 
237  bool has(const Value& val) const
238  {
239  return this->find(val) != this->end();
240  }
241 };
242 
243 }
244 }
245 
246 #endif
Definition: cmdline.h:18
Definition: smallset.h:164
Set structure optimized for a small number of items.
Definition: smallset.h:16
Container for a wreport::Var pointer.
Definition: value.h:18
Definition: smallset.h:195