hat.h

vdhl and matlab, i think it good for you

#ifndef HAT_H
#define HAT_H

#include "sysinc.h"

/** These macros ensure the these calculations get
   inlined even for stupid compilers.
*/
#define GetTopIndex(i) ((i)>>power)
#define GetLeafIndex(i) ((i)&leafMask)

/** Minimum hat array will hold 32 *32 = 1024 elements.  Note
   that the 32 element leaves will be allocated on demand. */
typedef enum { min_hat_size = 32 };

#ifndef NULL
#define NULL 0
#endif

/**
   This class implements a dynamicly growable array.  Arrays of this
   type are particularly useful in code generators, where algorithms
   like register range analysis and peephole optimization work best on
   arrays of instructions.

   This class is implemented by a Hashed Array Tree (see <i>HATs: Hashed
   Array Trees - very fast variable length arrays</i> by Edward Sitarski,
   published in the "Algorithm Alley" section of Dr. Dobb's Journal,
   September 1996).  The code here is derived from the public domain
   code published along with this article (e.g., ftp from the Dr. Dobbs
   ftp site).

   This is a template class.  Some C++ compilers (e.g., Sun) will only
   compile template classes with in-line class functions.

   This code is fairly tricky.  Memory is only allocated when it is needed
   and the addLeaf and resize functions end up being recursive co-routines.
   I like to think that my code is more transparent than this, since trickiness
   makes code difficult to understand and maintain.  However, I've combed 
   through this code and run some tests on it and as far as I can tell,
   it works correctly.
<h4>
  Notes
</h4>
<ul>
<li>
<p>
    Hashed Array Trees (hat)
</p>
<p>
      A slightly altered quote from the <i>Hats: Hashed Array Trees</i> article
      is included below:
</p>
<p>
<i>
        Although used to implement one dimensional arrays, HATs are
        really two dimensional.  A HAT consists of a "Top" array and a
        number of "Leaves" which are pointed to by the Top array.  The
        number of pointers in the Top array and the number of elements
        in each Leaf is the same, and is always a power of 2.
</i>
</p>
<p>
<i>
        Because the Top and Leaf arrays are powers of 2, you can
	efficiently find an element in a HAT using bit operations.
	Usually appending elements is very fast since the last leaf
	may have empty space.  Less frequently, a new leaf must be
	added, which is also very fast and requires no copying.
</i>
</p>
<p>
<i>
        When the Top array is full, the size of new Top and Leaf
	arrays are calculated (e.g., a Top, that is twice as big,
	is allocated and enough leaf arrays are allocated to hold
	the current data set).  A new Top is allocated.  The existing
	data is "appended" to the new hat, allocating new leaves and
	deallocating old leaves as the copying is done.
</i>
</p>
<i>
        Recopying only occurs when the Top array is full and this
	happens when the number of elements exceeds the square of a
	power of two
</i>
</p>
</li>
<li>
<p>
    size_t
</p>
<p>
      You've got to love C++, it's huge and they constantly add to it.  There
      are endless corners of the language that few people know about which
      allow people like Al Stevens (a Dr. Dobb's columnist) to count coup on
      the rest of us.  One of these obscure features is size_t.  From
      section 5.3.2 of The Annotated C++ Reference Manual:
</p>
<p>
         ... size_t, an impementation-dependent unsigned integral type
         defined in the standard header <stddef.h>.
</p>
      On most systems this is the local version of "unsigned int".
</li>
<li>
<p>
    Code bloat
</p>
<p>
      The Sun compiler has a habbit of in-lining constructors.  As
      a result, a lot of code, especially in templates, ends up
      in line, exploding the size of the program.
</p>
</li>
</ul>

 */

template <class T>
class Hat
{
private:
    size_t leafSize() const { return 1<<power; /* return 2^power */ }
    size_t topSize() const { return 1<<power; /* return 2^power */ }
    size_t topIndex( const unsigned i ) const { return GetTopIndex(i); }
    size_t leafIndex( const unsigned i ) const { return GetLeafIndex(i); }

    /**
     Allocate a new HAT and copy the data from "this" HAT
     into the new HAT.
     */
    void resize( const size_t newExpectedSize )
    {
	size_t	i, leaf_ix;

	Hat<T>	hatNew( newExpectedSize );

	/* if the new HAT is the same size (e.g., power) as "this"
	   HAT, return */
	if( hatNew.power == power )
	    return;

	/* copy the data from "this" hat into the new array */
	for( i = 0, leaf_ix = 0; i < numElements; i++ )
	    {
		hatNew.add_to_end( (*this)[i], 0 );	// append, but do not resize again

		leaf_ix++;
		// delete the leaves as we go - this decreases memory overhead.
		if( leaf_ix == leafSize() )
		    {
			delete [] top[topIndex(i)];
			leaf_ix = 0;
		    }
	    }

	// delete any unused leaves.
	for( i = topIndex(numElements); i < topUsed; i++ )
	    delete [] top[i];

	// assign the new array to the old.
	delete top;
	top = hatNew.top;
	setPower( hatNew.power );
	topUsed = hatNew.topUsed;
	numAvail = hatNew.numAvail;

	// clean up so nothing gets corrupted.
	hatNew.numElements = 0;
	hatNew.topUsed = 0;
	hatNew.top = NULL;
    }  // resize


    /**
     Add a new Leaf to the HAT pointer array and insert the
     new data element (aValue) into it.

     */
    void addLeaf( const T &aValue, const int doResize )
    {
	/* If the top array is either empty (topUsed == 0) or is full
	   topUsed == topSize (no new leaves can be added), reallocate the
	   array.  */
	if( topUsed % topSize() == 0 )
	    {
		int	growTop = TRUE;

		if( doResize )
		    {
			resize( numElements );

			// Check if after the resize we have room.
			if( topIndex(numElements) < topUsed )
			    {
				(*this)[numElements++] = aValue;
				return;
			    }

			// Check if we have room for a new leaf.
			if( topUsed % topSize() != 0 )
			    growTop = FALSE;
		    }
		if( growTop )
		    {
			// Increase the top array by topSize.
			T	**topNew = new T * [ topUsed + topSize() ];
			for( size_t i = 0; i < topUsed; i++ )
			    topNew[i] = top[i];
			delete [] top;
			top = topNew;
		    }
	    }
	/* add a new leaf */
	top[topUsed] = new T [leafSize()];
	top[topUsed][0] = aValue;
	numAvail += leafSize();
	topUsed++;
	numElements++;
    } /* addLeaf */


    size_t recommendedPower( const size_t s ) const
    {

	const size_t powerMin = 1; // set a resonable minimum
	size_t p;
	for( p = powerMin; s > (1<<(p<<1)); p++ )
	    ;
	return p;
    } // recommendedPower

    void setPower( const size_t p )
    {
	power = p;
	leafMask = leafSize()-1;
    }


    void add_to_end( const T &aValue, const int doResize = 1 )
    {
	if (numElements == numAvail) {
	    addLeaf( aValue, doResize );
	}
	else {
	    (*this)[numElements] = aValue;
	    numElements++;
	}
    }


    /** top points to leaves */
    T	**top;
    /** amount of top actually used (number of leaves) */
    size_t	topUsed;     
    /** power of 2 used for leaves and top */
    size_t	power;	     
    /** used to compute the leaf index */
    size_t	leafMask;    
    /** Number of elements used in the array.  numElements
        always points to the next free element in the array */
    size_t	numElements; 
    /** number of elements currently allocated in the array */
    size_t      numAvail;    

public:
    void init( const size_t aExpectedSize = min_hat_size )
    {
	size_t p;

	/* get the smallest power of two greater than aExpectedSize */
	p = recommendedPower(aExpectedSize);
	setPower( p );
	numElements = 0;
	numAvail = 0;

	top = NULL;
	topUsed = 0;
    } // init

  /**
     * Hat default constructor (e.g., default since the class definition
     * assigns a default value of zero to aExpectedSize).
     */
    Hat( const size_t aExpectedSize = min_hat_size )
    {
	init( aExpectedSize );
    }


    Hat( const Hat<T> &hat )
    {
	init( 0 );
	(*this) = hat;
    }

    ~Hat()
    {
	if (top != NULL) {
	    for( size_t i = 0; i < topUsed; i++ ) {
		if (top[i] != NULL) {
		    delete [] top[i];
		    top[i] = NULL;
		}
	    }
	    delete [] top;
	    top = NULL;
	}
    }
    

  /**
       Insert an element "a" into the array at index
       "i".
      
       An empty array is an array with no data elements in it.
       This is not necessarily the same as the number of storage
       elements currently available in the array.
      
       A data element can be inserted into an empty array at 
       index 0 (e.g., appended to an empty array).  A data
       element can be inserted at the end of the array (that
       is array.insert( a, array.length())).  A data element
       cannot be inserted beyond array.length() and an attempt
       to do so will result in an assert error.
      
       Except for insertion at element 0 of an empty array and
       insertion at the end of the array, insert can be an 
       expensive operation.  All elements from i+1 to the
       end of the array are moved up one array location.
  */
    void insert( const T &a, const size_t i )
    {
	assert( i <= numElements );

	if (numElements == 0 || i == numElements) {
	    append( a );
	}
	else {
	    assert( length() > 0 );

	    size_t last_ix = length() - 1;

	    // Move all data elements from i+1 up by one index
	    append( (*this)[last_ix] );  // append the last element to the end of the array
	    assert( length() == last_ix + 2 );

	    int ix;

	    for (ix = last_ix; ix > i; ix--) {
		(*this)[ix] = (*this)[ix-1];
	    }
	    (*this)[i] = a;
	}
    } // insert


  /** 
       Remove (delete is a reserved word) the element at index "i".
       Like insert, this can be an expensive operation.  Unless the
       element is at the very end of the array, elements from i+1 to
       numElements are moved "down" one element.

       It is an error to attempt to remove an element beyond the end
       of the array.  It is also an error to remove an element from an
       empty array.  
     */
    void remove( const size_t i )
    {
	assert( length() > 0 );
	assert( i < length() );

	if (i < length() - 1) {
	    int ix;

	    for (ix = i; ix < length()-1; ix++) {
		(*this)[ix] = (*this)[ix+1];
	    }
	}

	numElements--;
    }  // remove


  /** remove_n: like remove, but this function removes
      more than one item. */
    void remove_n( const size_t i, const size_t n)
    {
	assert( length() > 0 );
	assert( i + n <= length() );

	if (i + n < length()) {
	    int ix;

	    for (ix = i; ix < length()-n; ix++) {
		(*this)[ix] = (*this)[ix+n];
	    }
	}

	numElements -= n;;	
    }


    T &operator[](const size_t i)
    {
	assert( i < numAvail );
	return top[GetTopIndex(i)][GetLeafIndex(i)];
    }

    T operator[](const size_t i) const
    {
	assert( i < numAvail );
	return top[GetTopIndex(i)][GetLeafIndex(i)];
    }

  /** the at function as an l-value */
    T &at(const size_t i) 
    { 
	return (*this)[i]; 
    }

  /** return the address of a data element */
    T at(const size_t i) const 
    { 
	return (*this)[i]; 
    }

  /** return the first data element in the array */
    T first() const { 
	return (*this)[0]; 
    }

  /** Return the last data element in the array */
    T last() const { 
	return (*this)[numElements-1]; 
    }

  /** Add an element to the end of the array */
    void append( const T& a ) { 
	add_to_end(a); 
    }

  /** return TRUE if there are no data elements
      in the array. */
    int isEmpty() const { 
	return numElements == 0; 
    }

  /** When the number of elements is set to zero,
       the array is empty of data, but contains storage.
       This is the difference between numElements (the
       number of data items) and numAvail, the number of
       storage elements available.
  */
    void set_to_empty() {
	numElements = 0;
    }

  /** Return the number of data elements in the array.
       As noted above, this is different from the number
       of storage elements.
  */
    size_t length() const { 
	return numElements; 
    }

    void decrement_length( const unsigned int val ) {
	if (val <= numElements)
	    numElements = numElements - val;
	else
	    numElements = 0;
    } // decrement_length
};

#undef GetTopIndex
#undef GetLeafIndex

#endif