sync/internal_api/public/base/enum_set.h

   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   static_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
 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>
 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>
 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>
 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_