Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Chimaera

Check this out

This topic is 5656 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m trying to implement a doubly linked list for my upcoming engine. Since it''s going to be the key to my organization, I''d like to make sure there are no kinks in it before I start trying to add features. I''d hate to run into unnecessary problems later on. So, this is where I was hoping a few other people could read over my code and point out my (inevitable) mistakes. I''ll admit beforehand that this was inspired by open source code and although I''ve taken the time to read and understand all the workings and rewrite (not copy-and-paste) it, it may not be perfect. Please be gentle I''m not trying to push anyone into reading or rewriting my code, I would just appreciate some advice and for anyone who notices a problem to point it out to me. If you have something personal you''d like to say: go here. (Please realize i was never very good with pointers)
  
class CNode
{

	//-----------------------------------------------------

	// members

	//-----------------------------------------------------


	public:
	  
		CNode *pParent;
		CNode *pChild;
		CNode *pPrev;
		CNode *pNext;


	//-----------------------------------------------------

	// member functions

	//-----------------------------------------------------


	public:

		bool HasParent()
		{
			if(pParent != NULL)
				return TRUE;
			else
				return FALSE;

		} // end HasParent


		bool HasChild()
		{
			if(pChild != NULL)
				return TRUE;
			else
				return FALSE;

		} // end HasChild


		CNode * FindRoot()	{ return(pParent ? pParent->FindRoot() : this); }

	public:

		void Attach(CNode *pNewNode);
		void AttachTo(CNode *pNewParent);
		void Detach();

	//-----------------------------------------------------

	// constructors

	//-----------------------------------------------------


	public:

		CNode() : pParent(NULL), pChild(NULL)
		{
			pPrev = pNext = NULL;

		} // end CNode


		CNode(CNode *pAttachNode) : pParent(NULL), pChild(NULL)
		{
			pPrev = pNext = NULL;
			AttachTo(pAttachNode);

		} // end CNode


	//-----------------------------------------------------

	// destructors

	//-----------------------------------------------------


	public:

		virtual ~CNode()
		{
			Detach();
	
			while(pChild)
			{
				delete pChild;
			}
		
		} // end ~CNode

	
};


//---------------------------------------------------------------------------------------------


void CNode::Attach(CNode *pNewNode)
{
	// if new node already has a parent, detach it

	if(pNewNode->HasParent())
		pNewNode->Detach();

	pNewNode->pParent = this;

	// if there''s a child, do lots of re-arranging

	if(pChild)
	{
		CNode *p0	= pChild;
		CNode *p1	= pChild->pPrev;
		CNode *p2	= pNewNode;
		CNode *p3	= pNewNode->pPrev;

		p0->pPrev	= p3;	p3->pNext = p0;
		p1->pNext	= p2;	p2->pPrev = p1;

	}
	else
		// otherwise..

		pChild = pNewNode;

} // end Attach


//---------------------------------------------------------------------------------------------


void CNode::AttachTo(CNode *pNewParent)
{
	// if node already has a parent, detach

	if(this->HasParent())
		Detach();

	pParent = pNewParent;

	// if the new parent has a child, more re-arranging

	if(pParent->HasChild())
	{
		CNode *p0	= pParent->pChild;
		CNode *p1	= pParent->pChild->pPrev;
		CNode *p2	= this;
		CNode *p3	= pPrev;

		p0->pPrev	= p3;	p3->pNext	= p0; 
		p1->pNext	= p2;	p2->pPrev	= p1;
	}
	else
		// otherwise..

		pParent->pChild = this;

} // end AttachTo


//---------------------------------------------------------------------------------------------


void CNode::Detach()
{
	// if this node is the first child of the parent

	// make the parent point to the next child in the list

	if(pParent && (pParent->pChild == this))
		pParent->pChild   = (pNext == NULL) ? NULL : pNext;

	// exclude it from the tree

	pNext->pPrev = NULL;
	pPrev->pNext = NULL;

	pPrev   = NULL;
	pNext   = NULL;
	pParent = NULL;

} // end Detach


//---------------------------------------------------------------------------------------------

  
Thanks for any help in advance. // "Programmers don''t byte, they nibble a bit." // chimaera

Share this post


Link to post
Share on other sites
Advertisement
Although writing a doubly-linked list is fun from a challenge perspective, why don''t you save yourself the time and just use std::list? It probably already has everything and then some that you could possibly be looking for, including iterators. And it has been extensively tested by your compiler writer or an outsource such as RogueWave or STLPort or someone with much more time on their hands than you have to perfect your list, and been corrected of many minor and major flaws. And it will be just as fast as anything you write (with at least 95% certainty).

David

(just briefly looking over your code, you could do things like:

bool HasParent() { return pParent; }
bool HasChild() { return pChild; }

and save yourself some typing!

Also, use ''true'' and ''false'', not ''TRUE'' and ''FALSE''. In other words prefer built-in types, and not typedefs from MS or whoever.

Other than that, a quick glance says it looks clean, but I have never made a doubly-linked list (I did my learning with vectors)

David

Share this post


Link to post
Share on other sites
If you are creating your own list it's a good idea to make it compatible with the standard containers. Then you can make use of all the useful algorithms that come in the standard library. Also you'll be able to swap yours for the standard one to see how they compare without having to change any other code.

Also, just to note, the title of your post isn't very distinctive 'look at this','i've got a problem','check this out','i need help','does anyone know...','I would like comments on my linked list','where can i find help?','what can i do to...' etc.

[edited by - petewood on April 1, 2003 3:03:21 AM]

Share this post


Link to post
Share on other sites
Pete

I’m a little curious in the algorithms in the double liked list, what kind of algorithms are you talking about? A program is an algorithm.

Share this post


Link to post
Share on other sites
quote:
Original post by David ONeil
bool HasParent() { return pParent; }
bool HasChild() { return pChild; }



That causes annoying warnings in MSVC. To eliminate those:


  
bool HasParent () const { return !!pParent; }
bool HasChild () const { return !!pChild; }




Share this post


Link to post
Share on other sites
The c++ standard library comes with containers and algorithms. The algorithms can do all kinds of things such as sort the contents of the container, call a function for each object in the container, call a function for each and put the result into another container, shuffle the order according to some random number generator (that you can supply if you wish)... just to scratch the surface with the simple ones. They mean you'll never have to write a loop again! (or nowhere near as many) so that will be one area that you can eliminate bugs in your code. You just say what you want to be going on whilst looping over all the elements. It could be that it breaks out of the loop when an item is found, or it could be that it skips over elements and only modifys certain ones. Again this is only the beginning. There are many ways to extend and modify the behaviour of the existing algorithms.

It's worth investing time learning to use them and structure your code to make use of them. They're well tested and can let you get on with chasing down your own bugs.

[edited by - petewood on April 1, 2003 5:38:23 AM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!