#ifndef _BITARRAY_
#define _BITARRAY_

#undef pptr
#include <vector>
#include <string>
#include <algorithm>    // swap
#define pptr(x) (((uchar *)&now)+proc_offset[x])

using namespace std;
 
class BitArray {
  class reference {
    unsigned long mask;
    unsigned long &ref;
  public:
    reference(unsigned long m, unsigned long &r) : mask(m), ref(r) {}
    reference &operator=(bool val) {
      if(val)
        ref |= mask;
      else
        ref &= ~mask;
      return *this;
    }
    operator bool()   {return (ref & mask) != 0;}     // returns 0 or 1
    bool operator~()  {return !(bool(*this));}
  };

  enum {BITS = sizeof(unsigned long) * 8};
  unsigned long *data;
  int bitSize;
  int chunkCount;
  void init(int size);
  void assign(const BitArray &copy);
public:
  unsigned long *posn1, *posn2, *endn1;
  explicit BitArray(int size = 0)           {init(size);}
  BitArray(const BitArray &copy)            {assign(copy);}
  BitArray(int size, const vector<int> &set); // dual to toIntVector
  BitArray &operator=(const BitArray &copy) {
    bitSize = copy.bitSize;
    chunkCount = copy.chunkCount;
    // data = new unsigned long[chunkCount];
    for(int i = 0; i < chunkCount; i++)
    data[i] = copy.data[i];
    // delete[] data; assign(copy); 
    return *this;
  }
  ~BitArray()                               {delete[] data;}
  void resize(int size)                     {delete[] data; init(size);}
  void swap(BitArray &other);
  int hash(int max);

  int size() {return bitSize;}
  reference operator[](int idx) {return reference(1UL << (idx % BITS), data[idx / BITS]);}

  // methods for very fast manipulation and access
  unsigned long get(int idx) const {   // returns 0 or non-0
    return data[idx / BITS] & (1UL << (idx % BITS));
  }
  void set(int idx)   {data[idx / BITS] |= 1UL << (idx % BITS);}
  void clear(int idx) {data[idx / BITS] &= ~(1UL << (idx % BITS));}
  void flip(int idx)  {data[idx / BITS] ^= 1UL << (idx % BITS);}

  BitArray &operator|=(const BitArray &other) {
    //    if(bitSize != other.bitSize) throw InvalidSizeException();
    posn1 = data; endn1 = data + chunkCount;
    posn2 = other.data;
    while(posn1 != endn1)
      *posn1++ |= *posn2++;
    return *this;
  }

  bool operator==(const BitArray &comp) {
    //  if(bitSize != comp.bitSize) return false;
    posn1 = data; endn1 = data + chunkCount;
    posn2 = comp.data;
    while(posn1 != endn1)
      if(*posn1++ != *posn2++)
        return false;
    return true;
  }

  bool operator<=(const BitArray &comp) {
    //  if(bitSize != comp.bitSize) return false;
    posn1 = data; endn1 = data + chunkCount;
    posn2 = comp.data;
    while(posn1 != endn1) 
      if(*posn2++ != (*posn2 & *posn1++))
        return false;
    return true;
  }

  BitArray &operator&=(const BitArray &other) {
    //    if(bitSize != other.bitSize) throw InvalidSizeException();
    posn1 = data; endn1 = data + chunkCount;
    posn2 = other.data;
    while(posn1 != endn1)
      *posn1++ &= *posn2++;
    return *this;
  }
  BitArray &operator^=(const BitArray &other) {
    //    if(bitSize != other.bitSize) throw InvalidSizeException();
    posn1 = data; endn1 = data + chunkCount;
    posn2 = other.data;
    while(posn1 != endn1)
      *posn1++ ^= *posn2++;
    return *this;
  }
  BitArray &operator-=(const BitArray &other) {
    //    if(bitSize != other.bitSize) throw InvalidSizeException();
    posn1 = data; endn1 = data + chunkCount;
    posn2 = other.data;
    while(posn1 != endn1)
      *posn1++ &= (-1UL ^ *posn2++);
    return *this;
  }

  vector<int> toIntVector() const;
  void toIntVector(vector<int> &vec) const;
  string toString() {
    string back;
    for (int i=0; i<bitSize; i++) 
      if (get(i)) back += "1"; else back += "0";
    back += "\n";
    return back;
  }
  void BitArray::toIntArray(int* vec, int& i) const;

  struct InvalidSizeException {};
};

/* --------------
   
   Implementation

   -------------- */

void BitArray::init(int size) {
  bitSize = size;
  chunkCount = (size + BITS - 1) / BITS;
  data = new unsigned long[chunkCount];
  for(int i = 0; i < chunkCount; i++)
    data[i] = 0;
}

void BitArray::assign(const BitArray &copy) {
  bitSize = copy.bitSize;
  chunkCount = copy.chunkCount;
  data = new unsigned long[chunkCount];
  for(int i = 0; i < chunkCount; i++)
    data[i] = copy.data[i];
}

void BitArray::swap(BitArray &other) {
  std::swap(data, other.data);
  std::swap(bitSize, other.bitSize);
  std::swap(chunkCount, other.chunkCount);
}

vector<int> BitArray::toIntVector() const {
  vector<int> back;
  toIntVector(back);
  return back;
}

BitArray::BitArray(int size, const vector<int> &vec) {
  init(size);
  for(int i = 0; i < vec.size(); i++)
    set(vec[i]);
}

BitArray::hash(int max) {
  unsigned int result = 0;
  for(int i = 0; i < chunkCount; i++)
    result += data[i] * 3; 
  return (int) (result % max);
}

void BitArray::toIntVector(vector<int> &vec) const {
  vec.clear();
  unsigned long *pos = data, *end = data + chunkCount;
  int i = 0;
  while(pos != end) {
    unsigned long val = *pos++;
    unsigned long mask = 1;
    do {
      if(val & mask)
        vec.push_back(i);
      mask <<= 1;
      i++;
    } while(mask);    // becomes 0 on shift overflow
  }
}

void BitArray::toIntArray(int* vec, int& size) const {
  unsigned long *pos = data, *end = data + chunkCount;
  int i = 0;
  size = 0;
  while(pos != end) {
    unsigned long val = *pos++;
    unsigned long mask = 1;
    do {
      if(val & mask)
        vec[size++] = i;
      mask <<= 1;
      i++;
    } while(mask);    // becomes 0 on shift overflow
  }
}

#endif //
