/*********************************************************************
 * This file is part of the cpplibs suite.
 *
 * Copyright (C) 2001 Topi Mäenpää
 * All rights reserved.
 *
 * This program is free software. You can redistribute and/or modify
 * it under the terms of the free software licence found in the
 * accompanying file "COPYING". The licence terms must always be
 * redistributed with this source file. The above copyright notice
 * must be reproduced in all modified and unmodified copies of this
 * source file.
 *
 * $Revision: 1.4 $
 *********************************************************************/

#ifndef _TREE_H
#define _TREE_H

#include "List.h"

namespace util
{
	/**
	 * Tree represents a node in a tree data structure. A tree may have
	 * any number of children and a single parent.
	 **/
	template <class T> class Tree : virtual public Object
	{
	public:
		/**
		 * Create an empty tree node.
		 **/
		Tree() : _pParent(NULL) {}
		/**
		 * Create a tree node with the given data.
		 **/
		Tree(const T& d) : data(d), _pParent(NULL) {}
		/**
		 * Copy a tree node. Only the contents are copied. If you want to
		 * perform a deep copy of a tree, you must do it manually.
		 **/
		Tree(const Tree& other) : data(other.data), _pParent(NULL) {}
		/**
		 * Copy a tree node. Only the contents are copied. If you want to
		 * perform a deep copy of a tree, you must do it manually.
		 **/
		Tree& operator= (const Tree& other);

		/**
		 * Destroy a tree and all of its children.
		 **/
		virtual ~Tree();

		/**
		 * Remove a child node from this node. The parent of the removed
		 * child is set to NULL.
		 **/
		virtual void removeChild(Tree* child) { _plstChildren -= child; child->setParent(NULL); }
		/**
		 * Add a child to the end of child node list and update the parent
		 * pointer in child.
		 **/
		virtual void addChild(Tree* child) { _plstChildren += child; child->setParent(this); }

		/**
		 * Get the children of this node in insertion order.
		 **/
		List<Tree*> getChildren() const { return _plstChildren; }
		/**
		 * Get the children of this node in insertion order.
		 **/
		const List<Tree*>& children() const { return _plstChildren; }
		/**
		 * Get the children of this node in insertion order.
		 **/
		List<Tree*>& children() { return _plstChildren; }

		/**
		 * Set the parent node.
		 **/
		void setParent(Tree* parent) { _pParent = parent; }
		/**
		 * Get the parent node.
		 *
		 * @return parent node or NULL, if there is no parent
		 **/
		Tree* getParent() const { return _pParent; }

		/**
		 * The data contained in this node.
		 **/
		T data;

	protected:
		/**
		 * A list of child nodes.
		 **/
		List<Tree*> _plstChildren;
		/**
		 * A pointer to the parent node.
		 **/
		Tree* _pParent;
	};

	template <class T> Tree<T>::~Tree()
	{
		for (int i=_plstChildren.getLength();i--;)
			delete _plstChildren[i];
	}

	template <class T> Tree<T>& Tree<T>::operator= (const Tree<T>& other)
	{
		for (int i=_plstChildren.getLength();i--;)
			delete _plstChildren[i];
		_pParent = NULL;
		data = other.data;
		return *this;
	}
}

#endif