This section of the archives stores flipcode's complete Developer Toolbox collection, featuring a variety of mini-articles and source code contributions from our readers.

| List/Node Template Class Submitted by

Here I put a simple class of node of a double linked list with a little changue. Instead of storing a pointer to the previous item in the list, it keeps a pointer to the pointer that is referencing the current node.
It works as a simple linked list for iterate, but with the pointer to the pointer that is referencing the current node,we can move the node from a list to other in a very fast and simple way. It's also more flexible, because there's no need to have a previous node in the list, just a pointer to the node, a list is represented just as. TListN *pIntegerList=NULL;
Also it has a diferent way of work than traditional lists, more focused to work with dinamic items that move between different lists.
--> include ListNode.h And here are some examples of code using the class. --> include ListNode.cpp
As ilustrated in the Example2, i's thought to be used in objects as lights, or items in a game/engine, that are frequently changuing from one node of an space partition tree to other node.
It could be done with simple lists, but in that way, we don't have to care about the previous list where the item was, we don't have to do things like :

        previousNode-Items.Delete( curItem );
        curNode-Items.Add( curItem );

We just insert the current item in the new list, and don't care about the old list.

        curItem.InsertTo( &curNode-Items );

It's more focused in nodes than in lists. A little different way of thinking, that gives more importance to nodes, where the real datas are :-).
Alberto García-Baquero Vega
Nébula Entertainment (wisefox@jet.es)

Currently browsing [listnode.zip] (3,234 bytes) - [ListNode.h] - (6,389 bytes)

    #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__

Currently browsing [listnode.zip] (3,234 bytes) - [ListNode.cpp] - (4,438 bytes)

    #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();
    }

The zip file viewer built into the Developer Toolbox made use of the zlib library, as well as the zlibdll source additions.

Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.