/*
  File: include/basic/List.h
  Description: A linked list class.
  Part of the Mantis project
  (c) 2002 Lycos Inc.
  Author(s): Andrew McCann

  This file is distributed for the sole purpose of allowing you to write
  software to interface with Sonique 2 and other Mantis programs. It is
  not to be modified or used for any other purpose without written
  authorization.

  If you redistribute this file, it must be in the original package
  complete with all other files provided, including the usage agreement.

  Do not remove this notice.
*/

#ifndef _LIST_H__
#define _LIST_H__

#ifdef DEBUG_INCLUDE_ORDER
#pragma message("Including " __FILE__ "\n" )
#endif

#if _MSC_VER > 1000
#pragma once
#endif

#include "typesport.h"

/* NV - already defined and I don't know where from!*/
struct	__POSITION { };
typedef __POSITION* POSITION;



template< class TYPE >
class DefaultListNode
{
public:
	DefaultListNode<TYPE>*  pNext;
	DefaultListNode<TYPE>*  pPrev;
	TYPE					data;
};


#pragma warning (push)
#pragma warning (disable: 4786)		//debug warning, type name exceeds 255 chars

template<class TYPE, class ARG_TYPE, class NODETYPE = DefaultListNode<TYPE> > 
class List  
{
protected:

	NODETYPE* m_pNodeHead;
	NODETYPE* m_pNodeTail;
	uint32   m_nCount;
	NODETYPE* m_pNodeFree;
	

	NODETYPE* NewNode(NODETYPE*, NODETYPE*);
	void FreeNode(NODETYPE*);
	static void DeleteNode(NODETYPE* pNode){ delete pNode; }

public:

	// peek at head or tail
	TYPE& GetHead();
	TYPE GetHead() const;
	TYPE& GetTail();
	TYPE GetTail() const;

	// get head or tail (and remove it) - don't call on empty list !
	TYPE RemoveHead();
	TYPE RemoveTail();

	// add before head or after tail
	POSITION AddHead(ARG_TYPE newElement);
	POSITION AddTail(ARG_TYPE newElement);

	// add another list of elements before head or after tail
	void AddHead(const List* pNewList);
	void AddTail(const List* pNewList);

	POSITION AddHead();
	POSITION AddTail();

	// remove all elements
	void RemoveAll();

	// iteration
	POSITION GetHeadPosition() const;
	POSITION GetTailPosition() const;
	TYPE& GetNext(POSITION& rPosition); // return *Position++
	TYPE GetNext(POSITION& rPosition) const; // return *Position++
	TYPE& GetPrev(POSITION& rPosition); // return *Position--
	TYPE GetPrev(POSITION& rPosition) const; // return *Position--

	// getting/modifying an element at a given position
	TYPE& GetAt(POSITION position);
	TYPE GetAt(POSITION position) const;
	void SetAt(POSITION pos, ARG_TYPE newElement);
	void RemoveAt(POSITION position);

	// inserting before or after a given position
	POSITION InsertBefore(POSITION position, ARG_TYPE newElement);
	POSITION InsertAfter(POSITION position, ARG_TYPE newElement);

	// helper functions (note: O(n) speed)
	POSITION Find(ARG_TYPE searchValue, POSITION startAfter = NULL) const;
		// defaults to starting at the HEAD, return NULL if not found
	POSITION FindIndex(uint32 nIndex) const;
		// get the 'nIndex'th element (may return NULL)

	uint32 GetCount() const;
	bool IsEmpty() const;

	List();
	virtual ~List();

	List& operator=( const List& other);

	
};
#pragma warning (pop)

template<class TYPE, class ARG_TYPE, class NODETYPE  > 
List<TYPE, ARG_TYPE, NODETYPE>& List<TYPE, ARG_TYPE, NODETYPE>::operator=( const List<TYPE, ARG_TYPE, NODETYPE>& other)
{
	RemoveAll();
	AddHead( &other );
	return *this;
}


template<class TYPE, class ARG_TYPE, class NODETYPE  > 
List<TYPE, ARG_TYPE, NODETYPE>::List()
{
	m_nCount = 0;
	m_pNodeHead = m_pNodeTail = m_pNodeFree = NULL;

}
template<class TYPE, class ARG_TYPE, class NODETYPE  > 
List<TYPE, ARG_TYPE, NODETYPE>::~List()
{
	RemoveAll();
}
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline uint32 List<TYPE, ARG_TYPE, NODETYPE>::GetCount() const
	{ return m_nCount; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline bool List<TYPE, ARG_TYPE, NODETYPE>::IsEmpty() const
	{ return m_nCount == 0; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline TYPE& List<TYPE, ARG_TYPE, NODETYPE>::GetHead()
	{ 	return m_pNodeHead->data; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline TYPE List<TYPE, ARG_TYPE, NODETYPE>::GetHead() const
	{ 	return m_pNodeHead->data; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline TYPE& List<TYPE, ARG_TYPE, NODETYPE>::GetTail()
	{ 	return m_pNodeTail->data; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline TYPE List<TYPE, ARG_TYPE, NODETYPE>::GetTail() const
	{ 	return m_pNodeTail->data; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline POSITION List<TYPE, ARG_TYPE, NODETYPE>::GetHeadPosition() const
	{ return (POSITION) m_pNodeHead; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline POSITION List<TYPE, ARG_TYPE, NODETYPE>::GetTailPosition() const
	{ return (POSITION) m_pNodeTail; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline TYPE& List<TYPE, ARG_TYPE, NODETYPE>::GetNext(POSITION& rPosition) // return *Position++
	{ NODETYPE* pNode = (NODETYPE*) rPosition;
	  rPosition = (POSITION) pNode->pNext;
	  return pNode->data; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline TYPE List<TYPE, ARG_TYPE, NODETYPE>::GetNext(POSITION& rPosition) const // return *Position++
	{ NODETYPE* pNode = (NODETYPE*) rPosition;
	  rPosition = (POSITION) pNode->pNext;
	  return pNode->data; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline TYPE& List<TYPE, ARG_TYPE, NODETYPE>::GetPrev(POSITION& rPosition) // return *Position--
	{ NODETYPE* pNode = (NODETYPE*) rPosition;
	  rPosition = (POSITION) pNode->pPrev;
	  return pNode->data; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline TYPE List<TYPE, ARG_TYPE, NODETYPE>::GetPrev(POSITION& rPosition) const // return *Position--
	{ NODETYPE* pNode = (NODETYPE*) rPosition;
	  rPosition = (POSITION) pNode->pPrev;
	  return pNode->data; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline TYPE& List<TYPE, ARG_TYPE, NODETYPE>::GetAt(POSITION position)
	{ NODETYPE* pNode = (NODETYPE*) position;
	  return pNode->data; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline TYPE List<TYPE, ARG_TYPE, NODETYPE>::GetAt(POSITION position) const
	{ NODETYPE* pNode = (NODETYPE*) position;
	  return pNode->data; }
template<class TYPE, class ARG_TYPE, class NODETYPE  >
inline void List<TYPE, ARG_TYPE, NODETYPE>::SetAt(POSITION pos, ARG_TYPE newElement)
	{ NODETYPE* pNode = (NODETYPE*) pos;
	  pNode->data = newElement; }


template<class TYPE, class ARG_TYPE, class NODETYPE  >

NODETYPE* List<TYPE, ARG_TYPE, NODETYPE>::NewNode(NODETYPE* pPrev, NODETYPE* pNext)
{
	NODETYPE *TempNode;
	if( m_pNodeFree )
	{
		TempNode = m_pNodeFree;
		if( m_pNodeFree->pNext )
			m_pNodeFree = m_pNodeFree->pNext;
		else
			m_pNodeFree = NULL;
	}
	else
	{
		TempNode = new NODETYPE;
	}

	TempNode->pNext = pNext;
	TempNode->pPrev = pPrev;

	m_nCount++;
	return TempNode;
}

template<class TYPE, class ARG_TYPE, class NODETYPE  >
void List<TYPE, ARG_TYPE, NODETYPE>::FreeNode(NODETYPE* pNode)
{
	pNode->pNext = m_pNodeFree;
	m_pNodeFree  = pNode;
		
	//delete pNode;
	m_nCount--;
}

template<class TYPE, class ARG_TYPE, class NODETYPE  >
POSITION List<TYPE, ARG_TYPE, NODETYPE>::AddHead(ARG_TYPE newElement)
{
	NODETYPE* pNewNode = NewNode(NULL, m_pNodeHead);
	pNewNode->data = newElement;
	if (m_pNodeHead != NULL)
		m_pNodeHead->pPrev = pNewNode;
	else
		m_pNodeTail = pNewNode;
	m_pNodeHead = pNewNode;
	return (POSITION) pNewNode;
}

template<class TYPE, class ARG_TYPE, class NODETYPE  >
POSITION List<TYPE, ARG_TYPE, NODETYPE>::AddTail(ARG_TYPE newElement)
{
	NODETYPE* pNewNode = NewNode(m_pNodeTail, NULL);
	pNewNode->data = newElement;
	if (m_pNodeTail != NULL)
		m_pNodeTail->pNext = pNewNode;
	else
		m_pNodeHead = pNewNode;
	m_pNodeTail = pNewNode;
	return (POSITION) pNewNode;
}

// grow the list, and return the newly added element
template<class TYPE, class ARG_TYPE, class NODETYPE  >
POSITION List<TYPE, ARG_TYPE, NODETYPE>::AddHead()
{
	NODETYPE* pNewNode = NewNode(NULL, m_pNodeHead);
	if (m_pNodeHead != NULL)
		m_pNodeHead->pPrev = pNewNode;
	else
		m_pNodeTail = pNewNode;
	m_pNodeHead = pNewNode;

	return (POSITION) pNewNode;
}
template<class TYPE, class ARG_TYPE, class NODETYPE  >
POSITION List<TYPE, ARG_TYPE, NODETYPE>::AddTail()
{
	NODETYPE* pNewNode = NewNode(m_pNodeTail, NULL);

	if (m_pNodeTail != NULL)
		m_pNodeTail->pNext = pNewNode;
	else
		m_pNodeHead = pNewNode;
	m_pNodeTail = pNewNode;
	
	return (POSITION) pNewNode;
}

template<class TYPE, class ARG_TYPE, class NODETYPE  >
void List<TYPE, ARG_TYPE, NODETYPE>::AddHead( const List* pNewList)
{
	// add a list of same elements to head (maintain order)
	POSITION pos = pNewList->GetTailPosition();
	while (pos != NULL)
		AddHead(pNewList->GetPrev(pos));
}

template<class TYPE, class ARG_TYPE, class NODETYPE  >
void List<TYPE, ARG_TYPE, NODETYPE>::AddTail( const List* pNewList)
{
	// add a list of same elements
	POSITION pos = pNewList->GetHeadPosition();
	while (pos != NULL)
		AddTail(pNewList->GetNext(pos));
}

template<class TYPE, class ARG_TYPE, class NODETYPE  >
TYPE List<TYPE, ARG_TYPE, NODETYPE>::RemoveHead()
{
	NODETYPE* pOldNode = m_pNodeHead;
	TYPE returnValue = pOldNode->data;

	m_pNodeHead = pOldNode->pNext;
	if (m_pNodeHead != NULL)
		m_pNodeHead->pPrev = NULL;
	else
		m_pNodeTail = NULL;
	FreeNode(pOldNode);
	return returnValue;
}

template<class TYPE, class ARG_TYPE, class NODETYPE  >
TYPE List<TYPE, ARG_TYPE, NODETYPE>::RemoveTail()
{
	NODETYPE* pOldNode = m_pNodeTail;
	TYPE returnValue = pOldNode->data;

	m_pNodeTail = pOldNode->pPrev;
	if (m_pNodeTail != NULL)
		m_pNodeTail->pNext = NULL;
	else
		m_pNodeHead = NULL;
	FreeNode(pOldNode);
	return returnValue;
}


template<class TYPE, class ARG_TYPE, class NODETYPE  >
void List<TYPE, ARG_TYPE, NODETYPE>::RemoveAll()
{

	// remove all the nodes
	NODETYPE* pOldNode;
	while( m_pNodeHead )
	{
		pOldNode  = m_pNodeHead;
		m_pNodeHead = m_pNodeHead->pNext;

		if (m_pNodeHead != NULL)
			m_pNodeHead->pPrev = NULL;
		else
			m_pNodeTail = NULL;

		FreeNode(pOldNode);
	}

	while( m_pNodeFree )
	{
		NODETYPE* pTemp = m_pNodeFree;
		m_pNodeFree = m_pNodeFree->pNext;

		DeleteNode( pTemp );
	}
}

template<class TYPE, class ARG_TYPE, class NODETYPE  >
POSITION List<TYPE, ARG_TYPE, NODETYPE>::InsertBefore(POSITION position, ARG_TYPE newElement)
{

	if (position == NULL)
		return AddHead(newElement); // insert before nothing -> head of the list

	// Insert it before position
	NODETYPE* pOldNode = (NODETYPE*) position;
	NODETYPE* pNewNode = NewNode(pOldNode->pPrev, pOldNode);
	pNewNode->data = newElement;

	if (pOldNode->pPrev != NULL)
	{
		pOldNode->pPrev->pNext = pNewNode;
	}
	else
	{
		m_pNodeHead = pNewNode;
	}
	pOldNode->pPrev = pNewNode;
	return (POSITION) pNewNode;
}

template<class TYPE, class ARG_TYPE, class NODETYPE  >
POSITION List<TYPE, ARG_TYPE, NODETYPE>::InsertAfter(POSITION position, ARG_TYPE newElement)
{

	if (position == NULL)
		return AddTail(newElement); // insert after nothing -> tail of the list

	// Insert it before position
	NODETYPE* pOldNode = (NODETYPE*) position;
	NODETYPE* pNewNode = NewNode(pOldNode, pOldNode->pNext);
	pNewNode->data = newElement;

	if (pOldNode->pNext != NULL)
	{
		pOldNode->pNext->pPrev = pNewNode;
	}
	else
	{
		m_pNodeTail = pNewNode;
	}
	pOldNode->pNext = pNewNode;
	return (POSITION) pNewNode;
}

template<class TYPE, class ARG_TYPE, class NODETYPE  >
void List<TYPE, ARG_TYPE, NODETYPE>::RemoveAt(POSITION position)
{
	NODETYPE* pOldNode = (NODETYPE*) position;

	// remove pOldNode from list
	if (pOldNode == m_pNodeHead)
	{
		m_pNodeHead = pOldNode->pNext;
	}
	else
	{
		pOldNode->pPrev->pNext = pOldNode->pNext;
	}
	if (pOldNode == m_pNodeTail)
	{
		m_pNodeTail = pOldNode->pPrev;
	}
	else
	{
		pOldNode->pNext->pPrev = pOldNode->pPrev;
	}
	FreeNode(pOldNode);
}

template<class TYPE, class ARG_TYPE, class NODETYPE  >
POSITION List<TYPE, ARG_TYPE, NODETYPE>::FindIndex(uint32 nIndex) const
{
	if (nIndex >= m_nCount)
		return NULL;  // went too far

	NODETYPE* pNode = m_pNodeHead;
	while (nIndex--)
	{
		pNode = pNode->pNext;
	}
	return (POSITION) pNode;
}

template<class TYPE, class ARG_TYPE, class NODETYPE  >
POSITION List<TYPE, ARG_TYPE, NODETYPE>::Find(ARG_TYPE searchValue, POSITION startAfter) const
{
	if( startAfter == NULL )
		startAfter = GetHeadPosition();

	while( startAfter )
	{
		if( GetAt(startAfter) == searchValue )
			return startAfter;

		GetNext(startAfter);
	}

	return NULL;
}


template< class TYPE, class ARG_TYPE, class NODETYPE> class ListTree;

template< class TYPE, class ARG_TYPE>
class ListTree_Node
{
public:
	ListTree_Node							*pNext;
	ListTree_Node							*pPrev;
	ListTree<TYPE,ARG_TYPE,ListTree_Node>	*pSubList;
	TYPE									data;

	ListTree_Node()
	{
		pSubList = NULL;
	}
	~ListTree_Node()
	{
		delete pSubList;
	}
};


template< class TYPE, class ARG_TYPE = TYPE&, class NODETYPE = ListTree_Node<TYPE,ARG_TYPE> > 
class ListTree : public List<TYPE,ARG_TYPE,NODETYPE>
{
protected:
	ListTree<TYPE,ARG_TYPE,NODETYPE>* 	 m_pParentList;

	ListTree*	NewSubList(ListTree* pList)
	{
		return new ListTree(pList);
	}
public:
	ListTree( ListTree* pList = NULL )
	{
		m_pParentList = pList;
	}

	~ListTree()
	{

	}
	
	ListTree<TYPE,ARG_TYPE,NODETYPE>* GetParentList()
	{
		return (ListTree<TYPE,ARG_TYPE,NODETYPE>*) m_pParentList;
	}

	ListTree<TYPE,ARG_TYPE,NODETYPE>* GetSubListAt(POSITION position)
	{ 
		ASSERT(position);
		NODETYPE* pNode = (NODETYPE*) position;

		if( !pNode->pSubList )
			pNode->pSubList = NewSubList(this);

		return (ListTree<TYPE,ARG_TYPE,NODETYPE>*) pNode->pSubList; 
	}

	ListTree<TYPE,ARG_TYPE,NODETYPE>* GetTailSubList()
	{
		return GetSubListAt(GetTailPosition());
	}

	uint32	GetSubListCount( POSITION pos )
	{
		ASSERT(pos);
		NODETYPE* pNode = (NODETYPE*) pos;

		if( pNode->pSubList )
			return ((ListTree<TYPE,ARG_TYPE,NODETYPE>*)pNode->pSubList)->GetCount();
		else
			return 0;
	}

};

/*
#ifndef NOBUILD_RES_LIST

#include "ResourceCache.h"

template <class TYPE, class ARG_TYPE, class NODETYPE = DefaultListNode<TYPE>, int PageSize = 100, bool bConstructCacheNodes  = true >
class ResCacheList : 
	public List<TYPE,ARG_TYPE,NODETYPE>,
	public ResourceCache<NODETYPE,PageSize,bConstructCacheNodes>
{
protected:
	NODETYPE* NewNode(NODETYPE* pPrev, NODETYPE* pNext)
	{
		NODETYPE *TempNode;
		TempNode = GetNew();
		
		TempNode->pNext = pNext;
		TempNode->pPrev = pPrev;

		m_nCount++;
		return TempNode;
	}

	void FreeNode(NODETYPE* pNode)
	{
		Return(pNode);
		m_nCount--;
	}

	void DeleteNode()
	{
	}

public:
	
#ifdef _DEBUG
	ResCacheList(char* szName ) : ResourceCache<NODETYPE,PageSize,bConstructCacheNodes>( szName ) {};
#endif

};

#endif 
*/


#endif 

