//----------------------------------------------------------------------------
// William Baxter III's Ray Tracer
//
//     Project for Comp 238, Raster Graphics
//     University of North Carolina at Chapel Hill
//     
// $Id:$
// Code in this file copyright Numerical Design Ltd.
//----------------------------------------------------------------------------


#ifndef WB3TLIST_H
#define WB3TLIST_H

// While the template lists work best for pointer types T, other types
// certainly will work when they satisfy the conditions below.  The template
// class assumes that type T has the following:
//   1.  A "zero" element (i.e., T var; var = 0; is supported)
//       which is considered to be a null array element.
//   2.  The default constructor for T must exist and create the
//       "zero" element.  The constructor must also handle all necessary
//       actions for constructing elements.  That is, the template array
//       class cannot make any post-construction member calls that are
//       specific to class T.
//   3.  Copy constructor T::T (const T&) must work properly.  The class T is
//       responsible for implementing this if need be.
//   4.  The destructor must handle all necessary actions for destroying
//       elements.  That is, the template array class cannot make any
//       pre-destruction member calls that are specific to class T.
//   5.  bool operator== (const T&);
//   6.  bool operator!= (const T&);
//   7.  T& operator= (const T&);
//
//
// Example of iteration from head to tail:
//
//   wb3TList<T> list;
//   wb3TListIterator pos = list.GetHeadPos();
//   while ( pos )
//   {
//       T element = list.GetNext(pos);
//       <process element here>;
//   }


typedef void* wb3TListIterator;

template <class T> class wb3TList 
{
public:
    // construction and destruction
    wb3TList (unsigned int uiBlockSize = 2);
    ~wb3TList ();

    // counting elements in list
    unsigned int GetSize () const;
    bool IsEmpty () const;

    // add or remove elements
    void AddHead (T element);
    void AddTail (T element);
    wb3TListIterator InsertBefore (wb3TListIterator pos, T element);
    wb3TListIterator InsertAfter (wb3TListIterator pos, T element);
    T RemoveHead ();
    T RemoveTail ();
    T RemovePos (wb3TListIterator& pos);
    T Remove (T element);
    void RemoveAll ();

    // element access
    T GetHead () const;
    T GetTail () const;
    wb3TListIterator GetHeadPos () const;
    wb3TListIterator GetTailPos () const;
    T Get (wb3TListIterator pPos) const;

    // list traversal
    T GetNext (wb3TListIterator& pos) const;
    T GetPrev (wb3TListIterator& pos) const;
    wb3TListIterator GetNextPos (wb3TListIterator pos) const;
    wb3TListIterator GetPrevPos (wb3TListIterator pos) const;
    wb3TListIterator FindPos (T element, wb3TListIterator start = 0) const;

protected:
    // list is doubly-linked
    class Node 
    {
    public:
        T m_element;
        Node* m_pNext;
        Node* m_pPrev;
    };

    class Block 
    {
    public:
        Block (unsigned int uiSize)
        {
            m_pNext = 0;
            m_pNodes = (Node*) new Node[uiSize];
            assert( m_pNodes );
            for (unsigned int i = 0; i < uiSize-1; i++)
                m_pNodes[i].m_pNext = &m_pNodes[i+1];
            m_pNodes[uiSize-1].m_pNext = 0;
        };

        ~Block () { delete[] m_pNodes; }

        Block* m_pNext;
        Node* m_pNodes;
    };

    Node* AllocNode();
    void FreeNode (Node* pNode);

    unsigned int m_uiCount;      // number of elements in list
    Node* m_pHead;               // points to head of list
    Node* m_pTail;               // points to tail of list
    Node* m_pFree;               // list of free nodes
    Block* m_pBlocks;            // memory pool
    unsigned int m_uiBlockSize;  // number of nodes per block in pool
};

//---------------------------------------------------------------------------
template <class T> inline
wb3TList<T>::wb3TList (unsigned int uiBlockSize)
{
    m_uiCount = 0;
    m_pHead = 0;
    m_pTail = 0;
    m_pFree = 0;
    m_pBlocks = 0;

    // Nodes per block must be at least 2, otherwise the memory pool is
    // less efficient than regular memory management.
    m_uiBlockSize = (uiBlockSize > 2) ? uiBlockSize : 2;
}
//---------------------------------------------------------------------------
template <class T> inline
wb3TList<T>::~wb3TList ()
{
    RemoveAll();
}
//---------------------------------------------------------------------------
template <class T> inline
unsigned int wb3TList<T>::GetSize () const
{
    return m_uiCount;
}
//---------------------------------------------------------------------------
template <class T> inline
bool wb3TList<T>::IsEmpty () const
{
    return m_uiCount == 0;
}
//---------------------------------------------------------------------------
template <class T> inline
void wb3TList<T>::AddHead (T element)
{
    wb3TList::Node* pNode = AllocNode();

    pNode->m_element = element;
    pNode->m_pPrev = 0;
    pNode->m_pNext = m_pHead;
    
    if ( m_pHead )
        m_pHead->m_pPrev = pNode;
    else
        m_pTail = pNode;
    
    m_pHead = pNode;
    m_uiCount++;
}
//---------------------------------------------------------------------------
template <class T> inline
void wb3TList<T>::AddTail (T element)
{
    wb3TList::Node* pNode = AllocNode();
    
    pNode->m_element = element;
    pNode->m_pNext = 0;
    pNode->m_pPrev = m_pTail;
    
    if ( m_pTail )
        m_pTail->m_pNext = pNode;
    else
        m_pHead = pNode;
    
    m_pTail = pNode;
    m_uiCount++;
}
//---------------------------------------------------------------------------
template <class T> inline
wb3TListIterator wb3TList<T>::InsertBefore (wb3TListIterator pos, T element)
{
    wb3TList::Node* pNode = AllocNode();
    wb3TList::Node* pNext = (wb3TList::Node*) pos;
    pNode->m_element = element;
    pNode->m_pNext = pNext;
    pNode->m_pPrev = pNext->m_pPrev;
    
    if ( pNext->m_pPrev )
        pNext->m_pPrev->m_pNext = pNode;
    else
        m_pHead = pNode;

    pNext->m_pPrev = pNode;

    m_uiCount++;
    return pNode;
}
//---------------------------------------------------------------------------
template <class T> inline
wb3TListIterator wb3TList<T>::InsertAfter (wb3TListIterator pos, T element)
{
    wb3TList::Node* pNode = AllocNode();
    wb3TList::Node* pPrev = (wb3TList::Node*) pos;
    pNode->m_element = element;
    pNode->m_pPrev = pPrev;
    pNode->m_pNext = pPrev->m_pNext;
    
    if ( pPrev->m_pNext )
        pPrev->m_pNext->m_pPrev = pNode;
    else
        m_pTail = pNode;

    pPrev->m_pNext = pNode;

    m_uiCount++;
    return pNode;
}
//---------------------------------------------------------------------------
template <class T> inline
T wb3TList<T>::RemoveHead ()
{
    assert( m_pHead );

    wb3TList::Node* pNode = m_pHead;
    
    m_pHead = m_pHead->m_pNext;
    
    if ( m_pHead )
        m_pHead->m_pPrev = 0;
    else
        m_pTail = 0;
    
    T element = pNode->m_element;
    FreeNode(pNode);
    m_uiCount--;

    return element;
}
//---------------------------------------------------------------------------
template <class T> inline
T wb3TList<T>::RemoveTail ()
{
    assert( m_pTail );
    
    wb3TList::Node* pNode = m_pTail;
    
    m_pTail = m_pTail->m_pPrev;
    
    if ( m_pTail )
        m_pTail->m_pNext = 0;
    else
        m_pHead = 0;
    
    T element = pNode->m_element;
    FreeNode(pNode);
    m_uiCount--;
    
    return element;
}
//---------------------------------------------------------------------------
template <class T> inline
T wb3TList<T>::RemovePos (wb3TListIterator& pos)
{
    wb3TList::Node* pNode = (wb3TList::Node*) pos;
    assert( pNode );

    if ( pNode == m_pHead )
    {
        pos = pNode->m_pNext; // pos points to new head
        return RemoveHead();
    }
    if ( pNode == m_pTail )
    {
        pos = 0; // pos has walked off end of list
        return RemoveTail();
    }

    wb3TList::Node* pPrev = pNode->m_pPrev;
    wb3TList::Node* pNext = pNode->m_pNext;

    pos = pNext;
    
    if ( pPrev )
        pPrev->m_pNext = pNext;
    if ( pNext )
        pNext->m_pPrev = pPrev;
    
    T element = pNode->m_element;
    FreeNode(pNode);
    m_uiCount--;
    
    return element;
}
//---------------------------------------------------------------------------
template <class T> inline
T wb3TList<T>::Remove (T element)
{
    wb3TListIterator pos = FindPos(element);
    return pos ? RemovePos(pos) : element;
}
//---------------------------------------------------------------------------
template <class T> inline
void wb3TList<T>::RemoveAll ()
{
    wb3TList::Block* pBlock = m_pBlocks;
    while ( pBlock )
    {
        wb3TList::Block* pDel = pBlock;
        pBlock = pBlock->m_pNext;
        delete pDel;
    }

    m_uiCount = 0;
    m_pHead = 0;
    m_pTail = 0;
    m_pFree = 0;
    m_pBlocks = 0;
} 
//---------------------------------------------------------------------------
template <class T> inline
T wb3TList<T>::GetHead () const
{
    return m_pHead->m_element;
}
//---------------------------------------------------------------------------
template <class T> inline
T wb3TList<T>::GetTail () const
{
    return m_pTail->m_element;
}
//---------------------------------------------------------------------------
template <class T> inline
wb3TListIterator wb3TList<T>::GetHeadPos () const
{
    return m_pHead;
}
//---------------------------------------------------------------------------
template <class T> inline
wb3TListIterator wb3TList<T>::GetTailPos () const
{
    return m_pTail;
}
//---------------------------------------------------------------------------
template <class T> inline
T wb3TList<T>::GetNext (wb3TListIterator& pos) const 
{
    if ( pos == 0 )
        return 0;

    T element = ((wb3TList::Node*)pos)->m_element;
    pos = ((wb3TList::Node*)pos)->m_pNext;
    return element;
}
//---------------------------------------------------------------------------
template <class T> inline
T wb3TList<T>::GetPrev (wb3TListIterator& pos) const
{
    if ( pos == 0 )
        return 0;

    T element = ((wb3TList::Node*)pos)->m_element;
    pos = ((wb3TList::Node*)pos)->m_pPrev;
    return element;
}
//---------------------------------------------------------------------------
template <class T> inline
T wb3TList<T>::Get (wb3TListIterator pos) const
{
    return pos ? ((wb3TList::Node*)pos)->m_element : 0;
}
//---------------------------------------------------------------------------
template <class T> inline
wb3TListIterator wb3TList<T>::GetNextPos (wb3TListIterator pos) const
{
    return pos ? ((wb3TList::Node*)pos)->m_pNext : 0;
}
//---------------------------------------------------------------------------
template <class T> inline
wb3TListIterator wb3TList<T>::GetPrevPos (wb3TListIterator pos) const
{
    return pos ? ((wb3TList::Node*)pos)->m_pPrev : 0;
}
//---------------------------------------------------------------------------
template <class T> inline
wb3TListIterator wb3TList<T>::FindPos (T element, wb3TListIterator start) const
{
    if ( start == 0 )
        start = GetHeadPos();
    
    while ( start )
    {
        wb3TListIterator pos = start;
        if ( element == GetNext(start) )
            return pos;
    }
    return 0;
}
//---------------------------------------------------------------------------
template <class T> inline
wb3TList<T>::Node* wb3TList<T>::AllocNode()
{
    if ( !m_pFree )
    {
        // all blocks used, memory pool needs another one
        wb3TList::Block* pBlock = new Block(m_uiBlockSize);
        assert( pBlock );        
        pBlock->m_pNext = m_pBlocks;
        m_pBlocks = pBlock;
        m_pFree = pBlock->m_pNodes;
    }

    // get a node from the free node list
    wb3TList::Node* pNode = m_pFree;
    m_pFree = m_pFree->m_pNext;
    return pNode;
}
//---------------------------------------------------------------------------
template <class T> inline
void wb3TList<T>::FreeNode (Node* pNode)
{
    // The element in the to-be-deleted node must be zeroed in case class T
    // has side effects that must occur.  For example, if T is a smart
    // pointer class, then decrementing the ref count must occur.
    pNode->m_element = 0;

    // return the node to the free node list
    pNode->m_pNext = m_pFree;
    m_pFree = pNode;
} 
//---------------------------------------------------------------------------

#endif