#ifndef _BitList_h
#define _BitList_h
/*
//#     Filename:       BitList.h
//#
//#     Declarations for the BitList and BitListIterator classes
//#
//#
//#     Author:         Peter Z. Kunszt
//#     
//#     Date:           June 3, 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.
//#
//#
*/
#include <stdio.h>
#include "SpatialGeneral.h"

/*
// The BitList is an array of bits. A bit can be set at any index using the
// set member function, the array expands itself automatically if the index
// exceeds the current size.
*/
typedef struct {
  uint32* bits_;     /* The array we store the bits in */
  size_t length_;    /* Length of the array            */
  size_t increment_; /* Increment of the array         */
  size_t capacity_;  /* Capacity of the array          */
  size_t size_;      /* Size of the bitlist            */
} BitList;

typedef struct {
  const BitList * bitlist;   /* The BitList associated with this iterator */
  uint32 word_;              /* The current word in bitlist_.bits_        */
  size_t wordIndex_;         /* The index of the word in bitlist_.bits_   */
  size_t bitIndex_;          /* The index of the bit in the current word. */
} BitListIterator;

/* Default constructor, you can initialize the BitList to a specific size
 * and optionally the increment may be set by which the size internal ValVec
 * will be incremented upon need. (See VarVec.h for explanation on this.)
 * The default is to double the size of the array whenever an expansion
 * is requested. */
BitList * bitListNew( );
void bitListInit( BitList *bl );
BitList * bitListNewSize( size_t size, size_t inc );

/* Copy constructor */
BitList * bitListCopy( const BitList * );

/* Destructor */
void bitListDelete( BitList * );

/* The assignment operator. */
void bitListAssign( BitList *, const BitList * );

/* Set a bit at a specific index to a given value. If the index is larger
 * than the current size, the BitList expands itself to be able to hold
 * that value at the given index. */
void bitListSet( BitList *bl, size_t index, bool value );

/* Get the bit at a given index. If the index exceeds the size, the return
 * value is 'false'. All BitLists are treated as if they were of infinite
 * size, all bits set to zero at initialization. */
bool bitListGet( const BitList *bl, size_t i);

/* Extend the size of the bitlist so that it fits size bits */
void bitListExtend( BitList *bl, size_t size );

/* Count the TRUE bits from a certain index on */
size_t bitListCount( const BitList *bl );

/* Just chop off all trailing 'false' bits. Returns new size. */
size_t bitListTrim(  BitList *bl );

/* Clear the list, reset size to 0 by default. If true is given as an
 * argument, the size is kept. */
void bitListClear(  BitList *bl, bool keepLength );

/* The standard &= operator. */
void bitListAnd( BitList *bl, const BitList * BL);

/* The standard |= operator. */
void bitListOr( BitList *bl, const BitList * BL);

/* The standard ^= operator. */
void bitListXor( BitList *bl, const BitList * BL);

/* The inversion method, flip every bit in the BitList. */
void bitListInvert( BitList *bl );

/* Check if BL is a subset of the current list */
bool bitListCovers( const BitList *bl, const BitList * BL);

/* Check if the current BitList overlaps with the other (i.e. they have
 * at least one common Bit) */
bool bitListOverlaps( const BitList *bl, const BitList * BL);

/* compress output */
void bitListCompress( const BitList *bl, FILE *);

/* decompress input */
void bitListDecompress( BitList *bl, FILE *);

/* Mask off litter at the end of a word not belonging to the array */
void bitListChoplitter_( BitList * bl );


/* #########################################################################
//
// <SUMMARY> BitListIterator class </SUMMARY>
//

// The BitListIterator iterates through a BitList efficiently.
// next() and prev() functions are supplied. The functionality is
// the following: The BLI saves an index to a certain bit in the BitList.
// By calling either next() or prev(), the index is incremented/decremented and
// the bit it is pointing to now is returned. If it gets out of bounds,
// these functions return 'false'. The out-of-bounds index is always 
// index=size. So by calling next() or prev() again when a 'false' was 
// returned previously, they return the first/last bit, respectively. */

/* Default Constructor and initializer */
BitListIterator* bitListIteratorNew();

void bitListIteratorInit(BitListIterator *iter);

/* Normal Constructor: needs the BitList to initialize.
 * The index is initialized to the out-of-bounds index. */
BitListIterator* bitListIteratorList( const BitList * bitlist ); 

/* Alternate constructor: set the starting index yourself. */
BitListIterator* bitListIteratorStart( const BitList* bitlist, size_t start ); 

/* Copy Constructor. */
BitListIterator* bitListIteratorCopy( const BitListIterator *);

/* Assignment. */
void bitListIteratorAssign( BitListIterator *, const BitListIterator *);

/* Set bitlist to iterate upon */
void bitListIteratorSet( BitListIterator *, const BitList * );

/* Init: set current index */
void bitListIteratorSetindex( BitListIterator *, size_t index );

/* Set the internal index to the next 'true' or 'false' bit, indicated by 
 * the first argument, and return the index in the second argument. 
 * Returns 'false' if it gets out of bounds.
 * Example: For a BitList 001100110011 (from left to right, index starts
 * at 0), the subsequent call to next(true,index) returns 'true' and sets 
 * index to 2, 3, 6, 7, 10, 11. The next call puts leaves index and 
 * returns 'false'. A subsequent next() call would again return 'true' and 
 * set index=2. */

bool bitListIteratorNext( BitListIterator *, bool bit, size_t * _index );

/* Just like next(), but the index is moved backwards. */
bool bitListIteratorPrev( BitListIterator *, bool bit, size_t * _index);

/* Increment the internal index and put the value of the bit it points to
 * into bit. Returns 'false' if the boundary is reached.
 * Example: For a BitList 001100110011 the calls to next(val) return
 * 'true' and set bit to 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1. The next call
 * returns 'false' and does not set bit. A subsequent call would return
 * again 'true' and set bit to the first bit in the list, in this case 0. */
bool bitListIteratorNextBit( BitListIterator *, bool * bit);

/* Just like next() above, just decrement the internal index.
 * The two versions of next() and prev() may be used in conjunction. */
bool bitListIteratorPrevBit( BitListIterator *, bool * bit);

/* increment, decrement current index, return 'true' or 'false' if boundary
 * has been reached */
bool bitListIteratorIncr( BitListIterator * );
bool bitListIteratorDecr( BitListIterator * );



/* #######################################################################
 *
 * Friend functions to BitList
 *

 * Bitwise operators returning the result in a separate BitList.
 * First argument: return list, second and third arguments: bitlists
 * to process. AND operator */

BitList * and (BitList *, const BitList *, const BitList *);

/* OR operator */
BitList * or  (BitList *, const BitList *, const BitList *);

/* XOR operator */
BitList * xor (BitList *, const BitList *, const BitList *);

/* NOT operator */
BitList * not (BitList *, const BitList *);

#endif /* _BitList_h */