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
15namespace syncer {
16
17// Forward declarations needed for friend declarations.
18template <typename E, E MinEnumValue, E MaxEnumValue>
19class EnumSet;
20
21template <typename E, E Min, E Max>
22EnumSet<E, Min, Max> Union(EnumSet<E, Min, Max> set1,
23                           EnumSet<E, Min, Max> set2);
24
25template <typename E, E Min, E Max>
26EnumSet<E, Min, Max> Intersection(EnumSet<E, Min, Max> set1,
27                                  EnumSet<E, Min, Max> set2);
28
29template <typename E, E Min, E Max>
30EnumSet<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
42template <typename E, E MinEnumValue, E MaxEnumValue>
43class 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.
82    Iterator() : enums_(NULL), i_(kValueCount) {}
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.
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.
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.
102    void Inc() {
103      CHECK(Good());
104      i_ = FindNext(i_ + 1);
105    }
106
107   private:
108    friend Iterator EnumSet::First() const;
109
110    explicit Iterator(const EnumBitSet& enums)
111        : enums_(&enums), i_(FindNext(0)) {}
112
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
126  EnumSet() {}
127
128  explicit EnumSet(E value) {
129    Put(value);
130  }
131
132  EnumSet(E value1, E value2) {
133    Put(value1);
134    Put(value2);
135  }
136
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.
144  static EnumSet All() {
145    EnumBitSet enums;
146    enums.set();
147    return EnumSet(enums);
148  }
149
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.
159  void Put(E value) {
160    enums_.set(ToIndex(value));
161  }
162
163  // Adds all values in the given set to our set.
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.
171  void RetainAll(EnumSet other) {
172    enums_ &= other.enums_;
173  }
174
175  // If the given value is in range, removes it from our set.
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.
183  void RemoveAll(EnumSet other) {
184    enums_ &= ~other.enums_;
185  }
186
187  // Removes all values from our set.
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.
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.
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.
205  bool Equals(const EnumSet& other) const {
206    return enums_ == other.enums_;
207  }
208
209  // Returns true iff our set is empty.
210  bool Empty() const {
211    return !enums_.any();
212  }
213
214  // Returns how many values our set has.
215  size_t Size() const {
216    return enums_.count();
217  }
218
219  // Returns an iterator pointing to the first element (if any).
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
232  explicit EnumSet(EnumBitSet enums) : enums_(enums) {}
233
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
240  static size_t ToIndex(E value) {
241    DCHECK_GE(value, MinEnumValue);
242    DCHECK_LE(value, MaxEnumValue);
243    return value - MinEnumValue;
244  }
245
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
254template <typename E, E MinEnumValue, E MaxEnumValue>
255const E EnumSet<E, MinEnumValue, MaxEnumValue>::kMinValue;
256
257template <typename E, E MinEnumValue, E MaxEnumValue>
258const E EnumSet<E, MinEnumValue, MaxEnumValue>::kMaxValue;
259
260template <typename E, E MinEnumValue, E MaxEnumValue>
261const size_t EnumSet<E, MinEnumValue, MaxEnumValue>::kValueCount;
262
263// The usual set operations.
264
265template <typename E, E Min, E Max>
266EnumSet<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
271template <typename E, E Min, E Max>
272EnumSet<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
277template <typename E, E Min, E Max>
278EnumSet<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