libdballe 9.6
smallset.h
1#ifndef DBALLE_CORE_SMALLSET_H
2#define DBALLE_CORE_SMALLSET_H
3
4#include <vector>
5#include <algorithm>
6
7namespace dballe {
8namespace core {
9
10template<typename T> inline const T& smallset_default_get_value(const T& val) { return val; }
11
15template<typename Item, typename Value=Item, const Value& (*get_value)(const Item&)=smallset_default_get_value>
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
163template<typename Value>
164struct SmallUniqueValueSet : protected SmallSet<Value>
165{
166 using SmallSet<Value>::iterator;
167 using SmallSet<Value>::const_iterator;
168 using SmallSet<Value>::reverse_iterator;
169 using SmallSet<Value>::const_reverse_iterator;
170 using SmallSet<Value>::begin;
171 using SmallSet<Value>::end;
172 using SmallSet<Value>::rbegin;
173 using SmallSet<Value>::rend;
174 using SmallSet<Value>::empty;
175 using SmallSet<Value>::size;
176 using SmallSet<Value>::clear;
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
194template<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;
201 using SmallUniqueValueSet<Value>::end;
202 using SmallUniqueValueSet<Value>::rend;
203 using SmallUniqueValueSet<Value>::empty;
204 using SmallUniqueValueSet<Value>::size;
205 using SmallUniqueValueSet<Value>::clear;
206 using SmallUniqueValueSet<Value>::operator==;
207 using SmallUniqueValueSet<Value>::operator!=;
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
Container for a wreport::Var pointer.
Definition: value.h:19
Set structure optimized for a small number of items.
Definition: smallset.h:17
Definition: smallset.h:165
Definition: smallset.h:196