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