#ifndef __TREE_ITERATOR_AMV
	#define __TREE_ITERATOR_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

*/

#include <stack>

using namespace std;

namespace amv	{

/*
	Iterador para árboles, hace el recorrido postorden.
	N es el tipo de nodo del árbol que debe tener la función
	getfather() que devuelve el apuntador al nodo padre.

	El tipo N debe tener definido el tipo N::sequence_type,
	que debe ser una secuencia al estilo de la STL en la que
	se guardan los apuntadores a los nodos hijos. Dicha secuencia
	deberá poder obtenerse mediante la función miembro
	const N::sequence_type &N::getsequence() const.

	El iterador será válido mientras no se aplique una función
	no const al nodo o alguno de sus hijos.

*/
template <class N>
class tree_iterator {

	tree_iterator(N *cur, stack<N::sequence_type::iterator> &ei, stack<N::sequence_type::iterator> &ci):
	current(cur), beg(cur), ends(ei), ends1(ei), curit(ci),
	curit1(ci)
		{
		}

public:
        typedef tree_iterator<N> iterator;

		tree_iterator(): current(0), beg(0){}
        tree_iterator (N *proot);
        tree_iterator (iterator & it)
         : current (it.current), beg(it.beg), ends(it.ends), curit(it.curit),
		 ends1(it.ends1), curit1(it.curit1)
		{
		}

        tree_iterator<N> & operator ++();
        tree_iterator<N> operator ++(int);
		
		N &operator*() const
			{
			return *current;
			}

		N *operator->() const
			{
			return current;
			}

		void operator=(iterator & it)
			{
			current=it.current;
			beg=it.beg;
			curit=it.curit;
			ends=it.ends;
			}

		bool operator==(iterator &it2)
			{
			return current==it2.current;
			}

		bool operator!=(iterator &it2)
			{
			return current!=it2.current;
			}
		
		tree_iterator<N> begin() const
			{
			return iterator(beg,ends1,curit1);
			}
		tree_iterator<N> begin()
			{
			return tree_iterator(beg,ends1,curit1);
			}
		tree_iterator<N> end() const
			{
			return iterator();
			}
		tree_iterator<N> end()
			{
			return iterator();
			}

protected:
        N *current, *beg;
		stack<N::sequence_type::iterator> ends, ends1;
		stack<N::sequence_type::iterator> curit, curit1;

};

template <class N>
tree_iterator<N> &tree_iterator<N>::operator++()
{
if(curit.size())
	{
	if(++curit.top()!=ends.top())
		{
		current=*curit.top();
		while (current && current->getsequence().size())
			{
			ends.push(current->getsequence().end());
			curit.push(current->getsequence().begin());
			current=current->getsequence().front();
			}
		}
	else
		{
		ends.pop();
		curit.pop();
		current=current->getfather();
		}
	}
else
	current=0;

return *this;
}

template <class N>
tree_iterator<N> tree_iterator<N>::operator++(int)
{
tree_iterator<N> temp(*this);
operator++();

return temp;
}

template <class N>
tree_iterator<N>::tree_iterator(N *proot)
{
current=proot;

while (current && current->getsequence().size())
	{
	ends.push(current->getsequence().end());
	curit.push(current->getsequence().begin());
	current=current->getsequence().front();
	}

beg=current;
ends1=ends;
curit1=curit;
}

/*
	Imprime un árbol, dado el nodo sobre el que se quiera empezar.
	Los nodos hijos se imprimen entre llaves y con la indentación
	adecuada.

	El tipo node debe tener definido el tipo node::sequence_type,
	que debe ser una secuencia al estilo de la STL en la que
	se guardan los apuntadores a los nodos hijos. Dicha secuencia
	deberá poder obtenerse mediante la función miembro
	const node::sequence_type &node::getsequence() const.

	Asimismo deberá existir una función que sobrecargue	el operador
	<< para enviar objetos de tipo node a un flujo.

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

os<<Node;

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

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

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

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

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

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

return os;
}

}

#endif