//////////////////////////////////////////////////////////////////////////////
//
// Asura_LinkList.h
//
// Copyright (C) 2008 Rebellion, All Rights Reserved.
//
//////////////////////////////////////////////////////////////////////////////

// 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_LINKLIST_H__
#define __ASURA_LINKLIST_H__

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

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

// asura
#include "Debugging/Asura_Assert.h"
#include "Network/Asura_Guid.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_LinkList_It;

//////////////////////////////////////////////////////////////////////////////
//
// Asura_ListElt
//
//////////////////////////////////////////////////////////////////////////////

template< typename T > class Asura_LinkList;

template< typename T > class Asura_ListElt
{        
public:
	Asura_ListElt<T>() : m_pxNext( NULL ), m_pxPrev( NULL ), m_xData() {}

    Asura_ListElt<T>( const T& xNew, Asura_ListElt<T>* pxNext = NULL, Asura_ListElt<T>* pxPrev = NULL )
	: m_pxNext( pxNext )
	, m_pxPrev( pxPrev )
	, m_xData( xNew )
    {
        // Connect it to the elements either side.
        if ( m_pxNext ) { m_pxNext->m_pxPrev = this; }
        if ( m_pxPrev ) { m_pxPrev->m_pxNext = this; }
    }

    Asura_ListElt<T>* Next() const {return m_pxNext;}
    Asura_ListElt<T>* Prev() const {return m_pxPrev;}

    T& Data() {return m_xData;}
    const T& Data() const {return m_xData;}

	void SetData( const T& xData ) { m_xData = xData; }

private:
	void SetNext( Asura_ListElt< T >* pxNext )
	{
		m_pxNext = pxNext;
		if ( m_pxNext ) { m_pxNext->m_pxPrev = this; }
	}
	void SetPrev( Asura_ListElt< T >* pxPrev )
	{
		m_pxPrev = pxPrev;
		if ( m_pxPrev ) { m_pxPrev->m_pxNext = this; }
	}

private:
	friend class Asura_LinkList<T>;
	Asura_ListElt<T> *m_pxNext, *m_pxPrev;
	T m_xData;
};

//////////////////////////////////////////////////////////////////////////////
//
// Asura_LinkList
// Simple doubly linked list class.
//
//////////////////////////////////////////////////////////////////////////////

typedef void*( Asura_LinkList_MemSupplyFuncPtr() );
typedef void( Asura_LinkList_MemReturnFuncPtr( void* ) );

template< typename T > class Asura_LinkList
{
public:
    Asura_LinkList<T>()
	: m_pxFront( NULL )
	, m_pxBack( NULL )
	, m_uSize( 0 )
    {
    }

	Asura_LinkList<T>( const Asura_LinkList<T>& xRHS )
	: m_pxFront( NULL )
	, m_pxBack( NULL )
	, m_uSize( 0 )
	{
		*this = xRHS;
	}

	~Asura_LinkList<T>()
    {
        Clear();
    }

	// 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_ListElt< T > ); }
	static void SetMemorySupplyFunction( Asura_LinkList_MemSupplyFuncPtr pMemSupplyFuncPtr ) { s_pMemSupplyFuncPtr = pMemSupplyFuncPtr; }
	static void SetMemoryReturnFunction( Asura_LinkList_MemReturnFuncPtr pMemReturnFuncPtr ) { s_pMemReturnFuncPtr = pMemReturnFuncPtr; }

    void Clear()
    {
        Asura_ListElt<T>* pxNextElt;
        for (Asura_ListElt<T>* pxElt = m_pxFront; pxElt; pxElt = pxNextElt)
        {
            pxNextElt = pxElt->m_pxNext;
			s_pMemReturnFuncPtr ? s_pMemReturnFuncPtr( pxElt ) : delete pxElt;
        } 

        m_pxBack  = NULL;
        m_pxFront = NULL;
        m_uSize   = 0;
    }

    Asura_ListElt<T>* Push_Front( const T& xNew ) { return PushFront( xNew ); }
	Asura_ListElt<T>* PushFront( const T& xNew )
	{
        // make a new element the front, attaching to previous if it exists
		++m_uSize;
		if ( s_pMemSupplyFuncPtr )
		{
			Asura_ListElt< T >* pxNew = static_cast< Asura_ListElt< T >* >( s_pMemSupplyFuncPtr() );
			pxNew->SetPrev( NULL );
			pxNew->SetNext( m_pxFront );
			pxNew->SetData( xNew );
			m_pxFront = pxNew;
		}
		else
		{
			m_pxFront = new Asura_ListElt< T >( xNew, m_pxFront );
		}
		if ( !m_pxBack ) { m_pxBack = m_pxFront; }
        return m_pxFront;
    }

    Asura_ListElt<T>* Push_Back( const T& xNew ) { return PushBack( xNew ); }
	Asura_ListElt<T>* PushBack( const T& xNew )
	{
        // make a new element the back, attaching to previous if it exists
		++m_uSize;
		if ( s_pMemSupplyFuncPtr )
		{
			Asura_ListElt< T >* pxNew = static_cast< Asura_ListElt< T >* >( s_pMemSupplyFuncPtr() );
			pxNew->SetPrev( m_pxBack );
			pxNew->SetNext( NULL );
			pxNew->SetData( xNew );
			m_pxBack = pxNew;
		}
		else
		{
			m_pxBack = new Asura_ListElt< T >( xNew, NULL, m_pxBack );
		}
		if ( !m_pxFront ) { m_pxFront = m_pxBack; }
        return m_pxBack;
    }

	Asura_ListElt<T>* Front() const { return m_pxFront; }
    Asura_ListElt<T>* Back()  const { return m_pxBack; }

	void PopFront() { Remove( Front() ); }
	void PopBack() { Remove( Back() ); }

    Asura_ListElt< T >* Find( const T& xToFind ) const 
    {
        // return a pointer to element with specified data if it exists (or NULL if it doesn't)
        for (Asura_ListElt<T>* pxElt = m_pxFront; pxElt; pxElt = pxElt->Next())
        {
            if (pxElt->Data() == xToFind)
            {
                return pxElt;
            }
        }
        return NULL;
    }

	// Won't be defined if not called for a particular type, so types don't have to specify GetGuid() if they don't want to.
	Asura_ListElt< T >* FindByGuid( const Asura_Guid uGuid ) const
	{
		for (Asura_ListElt<T>* pxElt = m_pxFront; pxElt; pxElt = pxElt->Next())
		{
			if (pxElt->Data().GetGuid() == uGuid)
			{
				return pxElt;
			}
		}
		return NULL;
	}

	// Won't be defined if not called for a particular type, so types don't have to specify GetGuid() if they don't want to.
	// This was considered to be the best method for providing this function for pointer-to-T types.
	// Partial template specialisation for the whole class is possible, but would duplicate a lot of code and potentially cause confusion.
	Asura_ListElt< T >* FindByGuidPtrT( const Asura_Guid uGuid ) const
	{
		for (Asura_ListElt<T>* pxElt = m_pxFront; pxElt; pxElt = pxElt->Next())
		{
			if (pxElt->Data()->GetGuid() == uGuid)
			{
				return pxElt;
			}
		}
		return NULL;
	}

	// Be aware that it is slow to access elements like this. Use the iterator for sequential access.
	Asura_ListElt< T >* operator[]( u_int u ) const
	{
		for ( Asura_ListElt< T >* pxElt = m_pxFront; pxElt; pxElt = pxElt->Next(), --u )
		{
			if ( u == 0 )
			{
				return pxElt;
			}
		}
		return NULL;		
	}

	bool Remove( const T& xToRemove )
	{
		return Remove( Find( xToRemove ) );
	}

    bool Remove( Asura_ListElt< T >* pxToRemove )
    {
		if ( pxToRemove )
		{
			--m_uSize;
			if ( pxToRemove->m_pxNext )
			{
				pxToRemove->m_pxNext->m_pxPrev = pxToRemove->m_pxPrev;
			}
			else
			{
				m_pxBack = pxToRemove->m_pxPrev;
			}

			if ( pxToRemove->m_pxPrev )
			{
				pxToRemove->m_pxPrev->m_pxNext = pxToRemove->m_pxNext;
			} 
			else
			{
				m_pxFront = pxToRemove->m_pxNext;
			}

			s_pMemReturnFuncPtr ? s_pMemReturnFuncPtr( pxToRemove ) : delete pxToRemove;

			return true;
		}
		else
		{
			return false;
		}
    }

	// Comparison function should return positive if object one should come after object two in the list.
	Asura_ListElt<T>* Insert( const T& xNew, int ( *pfnComparison )( const T& xObjectOne, const T& xObjectTwo ) )
	{
		Asura_ListElt<T>* pxNode = Front();
		while ( pxNode )
		{
			if ( pfnComparison( xNew, pxNode->Data() ) <= 0 )
			{
				return InsertBefore( pxNode, xNew );
			}

			pxNode = pxNode->Next();
		}

		// We have hit the end of the nodes.
		return PushBack( xNew );
	}

	Asura_ListElt<T>* Insert_After(Asura_ListElt<T>* pxElt, const T& xNew) { return InsertAfter( pxElt, xNew ); }
    Asura_ListElt<T>* InsertAfter(Asura_ListElt<T>* pxElt, const T& xNew)
    {
        if (pxElt)
        {
			++m_uSize;
			if ( s_pMemSupplyFuncPtr )
			{
				Asura_ListElt< T >* pxNew = static_cast< Asura_ListElt< T >* >( s_pMemSupplyFuncPtr() );
				pxNew->SetData( xNew );
				pxNew->SetNext( pxElt->Next() );
				pxElt->SetNext( pxNew );
			}
			else
			{
				pxElt->m_pxNext = new Asura_ListElt< T >( xNew, pxElt->m_pxNext, pxElt );
			}

            if (pxElt->m_pxNext && !pxElt->m_pxNext->m_pxNext) 
            {
                // it's the new back
                m_pxBack = pxElt->m_pxNext;
            }
            return pxElt->m_pxNext;
        }
        else
        {
            return PushBack(xNew);
        }
    }

	Asura_ListElt<T>* Insert_Before(Asura_ListElt<T>* pxElt, const T& xNew) { return InsertBefore( pxElt, xNew ); }
    Asura_ListElt<T>* InsertBefore(Asura_ListElt<T>* pxElt, const T& xNew)
    {
        if (pxElt)
        {
			++m_uSize;
			if ( s_pMemSupplyFuncPtr )
			{
				Asura_ListElt< T >* pxNew = static_cast< Asura_ListElt< T >* >( s_pMemSupplyFuncPtr() );
				pxNew->SetData( xNew );
				pxNew->SetPrev( pxElt->Prev() );
				pxElt->SetPrev( pxNew );
			}
			else
			{
				pxElt->m_pxPrev = new Asura_ListElt< T >( xNew, pxElt, pxElt->m_pxPrev );
			}

            if (pxElt->m_pxPrev && !pxElt->m_pxPrev->m_pxPrev)
            {
                // it's the new front
                m_pxFront = pxElt->m_pxPrev;
            }
            return pxElt->m_pxPrev;
        }
        else
        {
            return PushFront(xNew);
        }
    }

	u_int Size() const { return m_uSize; }

	inline Asura_LinkList& operator = ( const Asura_LinkList<T>& xList ) 
	{
		if(this != &xList)
		{
			Clear();
			for(const Asura_ListElt<T>* pxIt = xList.m_pxFront; pxIt; pxIt = pxIt->Next())
			{
				PushBack(pxIt->Data());
			}
		}
		return *this;
	}

private:
	Asura_ListElt< T >* m_pxFront;
	Asura_ListElt< T >* m_pxBack;
	u_int               m_uSize;

	static Asura_LinkList_MemSupplyFuncPtr* s_pMemSupplyFuncPtr;
	static Asura_LinkList_MemReturnFuncPtr* s_pMemReturnFuncPtr;
};

template < typename T > Asura_LinkList_MemSupplyFuncPtr* Asura_LinkList< T >::s_pMemSupplyFuncPtr = NULL;
template < typename T > Asura_LinkList_MemReturnFuncPtr* Asura_LinkList< T >::s_pMemReturnFuncPtr = NULL;

//////////////////////////////////////////////////////////////////////////////
//
// Asura_LinkList_It
//
//////////////////////////////////////////////////////////////////////////////

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

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

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

	Asura_ListElt< T >* GetCurrentNode() const
	{
		return m_pxCurrentNode;
	}

	// gets the data just after the current point in the iteration, returning 0 if there is no next.
	T* GetNext() const
	{
		if(m_pxCurrentNode && m_pxCurrentNode->Next())
		{
			return &(m_pxCurrentNode->Next()->Data());
		}
		else
		{
			return NULL;
		}
	}

    // deletes the current entity and moves to the next in the list
    void DeleteCurrent()
    {
		if ( m_pxCurrentNode )
        {
            Asura_ListElt< T >* pxToDelete = m_pxCurrentNode;
            Next();
			m_pxList->Remove( 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->Front();

        while ( m_pxCurrentNode )
        {
            return;

            ReEnterLoop:

            m_pxCurrentNode = m_pxCurrentNode->Next();
        }
    }

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

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

private:
    Asura_LinkList< T >* m_pxList;
    Asura_ListElt< T >*  m_pxCurrentNode;
};

//////////////////////////////////////////////////////////////////////////////
//
// Asura_LinkList_ConstIt
//
//////////////////////////////////////////////////////////////////////////////

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

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

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

    // 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->Front();

        while ( m_pxCurrentNode )
        {
            return;

            ReEnterLoop:

            m_pxCurrentNode = m_pxCurrentNode->Next();
        }
    }

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

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

private:
    const Asura_LinkList< T >* m_pxList;
    const Asura_ListElt< T >*  m_pxCurrentNode;
};

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

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

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

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


    // deletes the current entity and moves to the next in the list
    void DeleteCurrent()
    {
		if ( m_pxCurrentNode )
        {
            Asura_ListElt< T >* pxToDelete = m_pxCurrentNode;
            Next();
			m_pxList->Remove( 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->Back();

        while ( m_pxCurrentNode )
        {
            return;

            ReEnterLoop:

            m_pxCurrentNode = m_pxCurrentNode->Prev();
        }
    }

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

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

private:
    Asura_LinkList< T >* m_pxList;
    Asura_ListElt< T >*  m_pxCurrentNode;
};

//////////////////////////////////////////////////////////////////////////////
//
// Asura_LinkList_ConstReverseIt
//
//////////////////////////////////////////////////////////////////////////////

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

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

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

    // 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->Back();

        while ( m_pxCurrentNode )
        {
            return;

            ReEnterLoop:

            m_pxCurrentNode = m_pxCurrentNode->Prev();
        }
    }

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

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

private:
    const Asura_LinkList< T >* m_pxList;
    const Asura_ListElt< T >*  m_pxCurrentNode;
};

#endif //__ASURA_LINKLIST_H__
