#ifndef __TREE_AMV
	#define __TREE_AMV
/*

This program or library is part of amv::software.

Copyright (C) 1995-2007  Ariel Alonzo Medina Vázquez

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
License as published by the Free Software Foundation; either
version 2.1 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Lesser General Public License for more details.

You should have received a copy of the GNU Lesser General Public
License along with this program; if not, visit
http://www.gnu.org/licenses/lgpl.html
or write to the Free Software Foundation, Inc., 51 Franklin Street,
Fifth Floor, Boston, MA  02110-1301, USA.


Ariel Alonzo Medina Vázquez

ariel_medina21@hotmail.com
http://www.paginasprodigy.com/campechedigital/arielmedina1978
Campeche, Campeche, México

*/

/*
// Árbol con múltiples nodos hijos

Su objetivo es representar una estructura arborescente arbitraria, tal como:

- El árbol sintáctico de una producción de la gramática de un lenguaje de
programación determinado,
- Un mensaje en formato MIME cuyas partes pueden ser a su vez mensajes MIME
y así sucesivamente (o recursivamente),
- Un documento HTML o XML,
- Una base de datos MIB,
-etc.

Esta estructura de datos nos permite crear árboles con N nodos hijos
y M niveles de profundidad. El usuario de la clase es el responsable
de dar forma al árbol mediante la función insert() en el nodo
correspondiente.

El orden de los elementos es conforme al orden de inserción y al punto de
inserción, no se utiliza una función de comparación para insertar los
elementos.

Por lo tanto, no se recomienda su uso si el fin es la inserción ordenada
conforme a un criterio de comparación y la búsqueda rápida de elementos.
En ese caso se recomiendan árboles binarios, AVL o B-Trees.

Los elementos pueden recorrerse al modo de la STL mediante la clase
amv::tree_iterator<amv::tree<type>::node>.

*/
#pragma warning(disable:4786 4503)

#include <iostream>
#include <deque>
#include <algorithm>
#include "amvdefs.h"

using std::deque;

namespace amv	{

template <class type>
class tree	{

	public:

	class node	{
		type object;
		
		node *father;
		deque<node *> childs;
		
		public:
			node(const type &sourceObject, node *pFatherNode=(node *)0):
			object(sourceObject), father(pFatherNode)
				{
				}
			node(const node &n, node *pFatherNode=(node *)0): object(n.object),
			father(pFatherNode)
				{
				for(deque<node *>::const_iterator it=n.childs.begin(); it!=n.childs.end(); ++it)
					childs.push_back(new node(**it,this));
				}

			~node()
				{
				for(deque<node *>::iterator it=childs.begin(); it!=childs.end(); ++it)
					delete *it;
				//Convierte el apuntador del padre a este nodo a 0, de manera que queda
				//un espacio vacío, no podemos eliminar el elemento porque alteramos
				//los iteradores del padre. Usando list tal vez podríamos hacerlo.
				//De tal suerte que si se utiliza el destructor explicitamente, se es
				//responsable de quitar el elemento de childs para evitar referencias
				//a un apuntador nulo.
				if(father)
					*std::find(father->childs.begin(),father->childs.end(),this)=0;
				}

			//Para borrar un nodo, elimina el apuntador del nodo padre a éste
			void deleteNode()
				{
				for(deque<node *>::iterator it=childs.begin(); it!=childs.end(); ++it)
					delete *it;

				if(father)
					father->childs.erase(std::find(father->childs.begin(),father->childs.end(),this));
				}

			node *insert(const type &sourceObject)
				{
				childs.push_back(new node(sourceObject,this));

				return &*childs.back();
				}

			node *find(const type &searchedObject)
				{
				if(object==searchedObject)
					return this;
				else
					{
					node *p=0;
					for(deque<node *>::iterator it=childs.begin(); it!=childs.end(); ++it)
						{//devuelve el primero que encuentra de arriba hacia abajo, de izquierda a derecha
						if(p=(*it)->find(searchedObject))
							{
							return p;
							}
						}
					}

				return 0;
				}

			const node *find(const type &searchedObject) const
				{
				if(object==searchedObject)
					return this;
				else
					{
					const node *p=0;
					for(deque<node *>::iterator it=childs.begin(); it!=childs.end(); ++it)
						{//devuelve el primero que encuentra de arriba hacia abajo, de izquierda a derecha
						if(p=(*it)->find(searchedObject))
							{
							return p;
							}
						}
					}

				return 0;
				}

			const node &operator[](unsigned int i) const
				{
				return *childs[i];
				}

			node &operator[](unsigned int i)
				{
				return *childs[i];
				}

			const type &getvalue() const
				{
				return object;
				}

			type &getvalue()
				{
				return object;
				}
			
			const node *getfather() const
				{
				return father;
				}

			node *getfather()
				{
				return father;
				}

			typedef deque<node *> sequence_type;

			sequence_type &getsequence()
				{
				return childs;
				}

			const sequence_type &getsequence() const
				{
				return childs;
				}

			//se imprimen los hijos y luego el padre
			void printValues(ostream &os, char delimiter=' ') const
				{
				for(deque<node *>::iterator it=childs.begin(); it!=childs.end(); ++it)
					(*it)->printValues(os,delimiter);

				os<<object<<delimiter;
				}

			ostream &print(ostream &os, const node &Node, int n=0) const
				{
				int i;
				for(i=0; i<n; ++i)
					os<<"    ";

				os<<Node.object;

				if(Node.childs.size())
					{
					os<<endl;

					for(i=0; i<n; ++i)
						os<<"    ";

					os<<"{";
					}
				os<<endl;

				if(Node.childs.size())
					{
					for(deque<node *>::const_iterator it=Node.childs.begin(); it!=Node.childs.end(); ++it)
						print(os,**(it),n+1);
					}

				for(i=0; i<n; ++i)
					os<<"    ";

				if(Node.childs.size())
					os<<"}";
				os<<endl;

				return os;
				}

			friend ostream &operator<<(ostream &os, const node &Node)
				{
				return Node.print(os,Node);
				}

			friend class tree<type>;

	};

	private:
		node *pRootNode;

	public:

		tree();
		tree(const tree &t);
		template<class it>
		tree(it begin, it end)
			{
			while(begin!=end)
				{
				if(pRootNode)
					pRootNode->insert(*begin);
				else
					pRootNode=new node(*begin);
				++begin;
				}
			}
		~tree();
		tree &operator=(const tree &t);
		tree<type>::node *insert(const type &sourceObject);
		tree<type>::node *find(const type &sourceObject);
		const tree<type>::node *find(const type &sourceObject) const;
		operator bool() const;
		void printValues(ostream &os, char delimiter=' ') const;
		friend ostream &operator<<(ostream &os, const tree<type> &btree);
};

template <class type>
inline tree<type>::tree(): pRootNode(0)
{
}

template <class type>
inline tree<type>::tree(const tree &t): pRootNode(new node(*(t.pRootNode)))
{
}

template <class type>
inline tree<type>::~tree()
{
delete pRootNode;
}

template <class type>
tree<type> &tree<type>::operator=(const tree &t)
{
delete pRootNode;
if(t.pRootNode)
	pRootNode=new node(*(t.pRootNode));
else
	pRootNode=0;

return *this;
}

template <class type>
inline tree<type>::node *tree<type>::insert(const type &sourceObject)
{
if(pRootNode)
	return (pRootNode->insert(sourceObject));
else
	{
	pRootNode=new node(sourceObject);
	return (pRootNode);
	}
}

template <class type>
inline tree<type>::node *tree<type>::find(const type &sourceObject)
{
if(pRootNode)
	return (pRootNode->find(sourceObject));
else
	return 0;
}

template <class type>
inline const tree<type>::node *tree<type>::find(const type &sourceObject) const
{
if(pRootNode)
	return (pRootNode->find(sourceObject));
else
	return 0;
}

template <class type>
inline tree<type>::operator bool() const
{
return pRootNode;
}

template <class type>
void tree<type>::printValues(ostream &os, char delimiter) const
{
if(pRootNode)
	pRootNode->printValues(os,delimiter);
}

template <class type>
inline ostream &operator<<(ostream &os, const tree<type> &btree)
{
if(btree.pRootNode)
	return (os<<(*(btree.pRootNode)));

return os;
}

}
		
#endif