OLD | NEW |
| (Empty) |
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 #ifndef SYNC_INTERNAL_API_PUBLIC_BASE_ENUM_SET_H_ | |
6 #define SYNC_INTERNAL_API_PUBLIC_BASE_ENUM_SET_H_ | |
7 | |
8 #include <bitset> | |
9 #include <cstddef> | |
10 #include <string> | |
11 | |
12 #include "base/logging.h" | |
13 | |
14 namespace syncer { | |
15 | |
16 // Forward declarations needed for friend declarations. | |
17 template <typename E, E MinEnumValue, E MaxEnumValue> | |
18 class EnumSet; | |
19 | |
20 template <typename E, E Min, E Max> | |
21 EnumSet<E, Min, Max> Union(EnumSet<E, Min, Max> set1, | |
22 EnumSet<E, Min, Max> set2); | |
23 | |
24 template <typename E, E Min, E Max> | |
25 EnumSet<E, Min, Max> Intersection(EnumSet<E, Min, Max> set1, | |
26 EnumSet<E, Min, Max> set2); | |
27 | |
28 template <typename E, E Min, E Max> | |
29 EnumSet<E, Min, Max> Difference(EnumSet<E, Min, Max> set1, | |
30 EnumSet<E, Min, Max> set2); | |
31 | |
32 // An EnumSet is a set that can hold enum values between a min and a | |
33 // max value (inclusive of both). It's essentially a wrapper around | |
34 // std::bitset<> with stronger type enforcement, more descriptive | |
35 // member function names, and an iterator interface. | |
36 // | |
37 // If you're working with enums with a small number of possible values | |
38 // (say, fewer than 64), you can efficiently pass around an EnumSet | |
39 // for that enum around by value. | |
40 | |
41 template <typename E, E MinEnumValue, E MaxEnumValue> | |
42 class EnumSet { | |
43 public: | |
44 typedef E EnumType; | |
45 static const E kMinValue = MinEnumValue; | |
46 static const E kMaxValue = MaxEnumValue; | |
47 static const size_t kValueCount = kMaxValue - kMinValue + 1; | |
48 static_assert(kMinValue < kMaxValue, | |
49 "min value must be less than max value"); | |
50 | |
51 private: | |
52 // Declaration needed by Iterator. | |
53 typedef std::bitset<kValueCount> EnumBitSet; | |
54 | |
55 public: | |
56 // Iterator is a forward-only read-only iterator for EnumSet. Its | |
57 // interface is deliberately distinct from an STL iterator as its | |
58 // semantics are substantially different. | |
59 // | |
60 // Example usage: | |
61 // | |
62 // for (EnumSet<...>::Iterator it = enums.First(); it.Good(); it.Inc()) { | |
63 // Process(it.Get()); | |
64 // } | |
65 // | |
66 // The iterator must not be outlived by the set. In particular, the | |
67 // following is an error: | |
68 // | |
69 // EnumSet<...> SomeFn() { ... } | |
70 // | |
71 // /* ERROR */ | |
72 // for (EnumSet<...>::Iterator it = SomeFun().First(); ... | |
73 // | |
74 // Also, there are no guarantees as to what will happen if you | |
75 // modify an EnumSet while traversing it with an iterator. | |
76 class Iterator { | |
77 public: | |
78 // A default-constructed iterator can't do anything except check | |
79 // Good(). You need to call First() on an EnumSet to get a usable | |
80 // iterator. | |
81 Iterator() : enums_(NULL), i_(kValueCount) {} | |
82 ~Iterator() {} | |
83 | |
84 // Copy constructor and assignment welcome. | |
85 | |
86 // Returns true iff the iterator points to an EnumSet and it | |
87 // hasn't yet traversed the EnumSet entirely. | |
88 bool Good() const { | |
89 return enums_ && i_ < kValueCount && enums_->test(i_); | |
90 } | |
91 | |
92 // Returns the value the iterator currently points to. Good() | |
93 // must hold. | |
94 E Get() const { | |
95 CHECK(Good()); | |
96 return FromIndex(i_); | |
97 } | |
98 | |
99 // Moves the iterator to the next value in the EnumSet. Good() | |
100 // must hold. Takes linear time. | |
101 void Inc() { | |
102 CHECK(Good()); | |
103 i_ = FindNext(i_ + 1); | |
104 } | |
105 | |
106 private: | |
107 friend Iterator EnumSet::First() const; | |
108 | |
109 explicit Iterator(const EnumBitSet& enums) | |
110 : enums_(&enums), i_(FindNext(0)) {} | |
111 | |
112 size_t FindNext(size_t i) { | |
113 while ((i < kValueCount) && !enums_->test(i)) { | |
114 ++i; | |
115 } | |
116 return i; | |
117 } | |
118 | |
119 const EnumBitSet* enums_; | |
120 size_t i_; | |
121 }; | |
122 | |
123 // You can construct an EnumSet with 0, 1, 2, or 3 initial values. | |
124 | |
125 EnumSet() {} | |
126 | |
127 explicit EnumSet(E value) { | |
128 Put(value); | |
129 } | |
130 | |
131 EnumSet(E value1, E value2) { | |
132 Put(value1); | |
133 Put(value2); | |
134 } | |
135 | |
136 EnumSet(E value1, E value2, E value3) { | |
137 Put(value1); | |
138 Put(value2); | |
139 Put(value3); | |
140 } | |
141 | |
142 // Returns an EnumSet with all possible values. | |
143 static EnumSet All() { | |
144 EnumBitSet enums; | |
145 enums.set(); | |
146 return EnumSet(enums); | |
147 } | |
148 | |
149 ~EnumSet() {} | |
150 | |
151 // Copy constructor and assignment welcome. | |
152 | |
153 // Set operations. Put, Retain, and Remove are basically | |
154 // self-mutating versions of Union, Intersection, and Difference | |
155 // (defined below). | |
156 | |
157 // Adds the given value (which must be in range) to our set. | |
158 void Put(E value) { | |
159 enums_.set(ToIndex(value)); | |
160 } | |
161 | |
162 // Adds all values in the given set to our set. | |
163 void PutAll(EnumSet other) { | |
164 enums_ |= other.enums_; | |
165 } | |
166 | |
167 // There's no real need for a Retain(E) member function. | |
168 | |
169 // Removes all values not in the given set from our set. | |
170 void RetainAll(EnumSet other) { | |
171 enums_ &= other.enums_; | |
172 } | |
173 | |
174 // If the given value is in range, removes it from our set. | |
175 void Remove(E value) { | |
176 if (InRange(value)) { | |
177 enums_.reset(ToIndex(value)); | |
178 } | |
179 } | |
180 | |
181 // Removes all values in the given set from our set. | |
182 void RemoveAll(EnumSet other) { | |
183 enums_ &= ~other.enums_; | |
184 } | |
185 | |
186 // Removes all values from our set. | |
187 void Clear() { | |
188 enums_.reset(); | |
189 } | |
190 | |
191 // Returns true iff the given value is in range and a member of our set. | |
192 bool Has(E value) const { | |
193 return InRange(value) && enums_.test(ToIndex(value)); | |
194 } | |
195 | |
196 // Returns true iff the given set is a subset of our set. | |
197 bool HasAll(EnumSet other) const { | |
198 return (enums_ & other.enums_) == other.enums_; | |
199 } | |
200 | |
201 // Returns true iff our set is empty. | |
202 bool Empty() const { | |
203 return !enums_.any(); | |
204 } | |
205 | |
206 // Returns how many values our set has. | |
207 size_t Size() const { | |
208 return enums_.count(); | |
209 } | |
210 | |
211 // Returns an iterator pointing to the first element (if any). | |
212 Iterator First() const { | |
213 return Iterator(enums_); | |
214 } | |
215 | |
216 // Returns true iff our set and the given set contain exactly the same values. | |
217 bool operator==(const EnumSet& other) const { return enums_ == other.enums_; } | |
218 | |
219 // Returns true iff our set and the given set do not contain exactly the same | |
220 // values. | |
221 bool operator!=(const EnumSet& other) const { return enums_ != other.enums_; } | |
222 | |
223 private: | |
224 friend EnumSet Union<E, MinEnumValue, MaxEnumValue>( | |
225 EnumSet set1, EnumSet set2); | |
226 friend EnumSet Intersection<E, MinEnumValue, MaxEnumValue>( | |
227 EnumSet set1, EnumSet set2); | |
228 friend EnumSet Difference<E, MinEnumValue, MaxEnumValue>( | |
229 EnumSet set1, EnumSet set2); | |
230 | |
231 explicit EnumSet(EnumBitSet enums) : enums_(enums) {} | |
232 | |
233 static bool InRange(E value) { | |
234 return (value >= MinEnumValue) && (value <= MaxEnumValue); | |
235 } | |
236 | |
237 // Converts a value to/from an index into |enums_|. | |
238 | |
239 static size_t ToIndex(E value) { | |
240 DCHECK_GE(value, MinEnumValue); | |
241 DCHECK_LE(value, MaxEnumValue); | |
242 return value - MinEnumValue; | |
243 } | |
244 | |
245 static E FromIndex(size_t i) { | |
246 DCHECK_LT(i, kValueCount); | |
247 return static_cast<E>(MinEnumValue + i); | |
248 } | |
249 | |
250 EnumBitSet enums_; | |
251 }; | |
252 | |
253 template <typename E, E MinEnumValue, E MaxEnumValue> | |
254 const E EnumSet<E, MinEnumValue, MaxEnumValue>::kMinValue; | |
255 | |
256 template <typename E, E MinEnumValue, E MaxEnumValue> | |
257 const E EnumSet<E, MinEnumValue, MaxEnumValue>::kMaxValue; | |
258 | |
259 template <typename E, E MinEnumValue, E MaxEnumValue> | |
260 const size_t EnumSet<E, MinEnumValue, MaxEnumValue>::kValueCount; | |
261 | |
262 // The usual set operations. | |
263 | |
264 template <typename E, E Min, E Max> | |
265 EnumSet<E, Min, Max> Union(EnumSet<E, Min, Max> set1, | |
266 EnumSet<E, Min, Max> set2) { | |
267 return EnumSet<E, Min, Max>(set1.enums_ | set2.enums_); | |
268 } | |
269 | |
270 template <typename E, E Min, E Max> | |
271 EnumSet<E, Min, Max> Intersection(EnumSet<E, Min, Max> set1, | |
272 EnumSet<E, Min, Max> set2) { | |
273 return EnumSet<E, Min, Max>(set1.enums_ & set2.enums_); | |
274 } | |
275 | |
276 template <typename E, E Min, E Max> | |
277 EnumSet<E, Min, Max> Difference(EnumSet<E, Min, Max> set1, | |
278 EnumSet<E, Min, Max> set2) { | |
279 return EnumSet<E, Min, Max>(set1.enums_ & ~set2.enums_); | |
280 } | |
281 | |
282 } // namespace syncer | |
283 | |
284 #endif // SYNC_INTERNAL_API_PUBLIC_BASE_ENUM_SET_H_ | |
OLD | NEW |