// Node form for the family tree

template <typename Etype>
class Tnode
{
	public:
		Etype			info;			// The data
		Tnode<Etype>	*firstchild;	// Points to first child (left)
		Tnode<Etype>	*sibling;		// Points to a sibling (right)
		Tnode<Etype>	*parents;		// Points to the parents (up)

		Tnode () : firstchild(NULL), sibling(NULL), parents(NULL)
		{ }
		Tnode (const Etype & one) :
			info(one), firstchild(NULL), sibling(NULL), parents(NULL)
		{	}
};

// Template class for a family tree

template <typename Etype>
class FTree
{
	private:
		Tnode<Etype>	*root;				// Pointer to root node

		void VisitAndDestroy(Tnode<Etype> *);	// To erase subtree
		FTree(const FTree &);					// Make copy constructor
	public:										//  inaccessible
		class iterator;
		FTree();								// Create empty tree
		FTree (const Etype &);					// Make single node tree
		~FTree ();								// Destroy tree
		bool empty () const;					// Test for empty
		iterator begin() const;					// Set iterator to root
		iterator end() const;					// Make iterator invalid
		iterator  insertL(iterator &, Etype &);	// Add firstchild node
		iterator  insertR(iterator &, Etype &);	// Add sibling node
		void erase (iterator &);				// Erase descendants

		
	class iterator								// Nested iterator
	{
		private:
			Tnode<Etype>		* current;		// Pointer to tree node

			iterator (Tnode<Etype> * where)	// Make iterator point to a node 
			{
				current = where;
			}
		public:
			friend class FTree<Etype>;			// Set relationship to tree
												// Make iterator for client
			iterator(): current(NULL) 
			{ };
												// Compare iterators for =
			bool operator == (iterator & rhs)
			{
				return	current == rhs.current;
			}
												// Compare iterators for !=
			bool operator != (iterator & rhs)
			{
				return current != rhs.current;
			}
												// Return reference to the
			Etype & operator* ()				//  data in the node
			{
				if (current == NULL)
					throw logic_error ("Invalid dereference: *");
				return current->info;
			}
												// Return pointer to the
			Etype * operator-> ()				//  data in the node
			{
				if (current == NULL)
					throw logic_error ("Invalid dereference: ->");
				return &(current->info);
			}
												// Return iterator referencing
			iterator DownFirst ()				//  firstchild node
			{
				if (current == NULL)
					throw logic_error ("Invalid dereference: DownFirst");
				return iterator(current->firstchild); 
			}
												// Return iterator referencing
			iterator DownSibling ()				//  next sibling node
			{
				if (current == NULL)
					throw logic_error ("Invalid dereference: DownSibling");
				return iterator(current->sibling); 
			}
												// Return iterator referencing
			iterator Up ()						//  parents node
			{
				if (current == NULL)
					throw logic_error ("Invalid dereference: Up");
				return iterator(current->parents); 
			}
	};
};

// Recursive function to visit all nodes in subtree rooted
//  at start and delete each node

template <typename Etype>
void FTree<Etype>::VisitAndDestroy(Tnode<Etype> *start)
{
	if (start == NULL) return;
	else {
		VisitAndDestroy (start->firstchild);
		VisitAndDestroy (start->sibling);
		delete start;
	}
}
									// Build empty tree
template <typename Etype>
FTree<Etype>::FTree (void)
{
	root = NULL;
}
									// Build tree with root only
template <typename Etype>
FTree<Etype>::FTree (const Etype & one)
{
	root = new Tnode<Etype>(one);
}
									// Destroy whole tree
template <typename Etype>
FTree<Etype>::~FTree (void)
{
	VisitAndDestroy (root);
	root = NULL;
}
									// Test for empty tree
template <typename Etype>
bool FTree<Etype>::empty () const
{
	return root == NULL;
}
									// Return iterator pointing to root 
template <typename Etype>
FTree<Etype>::iterator FTree<Etype>::begin () const
{
	return FTree<Etype>::iterator(root);
}
									// Return iterator referencing NULL
template <typename Etype>
FTree<Etype>::iterator FTree<Etype>::end () const
{
	return FTree<Etype>::iterator();
}
									// Insert left child (firstchild) node
template <typename Etype>
FTree<Etype>::iterator  FTree<Etype>::insertL	// Return iterator ref new node
		(FTree<Etype>::iterator & where,		// Iterator to parent
		Etype & one)							// Data
{
	Tnode<Etype>	* add;
	Tnode<Etype>	* was;

	was = where.current;
	add = new Tnode<Etype>(one);	// Create node with data
	if (was != NULL)				// Fill in pointers
	{
		add->firstchild = was->firstchild;
		add->parents = was;
		was->firstchild = add;
	}
	else							// Special case for making the root
	{
		add->firstchild = add->sibling = add->parents = NULL;
		root = add;
	}
	return FTree<Etype>::iterator(add); 	// Return iterator to new node
}
									// Insert right child (sibling) node
template <typename Etype>
FTree<Etype>::iterator  FTree<Etype>::insertR	// Return iterator ref new node
		(FTree<Etype>::iterator & where,		// Iterator to parent node
		Etype & one)							// Data to add
{
	Tnode<Etype>	* add;
	Tnode<Etype>	* was;

	was = where.current;
	if (was == NULL)
		throw logic_error ("Can't attach to an invalid iterator position");
	add = new Tnode<Etype>(one);	// Make new node with data
	add->sibling = was->sibling;	// Fill in pointers
	add->parents = was->parents;
	was->sibling = add;
	return FTree<Etype>::iterator(add);		// Return iterator to new node
}
									// Erase descendants from start
template <typename Etype>
void FTree<Etype>::erase (FTree<Etype>::iterator & start)
{
	Tnode<Etype>	* other;

	if (start.current == NULL)		// Make sure start is valid
		throw logic_error ("Can't erase; tree is empty or iterator invalid");
	other = start.current->parents;				// Locate parents
	if (other != NULL)
	{
		if (start.current == other->firstchild)	// If start if first child
			other->firstchild = start.current->sibling;	// Disconnect it
		else
		{
			other = other->firstchild;
			while (other->sibling != start.current)	// Find which sibling start is
				other = other->sibling;
			other->sibling = start.current->sibling;// Disconnect it
		}
		start.current->sibling = NULL;
	}
	VisitAndDestroy(start.current);				// Clear subtree
	start = FTree<Etype>::iterator();			// Invalidate iterator
}