//////////////////////////////////////////////////////////////////////////////
//
// Asura_List.h
//
// Copyright (c) 2004 Rebellion. All rights reserved.
//
// Description:
//
//      General templatised list class. Best for use with user defined classes
//      that do not have an Asura_Guid.
//      For entities with Asura_Guids the Asura_HashedList.h class will
//      provide quicker access to specific objects.
//
//////////////////////////////////////////////////////////////////////////////

// B E G I N   F I L E   W R A P P E R ///////////////////////////////////////

#ifdef ASURA_USE_PRAGMA_ONCE
    #pragma once
#endif

#ifndef ___ASURA_LIST_H___
#define ___ASURA_LIST_H___ 1

// E N D   F I L E   W R A P P E R ///////////////////////////////////////////

// I N C L U D E S ///////////////////////////////////////////////////////////

#include "Debugging/Asura_Assert.h"

// F O R W A R D   D E C L A R A T I O N S ///////////////////////////////////

template< typename T > class Asura_List_It;
template< typename T > class Asura_List_ConstIt;
template< typename T > class Asura_List_ReverseIt;

typedef void*( Asura_List_MemSupplyFuncPtr() );
typedef void( Asura_List_MemReturnFuncPtr( void* ) );

//////////////////////////////////////////////////////////////////////////////
//
// Asura_List_Node
//
//////////////////////////////////////////////////////////////////////////////

template< typename T >
class Asura_List_Node
{
public:
    T*                    m_pxObject;
    Asura_List_Node< T >* m_pxPrev;
    Asura_List_Node< T >* m_pxNext;
};

//////////////////////////////////////////////////////////////////////////////
//
// Asura_List
//
//////////////////////////////////////////////////////////////////////////////

template< typename T >
class Asura_List
{
    friend class Asura_List_It< T >;
	friend class Asura_List_ConstIt< T >;
	friend class Asura_List_ReverseIt< T >;

public:
    Asura_List< T >()
    : m_pxHead( NULL )
    , m_pxTail( NULL )
    , m_iNumEntries( 0 )
    {
    }

    ~Asura_List< T >()
    {
        ClearList();
    }

    // provides functionality for supplying your own memory to the linked list
    // get the memory element size and create your mempool or whatever
    // implement the supply and return functions to supply and return memory from your storage
    // obviously you must either provide both of these or neither, otherwise things go bad
    static size_t GetMemoryElementSize() { return sizeof( Asura_List_Node< T > ); }
    static void SetMemorySupplyFunction( Asura_List_MemSupplyFuncPtr pMemSupplyFuncPtr ) { s_pMemSupplyFuncPtr = pMemSupplyFuncPtr; }
    static void SetMemoryReturnFunction( Asura_List_MemReturnFuncPtr pMemReturnFuncPtr ) { s_pMemReturnFuncPtr = pMemReturnFuncPtr; }

    void AddToList( T* pxObject, const bool bAddToHead = true )
    {
        Asura_List_Node< T >* pxNewNode = NULL;
        if ( s_pMemSupplyFuncPtr == NULL )
        {
            pxNewNode = new Asura_List_Node< T >;
        }
        else
        {
            pxNewNode = static_cast< Asura_List_Node< T >* >( s_pMemSupplyFuncPtr() );
        }

        pxNewNode->m_pxObject = pxObject;

		if(bAddToHead)
		{
			pxNewNode->m_pxNext   = m_pxHead;
			pxNewNode->m_pxPrev   = NULL;

			if ( pxNewNode->m_pxNext )
			{
				pxNewNode->m_pxNext->m_pxPrev = pxNewNode;
			}
			else
			{
				m_pxTail = pxNewNode;
			}

			m_pxHead = pxNewNode;
		}
		else
		{
			pxNewNode->m_pxNext   = NULL;
			pxNewNode->m_pxPrev   = m_pxTail;

			if ( pxNewNode->m_pxPrev )
			{
				pxNewNode->m_pxPrev->m_pxNext = pxNewNode;
			}
			else
			{
				m_pxHead = pxNewNode;
			}

			m_pxTail = pxNewNode;
		}

        ++m_iNumEntries;
    }

	void PushHead(T* pxObject)
	{
		AddToList(pxObject, true);
	}

	void PushTail(T* pxObject)
	{
		AddToList(pxObject, false);
	}

    // sorts and inserts into the list
    // comparison function should return positive if object one should come after object two in the list
	// for numerical order, just do pxObjectOne - pxObjectTwo, or equivalent
    void InsertInList( T* pxObject, int ( *pfnComparison )( const T& pxObjectOne, const T& pxObjectTwo ) )
    {
        ++m_iNumEntries;

        Asura_List_Node< T >* pxNewNode = NULL;
        if ( s_pMemSupplyFuncPtr == NULL )
        {
            pxNewNode = new Asura_List_Node< T >;
        }
        else
        {
            pxNewNode = static_cast< Asura_List_Node< T >* >( s_pMemSupplyFuncPtr() );
        }

        pxNewNode->m_pxObject = pxObject;
        pxNewNode->m_pxNext   = 0;
        pxNewNode->m_pxPrev   = 0;

        Asura_List_Node< T >* pxNode = m_pxHead;

        while ( pxNode )
        {
            if ( pfnComparison( *pxNewNode->m_pxObject, *pxNode->m_pxObject ) <= 0 )
            {
                // insert before this one
                pxNewNode->m_pxPrev = pxNode->m_pxPrev;
                pxNewNode->m_pxNext = pxNode;

                if ( pxNode->m_pxPrev )
                {
                    pxNode->m_pxPrev->m_pxNext = pxNewNode;
                }
                pxNode->m_pxPrev = pxNewNode;

                if ( pxNode == m_pxHead )
                {
                    m_pxHead = pxNewNode;
                }

                return;
            }
            else
            {
                // check the next node along
                if ( pxNode->m_pxNext == 0 ||
                     pfnComparison( *pxNewNode->m_pxObject, *pxNode->m_pxNext->m_pxObject ) <= 0 )
                {
                    // insert it after this one
                    pxNewNode->m_pxPrev = pxNode;
                    pxNewNode->m_pxNext = pxNode->m_pxNext;

                    if ( pxNode->m_pxNext )
                    {
                        pxNode->m_pxNext->m_pxPrev = pxNewNode;
                    }
                    else
                    {
                        m_pxTail = pxNewNode;
                    }

                    pxNode->m_pxNext = pxNewNode;

                    return;
                }
            }

            pxNode = pxNode->m_pxNext;
        }

        // if we get here we haven't managed to insert this new object, meaning there are no objects
        // currently in the list - just add it at the front
        m_pxHead = pxNewNode;
        m_pxTail = pxNewNode;
    }

    bool RemoveFromListIfPresent( T* pxObject )
    {
        Asura_List_Node< T >* pxNode = m_pxHead;

        while ( pxNode )
        {
            if ( pxNode->m_pxObject == pxObject )
            {
				RemoveNodeFromList(pxNode);
                return true;
            }
            
            pxNode = pxNode->m_pxNext;
        }

        return false;
    }

	void RemoveFromList( T* pxObject )
	{
#ifdef ASURA_ASSERT
		bool bFound =
#endif
		RemoveFromListIfPresent(pxObject);

		Asura_Assert( bFound, "Asura_List<T>::RemoveFromList - Node not found" );
	}

    T* FindObject( T* pxObject )
    {
        Asura_List_Node<T>* pxNode = m_pxHead;

        while ( pxNode )
        {
            if ( pxNode->m_pxObject == pxObject )
            {
                return pxNode->m_pxObject;
            }

            pxNode = pxNode->m_pxNext;
        }

        return NULL;
    }

    T* GetHeadObject() { return ( m_pxHead == NULL ? NULL : m_pxHead->m_pxObject ); }
	T* GetTailObject() { return ( m_pxTail == NULL ? NULL : m_pxTail->m_pxObject ); }

	const T* GetHeadObject() const { return ( m_pxHead == NULL ? NULL : m_pxHead->m_pxObject ); }
    const T* GetTailObject() const { return ( m_pxTail == NULL ? NULL : m_pxTail->m_pxObject ); }

    T* PopHeadObject()
    {
        if ( !m_pxHead )
        {
            return NULL;
        }

        Asura_List_Node< T >* pxNode = m_pxHead;
        T* pxObject = pxNode->m_pxObject;

        if ( pxNode->m_pxNext )
        {
            pxNode->m_pxNext->m_pxPrev = pxNode->m_pxPrev;
            m_pxHead = pxNode->m_pxNext;
        }
        else
        {
            m_pxHead = NULL;
            m_pxTail = NULL;
        }

        if ( s_pMemReturnFuncPtr == NULL )
        {
            delete pxNode;
        }
        else
        {
            s_pMemReturnFuncPtr( pxNode );
        }

        --m_iNumEntries;

        return pxObject;
    }

    T* PopTailObject()
    {
        if ( !m_pxTail )
        {
            return NULL;
        }

        Asura_List_Node< T >* pxNode = m_pxTail;
        T* pxObject = pxNode->m_pxObject;

        if ( pxNode->m_pxPrev )
        {
            pxNode->m_pxPrev->m_pxNext = pxNode->m_pxNext;
            m_pxTail = pxNode->m_pxPrev;
        }
        else
        {
            m_pxHead = NULL;
            m_pxTail = NULL;
        }

        if ( s_pMemReturnFuncPtr == NULL )
        {
            delete pxNode;
        }
        else
        {
            s_pMemReturnFuncPtr( pxNode );
        }

        --m_iNumEntries;

        return pxObject;
    }

    void ClearList()
    {
        Asura_List_Node< T >* pxNode = m_pxHead;

        while ( pxNode )
        {
            Asura_List_Node< T >* pxToDelete = pxNode;

            pxNode = pxNode->m_pxNext;

            if ( s_pMemReturnFuncPtr == NULL )
            {
                delete pxToDelete;
            }
            else
            {
                s_pMemReturnFuncPtr( pxToDelete );
            }
        }

		m_pxHead = NULL;
        m_pxTail = NULL;

        m_iNumEntries = 0;
    }

	bool IsEmpty() const 
	{ 
		return (m_pxHead == NULL);
	}

    int GetNumEntries() const { return m_iNumEntries; }

    const T* GetEntryByIndex( int iIndex ) const
    {
        if( iIndex < 0 || iIndex >= m_iNumEntries ) { return NULL; }

        const Asura_List_Node<T>* pxCurNode = m_pxHead;
        while( iIndex-- )
        {
            pxCurNode = pxCurNode->m_pxNext;
        }

        return pxCurNode->m_pxObject;
    }

	T* GetEntryByIndex( int iIndex )
	{
		if( iIndex < 0 || iIndex >= m_iNumEntries ) { return NULL; }

        Asura_List_Node<T>* pxCurNode = m_pxHead;
        while( iIndex-- )
        {
            pxCurNode = pxCurNode->m_pxNext;
        }

        return pxCurNode->m_pxObject;
	}

protected:
	void RemoveNodeFromList(Asura_List_Node< T >* pxNode)
	{
		if (pxNode)
		{
			if ( pxNode->m_pxNext )
            {
                pxNode->m_pxNext->m_pxPrev = pxNode->m_pxPrev;
            }
            else
            {
                m_pxTail = pxNode->m_pxPrev;
            }
            if ( pxNode->m_pxPrev )
            {
                pxNode->m_pxPrev->m_pxNext = pxNode->m_pxNext;
            }
            else
            {
                m_pxHead = pxNode->m_pxNext;
            }

            if ( s_pMemReturnFuncPtr == NULL )
            {
                delete pxNode;
            }
            else
            {
                s_pMemReturnFuncPtr( pxNode );
            }

            --m_iNumEntries;
		}
	}

protected:
    Asura_List_Node< T >* m_pxHead;
    Asura_List_Node< T >* m_pxTail;
    int                   m_iNumEntries;

	static Asura_List_MemSupplyFuncPtr* s_pMemSupplyFuncPtr;
	static Asura_List_MemReturnFuncPtr* s_pMemReturnFuncPtr;
};

template < typename T > Asura_List_MemSupplyFuncPtr* Asura_List< T >::s_pMemSupplyFuncPtr = NULL;
template < typename T > Asura_List_MemReturnFuncPtr* Asura_List< T >::s_pMemReturnFuncPtr = NULL;

//////////////////////////////////////////////////////////////////////////////
//
// Asura_List_It
//
//////////////////////////////////////////////////////////////////////////////

template< typename T >
class Asura_List_It
{
public:
    // constructor for iterator, also starts the iteration
	Asura_List_It< T >( Asura_List< T >& xList )
	{
		m_pxList = &xList;
		Restart();
	}

    Asura_List_It< T >( Asura_List< T >* pxList )
    {
        Asura_Assert( pxList, "" );
        m_pxList = pxList;
        Restart();
    }

    // gets the current entity in the iteration
    T* GetCurrent() const
    {
        return m_pxCurrentNode->m_pxObject;
    }

    // deletes the current entity and moves to the next in the list
    void DeleteCurrent()
    {
		if ( m_pxCurrentNode )
        {
            Asura_List_Node< T >* pxToDelete = m_pxCurrentNode;
            Next();
			// MGH 15/10/2007: There is no need to search through the list for the node.
            //m_pxList->RemoveFromList( pxToDelete->m_pxObject );
			m_pxList->RemoveNodeFromList(pxToDelete);
        }
    }

    // advance to the next entity in the list
    void Next()
    {
        if ( m_pxCurrentNode )
        {
            m_pxCurrentNode = m_pxCurrentNode->m_pxNext;
        }
    }

    // indicates whether the iteration has finished
    bool Done() const
    {
        return ( m_pxCurrentNode == 0 );
    }

    // restarts the iteration
    void Restart()
    {
        m_pxCurrentNode = m_pxList->m_pxHead;
    }

private:
    Asura_List< T >*      m_pxList;
    Asura_List_Node< T >* m_pxCurrentNode;
};

//////////////////////////////////////////////////////////////////////////////
//
// Asura_List_ConstIt
//
//////////////////////////////////////////////////////////////////////////////

template< typename T >
class Asura_List_ConstIt
{
public:
    // constructor for iterator, also starts the iteration
    Asura_List_ConstIt< T >( const Asura_List< T >& xList )
    {
        m_pxList = &xList;
        Restart();
    }

	Asura_List_ConstIt< T >( const Asura_List< T >* pxList )
	{
		Asura_Assert( pxList, "" );
		m_pxList = pxList;
		Restart();
	}

    // gets the current entity in the iteration
    const T* GetCurrent() const
    {
        return m_pxCurrentNode->m_pxObject;
    }

    // advance to the next entity in the list
    void Next()
    {
        if ( m_pxCurrentNode )
        {
			m_pxCurrentNode = m_pxCurrentNode->m_pxNext;
        }
    }

    // indicates whether the iteration has finished
    bool Done() const
    {
        return ( m_pxCurrentNode == 0 );
    }

    // restarts the iteration
    void Restart()
    {
        m_pxCurrentNode = m_pxList->m_pxHead;
    }

private:
    const Asura_List< T >*      m_pxList;
    const Asura_List_Node< T >* m_pxCurrentNode;
};

//////////////////////////////////////////////////////////////////////////////
//
// Asura_List_ReverseIt
// Traverses the list from the tail to the head.
//
//////////////////////////////////////////////////////////////////////////////

template< typename T >
class Asura_List_ReverseIt
{
public:
    // constructor for iterator, also starts the iteration
    Asura_List_ReverseIt< T >( Asura_List< T >& xList )
    {
        m_pxList = &xList;
        Restart();
    }

	Asura_List_ReverseIt< T >( Asura_List< T >* pxList )
	{
		Asura_Assert( pxList, "" );
		m_pxList = pxList;
		Restart();
	}

    // gets the current entity in the iteration
    T* GetCurrent() const
    {
        return m_pxCurrentNode->m_pxObject;
    }

    // deletes the current entity and moves to the next in the list
    void DeleteCurrent()
    {
		if ( m_pxCurrentNode )
        {
            Asura_List_Node< T >* pxToDelete = m_pxCurrentNode;
            Next();
			// MGH 15/10/2007: There is no need to search through the list for the node.
			//m_pxList->RemoveFromList( pxToDelete->m_pxObject );
			m_pxList->RemoveNodeFromList(pxToDelete);
        }
    }

    // advance to the next entity in the list
    void Next()
    {
        // return to our place in the loop, if this isn't the first time
        if ( m_pxCurrentNode )
        {
            goto ReEnterLoop;
        }
        
        m_pxCurrentNode = m_pxList->m_pxTail;

        while ( m_pxCurrentNode )
        {
            return;

            ReEnterLoop:

            m_pxCurrentNode = m_pxCurrentNode->m_pxPrev;
        }
    }

    // indicates whether the iteration has finished
    bool Done() const
    {
        return ( m_pxCurrentNode == 0 );
    }

    // restarts the iteration
    void Restart()
    {
        m_pxCurrentNode = 0;
        Next();
    }

private:
    Asura_List< T >*      m_pxList;
    Asura_List_Node< T >* m_pxCurrentNode;
};

//////////////////////////////////////////////////////////////////////////////
//
// 
//
//////////////////////////////////////////////////////////////////////////////

#endif // #ifndef ___ASURA_LIST_H___
