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