/**************************************************************** 
 * PrBitmap.cpp
 *
 * This is an implementation of bitmap methods.
 *
 ****************************************************************/

/*
 * modification history
 *----------------------
 *
 * 02/18/98: K.C. Chang: created.
 */


#include "PrBitmap.h"

PrBitmap::PrBitmap( int numBits ) 
{ 
    assert(numBits > 0);

    numBits_ = numBits;
    bitsPerWord_ = PR_BITS_PER_BYTE * PR_BYTES_PER_WORD;

    int numWords = numBits_ / bitsPerWord_;

    if (numBits_%bitsPerWord_ > 0)
      numWords++;

    map_ = new unsigned int[numWords];

    int i;
    for(i=0;i<numWords;i++) 
      map_[i] = 0;

    for(i=0;i<numBits_;i++)
      clear(i);
}

PrBitmap::~PrBitmap()
{ 
    delete[] map_;
}

void PrBitmap::set( int n ) 
{ 
    assert(n >= 0 && n < numBits_);

    map_[n/bitsPerWord_] |= 1 << (n%bitsPerWord_);

    assert(test(n));
}
    
void PrBitmap::clear( int n ) 
{
    assert(n >= 0 && n < numBits_);

    map_[n/bitsPerWord_] &= ~(1 << (n%bitsPerWord_));

    assert(!test(n));
}

int PrBitmap::test(int n) const
{
    assert(n >= 0 && n < numBits_);
    
    if (map_[n/bitsPerWord_] & (1 << (n%bitsPerWord_)))
      return 1;
    else
      return 0;
}

// if no bits are clear, return -1.
int PrBitmap::findAndSet() 
{
    for(int i=0;i<numBits_;i++) 
      if (!test(i)) 
	{
	    set(i);
	    return i;
	}
    return -1;
}

// return the number of clear bits in the bitmap.
int PrBitmap::numClear() const
{
    int count = 0;

    for(int i=0;i<numBits_;i++) 
      if (!test(i)) 
	count++;

    return count;
}

void PrBitmap::display() const
{
    printf("PrBitmap::display(): %d bits: set:\n",numBits_); 
    for(int i=0;i<numBits_;i++)
      if (test(i))
	printf("%d,", i);
    printf("\n"); 
}


void PrBitmap::selfTest() 
{
//    assert(numBits_ >= bitsPerWord_);	// bitmap must be big enough
    assert(numClear() == numBits_);	// bitmap must be empty
    assert(findAndSet() == 0);
    set(31);
    assert(test(0) && test(31));
    assert(findAndSet() == 1);
    clear(0);
    clear(1);
    clear(31);

    int i;
    for (i=0;i<numBits_;i++)
      set(i);

    assert(findAndSet() == -1);		// bitmap should be full!
    for (i=0;i<numBits_;i++)
      clear(i);
    assert(numClear() == numBits_);
}


