summaryrefslogtreecommitdiff
path: root/impl/IdSet.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'impl/IdSet.hpp')
-rw-r--r--impl/IdSet.hpp187
1 files changed, 187 insertions, 0 deletions
diff --git a/impl/IdSet.hpp b/impl/IdSet.hpp
new file mode 100644
index 0000000..6ced6b3
--- /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 < _length; ++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 < _length; ++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 < _length; ++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 < _length; ++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