FastMap.h

Go to the documentation of this file.

#ifndef FASTMAP_H_
#define FASTMAP_H_

#include "FlexArray.h"
#include "MapEntry.h"

template <typename S, typename T>
class FastMap
{
public:
    FastMap( bool allowDups = false, const unsigned short initialSize = 32 )
        : array_( true, initialSize, 16384 ),
          allowDups_( allowDups ),
          nullItem_( 0 )
    {}
    virtual ~FastMap()
    {}

    bool put( S& key, T item, bool deleteOnCleanup = false )
    {
        int insertIndex = findIndex( key, 0, array_.getMaxIndex() );
        if( insertIndex >= 0 && !allowDups_ )
        {
            return false;
        }
        // This puts duplicates in the order that they are added.
        while( allowDups_
                && insertIndex >= 0
                && insertIndex <= array_.getMaxIndex()
                && getIndexedEntry( insertIndex )->getKey() == key )
        {
            ++insertIndex;
        }
        // Need to insert at the indicated (xor-ed) location
        // So, if insertIndex = -1, insert at 0
        // So, if insertIndex = -2, insert at 1
        if( insertIndex < 0 )
        {
            insertIndex ^= -1;
        }
        MapEntry<S, T>* entry = new MapEntry<S, T>( key, item, deleteOnCleanup );
        array_.insert( insertIndex, entry );
        return true;
    }

    T get( const S& key, bool andPop = false )
    {
        int index = findIndex( key, 0, array_.getMaxIndex() );
        if( index >= 0 )
        {
            return getIndexed( index, andPop );
        }
        return nullItem_;
    }

    T pop( S& key )
    {
        return get( key, true );
    }

    T getIndexed( unsigned int index, bool andPop = false )
    {
        MapEntry<S, T>* entry = getIndexedEntry( index, andPop );
        if( 0 != entry )
        {
            T item = entry->getItem();
            if( andPop )
            {
                delete entry;
            }
            return item;
        }
        return nullItem_;
    }

    MapEntry<S, T>* getIndexedEntry( unsigned int index, bool andPop = false )
    {
        MapEntry<S, T>* entry = array_[index];
        if( 0 != entry && andPop )
        {
            array_.pop( index );
        }
        return entry;
    }

    T popIndexed( unsigned int index )
    {
        return getIndexed( index, true );
    }

    S& findKey( T item, const S& defaultValue )
    {
        for( int i = 0; i <= array_.getMaxIndex(); ++i )
        {
            MapEntry<S, T>* entry = array_[i];
            if( 0 != entry && entry->getItem() == item )
            {
                return entry->getKey();
            }
        }
        return defaultValue; // returns -1 for an empty array
    }

    int findIndex( const S& key, int minIndex = 0, int maxIndex = -1 )
    {
        if( maxIndex == -1 )
        {
            maxIndex = array_.getMaxIndex();
        }
        if( maxIndex < minIndex )
        {
            return -1; // returns -1 for an empty array
        }
        int midIndex = ( maxIndex + minIndex ) / 2;
        MapEntry<S, T>* midEntry( array_[ midIndex ] );
        //printf("midEntry at 0x%08X\n", (int)midEntry);
        if( key == midEntry->getKey() )
        {
            return midIndex;
        }
        else if( key < midEntry->getKey() )
        {
            if( midIndex == minIndex )
            {
                return midIndex ^ -1;
            }
            return findIndex( key, minIndex, midIndex - 1 );
        }
        else
        {
            if( midIndex == maxIndex )
            {
                return ( midIndex + 1 ) ^ -1;
            }
            return findIndex( key, midIndex + 1, maxIndex );
        }
    }

    unsigned int size()
    {
        return array_.size();
    }

    FlexArray<MapEntry<S, T>*> getArray()
    {
        return array_;
    }

    void clear( bool andDeleteValues = false )
    {
        for( unsigned int i = 0; andDeleteValues && i < size(); ++i )
        {
            delete getIndexed( i );
        }
        array_.clear();
    }

protected:

    FlexArray<MapEntry<S, T>*> array_;
    bool allowDups_;
    T nullItem_;

private:
    // Note that the copy constructor below is private and not given a body.
    // Any attempt to call it will return a compiler error.
    FastMap( const FastMap<S, T>& old ); // disallow copy constructor

};

#endif /*FASTMAP_H_*/