#ifndef _BITSET_H_
#define _BITSET_H_

#include <cassert>
#include <cstring>
#include <cstdlib>

#include "gc.h"

///////////////////////////
//                       //
// Bare-bones bitvectors.//
//                       //
///////////////////////////

class Bitset : public gc {
protected:
  int *array;
  int _size;
  static int intLogSize; // log2 of number of bits in an int.
  static int intSize; // number of bits in an int.			   
  static inline void calcIntSize() {
    intSize = sizeof(int)*8;
    intLogSize = 0;
    int kount = intSize;
    while (kount != 1) {
      intLogSize++;
      kount = kount >> 1;
    }
  }
  inline int getBitIndex(int index) {
    return ((array[index >> intLogSize]) >> (index % intSize) & 1);
  }
  inline void setBitIndex(int index) {
    int selectInt = index >> intLogSize;
    array[selectInt] = array[selectInt] | 
                                     ( 1 << (index % intSize));
  }
  inline void clearBitIndex(int index) {
    int selectInt = index >> intLogSize;
    array[selectInt] = array[selectInt] & 
                                     (~( 1 << (index % intSize)));
  }
public:
  Bitset(int size) : _size(size) { 
    // Silly way to do this.
    if (!intLogSize) {
      calcIntSize();
    }
    int numints = ((size >> intLogSize) + 1);
    array = new int[numints];
    memset(array, 0, numints * sizeof(int));
  }
  ~Bitset() { delete [] array; }
  void un(Bitset *b);
  void subtract(Bitset *b);
  bool equal(Bitset *b);
  bool disjoint(Bitset *b);  
  bool test(int index) { 
    assert(index < _size); 
    return getBitIndex(index);
  }
  void set(int index) { 
    assert(index < _size); 
    setBitIndex(index);
  }
  void clear(int index) {
    assert(index < _size);
    clearBitIndex(index);
  }
  int size(void) { return _size; }
  void print(void);
};

#endif