#ifndef IDSET_HPP
#define IDSET_HPP

#include <ostream>

#define CELL_TYPE unsigned int 
#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;
  }

  void invert() {
    for (unsigned int i = 0; i < DIV_ROUND_UP(_length, CELL_SIZE); ++i) {
      _values[i] = ~_values[i];
    }
  }

  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;";
    }
  }
  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 < DIV_ROUND_UP(_length, CELL_SIZE); ++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)
      : 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;
  };
  iterator begin() const {
    return iterator(*this);
  }
  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