#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() : _range(0) { }
  IdSet(unsigned int length)
    : _range(length) { }

  virtual ~IdSet() {
  }

  IdSet(const IdSet& other) {
    _range = other._range;
    _set = other._set;
  }

  IdSet& operator=(const IdSet& other) {
    _range = other._range;
    _set = other._set;
    return *this;
  }

  void invert() {
    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 {
    return _set.find(obj.id()) != _set.end();
  }
  void insert(const T& obj) {
    _set.insert(obj.id());
  }
  void remove(const T& obj) {
    _set.erase(obj.id());
  }
  void clear() {
    _set.clear();
  }

  void absorb(const IdSet& other) {
    for (iterator it = other.begin(), end = other.end();
         it != end;
         ++it) {
      _set.insert(*it);
    }
  }
  void filter(const IdSet& other) {
    for (iterator it = other.begin(), end = other.end();
         it != end;
         ++it) {
      _set.erase(*it);
    }
  }

  bool operator==(const IdSet& other) const {
    return _set == other._set;
  }
  bool operator!=(const IdSet& other) const {
    return !(*this == other);
  }

  typedef std::set<unsigned int>::const_iterator iterator;
  iterator begin() const {
    return _set.begin();
  }
  iterator end() const {
    return _set.end();
  }

  unsigned int size() const {
    return _set.size();
  }

  private:
  unsigned int _range;
  std::set<unsigned int> _set;
};

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