MercuryVector.h

Go to the documentation of this file.

#ifndef MERCURYVECTOR_H
#define MERCURYVECTOR_H

#include "global.h"
#include <malloc.h>
#include <string.h>

//very stripped down and fast vector
template<typename T>
class MVector
{
    public:
        MVector()
            :m_reserved(0), m_size(0), m_data(0)
        {  }
        ~MVector()
        {
            clear();
        }
        MVector(const MVector<T>& v)
            :m_reserved(v.m_reserved), m_size(v.m_size)
        {
            m_data = (T*)malloc(sizeof(T)*m_reserved);
            for (unsigned int i = 0; i < m_size; ++i)
            {
                new( &m_data[i] ) T (v.m_data[i]);
                #if defined( _DEBUG_MEMORY )
                MercuryAFree( &m_data[i] );
                #endif
            }
        }
        void push_back(const T& element);
        inline unsigned int size() const { return m_size; }
        inline bool empty() const { return m_size == 0; }
        void resize(unsigned int newSize);
        void reserve(unsigned int newSize);
        inline T& operator[](unsigned int x) { return m_data[x]; }
        inline const T& operator[](unsigned int x) const { return m_data[x]; }
        inline T& at( unsigned int x ) { return m_data[x]; }
        inline const T& at( unsigned int x ) const { return m_data[x]; }
        const MVector<T>& operator=(const MVector<T>& v);
        void clear();
        void remove( int iPlace );
        void insert( int iPlace, const T & data );
    private:
        unsigned int m_reserved; //available space
        unsigned int m_size; //number of valid (constructed) objects
        T * m_data;
};

#include "MercuryUtil.h"

template<typename T>
void MVector<T>::push_back(const T& element)
{
    if (m_size >= m_reserved)
    {
        if (m_reserved <= 0)
        {
            SAFE_FREE( m_data );
            m_data = (T*)malloc(sizeof(T));
            m_reserved = 1;
        }
        else
        {
            int tsize = nextPow2(m_reserved);
            int size = m_size;
            reserve(tsize);
            m_size = size;
        }
    }

    new( &m_data[m_size] ) T ( element );
    #if defined( _DEBUG_MEMORY )
    MercuryAFree( &m_data[m_size] );
    #endif

    ++m_size;
}

template<typename T>
void MVector<T>::resize(unsigned int newSize)
{
    if (newSize == 0)
    {
        clear();
        return;
    }
    //Fully reserve space and initalize constructors
    //Make larger and reserve space
    if (newSize == m_size)
    {
        return;
    }
    else if(newSize > m_size)
    {
        if (newSize > m_reserved)
        {
            m_reserved = newSize;
            m_data = (T*)realloc(m_data, sizeof(T)*m_reserved);
        }

        for (unsigned int i = m_size; i < newSize; ++i)
        {
            new (&m_data[i]) (T);
            #if defined( _DEBUG_MEMORY )
            MercuryAFree( &m_data[i] );
            #endif

        }
    }
    else
    {
        //get smaller
        m_reserved = newSize;

        //destroy data that will be lost
        for (unsigned int i = m_reserved; i < m_size; ++i)
            (&m_data[i])->~T();

        m_data = (T*)realloc(m_data, sizeof(T)*m_reserved);
    }
    m_size = newSize;
}

template<typename T>
void MVector<T>::reserve(unsigned int newSize)
{
    if (newSize == 0)
    {
        clear();
        return;
    }
    if (newSize == m_reserved)
    {
        return;
    }
    else if (newSize > m_reserved)
    {
        m_reserved = newSize;
        m_data = (T*)realloc(m_data, sizeof(T)*m_reserved);
    }
    else
    {
        m_reserved = newSize;

        //destroy data that will be lost
        for (unsigned int i = m_reserved; i < m_size; ++i)
            (&m_data[i])->~T();

        m_data = (T*)realloc(m_data, sizeof(T)*m_reserved);
        m_size = newSize;
    }
}

template<typename T>
void MVector<T>::remove( int iPlace )
{
    m_size--;
    (&m_data[iPlace])->~T();
    memcpy( &m_data[iPlace], &m_data[iPlace+1], sizeof(T) * ( m_size - iPlace ) );
}

#include <stdio.h>
template<typename T>
void MVector<T>::insert( int iPlace, const T & data )
{
    int i;
    resize( m_size + 1 );

    (&m_data[m_size-1])->~T();
    for( i = m_size - 1; i > iPlace; i-- )
        memcpy( &m_data[i], &m_data[i-1], sizeof (T) );

    new ( &m_data[iPlace] ) T( data );
    #if defined( _DEBUG_MEMORY )
    MercuryAFree( &m_data[iPlace] );
    #endif

}

template<typename T>
void MVector<T>::clear()
{
    for (unsigned int i = 0; i < m_size; ++i)
        (&m_data[i])->~T();

    SAFE_FREE(m_data);
    m_size = m_reserved = 0;
}
template<typename T>
const MVector<T>& MVector<T>::operator=(const MVector<T>& v)
{
    clear();
    m_reserved = v.m_reserved;
    m_size = v.m_size;
    m_data = (T*)malloc(sizeof(T)*m_reserved);
    for (unsigned int i = 0; i < m_size; ++i)
    {
        new( &m_data[i]) T( v.m_data[i] );
#if defined( _DEBUG_MEMORY )
        MercuryAFree( &m_data[i] );
#endif
    }
    return *this;
}


template<typename T>
class MDequeNode
{
public:
    MDequeNode(): Next(0),Prev(0) { }
    MDequeNode( const T & tIn ): Data(tIn), Next(0), Prev(0) { }
    T            Data;
    MDequeNode<T> * Next;
    MDequeNode<T> * Prev;
};

template<typename T>
class MDequeIterator
{
public:
    MDequeIterator() : ThisNode( 0 ) { }
    ~MDequeIterator() { ThisNode = 0; }

    inline T & Data() { return ThisNode->Data; }
    inline T * operator -> () { return &ThisNode->Data; }
    inline T & operator * ()  { return ThisNode->Data; }

    inline MDequeIterator<T> & operator ++ () { if( ThisNode ) ThisNode = ThisNode->Next; return *this; }
    inline MDequeIterator<T> & operator -- () { if( ThisNode ) ThisNode = ThisNode->Prev; return *this; }

    //i++ save current iterator, incrememnt, then return the old iterator
    inline MDequeIterator<T> operator ++ ( int dummy ) { MDequeNode< T > * pS = ThisNode; ThisNode = ThisNode->Next; return MDequeIterator( pS ); }
    //i-- save current iterator, decrement, then return the old iterator
    inline MDequeIterator<T> operator -- ( int dummy ) { MDequeNode< T > * pS = ThisNode; ThisNode = ThisNode->Prev; return MDequeIterator( pS); }

    inline bool operator == ( const MDequeIterator & rhs ) { return (ThisNode == rhs.ThisNode ); }
    inline bool operator != ( const MDequeIterator & rhs ) { return (ThisNode != rhs.ThisNode ); }

    //Should be private but I Can't get friend functions to work right in this situation
    MDequeIterator( MDequeNode<T> * pBootNode ) { ThisNode = pBootNode; }
    MDequeNode<T> * ThisNode;
};


template<typename T>
//Mercury Deque (similar to list, and deque)
class MDeque
{
public:
    MDeque() : iSize(0), Head(0), Tail(0){ }
    ~MDeque() { while( Head ) { Temp = Head; Head=Head->Next; delete Temp; } }

    MDeque( const MDeque & rhs ) : iSize(0), Head(0), Tail(0)
    {
        MDequeIterator< T > t = rhs.begin();
        while( t != rhs.end() )
        {
            push_back( *t );
            ++t;
        }
    }

    MDeque & operator = ( const MDeque & rhs )
    {
        MDequeIterator< T > t = rhs.begin();
        while( t != rhs.end() )
        {
            push_back( *t );
            ++t;
        }
        return *this;
    }
    
    inline void swap( MDequeIterator<T> & p1, MDequeIterator<T> & p2 ) {

        if( p1.ThisNode->Next == p2.ThisNode )
        {
            p2.ThisNode->Prev = p1.ThisNode->Prev;
            p1.ThisNode->Prev = p2.ThisNode;
            p1.ThisNode->Next = p2.ThisNode->Next;
            p2.ThisNode->Next = p1.ThisNode;
            if( p2.ThisNode->Prev )
                p2.ThisNode->Prev->Next = p2.ThisNode;
            else 
                Head = p2.ThisNode;
            if( p1.ThisNode->Next )
                p1.ThisNode->Next->Prev = p1.ThisNode;
            else
                Tail = p1.ThisNode;
        }
        else if( p2.ThisNode->Next == p1.ThisNode )
        {
            p1.ThisNode->Prev = p2.ThisNode->Prev;
            p2.ThisNode->Prev = p1.ThisNode;
            p2.ThisNode->Next = p1.ThisNode->Next;
            p1.ThisNode->Next = p2.ThisNode;

            if( p1.ThisNode->Prev )
                p1.ThisNode->Prev->Next = p1.ThisNode;
            else 
                Head = p1.ThisNode;
            if( p2.ThisNode->Next )
                p2.ThisNode->Next->Prev = p2.ThisNode;
            else
                Tail = p2.ThisNode;
        }
        else {
            Temp = p1.ThisNode->Prev;
            p1.ThisNode->Prev = p2.ThisNode->Prev;
            p2.ThisNode->Prev = Temp;

            Temp = p1.ThisNode->Next;
            p1.ThisNode->Next = p2.ThisNode->Next;
            p2.ThisNode->Next = Temp;

            if( p1.ThisNode->Prev )
                p1.ThisNode->Prev->Next = p1.ThisNode;
            else 
                Head = p1.ThisNode;
            if( p1.ThisNode->Next )
                p1.ThisNode->Next->Prev = p1.ThisNode;
            else
                Tail = p1.ThisNode;



            if( p2.ThisNode->Prev )
                p2.ThisNode->Prev->Next = p2.ThisNode;
            else
                Head = p2.ThisNode;
            if( p2.ThisNode->Next )
                p2.ThisNode->Next->Prev = p2.ThisNode;
            else
                Tail = p2.ThisNode;

        }
    }

    inline void push_front( const T & pData ) { iSize++; Temp = Head; Head = new MDequeNode<T>( pData ); Head->Next = Temp; if( Temp ) Temp->Prev = Head; if( !Tail ) Tail = Head; }
    inline void push_back( const T & pData ) { iSize++; Temp = Tail; Tail = new MDequeNode<T>( pData ); Tail->Prev = Temp; if( Temp ) Temp->Next = Tail; if( !Head ) Head = Tail; }
    inline void pop_front() { Temp = Head->Next; delete Head; iSize--; Head = Temp; if ( !Temp ) Tail = 0; }
    inline void pop_back() { Temp = Tail->Prev; delete Tail; iSize--; Tail = Temp; if ( !Temp ) Head = 0; }
    inline T & front() const { return Head->Data; }
    inline T & back() const { return Tail->Data; }
    inline unsigned int size() const { return iSize; } 
    inline bool empty() const { return iSize==0; }

    inline MDequeIterator<T> begin() { return MDequeIterator<T>(Head); }
    inline MDequeIterator<T> & end() { return Nil; }

    inline const MDequeIterator<T> begin() const { return MDequeIterator<T>(Head); }
    inline const MDequeIterator<T> & end() const { return Nil; }

    inline MDequeIterator<T> find( const T & fCmp )
    {
        Temp = Head;
        while( Temp )
            if( Temp->Data == fCmp )
                return MDequeIterator<T>( Temp );
            else
                Temp = Temp->Next;
        return MDequeIterator<T>( Tail );
    }

    inline void erase( MDequeIterator<T> & p ) { 
        if( !p.ThisNode || iSize <= 0 )
            ASSERT_M( false, "DELETING NULL!!!" );
        iSize--;
        if( p.ThisNode == Tail )
        {
            //Special case (last element)
            if( p.ThisNode == Head )
            {
                delete Tail;
                Tail = 0;
                Head = 0;
                return;
            }
            Temp = Tail;
            Tail = Tail->Prev;
            Tail->Next = 0;
            delete Temp;
            return;
        }
        else if( p.ThisNode == Head )
        {
            Temp = Head;
            Head = Head->Next;
            Head->Prev = 0;
            delete Temp;
            return;
        } else {
            Temp = p.ThisNode;
            p.ThisNode->Prev->Next = p.ThisNode->Next;
            p.ThisNode->Next->Prev = p.ThisNode->Prev;
            delete Temp;
        }
    }
private:
    unsigned int iSize;
    MDequeIterator <T> Nil;
    MDequeNode <T> * Temp;
    MDequeNode <T> * Head;
    MDequeNode <T> * Tail;
};

int GetAPrime( int ith );

template<typename T>
class MHash
{
public:
    MHash( ) : m_iSize( GetAPrime( m_iPrimest = 1 ) ) 
    { 
        m_pTable = new MHashNode<T> * [m_iSize]; 
        memset( m_pTable, 0, m_iSize * sizeof( MHashNode<T>* ) );
        m_iCount = 0;
    }

    MHash( const MHash & rhs ) 
    {
        m_iPrimest = rhs.m_iPrimest;
        m_iCount = rhs.m_iCount;
        m_pTable = new MHashNode<T> * [rhs.m_iSize];
        m_iSize = rhs.m_iSize;
        
        memset( m_pTable, 0, m_iSize * sizeof( MHashNode<T>* ) );

        for( unsigned i = 0; i < m_iSize; ++i )
        {
            MHashNode <T> * TMP = rhs.m_pTable[i];
            while (TMP)
            {
                m_pTable[i] = new MHashNode<T>( m_pTable[i], TMP->Index, TMP->Data );
                TMP = TMP->Next;
            }
        }
    }

    MHash & operator = ( const MHash & rhs ) 
    {
        m_iPrimest = rhs.m_iPrimest;
        m_iCount = rhs.m_iCount;
        m_pTable = new MHashNode<T> * [rhs.m_iSize];
        m_iSize = rhs.m_iSize;
        
        memset( m_pTable, 0, m_iSize * sizeof( MHashNode<T>* ) );

        for( unsigned i = 0; i < m_iSize; ++i )
        {
            MHashNode <T> * TMP = rhs.m_pTable[i];
            while (TMP)
            {
                m_pTable[i] = new MHashNode<T>( m_pTable[i], TMP->Index, TMP->Data );
                TMP = TMP->Next;
            }
        }
        return *this;
    }

    void resize( int iNewSize )
    {
        MHashNode <T> ** pOldTable = m_pTable;
        int iOldSize = m_iSize;

        m_pTable = new MHashNode<T> * [iNewSize];
        m_iSize = iNewSize;
        memset( m_pTable, 0, iNewSize * sizeof( MHashNode<T>* ) );

        for( int i = 0; i < iOldSize; ++i )
        {
            while (pOldTable[i])
            {
                MHashNode <T> * TMP = pOldTable[i];
                pOldTable[i] = TMP->Next;

                int iNewHash = TMP->Index.hash();
                MHashNode <T> * TMP2 =  m_pTable[iNewHash%m_iSize];
                m_pTable[iNewHash%m_iSize] = TMP;
                TMP->Next = TMP2;
            }
        }

        free( pOldTable );
    }

    ~MHash()
    {
        for( unsigned i = 0; i < m_iSize; ++i )
            while (m_pTable[i])
            {
                MHashNode <T> * TMP = m_pTable[i];
                m_pTable[i] = TMP->Next;
                SAFE_DELETE( TMP );
            }
        SAFE_DELETE( m_pTable );
    }

    void clear()
    {
        for( unsigned i = 0; i < m_iSize; ++i )
        {
            while (m_pTable[i])
            {
                MHashNode <T> * TMP = m_pTable[i];
                m_pTable[i] = TMP->Next;
                SAFE_DELETE( TMP );
            }
            m_pTable[i] = 0;
        }
        m_iCount = 0;
    }

    T & operator[]( const MString & pIndex )
    {
        unsigned int iHash = pIndex.hash();
        MHashNode<T> * m_pTmp = m_pTable[iHash%m_iSize];

        while( m_pTmp )
            if( m_pTmp->Index == pIndex )
                return m_pTmp->Data;
            else
                m_pTmp = m_pTmp->Next;

        insert( pIndex, T() );

        m_pTmp = m_pTable[iHash%m_iSize];

        while( m_pTmp )
            if( m_pTmp->Index == pIndex )
                return m_pTmp->Data;
            else
                m_pTmp = m_pTmp->Next;

        //This should NEVER HAPPEN.
        FAIL( "FAIL! Hash insertion failed!" );
        return m_pNil;
    }

    void insert( const MString & pIndex, const T & pData )
    {
        unsigned int iHash = pIndex.hash();
        m_pTable[iHash%m_iSize] = new MHashNode<T>( m_pTable[iHash%m_iSize], pIndex, pData );
        
        if( ++m_iCount > m_iSize + 5 )
            resize( GetAPrime( ++m_iPrimest ) );
    }

    T * get( const MString & pIndex )
    {
        unsigned int iHash = pIndex.hash();
        MHashNode<T>    * m_pTmp = m_pTable[iHash%m_iSize];

        while( m_pTmp )
            if( m_pTmp->Index == pIndex )
                return &m_pTmp->Data;
            else
                m_pTmp = m_pTmp->Next;

        return 0;
    }

    bool remove( const MString & pIndex )
    {
        unsigned int iHash = pIndex.hash();
        MHashNode<T>    * m_pPrev = 0; 
        MHashNode<T>    * m_pTmp = m_pTable[iHash%m_iSize];

        while( m_pTmp )
            if( m_pTmp->Index == pIndex )
            {
                if( m_pPrev )
                    m_pPrev->Next = m_pTmp->Next;
                else
                    m_pTable[iHash%m_iSize] = m_pTable[iHash%m_iSize]->Next;
                SAFE_DELETE( m_pTmp );
                m_iCount--;
                return true;
            }
            else
            {
                m_pPrev = m_pTmp;
                m_pTmp = m_pTmp->Next;
            }

        return false;
    }

    void VectorIndicies( MVector < MString > & vOut )
    {
        unsigned int i;
        MHashNode<T> * m_pTmp;
        for( i = 0; i < m_iSize; i++ )
        {
            m_pTmp = m_pTable[i];
            while( m_pTmp )
            {
                vOut.push_back( m_pTmp->Index );
                m_pTmp = m_pTmp->Next;
            }
        }
    }

private:
    template<typename TC>
    struct MHashNode
    {
        MHashNode() : Next(0) { }
        MHashNode( MHashNode<TC> * pA, const MString & pIn, const TC & pD ) : Next( pA ), Index( pIn ), Data( pD ) { }

        MHashNode <TC> * Next;
        MString Index;
        TC      Data;
    };

    MHashNode <T> ** m_pTable;
    T               m_pNil;
    unsigned int    m_iSize;
    unsigned int    m_iPrimest;
    unsigned int    m_iCount;
};

#endif 

/* 
 * Copyright (c) 2006 Joshua Allen (MVector), Charles Lohr (MList)
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or
 * without modification, are permitted provided that the following
 * conditions are met:
 *  -   Redistributions of source code must retain the above
 *      copyright notice, this list of conditions and the following disclaimer.
 *  -   Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in
 *      the documentation and/or other materials provided with the distribution.
 *  -   Neither the name of the Mercury Engine nor the names of its
 *      contributors may be used to endorse or promote products derived from
 *      this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
 * USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

---

Hosted by