See what's going on with flipcode!




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.