Handy template for giving a class 'node' tree properties

Useful Tools and Components
1

It’s been a while since i’ve posted anything here, as I’ve been very busy doing non-juce programming! [I’d never have dreamed THAT would be the case, I miss Juce!]

There are loads of cases where it’s handy to have a class act as a ‘node’, where it can hold any number of children of a similar type (e.g. XML). I’m writing a game engine (using Juce for lots of gut-parts and SFML for the main graphics), and I need such a structure in lots of places.

So, to avoid having to either (a) rewrite the same sort of code in lots of places, or (b) use some horrible old-fashioned method involving some external node-type, I wrote a template. And I thought I’d share it here in case it’s handy for anyone else…

It’s not been optimised at all, and it does try to cover-many-bases (by being doubly-linked and holding a parent). Also, there may be one or two bugs, as I’ve yet to extensively test it… but it works so far and may at least give someone some ideas. Basically, it’s likely to change as I use it, but I’ll update it here when it do

Basic use?

class Thing : public xhNode<Thing>
{
};

… yes that’s right - use the class name as the template type in the base. Now your class automatically has the ability to hold children, act as an iterator to its siblings, and access its parent.

Code: xhNode.h

#ifndef _XHNODE_H_
#define _XHNODE_H_

#include "juce_amalgamated.h"

//-----------------------------------------------------------------------------
// Provides an easy way to give a class the ability to hold a tree of itself.
template <class NodeType>
class xhNode
{
public:

	xhNode ()
	{
		lastChild	= NULL;
		firstChild	= NULL;
		next		= NULL;
		prev		= NULL;
		parent		= NULL;
	}

	virtual ~xhNode ()
	{
	}

	void addChild (NodeType* newNode)
	{
		jassert (newNode->next == NULL && newNode->prev == NULL);

		if (newNode->parent)
		{
			DBG (T("Always make sure object is removed from parent"));
			jassertfalse;
			newNode->removeFromParent ();
		}
		if (lastChild)
		{
			jassert (lastChild->next == NULL);

			lastChild->next = newNode;
			newNode->prev = lastChild;
			lastChild = newNode;
		}
		else
		{
			jassert (firstChild == NULL);
			lastChild = newNode;
			firstChild = newNode;
		}
		newNode->onAttach ();
		newNode->parent = dynamic_cast<NodeType*>(this);
	}

	NodeType* getRoot ()
	{
		if (parent) return parent->getRoot();
		else return this;
	}

	NodeType* getParent () const
	{
		return parent;
	}

	NodeType* getFirstChild () const
	{
		return firstChild;
	}

	NodeType* getLastChild () const
	{
		return lastChild;
	}

	NodeType* getNextSibling () const
	{
		return next;
	}

	void removeFromParent ()
	{
		if (parent)
		{
			parent->removeChild (dynamic_cast<NodeType*>(this));
		}
	}

	int containsChild (NodeType* childToFind)
	{
		int count = 0;
		if (firstChild == NULL) return 0;

		NodeType* iterator = firstChild;
		while (iterator)
		{
			if (iterator == childToFind)
			{
				jassert (count == 0);
				return 1;
			}
			else count += iterator->containsChild(childToFind);
			iterator = iterator->next;
		}
		return count;
	}

	void removeChild (NodeType* childToRemove)
	{
		if (childToRemove == firstChild)
		{
			jassert (childToRemove->prev == NULL);
			jassert (childToRemove->parent == this);

			childToRemove->onDetach ();

			childToRemove->parent = NULL;
			firstChild = childToRemove->next;
			if (firstChild == NULL)
			{
				lastChild = NULL;
			}
			else
			{
				firstChild->prev = NULL;
			}
			childToRemove->next = NULL;
		}
		else if (childToRemove == lastChild)
		{
			jassert (childToRemove->next == NULL);
			jassert (childToRemove->parent == this);

			childToRemove->onDetach ();

			childToRemove->parent = NULL;
			lastChild = childToRemove->prev;
			if (lastChild == NULL)
			{
				firstChild = NULL;
			}
			else
			{
				lastChild->next = NULL;
			}
			childToRemove->prev = NULL;
		}
		else
		{
			bool found = false;
			// child may be somewhere inside...
			NodeType* iterator = firstChild;
			while (iterator)
			{
				iterator = iterator->next;
				if (iterator == childToRemove)
				{
					found = true;
					break;
				}
			}
			if (found)
			{
				// unlink from siblings
				jassert (childToRemove->parent == this);
				jassert (childToRemove->next && childToRemove->prev);

				childToRemove->onDetach ();

				childToRemove->prev->next	= childToRemove->next;
				childToRemove->next->prev	= childToRemove->prev;
				childToRemove->parent		= NULL;
				next = NULL;
				prev = NULL;
			}
			else
			{
				// not a child of this node.
			}
		}
	}

	virtual void onAttach ()
	{
	}

	virtual void onDetach ()
	{
	}

private:

	// parent
	NodeType* parent;
	// children...
	NodeType* firstChild;
	NodeType* lastChild;
	// siblings
	NodeType* prev;
	NodeType* next;
};

#endif//_XHNODE_H_