Change the set to use a std::set for now

This should perform better in cases where we have smaller sets.

1 files changed, 35 insertions, 109 deletions

diff --git a/impl/IdSet.hpp b/impl/IdSet.hpp
index f845325..99f89cc 100644
--- a/impl/IdSet.hpp
+++ b/impl/IdSet.hpp
@@ -10,159 +10,85 @@
 template<typename T>
 class IdSet {
   public:
-  IdSet() : _length(0), _values(NULL) { }
+  IdSet() : _range(0) { }
   IdSet(unsigned int length)
-    : _length(length),
-      _values(new CELL_TYPE[DIV_ROUND_UP(length, CELL_SIZE)]) {
-    for (unsigned int i = 0; i < DIV_ROUND_UP(_length, CELL_SIZE); ++i) {
-      _values[i] = 0;
-    }
-  }
+    : _range(length) { }
 
   virtual ~IdSet() {
-    if (_values != NULL)
-      delete[] _values;
   }
 
   IdSet(const IdSet& other) {
-    _length = other._length;
-    _values = new CELL_TYPE[DIV_ROUND_UP(_length, CELL_SIZE)];
-    for (unsigned int i = 0; i < DIV_ROUND_UP(_length, CELL_SIZE); ++i) {
-      _values[i] = other._values[i];
-    }
+    _range = other._range;
+    _set = other._set;
   }
 
   IdSet& operator=(const IdSet& other) {
-    if (_length != other._length) {
-      if (_values != NULL)
-        delete[] _values;
-      _length = other._length;
-      _values = new CELL_TYPE[DIV_ROUND_UP(_length, CELL_SIZE)];
-    }
-    for (unsigned int i = 0; i < DIV_ROUND_UP(_length, CELL_SIZE); ++i) {
-      _values[i] = other._values[i];
-    }
+    _range = other._range;
+    _set = other._set;
     return *this;
   }
 
   void invert() {
-    for (unsigned int i = 0; i < DIV_ROUND_UP(_length, CELL_SIZE); ++i) {
-      _values[i] = ~_values[i];
+    for (unsigned int i = 0; i < _range; ++i) {
+      iterator it = _set.find(i);
+      if (it == _set.end()) {
+        _set.insert(i);
+      } else {
+        _set.erase(it);
+      }
     }
   }
 
   bool contains(const T& obj) const {
-    unsigned int id = obj.id();
-    if (id >= _length) {
-      throw "Array out of bounds;";
-    }
-    unsigned int cell = id / CELL_SIZE;
-    unsigned int bit = id % CELL_SIZE;
-    return (_values[cell] & (1 << bit)) != 0;
+    return _set.find(obj.id()) != _set.end();
   }
   void insert(const T& obj) {
-    unsigned int id = obj.id();
-    if (id >= _length) {
-      throw "Array out of bounds;";
-    }
-    unsigned int cell = id / CELL_SIZE;
-    unsigned int bit = id % CELL_SIZE;
-    _values[cell] |= (1 << bit);
+    _set.insert(obj.id());
   }
   void remove(const T& obj) {
-    unsigned int id = obj.id();
-    if (id >= _length) {
-      throw "Array out of bounds;";
-    }
+    _set.erase(obj.id());
   }
   void clear() {
-    for (unsigned int i = 0; i < DIV_ROUND_UP(_length, CELL_SIZE); ++i) {
-      _values[i] = 0;
-    }
+    _set.clear();
   }
 
   void absorb(const IdSet& other) {
-    if (_length == other._length) {
-      for (unsigned int i = 0; i < DIV_ROUND_UP(_length, CELL_SIZE); ++i) {
-        _values[i] |= other._values[i];
-      }
-    } else {
-      throw "Sets of different sizes cannot be combined.";
+    for (iterator it = other.begin(), end = other.end();
+         it != end;
+         ++it) {
+      _set.insert(*it);
     }
   }
   void filter(const IdSet& other) {
-    if (_length == other._length) {
-      for (unsigned int i = 0; i < DIV_ROUND_UP(_length, CELL_SIZE); ++i) {
-        _values[i] &= ~(other._values[i]);
-      }
-    } else {
-      throw "Sets of different sizes cannot be filtered.";
+    for (iterator it = other.begin(), end = other.end();
+         it != end;
+         ++it) {
+      _set.erase(*it);
     }
   }
 
   bool operator==(const IdSet& other) const {
-    if (_length != other._length)
-      return false;
-    for (unsigned int i = 0; i < DIV_ROUND_UP(_length, CELL_SIZE); ++i) {
-      if (_values[i] != other._values[i])
-        return false;
-    }
-    return true;
+    return _set == other._set;
   }
   bool operator!=(const IdSet& other) const {
     return !(*this == other);
   }
 
-  struct iterator {
-    iterator(const IdSet& set)
-      : set(set), index(0) {
-      if (set._values[0] & 1) {
-        return; // we have a zero
-      }
-      ++(*this);
-    }
-    iterator(const IdSet& set, unsigned int index)
-      : set(set), index(index) { }
-    unsigned int operator*() const {
-      return index;
-    }
-    iterator& operator++() {
-      unsigned int cell, bit;
-      do {
-        index++;
-        for (;; index += CELL_SIZE) {
-          if (index >= set._length) {
-            index = set._length;
-            return *this;
-          }
-          cell = index / CELL_SIZE;
-          if (set._values[cell] != 0)
-            break;
-        }
-        bit = index % CELL_SIZE;
-      } while ((set._values[cell] & (1 << bit)) == 0);
-      return *this;
-    }
-    bool operator==(const iterator& other) {
-      return other.index == index;
-    }
-    bool operator!=(const iterator& other) {
-      return !(*this == other);
-    }
-    private:
-    const IdSet& set;
-    unsigned int index;
-  };
+  typedef std::set<unsigned int>::const_iterator iterator;
   iterator begin() const {
-    return iterator(*this);
+    return _set.begin();
   }
   iterator end() const {
-    return iterator(*this, _length);
+    return _set.end();
+  }
+
+  unsigned int size() const {
+    return _set.size();
   }
 
   private:
-  unsigned int _length;
-  CELL_TYPE* _values;
+  unsigned int _range;
+  std::set<unsigned int> _set;
 };
 
 template<typename T>