1 files changed, 187 insertions, 0 deletions
diff --git a/impl/IdSet.hpp b/impl/IdSet.hpp
new file mode 100644
index 0000000..6f6fd3f
--- /dev/null
+++ b/impl/IdSet.hpp
@@ -0,0 +1,187 @@
+#ifndef IDSET_HPP
+#define IDSET_HPP
+
+#include <ostream>
+
+#define CELL_TYPE char
+#define CELL_SIZE (8 * sizeof(CELL_TYPE))
+#define DIV_ROUND_UP(NUM, DEM) ((NUM + DEM - 1) / DEM)
+
+template<typename T>
+class IdSet {
+  public:
+  IdSet() : _length(0), _values(NULL) { }
+  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;
+    }
+  }
+
+  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];
+    }
+  }
+
+  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];
+    }
+    return *this;
+  }
+
+  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;
+  }
+  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);
+  }
+  void remove(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;
+    if (this->contains(obj)) {
+      std::cout << obj.id() << " -> ";
+    } else {
+      std::cout << "null" << " -> ";
+    }
+    _values[cell] &= ~(1 << bit);
+    if (this->contains(obj)) {
+      std::cout << "still here" << std::endl;
+    } else {
+      std::cout << "Gone!" << std::endl;
+    }
+  }
+  void clear() {
+    for (unsigned int i = 0; i < DIV_ROUND_UP(_length, CELL_SIZE); ++i) {
+      _values[i] = 0;
+    }
+  }
+
+  void absorb(const IdSet& other) {
+    if (_length == other._length) {
+      for (unsigned int i = 0; i < _length; ++i) {
+        _values[i] |= other._values[i];
+      }
+    } else {
+      throw "Sets of different sizes cannot be combined.";
+    }
+  }
+  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.";
+    }
+  }
+
+  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;
+  }
+  bool operator!=(const IdSet& other) const {
+    return !(*this == other);
+  }
+
+
+  struct iterator {
+    iterator(const IdSet& set, unsigned int index)
+      : set(set), index(index) {
+      unsigned int cell, bit;
+      cell = index / CELL_SIZE;
+      bit = index % CELL_SIZE;
+      while (index < set._length &&
+             (set._values[cell] & (1 << bit)) == 0) {
+        index++;
+        cell = index / CELL_SIZE;
+        bit = index % CELL_SIZE;
+      }
+    }
+    unsigned int operator*() const {
+      return index;
+    }
+    iterator& operator++() {
+      unsigned int cell, bit;
+      do {
+        index++;
+        if (index == set._length) {
+          return *this;
+        }
+        cell = index / CELL_SIZE;
+        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;
+  };
+  iterator begin() const {
+    return iterator(*this, 0);
+  }
+  iterator end() const {
+    return iterator(*this, _length);
+  }
+
+  private:
+  unsigned int _length;
+  CELL_TYPE* _values;
+};
+
+template<typename T>
+std::ostream& operator<<(std::ostream& cout, const IdSet<T>& set) {
+  cout << "{";
+  for (typename IdSet<T>::iterator it = set.begin();
+       it != set.end();
+       ++it) {
+    cout << *it << ", ";
+  }
+  cout << "}";
+  return cout;
+}
+
+#endif