lightatdawn




#include <windows.h>//for BOOL
#include <stdio.h> //for printf
#include <time.h> //to seed srand

//------------------------------------------
// ENHANCED LIST:
// Doubly Linked, Templated, Handled, Safe Lists
//------------------------------------------


//------------------------------------------
// Make sure you fully understand the first linked
// list example before proceeding to this one.
//------------------------------------------


//Total number of people created and polled for this example.
const int TOTAL_PEOPLE = 15;

/*
This is the definition for our Data. We'll create our List Handler using
this for the template. It will be explained later on...
*/

struct PERSON
{
BOOL isHappy;
};


/*
Here we have the definition of a single, yet incredibly complex, Node.


You'll also notice that all of the function bodies are defined _inside_
the struct. This method uses what it called inline member functions. Any code
written inline will be expanded by the compiler at every calling point (in
main for this example), as if it had been written there. Look up inline in
your help files if you want to know more.


Another thing is that this is a Doubly Linked List, unlike the first
examples Singly Linked List. This means that there is both a pNext, and a
pPrev (or previous) pointer. That allows us to move either forward or
backward through the list at will. Watch it in action....
*/

template <class TYPE> class NODE
{
public:
NODE()
{
/*
Default constructor. This way the pNext and pPrev pointers are set to
NULL as soon as a NODE object is created. Now we dont have to
do it ourselves every time we create a new NODE! Easier already.
*/

pNext = NULL;
pPrev = NULL;
};

~NODE()
{
/*
The next beautiful feature of this Super-Node. When it goes out of
scope (i.e. End of program for this example.) or when it is deleted or
removed, it looks ahead and behind. If there is a Node ahead of it (pNext),
it takes its pPrev pointer (pNext->pPrev) and points it to the Node before
it. Then it looks behind. If theres a node behind (pPrev), it takes its
pNext pointer (pPrev->pNext) and points it to the Node in front of itself
(pNext). Now the list remains unbroken.
*/

if (pNext != NULL)
pNext->pPrev = pPrev;
if (pPrev != NULL)
pPrev->pNext = pNext;
};

/*
This is the Data that this Node will contain. It is of type TYPE. TYPE is the
templated parameter. When we define a NODE in this example it will look like this:
NODE<PERSON> ANode;
This allow incredible versatility. You could use this same NODE to contain other
data. i.e. "NODE<char *> ANode;" would be a doubly linked list contain a character
pointer. Or you could use your own custom structs, just like we use PERSON. And
all without typing another line of list code.
*/

TYPE Data;

NODE * pNext;
NODE * pPrev;
};


/*
Here we have... *drum roll*... the CListHandler class. This class is written to take
care of the Nodes without fuss. It moves forward, backwards, from start to finish. It
can add and remove nodes on command. Notice the template. When an instance of
CListHandler is created, a template parameter is defined. In this case we used
CListHandler<PERSON> List; CListHandler uses this TYPE parameter to create specific
NODE data types and pointers, allowing CListHandler to be used repeatedly throughout
your code for any number of different Linked Lists. Theres a tear in my eye...
No, really.
*/

template <class TYPE> class CListHandler
{
public:
CListHandler()
{
ActiveNode = NULL;
//Set all values of our default "Safe" data to zero.
ZeroMemory(&SafeData, sizeof(SafeData));
/*
CListHandler contains a public pointer to the currently active nodes
data. Since the Nodes are kept private to avoid tampering, this allows
users to access the current data easily, without allowing full access to
the entire Node. We must reset the Pointer each time the active Node is
changed.
*/

SetDataPointer();
};

~CListHandler()
{
//Automatically clear up all memory when CListHandler goes out of scope
DeleteList();
};

//Deletes all Nodes in the entire list
void DeleteList()
{
if (ActiveNode == NULL)
return;

Reverse();

NODE<TYPE> * RememberNode;

do
{
RememberNode = ActiveNode->pNext;
delete ActiveNode;
ActiveNode = RememberNode;
}while(ActiveNode != NULL);
}

BOOL RemoveNode()
{
/*
As long as there is an ActiveNode to remove, this function deletes it,
resets the ActiveNode pointer to the closest Node, and resets the
CListHandlers data pointer to point to the new Nodes data.
*/

if (ActiveNode == NULL)
return FALSE;

NODE<TYPE> * RememberNode = ActiveNode;

if (RememberNode->pNext != NULL)
RememberNode = RememberNode->pNext;
else
{
//add new node if at end of list
InsertNode();
//update to empty node
RememberNode = ActiveNode;
//go back to old node for removal
ActiveNode = ActiveNode->pPrev;
}

ActiveNode->~NODE();
ActiveNode = RememberNode;

return TRUE;
};

TYPE & AddNode()
{
/*
Easily add a new Node to the position in front of the current Node.
AddNode resets the ActiveNode pointer as well as the pointer to its data,
*/


if (ActiveNode == NULL)
{
ActiveNode = new NODE<TYPE>;
ActiveNode->pNext = NULL;
ActiveNode->pPrev = NULL;
}
else
{
NODE<TYPE> * RememberNode = ActiveNode->pNext;

ActiveNode->pNext = new NODE<TYPE>;
ActiveNode->pNext->pNext = RememberNode;
ActiveNode->pNext->pPrev = ActiveNode;
ActiveNode = ActiveNode->pNext;
}

return ActiveNode->Data;
};

BOOL Reverse()
{
/*
This function ensures that we will only need one pointer for our entire
list. Most doubly linked lists will use three pointers. FirstNode,
EndNode, and CurrentNode. But by giving CListHandler the capacity to
rapidly return to the First Node in the list, we eradicate the need for
additional pointers or calculations.
*/

if (_ActiveNode == NULL)
return FALSE;

if (ActiveNode->pPrev == NULL)
return TRUE;

while (ActiveNode->pPrev != NULL)
{ ActiveNode = ActiveNode->pPrev; };

return TRUE;
};

BOOL End()
{
//Same as Reverse() but this function goes to the last Node in the List
if (_ActiveNode == NULL)
return FALSE;

if (ActiveNode->pNext == NULL)
return TRUE;

while (ActiveNode->pNext != NULL)
{ ActiveNode = ActiveNode->pNext; };

return TRUE;
};

//Checks if List is at end
BOOL isEnd()
{
if (_ActiveNode == NULL)
return FALSE;

if (ActiveNode->pNext == NULL)
return TRUE;
else
return
FALSE;
};

//Checks if List is at start
BOOL isStart()
{
if (_ActiveNode == NULL)
return FALSE;

if (ActiveNode->pPrev == NULL)
return TRUE;
else
return
FALSE;
};

BOOL Next()
{
/*
If there is a Node ahead, move up, else return FALSE and remain on the
last Node. We cant go romping off the end like you could when tracking
the First and Last Nodes. We only have one pointer so if it derails, we
lose all the memory as well as our data.
*/

if (_ActiveNode == NULL)
return FALSE;


if (ActiveNode->pNext != NULL)
{
ActiveNode = ActiveNode->pNext;
SetDataPointer();
return TRUE;
}
else
return
FALSE;
};

BOOL Prev()
{
//I think you can figure this out by now.
if (_ActiveNode == NULL)
return FALSE;

if (ActiveNode->pPrev != NULL)
{
ActiveNode = ActiveNode->pPrev;
SetDataPointer();
return TRUE;
}
else
return
FALSE;
};

//This is our public interface to the ActiveNodes private data. It returns
//the data by reference of type TYPE

TYPE & operator() ()
{
if (_ActiveNode == NULL)
{
//This would be a good place to flag some kind of error checking
//system so this failure wont go unnoticed

ZeroMemory(&_Failed, sizeof(_Failed));
return _Failed;
}

return _ActiveNode->Data;
};

//Checks if a List has been started. Returns TRUE if there is no list
BOOL IsNULL()
{
if (_ActiveNode == NULL)
return TRUE;

return FALSE;
};

private:

/*
This is the pointer to the Active Node. Notice that we pass in the same
parameter for _its_ template parameter as we recieved here. Thats so that
NODE knows what type its Data pointer is going to be.
*/

NODE<TYPE> * ActiveNode;
//Data for returning error value
TYPE _Failed;
};



//------------------------------------------
// MAIN
//------------------------------------------

int main(void)
{
int i;
int HappyPeople;

//Seed the random number generator
srand( (unsigned)time(NULL) );

/*
The first benefit of the CListHandler. Nothingelse to keep track of.
*/

CListHandler<PERSON> List;

/*
Now isn't this easier? We dont have to assign anything to anything else.
We dont have to track First and Last Nodes. All we have to do is keep
calling the AddNode member function and we can safely use the data pointed
to by the CListHandlers NodeData pointer.
*/

i = 0;
do
{
List.AddNode();
List().isHappy = rand() % 2;

i++;
}while(i < TOTAL_PEOPLE);

/*
Now lets poll all the people and see whos happy! Lets start from the
first person. So we call the Reverse() function of the List, and
whammo; first Node. We're there.


We call our Next() function at the end of each loop. If the function
returns false because theres no more nodes, the loop ends. Easy.
*/

HappyPeople = 0;
List.Reverse();
do
{
if (List().isHappy)
HappyPeople ++;
}while(List.Next());

//Woohoo. It appears a disturbingly low number of people are happy.
//Only about half (imagine that). Well, sucks to be them I guess.

printf("Of %i people, %i of them are happy.\n", TOTAL_PEOPLE, HappyPeople);

/*
Now for the next important part. Nothing!!
"But..." you say; "Memory was allocated and it needs to be deallocated or we'll
have nasty memory leaks." Yes, thats true. You know your stuff, obviously. But
our Super-Nodes clean up their own messes. CListHandler goes out of scope now
and calls DeleteList(): swoosh... deallocated automatically. Beaut.
*/


return 0;
}