hat.h

Go to the documentation of this file.

#ifndef HAT_H
#define HAT_H

#include "sysinc.h"

#define GetTopIndex(i) ((i)>>power)
#define GetLeafIndex(i) ((i)&leafMask)

typedef enum { min_hat_size = 32 };

#ifndef NULL
#define NULL 0
#endif

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); }

    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


    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++;
        }
    }


    T   **top;
    size_t      topUsed;     
    size_t      power;       
    size_t      leafMask;    
    size_t      numElements; 
    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( 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;
        }
    }
    

    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


    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


    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)];
    }

    T &at(const size_t i) 
    { 
        return (*this)[i]; 
    }

    T at(const size_t i) const 
    { 
        return (*this)[i]; 
    }

    T first() const { 
        return (*this)[0]; 
    }

    T last() const { 
        return (*this)[numElements-1]; 
    }

    void append( const T& a ) { 
        add_to_end(a); 
    }

    int isEmpty() const { 
        return numElements == 0; 
    }

    void set_to_empty() {
        numElements = 0;
    }

    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

---