// Bit-Array-Klasse (als Beispiel für Unit-Tests), Implementierung
//
// Klaus Kusche, 2012

#include "bitarray.h"

static const unsigned int bitsPerWord = sizeof(tBitArrayWord) * 8;
    
static inline unsigned int bitsToWords(unsigned int bits)
{
  return (bits == 0) ? 0 : ((bits - 1) / bitsPerWord + 1);
}

static inline unsigned int wordIndex(unsigned int index)
{
  return index / bitsPerWord;
}

static inline tBitArrayWord bitMask(unsigned int index)
{
  return (tBitArrayWord(1)) << (index % bitsPerWord);
}

static inline tBitArrayWord tailMask(unsigned int bits)
{
  unsigned int zeroes = (bitsPerWord - bits % bitsPerWord) % bitsPerWord;

  return ~(tBitArrayWord(0)) >> zeroes;
}

BitArray::BitArray(unsigned int size, bool initVal)
  : mBits(size), mWords(bitsToWords(size)), mArray(new tBitArrayWord[mWords])
{
  unsigned int i;
  tBitArrayWord w = (initVal) ? ~(tBitArrayWord(0)) : 0;
  
  for (i = 0; i < mWords; ++i) {
    mArray[i] = w;
  }
}

BitArray::BitArray(const BitArray &orig)
  : mBits(orig.mBits), mWords(orig.mWords), mArray(new tBitArrayWord[mWords])
{
  unsigned int i;

  for (i = 0; i < mWords; ++i) {
    mArray[i] = orig.mArray[i];
  }
}

bool BitArray::test(unsigned int index) const
{
  if (index >= mBits) {
    throw "BitArray::test: Index out of bounds";
  }
  return (mArray[wordIndex(index)] & bitMask(index)) != 0;
}

BitArray &BitArray::set(unsigned int index, bool val)
{
  if (index >= mBits) {
    throw "BitArray::set: Index out of bounds";
  }
  if (val) {
    mArray[wordIndex(index)] |= bitMask(index);
  } else {
    mArray[wordIndex(index)] &= ~bitMask(index);
  }

  return *this;
}

BitArray &BitArray::invert()
{
  unsigned int i;

  for (i = 0; i < mWords; ++i) {
    mArray[i] = ~mArray[i];
  }

  return *this;
}

BitArray &BitArray::intersect(const BitArray &a)
{
  unsigned int i;

  if (mBits != a.mBits) {
    throw "BitArray::and: Operands have different length";
  }

  for (i = 0; i < mWords; ++i) {
    mArray[i] = mArray[i] & a.mArray[i];
  }

  return *this;
}

bool BitArray::operator!() const
{
  unsigned int i;

  if (mWords == 0) return true;

  for (i = 0; i < mWords - 1; ++i) {
    if (mArray[i] != 0) return false;
  }

  return (mArray[i] & tailMask(mBits)) == 0;
}

bool BitArray::operator==(const BitArray &a) const
{
  unsigned int i;

  if (mBits != a.mBits) return false;
  if (mWords == 0) return true;

  for (i = 0; i < mWords - 1; ++i) {
    if (mArray[i] != a.mArray[i]) return false;
  }

  return (mArray[i] & tailMask(mBits)) == (a.mArray[i] & tailMask(mBits));
}

bool BitArray::operator<=(const BitArray &a) const
{
  unsigned int i;

  if (mBits != a.mBits) return false;
  if (mWords == 0) return true;

  for (i = 0; i < mWords - 1; ++i) {
    if ((mArray[i] & ~a.mArray[i]) != 0) return false;
  }

  return (mArray[i] & ~a.mArray[i] & tailMask(mBits)) == 0;
}

BitArray &BitArray::operator=(const BitArray &a)
{
  unsigned int i;

  if (this != &a) {
    if (mWords != a.mWords) {
      mWords = a.mWords;
      delete[] mArray;
      mArray = new tBitArrayWord[mWords];
    }
    mBits = a.mBits;
    for (i = 0; i < mWords; ++i) {
      mArray[i] = a.mArray[i];
    }
  }

  return *this;
}