/*
//#     Filename:       BitList.c
//#
//#     Member function definitions for classes associated with the BitList.
//#     Classes defined here are:
//#
//#		BitList	  - Bit array class
//#     	BitListIterator - Iterator through Bit Array
//#
//#     Author:         Peter Z. Kunszt
//#     
//#     Date:           June 4, 1998
//#
//#
//#
//# (c) Copyright The Johns Hopkins University 1998
//# All Rights Reserved
//#
//# The software and information contained herein are proprietary to The
//# Johns Hopkins University, Copyright 1998.  This software is furnished
//# pursuant to a written license agreement and may be used, copied,
//# transmitted, and stored only in accordance with the terms of such
//# license and with the inclusion of the above copyright notice.  This
//# software and information or any other copies thereof may not be
//# provided or otherwise made available to any other person.
//#
//#
//#     Modification History:
//#
//#     June 18, 1998 : pzk -- added compress/decompress methods
//#     June 29, 1998 : pzk -- added copy constructor/assignment to iterator
*/
#define HTM_LIB
#include "BitList.h"
#include <assert.h>
#include <stdlib.h>//added 8/15/02
#include <string.h>//added 8/15/02

/* ===========================================================================
//
// Member functions for class BitList
//
// ===========================================================================

//////////////////CONSTRUCTOR//////////////////////////////////////////////
// default constructor with size and increment options
*/
BitList * bitListNew() {
  BitList *bl;
  bl = (BitList *)malloc(sizeof(BitList));
  bitListInit( bl );
  return bl;
}

void bitListInit( BitList *bl ) {
  bl->bits_ = NULL;
  bl->size_ = 0;
  bl->increment_ = 0;
  bl->capacity_ = 0;
  bl->length_ = 0;
}

BitList * bitListNewSize( size_t size, size_t inc )
{
  int i;
  BitList *bl = bitListNew();
  bl->size_ = size;
  bl->increment_ = inc;
  bl->length_ = (size >> 5) + 1;
  bl->capacity_ = bl->length_;
  /* divide by 32: we have uint32s in the array */
  bl->bits_ = (uint32 *)malloc(sizeof(uint32) * (bl->length_));  
  for(i=0;i<bl->length_;i++)bl->bits_[i] = 0;
  return bl;
}

/* copy constructor */
BitList * bitListCopy( const BitList *old )
{
  BitList *bl;
  if(old == NULL) return NULL;
  bl = bitListNewSize(old->size_,0);
  bl->size_ = old->size_;
  bl->length_ = old->length_;
  bl->increment_ = old->increment_;
  bl->capacity_ = old->capacity_;
  memcpy(bl->bits_, old->bits_, bl->length_ * sizeof(uint32));
  return bl;
}

/* destructor */
void bitListDelete( BitList *bl )
{
  free(bl->bits_);
}

/* //////////////////ASSIGNMENT///////////////////////////////////////////////
 */
void bitListAssign( BitList *bl, const BitList *old )
{
  if (bl != old) { /* beware of self-assignment */
    bl->size_ = old->size_;
    bl->length_ = old->length_;
    bl->capacity_ = old->capacity_;
    bl->bits_ = (uint32 *)realloc(bl->bits_, old->length_ * sizeof(uint32));
    memcpy(bl->bits_, old->bits_, bl->length_ * sizeof(uint32));
  }
}

/* //////////////////SET//////////////////////////////////////////////////////
// Set bit at index to val 
*/
void bitListSet( BitList *bl, size_t index, bool val ) 
{
  uint32 one  = 1;
  size_t WordIndex = index >> 5;  /* set WordIndex since it's used a lot */

  /* Extend ValVec if out of bounds and set bit or
     Set or unset bit otherwise. */
  if (WordIndex >= bl->capacity_) {
    bitListExtend( bl, index );
    if(val)bl->bits_[WordIndex] = one << (index & 31);
    bl->size_ = index + 1;
  } else {
    if (val) {
      bl->bits_[WordIndex] = bl->bits_[WordIndex] | (one << (index & 31));
    } else {
      bl->bits_[WordIndex] = bl->bits_[WordIndex] & (~(one << (index & 31)));
    }
    if (index >= bl->size_) bl->size_ = index + 1;
  }
}

/* //////////////////EXTEND BITLIST///////////////////////////////////////////
//
// extend to new size
*/
void bitListExtend( BitList *bl, size_t index )
{
  int i;
  size_t WordIndex = index >> 5;  /* set WordIndex since it's used a lot */
  size_t newsize = bl->capacity_ + 
    (bl->increment_ ? bl->increment_ : bl->capacity_);
  if(newsize < WordIndex) newsize = WordIndex+1;

  if(bl->bits_ == NULL)
    bl->bits_ = (uint32 *)malloc(newsize * sizeof(uint32) );
  else 
    bl->bits_ = (uint32 *)realloc(bl->bits_,newsize * sizeof(uint32));

  for(i=bl->length_; i<newsize; i++) bl->bits_[i] = 0;
  bl->length_ = WordIndex;
  bl->capacity_ = newsize;
  bl->size_ = index;
}
/* //////////////////[]///////////////////////////////////////////////////////
//
// Get bit at index. Return false if out of bounds.
*/
bool bitListGet( const BitList *bl, size_t index)
{
  uint32 one  = 1;
  if(index >= bl->size_)
    return false;

  return (bl->bits_[index >> 5] & (one << (index & 31)) ? true : false);
}

/* //////////////////COUNT////////////////////////////////////////////////////
// Return number of set bits
*/
size_t bitListCount( const BitList *bl ) {
  size_t c = 0, w, i;
  uint32 one  = 1;
  uint32 word;
  for(w = 0; w < bl->length_ ; w++) {
    word = bl->bits_[w];
    for(i = 0; i < 32 ; i++)
      c += (word >> i) & one;
  }
  return c;
}

/* //////////////////CHOPLITTER_//////////////////////////////////////////////
// Chop off trailing litter on the bitlist: mask those bits off
// the last uint32 which are past the size_ */
void bitListChoplitter_( BitList * bl )
{
  uint32 word = 0;
  uint32 one  = 1;
  size_t i;

  if (bl->size_ == 0) return;

  for (i = 0 ; i < (bl->size_ & 31); i++)
    word += one << i ;
  if (word > 0)
    bl->bits_[bl->size_ >> 5] = bl->bits_[bl->size_ >> 5] & word;
  else {
    if( bl->length_ > (bl->size_ >> 5) )
      bl->bits_[bl->size_ >> 5] = 0;
  }
}

/* //////////////////TRIM/////////////////////////////////////////////////////
// Chop off trailing 'false' bits, return new size.
*/
size_t bitListTrim(  BitList *bl )
{
  BitListIterator Iter;
  size_t index;
  bitListIteratorInit( &Iter );
  bitListIteratorSet( &Iter, bl );

  if (bitListIteratorPrev(&Iter,true,&index)) { /* a true bit has been found */
    if (index < bl->size_ - 1) {       /* last bit is false, trim */
      bl->bits_ = (uint32 *)realloc(bl->bits_, (index >> 5)*sizeof(uint32) );
      bl->size_ = index + 1;
    }
  } else bitListClear( bl, false );                  /* all bits are false */

  bitListChoplitter_( bl );
  return bl->size_;
}

/* //////////////////CLEAR////////////////////////////////////////////////////
   // Reset size to 0, free up storage */
void bitListClear(  BitList *bl, bool keepLength )
{
  int i;
  if( keepLength )
    for( i=0; i < bl->length_; i++) bl->bits_[i] = 0;
  else {
    free(bl->bits_);
    bl->length_ = 0;
  }
  bl->size_ = 0;
}

/* //////////////////&=///////////////////////////////////////////////////////
// The bitwise &= operator, may be used to mask the current instance.
// Does not change the size. */
void bitListAnd( BitList *bl, const BitList * BL) {
  size_t i, len = bl->length_;
  if (bl == BL) return ;

  if ( bl->size_ > BL->size_)
    len = BL->length_;

  if (bl->size_ * BL->size_ > 0)          /* check for zero-length BitList */
    for (i = 0; i < len; i++)
      bl->bits_[i] &= BL->bits_[i];

  /* if size of current exceeds size of mask, set the rest to zero. */
  if (bl->size_ > 0)
    for (i = len; i < bl->length_; i++)
      bl->bits_[i] = 0;

}

/* //////////////////|=///////////////////////////////////////////////////////
// The bitwise |= operator, may be used to set bits in the current instance.
// expands instance if needed */
void bitListOr( BitList *bl, const BitList * BL) {
  size_t i;
  if (bl == BL) return;

  if ( bl->size_ < BL->size_){                  /* expand if mask longer */
    bl->bits_ = (uint32 *)realloc(bl->bits_,sizeof(uint32) * BL->length_);
    bl->size_ = BL->size_;
  }

  if (BL->size_ > 0)                  /* don't do anything if BL has 0 size */
    for (i = 0; i < BL->length_; i++)
      bl->bits_[i] |= BL->bits_[i];

  bitListChoplitter_(bl);
}

/* //////////////////^=///////////////////////////////////////////////////////
// The bitwise ^= operator, may be used to set bits in the current instance.
// expands instance if needed. Xor with itself sets all bits to zero. */
void bitListXor( BitList *bl, const BitList * BL) {
  size_t i,j;
  if (bl == BL) {  /* way of clearing bitlist */
    for (j = 0; j < bl->length_; j++) bl->bits_[j] = 0;
    return;
  }

  if ( bl->size_ < BL->size_){                  /* expand if mask longer */
    bl->bits_ = (uint32 *)realloc(bl->bits_,sizeof(uint32) * BL->length_);
    bl->size_ = BL->size_;
  }

  if (BL->size_ > 0)                  /* don't do anything if BL has 0 size */
    for (i = 0; i < BL->length_; i++)
      bl->bits_[i] ^= BL->bits_[i];

  bitListChoplitter_(bl);
}

/* //////////////////INVERT///////////////////////////////////////////////////
// The inversion method; flip every bit */
void bitListInvert( BitList *bl )
{
  size_t i;
  if(bl->length_ > 0)
    for (i = 0; i < bl->length_; i++)
      bl->bits_[i] = ~ bl->bits_[i];
  bitListChoplitter_(bl);
}

/* //////////////////OVERLAPS/////////////////////////////////////////////////
// Test if the current instance has at least one overlapping bit with BL */
bool bitListOverlaps( const BitList *bl, const BitList * BL)
{
  BitListIterator iter;
  size_t index;
  bitListIteratorInit(&iter);
  bitListIteratorSet(&iter,bl);

  while(bitListIteratorNext(&iter,true,&index))
    if(bitListGet(BL,index))return true;
  return false;
}

/* //////////////////COVERS///////////////////////////////////////////////////
// Test if the current instance is a subset of BL */
bool bitListCovers( const BitList *bl, const BitList * BL)
{
  BitListIterator iter;
  size_t index;
  bitListIteratorInit(&iter);
  bitListIteratorSet(&iter,bl);

  while(bitListIteratorNext(&iter,true,&index))
    if(!bitListGet(bl,index))return false;
  return true;
}

/* //////////////////AND//////////////////////////////////////////////////////
//
// The bitwise & operator. If one of the arrays is larger than the other,
// the size of the returned array matches the size of the shorter array.
// (the nonexistent elements are taken as 0
*/
BitList * and (BitList *_res, const BitList * BL1, const BitList * BL2)
{

  size_t i, len = BL1->length_;
  _res->size_ = BL1->size_;
  if (BL1->size_ > BL2->size_) {
    len = BL2->length_;
    _res->size_ = BL2->size_;
  }

  if (len > 0) {
    /* adjust length of result to the length of the shorter array */
    _res->bits_ = (uint32 *)realloc(_res->bits_, len * sizeof(uint32));
    _res->length_ = len;

    /* AND all words up to index len */
    for (i = 0; i < len; i++)
      _res->bits_[i] = BL1->bits_[i] & BL2->bits_[i];
  } else { 
    /* for zero length, return a zero result. */
    free(_res->bits_);
    _res->length_ = 0;
  }
  bitListChoplitter_(_res);
  return _res;
}

/* //////////////////OR///////////////////////////////////////////////////////
//
// The bitwise | operator. At nonequal sizes, the longer size is returned.
// Again, nonexistent elements are treated as 0.
*/
BitList * or (BitList *_res, const BitList * BL1, const BitList * BL2)
{

  /* determine the length of the shorter of the two (store it in len)
     Extend the result to size of first parm if BL is the shorter one.
     if we were unlucky to initialize to the shorter parameter,
     copy the remaining words of the longer parameter into the result */

  size_t i,len = BL2->length_;
  bitListAssign( _res, BL1 );

  if (BL1->size_ < BL2->size_) {
    bitListAssign( _res, BL2 );
    len = BL1->length_;
  }

  /* OR all words up to index len */
  if (len > 0)
    for (i = 0; i < len; i++)
      _res->bits_[i] = BL1->bits_[i] | BL2->bits_[i];

  bitListChoplitter_(_res);
  return _res;
}

/* //////////////////XOR//////////////////////////////////////////////////////
 */
BitList * xor (BitList *_res, const BitList * BL1, const BitList * BL2)
{


  /* determine the length of the shorter of the two (store it in len)
     Extend the result to size of first parm if BL is the shorter one.
     if we were unlucky to initialize to the shorter parameter,
     copy the remaining words of the longer parameter into the result */

  size_t i,len = BL2->length_;
  bitListAssign( _res, BL1 );

  if (BL1->size_ < BL2->size_) {
    bitListAssign( _res, BL2 );
    len = BL1->length_;
  }

  /* XOR all words up to index len */
  if (len > 0)
    for (i = 0; i < len; i++)
      _res->bits_[i] = BL1->bits_[i] ^ BL2->bits_[i];

  bitListChoplitter_(_res);
  return _res;
}

/* //////////////////NOT//////////////////////////////////////////////////////
//
// Not operator. Set the result to the same length as the current instance
// Copy each element with a bitwise not.
*/
BitList * not (BitList * _res, const BitList *BL)
{
  size_t i;
  bitListAssign(_res,BL);

  /* NOT all words of BL */
  if ( _res->size_ == 0) return _res;
  for ( i=0; i < BL->length_; i++)
      _res->bits_[i] = ~ BL->bits_[i];

  bitListChoplitter_(_res);
  return _res;
}

/* //////////////////COMPRESS_////////////////////////////////////////////////
// The compress utility makes a simple compression of the BitList, based
// on the PCX compression scheme.
//
// We do a byte-encoding, and write those bytes out in hex form (2 letters
// for each byte).
//
// The first bit (128) of each byte denotes whether the byte contains
// actual data or a count of bits. 
//
// If the first bit is 0, the next 7 bits are data-bits.
// If the first bit is 1, the next bit (64) is the value and the
// 6 last bits give the count (0-63). It does not make sense to
// count 0 times so bits are only counted if there are at least 8 bits
// with the same value. So the count is 8-71. For more than 71 bits,
// the next byte is taken.
//
// The byte is then written out to the stream as a hex number.
//
// This compression results in a 14% blowup in size for the worst case
// (i.e. BitList consists of 01010101...) and in a compression factor
// of 71 for the best case (all bits alike).
// Example: a series of 0101's of size 92 compresses into
//
//       2A552A552A552A552A552A552A.101
//
//          a series of 1111's of size 92 compresses into
//
//       FFCD.0
//
// The dot and the value following it indicates how many bits are in the
// last byte, if any, and then the last bytes follows in hex. In the above
// example, .101 means only a single bit=true. In this way the exact
// size of the BitList can be restored, not just chunks of 7.
//
*/
void bitListCompress( const BitList *bl, FILE *out)
{

  BitListIterator iter;
  bool bit, obit, flag = false;
  int b=0;
  uint8 byte = 0;
  uint8 one8 = 1;
  uint8 lhalf = 15;

  bitListIteratorInit(&iter);
  bitListIteratorSet(&iter,bl);
  if(bitListIteratorNextBit(&iter,&obit)){   /* get first bit into obit */
    byte = (int)(obit);    /* set byte's last bit to obit */
  } else b = -1;         /* BitList is empty. */

  /* loop over every bit in the BitList */
  while (bitListIteratorNextBit(&iter,&bit)) {
    b++;
    if(bit != obit && b > 0)flag = true;
    if(b < 7){
      if(bit) byte += (one8 << b);
    } else if (b == 7) {
      if(flag){
	fputc(( (byte >> 4) + 48 ),out); /* always digit 0-7, first bit=0 */
	fputc(( ((byte & lhalf) > 9) ? ((byte & lhalf) + 55)  /* letter */
		                    : ((byte & lhalf) + 48) ),out); /* digit */
	b = 0;
	flag = false;
	byte = (int)(bit);
      }
    } else if (b == 71){ /* reached maximal count */
      fputc((66 + 4 * (int)(obit)),out); /* either B or F, depending on bit */
      fputc('F',out);                  /* always F */
      b = 0;
      flag = false;
      byte = (int)(bit);
    } else {
      if(flag){
	byte = 128 + 64 * (int)(obit) + b - 8;
	fputc(( ((byte >> 4) > 9) ? ((byte >> 4) + 55)         /* letter */
		                  : ((byte >> 4) + 48) ),out); /* digit */
	fputc(( ((byte & lhalf) > 9) ? ((byte & lhalf) + 55)
		                       : ((byte & lhalf) + 48) ),out);
	b = 0;
	flag = false;
	byte = (int)(bit);
      }
    }
    obit = bit;
  }
  if(b<=7) {
    fputc('.',out);
    fputc((b+1)+48,out); /* indicate the bit count in last byte */
    if(b > -1) {         /* last byte. */
      fputc(( (byte >> 4) + 48 ),out); /* always digit 0-7,since first bit=0 */
      fputc(( ((byte & lhalf) > 9) ? ((byte & lhalf) + 55)        /* letter */
		                   : ((byte & lhalf) + 48) ),out);/* digit */
    } else {
      fputc('0',out);
    }
  } else {
    byte = 128 + 64 * (int)(obit) + b - 7;
    fputc(( ((byte >> 4) > 9) ? ((byte >> 4) + 55)        /* letter */
                              : ((byte >> 4) + 48) ),out);/* digit */
    fputc(( ((byte & lhalf) > 9) ? ((byte & lhalf) + 55)
	                         : ((byte & lhalf) + 48) ),out);
    fputc('.',out); fputc('0',out);
  }
  fputc('\n',out);
}

/* //////////////////DECOMPRESS_//////////////////////////////////////////////
// The decompress utility reads in a compressed BitList from a stream and
// fills in the bits in the real BitList. See compress_ for details.
*/
void bitListDecompress( BitList *bl, FILE *in) {

  char c1, c2;
  int count, i, idx=0;
  int8 byte;
  bool bit;
  uint8  one8 = 1;

  bitListClear(bl,false);
  c1 = fgetc(in);
  while(c1 != '.') {
    c2 = fgetc(in);
    if (c1 > '7') { /* count - byte */
      count = ( (c1>'9') ? (((int)(c1-'7') & 3) << 4) :
		           (((int)(c1-'0') & 3) << 4) ) + 
	  (int)( (c2>'9') ? (c2-'7') : 
                           (c2-'0') ) + 8 ;
	  bit = (int)(c1-'7') & 4 ? true : false;
      if(bit) {
	for ( i = 0; i < count; i++)
	  bitListSet(bl,idx++,bit);
      } else {
	idx += count-1;
	bitListSet(bl,idx++,bit);
      }
    } else {  /* data - byte */
      byte = ((int)(c1-'0') << 4) + (int)(( (c2>'9') ? (c2-'7') : (c2-'0')));
      for (i = 0; i < 7; i++) 
        bitListSet(bl,idx++,byte & (one8 << i) ? true : false);
    }
    c1 = fgetc(in);
  }
  c1 = fgetc(in);
  count = (int)(c1-'0');
  if(count) {
    c1 = fgetc(in);
    c2 = fgetc(in);
    byte = ((int)(c1-'0') << 4) + (int)(( (c2>'9') ? (c2-'7') : (c2-'0')));
    for (i = 0; i < count; i++)
		bitListSet(bl,idx++,byte & (one8 << i) ? true : false);
  }
}
/*
// ===========================================================================
//
// Member functions for class BitListIterator
//
// ===========================================================================

//////////////////CONSTRUCTOR//////////////////////////////////////////////
// default constructor: empty bitlistiterator
*/
BitListIterator* bitListIteratorNew()
{
  BitListIterator *iter = (BitListIterator *)malloc(sizeof(BitListIterator));
  bitListIteratorInit(iter);
  return iter;
}

void bitListIteratorInit(BitListIterator *iter) {
  iter->bitlist = NULL;
  iter->word_ = 0;
  iter->wordIndex_ = 0;
  iter->bitIndex_ = 0;
}

/* //////////////////CONSTRUCTOR//////////////////////////////////////////////
// Construct from a bitlist. Set the current index to the out-of-bounds
// index = size_.
*/
BitListIterator* bitListIteratorList( const BitList * bitlist )
{
  BitListIterator *iter = bitListIteratorNew();
  iter->bitlist = bitlist;
  bitListIteratorSetindex(iter,bitlist->size_);
  return iter;
}

/* //////////////////CONSTRUCTOR//////////////////////////////////////////////
// Construct from a bitlist and set starting index. */
BitListIterator* bitListIteratorStart( const BitList* bitlist, size_t start ) 
{
  BitListIterator *iter = bitListIteratorNew();
  iter->bitlist = bitlist;  
  bitListIteratorSetindex(iter,start);
  return iter;
}

/* //////////////////COPY CONSTRUCTOR/////////////////////////////////////////
// Copy construct */
BitListIterator* bitListIteratorCopy( const BitListIterator *Iter)
{
  BitListIterator *iter = (BitListIterator *)malloc(sizeof(BitListIterator));

  bitListIteratorAssign(iter,Iter);
  return iter;
}

/* //////////////////ASSIGNMENT///////////////////////////////////////////////
// Assignment */
void bitListIteratorAssign( BitListIterator *iter,const BitListIterator *Iter)
{
  iter->bitlist    = Iter->bitlist;
  iter->word_      = Iter->word_;
  iter->wordIndex_ = Iter->wordIndex_;
  iter->bitIndex_  = Iter->bitIndex_;

}

/* //////////////////SET//////////////////////////////////////////////////////
// Set bitlist.
*/
void bitListIteratorSet( BitListIterator* iter, 
				     const BitList * bitlist )
{
  iter->bitlist = bitlist;
  bitListIteratorSetindex(iter,bitlist->size_);
}

/* //////////////////SETINDEX/////////////////////////////////////////////////
// Initialize the internal counters to a certain starting point
*/
void bitListIteratorSetindex( BitListIterator *iter, size_t start )
{
  if (iter->bitlist == 0) {
    printf("BitListIteratorSetIndex: bitlist not initialized\n");
    assert(0);
  }
  /* the next next() returns first bit if start = bitlist.size_ */
  if (start > iter->bitlist->size_) start = iter->bitlist->size_; 

  iter->wordIndex_ = start >> 5;
  iter->bitIndex_ = start & 31;
  if(iter->bitlist->size_ > 0)
    iter->word_ = iter->bitlist->bits_[iter->wordIndex_];
}

/* //////////////////NEXT(BOOL, SIZE_T &)/////////////////////////////////////
// get the index of the next 'true' or 'false' bit (indicated by the first 
// argument)
*/
bool bitListIteratorNext( BitListIterator *iter, bool bit, size_t * _index )
{
  uint32 one  = 1;

  if (iter->bitlist == 0) {
    printf("BitListIteratorNext: bitlist not initialized\n");
    assert(0);
  }

  /*
#define ZEROS 0
#define ONES 0xffffffff;
  if(bitlist->size_==0)return false;
  uint32 val;
  if(bit)val = ZEROS;
  else val = ONES;
  if( bitlist->bits_.vector_[wordIndex_] == val ) {
    while(wordIndex_ < bitlist->length() && 
	  bitlist->bits_.vector_[wordIndex_] == val) wordIndex_++;
    wordIndex_--;
    bitIndex_ = 31;
  }
  */

  /* increment pointer, check for boundary */
  while (bitListIteratorIncr(iter)) {  
    /* If the bit is on, return the index value and set the pointer
       to the next bit. */
	  if( (iter->word_ & (one << iter->bitIndex_) ? true : false) == bit) {
      *_index = ((iter->wordIndex_ << 5) + iter->bitIndex_);
      return true;
    }
  } 
  return false;
}

/* //////////////////NEXT(BOOL &)/////////////////////////////////////////////
// get the next bit into bit and increment the internal index */
bool bitListIteratorNextBit( BitListIterator *iter, bool * _bit) {
  uint32 one  = 1;

  if (iter->bitlist == 0) { 
    printf("BitListIteratorNextBit: bitlist not initialized\n");
    assert(0);
  }

  /* increment pointer, check for boundary */
  if(bitListIteratorIncr(iter)) {
    *_bit = iter->word_ & (one << iter->bitIndex_) ? true : false;
    return true;
  }
  return false;
}

/* //////////////////PREV(BOOL, SIZE_T &)/////////////////////////////////////
// get the index of the previous 'true' or 'false' bit (indicated by the first 
// argument) */
bool bitListIteratorPrev( BitListIterator *iter, bool bit, size_t * _index)
{
  uint32 one  = 1;

  if (iter->bitlist == 0)  { 
    printf("BitListIteratorPrev: bitlist not initialized\n");
    assert(0);
  }

  while (bitListIteratorDecr(iter)) {

    /* If the bit is on, return the index value and set the pointer
       to the next bit. */
    if( (iter->word_ & (one << iter->bitIndex_) ? true : false) == bit) {
      *_index = ((iter->wordIndex_ << 5) + iter->bitIndex_);
      return true;
    }
  }
  return false;
}


/* //////////////////PREV(BOOL &)/////////////////////////////////////////////
// get the previous bit into bit and decrement the internal index */
bool bitListIteratorPrevBit( BitListIterator *iter, bool * _bit)
{
  uint32 one  = 1;

  if (iter->bitlist == 0)   { 
    printf("BitListIteratorPrevBit: bitlist not initialized\n");
    assert(0);
  }

  if(bitListIteratorDecr(iter)) {
	*_bit = iter->word_ & (one << iter->bitIndex_) ? true : false;
	return true;
  }
  return false;

}

/* //////////////////INCR////////////////////////////////////////////////////
// private function incrementing the pointer and returning
// true or false if it is within bounds or not */
bool bitListIteratorIncr( BitListIterator *iter )
{
  if ( ((iter->wordIndex_ << 5) + iter->bitIndex_) == iter->bitlist->size_ ) {
    if (iter->bitlist->size_ == 0) return false;/* check for 0-length array */
    iter->bitIndex_ = 0;
    iter->wordIndex_ = 0;
    iter->word_ = iter->bitlist->bits_[0];
    return true;
  } else {
    if(++(iter->bitIndex_) == 32) {        /* check if next word is needed */
      iter->bitIndex_ = 0;
      if ( ((++(iter->wordIndex_) << 5) + iter->bitIndex_) == 
	   iter->bitlist->size_ )
	return false;
      iter->word_ = iter->bitlist->bits_[iter->wordIndex_];
      return true;
    }
    return ((iter->wordIndex_ << 5) + iter->bitIndex_) != iter->bitlist->size_ ? true : false;
  }
}

/* //////////////////DECR////////////////////////////////////////////////////
// private function decrementing the pointer returning true or
// false if it is within bounds or not */
bool bitListIteratorDecr( BitListIterator *iter )
{
  if (iter->wordIndex_ + iter->bitIndex_ == 0) {
    iter->wordIndex_ = iter->bitlist->size_ >> 5;
    iter->bitIndex_ = iter->bitlist->size_ & 31;
    return false;
  } else {
    if(iter->bitIndex_ == 0) {
      iter->bitIndex_ = 32;
      iter->word_ = iter->bitlist->bits_[--(iter->wordIndex_)];
    }
    if ( ((iter->wordIndex_ << 5) + iter->bitIndex_) == iter->bitlist->size_ )
      iter->word_ = iter->bitlist->bits_[iter->wordIndex_];
    iter->bitIndex_--;
    return true;
  }

}