#ifndef __LISTNODE_H__
#define __LISTNODE_H__

#define		ASSERT(x)	assert(x)		// Define it as you want

/*---------------------------------------------------------
**	clase TListNode 
**
**		Class List/Node of list.
**
**		Mostly like a simple double linked list, but 
**		instead of a reference to the previous element,
**		it has a reference to the pointer that point the
**		current element. 
**
**		Each node represent the list that starts in that 
**		node and continues with the next nodes.
**	
**		An empty list is represented by a null pointer.
**		Example:
**					TListNode  *ppList=NULL;
**				Where ppList is an empty list.
**
**		Ideal for items that are moving frequently from
**		a list to other. 
**			By example movile objects that changue from the
**			the list from an space partition node to other 
**			list of a diferent node.
**
**-------------------------------------------------------*/
class TListNode
{
public:
	TListNode	**ppPrev;	// Pointer to the pointer that point us.
	TListNode	 *pNext;	// Pointer to the next node in the list.

public:
	inline	TListNode * Next()  { return pNext; } 

public:
	/*---------------------------------------------------------
	**	AssertValid
	**					Very strong invariant.
	**-------------------------------------------------------*/	
	inline	void	AssertValid()
	{
		#ifdef _DEBUG
			if( pNext != NULL )
			{
				ASSERT( (pNext->ppPrev  == &pNext) );
				ASSERT( pNext != this );
				pNext->AssertValid(); 
			}
			if( ppPrev != NULL )
			{
				ASSERT( ppPrev != &pNext );
				ASSERT( *ppPrev == this  );
			}
		#endif
	}

	/*---------------------------------------------------------
	**	AddTo
	**			Move the list headed by the current node	
	**				to the end of the given list.
	**
	**			Usefull to concatenate list.
	**
	**-------------------------------------------------------*/
	inline	void	AddTo( TListNode **new_ppPrev )
	{
		#ifdef _DEBUG
			AssertValid();
			if( *new_ppPrev != NULL ) (*new_ppPrev)->AssertValid();
		#endif

		//-------------------------------------------------
		//	1º Locate the last element of the given list.
		//-------------------------------------------------
		TListNode **cur_ppPrev = new_ppPrev;
		while( *cur_ppPrev != NULL )
		{
			cur_ppPrev = &((*cur_ppPrev)->pNext);
		}

		//-------------------------------------------------
		//	2º Move the current node to the end of the 
		//		given list.
		//-------------------------------------------------

			//-----------------------------------------------------
			//	2.1 Unlink from previous nodes.
			//-----------------------------------------------------
			if( ppPrev != NULL )
			{
				*ppPrev = NULL;
			}

			//-----------------------------------------------------
			//	2.2 Link after the last element of the given list.
			//-----------------------------------------------------
			ppPrev  = cur_ppPrev;
			*ppPrev = this;

		AssertValid();
	}

	/*---------------------------------------------------------
	**	InsertAt
	**
	**			Inserta el elemento en el puntero pasado.
	**			Enlaza la referencia dada, a la actual y
	**			la actual a la anterior, que tenía.
	**
	**-------------------------------------------------------*/
	inline	void	InsertAt( TListNode **new_ppPrev )
	{
		#ifdef _DEBUG
			ASSERT( new_ppPrev != NULL );
			AssertValid();
			if( *new_ppPrev != NULL ) (*new_ppPrev)->AssertValid();
		#endif	

		//-------------------------------------------------
		//	1º Unlink from previous list.
		//-------------------------------------------------
		Delete();

		//-------------------------------------------------
		//	2º Insert in the given list.
		//-------------------------------------------------
		ASSERT( new_ppPrev!=NULL );
		ASSERT( *new_ppPrev==NULL || (*new_ppPrev)->ppPrev == new_ppPrev );

		// Links current with next node and viceversa.
		pNext		= *new_ppPrev;	// Links current with next.
		if( *new_ppPrev != NULL )	// Links next with current.
			(*new_ppPrev)->ppPrev = &(this->pNext);

		// Links previous with current node and viceversa.
		ppPrev		= new_ppPrev;	// Links current with previous.
		*ppPrev		= this;			// Links previos with current.

		AssertValid();
	}

	/*---------------------------------------------------------
	**	Delete()
	**			Unlink current element, and left the list valid.
	**-------------------------------------------------------*/
	inline	void	Delete()
	{	
		AssertValid();

		if( pNext != NULL )
		{
			pNext->ppPrev = ppPrev;
		}

		if( ppPrev!= NULL )
		{
			*ppPrev = pNext;
			ppPrev  = NULL;
		}
		pNext	= NULL;

		AssertValid();
	}

	/*---------------------------------------------------------
	** Constructor / Destructor
	**-------------------------------------------------------*/
	inline	TListNode() 
	{ 
		ppPrev = NULL;
		pNext  = NULL;
	}
};

/*---------------------------------------------------------
**
**	template class for TListNode.
**
**		Represents a ListNode with elements of type T.
**
**		Adds automatic and easy access typecasting.
**		So you can use TListN<T> as an object of type T.
**
**-------------------------------------------------------*/
template <class T> class TListN : private TListNode
{
private:
	T			   data;
public:
	//
	//	Automatic type casting for transparent access to data.
	//
	inline	T&			   operator()()  { return data;  }		// Easy access cast.
	inline	T&			   Get()         { return data;  }		// Other easy access cast.
	inline	operator	   T&()	         { return data;  }		// Automatic cast.
	inline	TListN<T>    * Next()        { return (TListN<T>*) pNext; } 

	//
	//	Ensures we only add nodes of type T to list of type T.
	//
	inline	void	AddTo(	TListN<T> **new_ppPrev )	{ TListNode::AddTo( (TListNode **)new_ppPrev );		}
	inline	void	InsertAt( TListN<T> **new_ppPrev )	{ TListNode::InsertAt( (TListNode **)new_ppPrev );  }
	inline	void	Delete()							{ TListNode::Delete();								}

	//
	//	Default constructors.
	//
	inline	TListN<T>()				   : data()		{ }		// Default empty constructor.
	inline	TListN<T>( const T &init ) : data(init) { }		// Default copy constructor.
};

template <class T> inline	void	 Advance( TListN<T> *(&pNode) )  { pNode = (TListN<T>*)pNode->Next(); }

#endif // __LISTNODE_H__
 

#include <stdio.h>
#include <conio.h>
#include <assert.h>
#include "ListNode.h"

//--------------------------------------------------------------------------
// Example code
//--------------------------------------------------------------------------

//--------------------------------------------------------------------------
//	Basic example
//--------------------------------------------------------------------------
void Example1()
{
	TListN<int>		*pIterator;
	TListN<int>		*pListA=NULL;	// Empty list A.
	TListN<int>		*pListB=NULL;	// Empty list B.

	TListN<int>		A(10),B(2),C(3),D(4);		// Define datas.

	//	Add elements to list A.
	A.InsertAt( &pListA );				// Link A to list A
	B.InsertAt( &pListA );				// Link B to list A
	
	//	Display the list A
	printf("\n List A :");
	for( pIterator = pListA ; pIterator ; Advance( pIterator ) )
	{	
		printf("%d ", (int)*pIterator ); 
	}

	//	We add listA to listB.
	C.InsertAt( &pListB );				// Link C to list B
	D.InsertAt( &pListB );				// Link D to list B
	pListA->AddTo( &pListB );			// Concatenate listA and listB

	//	Display the list B
	printf("\n List B :");
	pIterator = pListB;
	while( pIterator )
	{
		printf("%d ", (int)*pIterator ); 
		Advance( pIterator );
	}

}

//--------------------------------------------------------------------------
//	Example of lights moving in a hierachial node structure.
//--------------------------------------------------------------------------

// Example definition of a light
typedef	struct	{			
	int		tag;						// tag number of the light.
	float	Pos[3],Color[3],Radius;		// Example datas...	
}	TLight;					

// Example definition of generic space part node.
class	TSNode {
public:
	int				 tag;				// tag number of the node.
	TListN<TLight>	*Lights;			// List of the lights in node.
	TListN<TSNode>	*Sons;				// List of sons of node.
	TSNode()		{ Sons = NULL; Lights = NULL; }
};		


void Example2()
{
	TSNode			Root;			
	TListN<TSNode>	n[10];
	TListN<TLight>	lights[5];		

	//	Names the lights and nodes for output.
	Root.tag	= -1;
	{	for(int i=0;i<10;i++)	n[i]().tag = i;		}
	{	for(int i=0;i< 5;i++)	lights[i]().tag = i;}
													// Build the tree as
													// Root
	n[0].InsertAt( &Root.Sons );					//	+  0
			n[1].InsertAt( &n[0]().Sons );			//	|  +---1
			n[2].InsertAt( &n[0]().Sons );			//	|  +---2
	n[3].InsertAt( &Root.Sons );					//	+--3
	n[4].InsertAt( &Root.Sons );					//	+--4
			n[5].InsertAt( &n[4]().Sons );			//     +---5
				n[6].InsertAt( &n[5]().Sons );		//         +---6
					n[7].InsertAt( &n[6]().Sons );	//         |   +---7
						n[8].InsertAt(&n[7]().Sons);//         |       +---8
				n[9].InsertAt( &n[5]().Sons );		//         +---9

	// Once the tree is created we can attach and move easily lights between nodes.
	// We attach lights
	lights[0].InsertAt( &Root.Lights   );
	lights[1].InsertAt( &n[3]().Lights );
	lights[2].InsertAt( &n[4]().Lights );
	lights[3].InsertAt( &n[4]().Lights );
	lights[4].InsertAt( &n[4]().Lights );

	//---------------------------------------------------------------------
	// Show the tree.
	//---------------------------------------------------------------------
	typedef struct {
		static void ShowTree( TSNode *n , int level )
		{
			// Examples of iterating.
			if( n != NULL )
			{
				// Show node and lights tags,
				{
					printf(" %*s Node %d	Lights-> ", level*2," ", n->tag );
					for( TListN<TLight> *pIt=n->Lights; pIt ; Advance( pIt ) )
						printf(" %d", pIt->Get().tag );
					printf("\n");						
				}
				// Show sons,
				{
					for( TListN<TSNode> *pIt=n->Sons; pIt ; Advance( pIt ) )
						ShowTree( &pIt->Get() , level+1 );
				}
			}
		}
	} local;

	printf("\n-------------\n");
	local::ShowTree( &Root , 0 ); getch();

	// Now we can move as much as we need.
	lights[3].InsertAt( &Root.Lights );		// Move light3 to root.
	lights[1].InsertAt( &Root.Lights );		// Move light1 to root.

	// We can move a complete list from a node to other.
	n[4]().Lights->AddTo( &n[5]().Lights );	// Move all the lights of node 4 to node 5.

	printf("\n-------------\n");
	local::ShowTree( &Root , 0 );
}

//--------------------------------------------------------------------------
//--------------------------------------------------------------------------
void main()
{
	Example1();
	Example2();
	getch();
}