///////////////////////////////////////////////////////////////////////////////
//
//      ##  ######          
//       ######  ###        Based on:
//  ## ###############      
//   ########## # # #       Shark 3D Engine (www.shark3d.com)
//    ########
//   ######### # # #        Copyright (c) 1996-2001 Spinor GmbH.
//  ##   ##########         
//      ##                  
//        
/////////////////////////////////////////////////////////////////////////////////
//
// G A M E.O.N.E - LOW LEVEL LIB V1.0
// Copyright (C) 2001 LEVEL ONE ENTERTAINMENT, 
// Licensed under the terms of LGPL.
//:---------------------------------------------------------------------------
//:Description
//
// LOW LEVEL QUEUE_LIST TEMPLATE HEADERFILE
//

#ifndef _LLQUEUE_LIST_TMPL_H
#define _LLQUEUE_LIST_TMPL_H

#include "llqueue_list.h"

namespace llqueue {


template<typename T> class CListNode;
template<typename T> class CList;

/*
 * Double Linked List Node Template
 * Template Argument ist der Node Inhalt (m_Data)
 */

template<typename T>
class CListNode: private queue_listnode
{
public:
    T m_Data;		// The content carried by this node:

    CListNode();	// Default constructor.
    CListNode(const T &Data);	// Constructor initializing the content.
    CListNode(const CListNode<T> &Node);// Copy constructor, which copies the content.
    ~CListNode();	// Destructor. The node is extracted from the list automatically if necessary.

    CListNode<T> &operator=(const CListNode<T> &Node);// Assignment operator, which assigns the content.
    CListNode<T> *GetPrev() const;// Get the previous node.
    CListNode<T> *GetNext() const;// Get the next node.
    CList<T> *GetBase() const;// Get the node owning this list.

    bool IsInserted() const;// Is this node part of a list?

    // Extract this node from the list.
    // Then the node is not part of the list any more.
    // Note that this method does not destroy the node.
    // If you both want to destroy the node and extract it from the list,
    // use the delete.
    void Extract();

private:
    friend class CList<T>;
};


/*
 * An intrusive list. 
 * The template argument is the content carried by the node 
 * in CListNode::m_Data.
 *
 * Important! 
 * A list CList does not own its nodes.
 * Thus, if you insert a node into a list, the list does not copy
 * or take over ownership of the node.
 * 
 * If the node is destroyed, it is automatically also extracted
 * from the list.
 * If the list is destroyed, all its nodes are extracted out of the list,
 * but not destroyed.
 * If you want to free all nodes, use CList::DeleteAll.
 *
 * A list has similar properties like a tree,
 *
 * CList is primary designed for performance critical 
 * low-level code. The user has to allocate, manage and deallocate
 * the list nodes explicitely.
 * For a more high-level container template class, see CArray.
 *
 * The entries of a list can be enumerated by a loop like the following:
 * {
 *      void HandleEachValue(CList<T> *List)
 *      {
 *          CList<T>::CNode *Node;
 *          for(Node = List->GetFirst(); Node; Node = Node->GetNext())
 *              HandleValue(Node->m_Data);
 *      }
 * }
 * Warning! As long as such a loop is active, you should ensure
 * that the list is not modified to avoid illegal node pointers.
 *
 *
 * Since the user manages the list nodes, they can be managed
 * efficiently by putting them in structures or classes
 * which anyway are existing.
 * For example, it all objects of an type should be registered
 * somewhere, these objects may carry by themself the list node:
 *
 * {
 *      class CMyObj
 *      {
 *      public:
 *          CMyObj() { m_Node.m_Data = this; }
 *          friend class CMyObjManager;
 *      private:
 *          int m_MyData;
 *          CList<CMyObj*>::CNode m_Node;
 *      }
 *
 *      class CMyObjManager
 *      {
 *      public:
 *          CMyObj *CreateMyObj();
 *      private:
 *          CList<CMyObj*> m_List;
 *      }
 *
 *      CMyObj *CMyObjManager::CreateMyObj()
 *      {
 *          CMyObj *MyObj = SYS_NEW CMyObj;
 *          m_List.InsertBack(&MyObj->m_Node);
 *          return MyObj;
 *      }
 * }
 * By this, the manager always has an up-to-date list
 * of all object it has created.
 * But note that the manager is not the owner of these objects.
 * If an object created by @code{CMyObjManager::CreateMyObj} is destroyed 
 * by the user, it also automatically is extracted from the list.
 */

template<typename T>
class CList: private queue_listhead
{
public:

    typedef CListNode<T> CNode;

    CList();
	~CList();

	// retrieve elements and information
    CListNode<T> *GetFirst() const;
	CListNode<T> *GetLast() const;
    bool IsEmpty() const;
    bool Contains(CListNode<T> *Node);
    int GetCount() const;

    // inserting elements
	void InsertFront(CListNode<T> *Node);
    void InsertBack(CListNode<T> *Node);
    void InsertAfter(CListNode<T> *Node, CListNode<T> *Pos);
    void InsertBefore(CListNode<T> *Node, CListNode<T> *Pos);
	void CopyFrom(const CList<T> &Base);
    
	// delete ALL
	void ExtractAll();
    void DeleteAll();

private:
    CList(const CList &List);
    CList &operator=(const CList &List);
};

/*
 *	Implementation
 */
template<typename T>
inline CListNode<T>::CListNode()
{
}

template<typename T>
inline CListNode<T>::CListNode(const T &Con)
: m_Data(Con)
{
}

template<typename T>
inline CListNode<T>::CListNode(const CListNode<T> &Node)
: m_Data(Node.m_Data)
{
}

template<typename T>
inline CListNode<T>::~CListNode()
{
}

template<typename T>
inline CListNode<T> &CListNode<T>::operator=(
                                const CListNode &Node)
{
    m_Data = Node.m_Data;
    return *this;
}

template<typename T>
inline CListNode<T> *CListNode<T>::GetPrev() const 
{ 
    return reinterpret_cast<CListNode<T>*>(queue_listnode::GetPrev());
}

template<typename T>
inline CListNode<T> *CListNode<T>::GetNext() const 
{ 
    return reinterpret_cast<CListNode<T>*>(queue_listnode::GetNext());
}

template<typename T>
inline CList<T> *CListNode<T>::GetBase() const 
{ 
    return reinterpret_cast<CList<T>*>(queue_listnode::GetBase());
}

template<typename T>
inline bool CListNode<T>::IsInserted() const 
{ 
    return queue_listnode::IsInserted();
}

template<typename T>
inline void CListNode<T>::Extract()
{
    queue_listnode::Extract();
}


template<typename T>
inline CList<T>::CList()
{
}

template<typename T>
inline CList<T>::~CList()
{
}

template<typename T>
inline CListNode<T> *CList<T>::GetFirst() const 
{ 
    return reinterpret_cast<CListNode<T>*>(queue_listhead::GetFirst());
}

template<typename T>
inline CListNode<T> *CList<T>::GetLast() const 
{ 
    return reinterpret_cast<CListNode<T>*>(queue_listhead::GetLast());
}

template<typename T>
inline bool CList<T>::IsEmpty() const 
{ 
    return queue_listhead::IsEmpty();
}

template<typename T>
inline bool CList<T>::Contains(CListNode<T> *Node)
{
    return queue_listhead::Contains(Node);
}

template<typename T>
inline int CList<T>::GetCount() const 
{ 
    return queue_listhead::GetCount();
}

template<typename T>
inline void CList<T>::InsertFront(CListNode<T> *Node)
{
    queue_listhead::InsertFront(Node);
}

template<typename T>
inline void CList<T>::InsertBack(CListNode<T> *Node)
{
    queue_listhead::InsertBack(Node);
}

template<typename T>
inline void CList<T>::InsertAfter(CListNode<T> *Node, 
                                    CListNode<T> *Pos)
{
    queue_listhead::InsertAfter(Node, Pos);
}

template<typename T>
inline void CList<T>::InsertBefore(CListNode<T> *Node, 
                                     CListNode<T> *Pos)
{
    queue_listhead::InsertBefore(Node, Pos);
}

template<typename T>
inline void CList<T>::ExtractAll()
{
    queue_listhead::ExtractAll();
}

template<typename T>
void CList<T>::DeleteAll()
{
    while(m_First)
        delete m_First;
}

template<typename T>
void CList<T>::CopyFrom(const CList<T> &Base)
{
    DeleteAll();
    CListNode<T> *Node;
    for(Node = Base.m_First; Node; Node = Node->m_Next)
    {
        CListNode<T> *Copy = new CListNode<T>(*Node);
        InsertBack(Copy);
    }
}

}// namespace ll

#endif // _LLQUEUE_LIST_TMPL_H