/*
 This file is part of the VRender library.
 Copyright (C) 2005 Cyril Soler (Cyril.Soler@imag.fr)
 Version 1.0.0, released on June 27, 2005.

 http://artis.imag.fr/Members/Cyril.Soler/VRender

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

 VRender 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 General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with VRender; if not, write to the Free Software Foundation, Inc.,
 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
*/

/****************************************************************************

 Copyright (C) 2002-2006 Gilles Debunne (Gilles.Debunne@imag.fr)

This file is part of the QGLViewer library.
 Version 2.2.4-1, released on December 12, 2006.

 http://artis.imag.fr/Members/Gilles.Debunne/QGLViewer

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

 libQGLViewer 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 General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with libQGLViewer; if not, write to the Free Software
 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*****************************************************************************/

#include <assert.h>
#include "VRender.h"
#include "Primitive.h"
#include "PrimitivePositioning.h"
#include "AxisAlignedBox.h"
#include "SortMethod.h"
#include "Vector2.h"

using namespace std ;
using namespace vrender ;

// #define DEBUG_TS

namespace vrender
{
class TopologicalSortUtils
{
	public:
		static void buildPrecedenceGraph(vector<PtrPrimitive>& primitive_tab, vector< vector<int> >& precedence_graph) ;

		static void recursFindNeighbors(	const vector<PtrPrimitive>& primitive_tab,
													const vector<int>& pindices,
													vector< vector<int> >& precedence_graph,
													const AxisAlignedBox_xy&,int) ;

		static void checkAndAddEdgeToGraph(int a,int b,vector< vector<int> >& precedence_graph) ;
		static void suppressPrecedence(int a,int b,vector< vector<int> >& precedence_graph) ;

		static void recursTopologicalSort(vector< vector<int> >& precedence_graph,
													 vector<PtrPrimitive>& primitive_tab,
													 vector<bool>& alread_rendered,
													 vector<bool>& alread_visited,
													 vector<PtrPrimitive>&,int,int&,
													 VRenderParams& vparams,
													 int info_cnt,int& nbrendered) ;

		static void recursTopologicalSort(vector< vector<int> >& precedence_graph,
													 vector<PtrPrimitive>& primitive_tab,
													 vector<bool>& alread_rendered,
													 vector<bool>& alread_visited,
													 vector<PtrPrimitive>&,int,
													 vector<int>& ancestors,
													 int&, int&,
													 VRenderParams& vparams,
													 int info_cnt,int& nbrendered) ;

		static void topologicalSort(	vector< vector<int> >& precedence_graph,
												vector<PtrPrimitive>& primitive_tab,
												VRenderParams&) ;

		static void topologicalSortBreakCycles(vector< vector<int> >& precedence_graph,
															vector<PtrPrimitive>& primitive_tab,
															VRenderParams&) ;

#ifdef DEBUG_TS
		static void printPrecedenceGraph(const vector< vector<int> >& precedence_graph,
													const vector<PtrPrimitive>& primitive_tab) ;
#endif
};

TopologicalSortMethod::TopologicalSortMethod()
{
	_break_cycles = false ;
}

void TopologicalSortMethod::sortPrimitives(vector<PtrPrimitive>& primitive_tab,VRenderParams& vparams)
{
	// 1 - build a precedence graph

#ifdef DEBUG_TS
	cout << "Computing precedence graph." << endl ;
	cout << "Old order: " ;
	for(unsigned int i=0;i<primitive_tab.size();++i) cout << (void *)(primitive_tab[i]) << " " ;
	cout << endl ;
#endif
	vector< vector<int> > precedence_graph(primitive_tab.size());
	TopologicalSortUtils::buildPrecedenceGraph(primitive_tab,precedence_graph) ;

#ifdef DEBUG_TS
	TopologicalSortUtils::printPrecedenceGraph(precedence_graph,primitive_tab) ;
#endif
	// 2 - perform a topological sorting of the graph

#ifdef DEBUG_TS
	cout << "Sorting." << endl ;
#endif

	if(_break_cycles)
		TopologicalSortUtils::topologicalSortBreakCycles(precedence_graph, primitive_tab,vparams) ;
	else
		TopologicalSortUtils::topologicalSort(precedence_graph, primitive_tab,vparams) ;

#ifdef DEBUG_TS
	cout << "New order: " ;
	for(unsigned int i=0;i<primitive_tab.size();++i) cout << (void *)(primitive_tab[i]) << " " ;
	cout << endl ;
#endif
}

#ifdef DEBUG_TS
void TopologicalSortUtils::printPrecedenceGraph(const vector< vector<int> >& precedence_graph,
																const vector<PtrPrimitive>& primitive_tab)
{
	for(unsigned int i=0;i<precedence_graph.size();++i)
	{
		cout << i << " (" << primitive_tab[i]->nbVertices() << ") : " ;
		for(unsigned int j=0;j<precedence_graph[i].size();++j)
			cout << precedence_graph[i][j] << " " ;

		cout << endl ;
	}
}
#endif

void TopologicalSortUtils::buildPrecedenceGraph(vector<PtrPrimitive>& primitive_tab,
																vector< vector<int> >& precedence_graph)
{
	// The precedence graph is constructed by first conservatively determining which
	// primitives can possibly intersect using a quadtree. Candidate pairs of
	// primitives are then carefully checked to compute their exact relative positionning.
	//
	// Because of the conservativeness of the quadtree, some pairs of primitives may be checked
	// multiple times for intersection. Using a buffer of already computed results may proove
	// very efficient.

	// 0 - compute bounding box of the set of primitives.

	AxisAlignedBox_xy BBox ;

	for(unsigned int i=0;i<primitive_tab.size();++i)
	{
		BBox.include(Vector2(primitive_tab[i]->bbox().mini().x(),primitive_tab[i]->bbox().mini().y())) ;
		BBox.include(Vector2(primitive_tab[i]->bbox().maxi().x(),primitive_tab[i]->bbox().maxi().y())) ;
	}

	// 1 - recursively find pairs.

	vector<int> pindices(primitive_tab.size()) ;
	for(unsigned int j=0;j<pindices.size();++j)
		pindices[j] = j ;

	recursFindNeighbors(primitive_tab, pindices, precedence_graph, BBox,0) ;
}

void TopologicalSortUtils::recursFindNeighbors(const vector<PtrPrimitive>& primitive_tab,
																const vector<int>& pindices,
																vector< vector<int> >& precedence_graph,
																const AxisAlignedBox_xy& bbox,
																int depth)
{
	static const unsigned int MAX_PRIMITIVES_IN_CELL = 5 ;

	// Refinment: first decide which sub-cell each primitive meets, then call
	// algorithm recursively.

	if(primitive_tab.size() > MAX_PRIMITIVES_IN_CELL)
	{
		vector<int> p_indices_min_min ;
		vector<int> p_indices_min_max ;
		vector<int> p_indices_max_min ;
		vector<int> p_indices_max_max ;

		double xmin = bbox.mini().x() ;
		double ymin = bbox.mini().y() ;
		double xmax = bbox.maxi().x() ;
		double ymax = bbox.maxi().y() ;

		double xMean = 0.5*(xmin+xmax) ;
		double yMean = 0.5*(ymin+ymax) ;

		for(unsigned int i=0;i<pindices.size();++i)
		{
			bool left  = primitive_tab[pindices[i]]->bbox().mini().x() <= xMean ;
			bool right = primitive_tab[pindices[i]]->bbox().maxi().x() >= xMean ;
			bool down  = primitive_tab[pindices[i]]->bbox().mini().y() <= yMean ;
			bool up    = primitive_tab[pindices[i]]->bbox().maxi().y() >= yMean ;

			if(left  && down) p_indices_min_min.push_back(pindices[i]) ;
			if(right && down) p_indices_max_min.push_back(pindices[i]) ;
			if(left  && up  ) p_indices_min_max.push_back(pindices[i]) ;
			if(right && up  ) p_indices_max_max.push_back(pindices[i]) ;
		}

		// checks if refining is not too much stupid

		if(p_indices_min_min.size() < pindices.size() && p_indices_max_min.size() < pindices.size()
				&& p_indices_min_max.size() < pindices.size() && p_indices_max_max.size() < pindices.size())
		{
			recursFindNeighbors(primitive_tab,p_indices_min_min,precedence_graph,AxisAlignedBox_xy(Vector2(xmin,xMean),Vector2(ymin,yMean)),depth+1) ;
			recursFindNeighbors(primitive_tab,p_indices_min_max,precedence_graph,AxisAlignedBox_xy(Vector2(xmin,xMean),Vector2(yMean,ymax)),depth+1) ;
			recursFindNeighbors(primitive_tab,p_indices_max_min,precedence_graph,AxisAlignedBox_xy(Vector2(xMean,xmax),Vector2(ymin,yMean)),depth+1) ;
			recursFindNeighbors(primitive_tab,p_indices_max_max,precedence_graph,AxisAlignedBox_xy(Vector2(xMean,xmax),Vector2(yMean,ymax)),depth+1) ;
			return ;
		}
	}

	// No refinment either because it could not be possible, or because the number of primitives is below
	// the predefined limit.

	for(unsigned int i=0;i<pindices.size();++i)
		for(unsigned int j=i+1;j<pindices.size();++j)
		{
			// Compute the position of j as regard to i

			int prp = PrimitivePositioning::computeRelativePosition(	primitive_tab[pindices[i]], primitive_tab[pindices[j]]) ;

			if(prp & PrimitivePositioning::Upper) checkAndAddEdgeToGraph(pindices[j],pindices[i],precedence_graph) ;
			if(prp & PrimitivePositioning::Lower) checkAndAddEdgeToGraph(pindices[i],pindices[j],precedence_graph) ;
		}
}

void TopologicalSortUtils::checkAndAddEdgeToGraph(int a,int b,vector< vector<int> >& precedence_graph)
{
#ifdef DEBUG_TS
	cout << "Trying to add " << a << " -> " << b << " " ;
#endif
	bool found = false ;

	for(unsigned int k=0;k<precedence_graph[a].size() && !found;++k)
		if(precedence_graph[a][k] == b)
			found = true ;

#ifdef DEBUG_TS
	if(found)
		cout << "already" << endl ;
	else
		cout << "ok" << endl ;
#endif
	if(!found)
		precedence_graph[a].push_back(b) ;
}

void TopologicalSortUtils::suppressPrecedence(int a,int b,vector< vector<int> >& precedence_graph)
{
	vector<int> prec_tab = vector<int>(precedence_graph[a]) ;
	bool trouve = false ;

	for(unsigned int k=0;k<prec_tab.size();++k)
		if(prec_tab[k] == b)
		{
			prec_tab[k] = prec_tab[prec_tab.size()-1] ;
			prec_tab.pop_back() ;
		}

	if(!trouve)
		throw runtime_error("Unexpected error in suppressPrecedence") ;
}

void TopologicalSortUtils::topologicalSort(vector< vector<int> >& precedence_graph,
														 vector<PtrPrimitive>& primitive_tab,
														 VRenderParams& vparams)
{
	vector<PtrPrimitive> new_pr_tab ;
	vector<bool> already_visited(primitive_tab.size(),false) ;
	vector<bool> already_rendered(primitive_tab.size(),false) ;
	int nb_skews = 0 ;

	int info_cnt = primitive_tab.size()/200 + 1 ;
	int nbrendered = 0 ;

	// 1 - sorts primitives by rendering order

	for(unsigned int i=0;i<primitive_tab.size();++i)
		if(!already_rendered[i])
			recursTopologicalSort(precedence_graph,primitive_tab,already_rendered,already_visited,new_pr_tab,i,nb_skews,vparams,info_cnt,nbrendered);

#ifdef DEBUG_TS
	if(nb_skews > 0)
		cout << nb_skews << " cycles found." << endl ;
	else
		cout << "No cycles found." << endl ;
#endif
	primitive_tab = new_pr_tab ;
}

void TopologicalSortUtils::topologicalSortBreakCycles(vector< vector<int> >& precedence_graph,
																		vector<PtrPrimitive>& primitive_tab,
																		VRenderParams& vparams)
{
	vector<PtrPrimitive> new_pr_tab ;
	vector<bool> already_visited(primitive_tab.size(),false) ;
	vector<bool> already_rendered(primitive_tab.size(),false) ;
	vector<int> ancestors ;
	int nb_skews = 0 ;
	int ancestors_backward_index ;

	int info_cnt = primitive_tab.size()/200 + 1 ;
	int nbrendered = 0 ;

	// 1 - sorts primitives by rendering order

	for(unsigned int i=0;i<primitive_tab.size();++i)
		if(!already_rendered[i])
			recursTopologicalSort(precedence_graph,primitive_tab,already_rendered,already_visited,
										new_pr_tab,i,ancestors,ancestors_backward_index,nb_skews,vparams,info_cnt,nbrendered) ;

#ifdef DEBUG_TS
	if(nb_skews > 0)
		cout << nb_skews << " cycles found." << endl ;
	else
		cout << "No cycles found." << endl ;
#endif
	primitive_tab = new_pr_tab ;
}

void TopologicalSortUtils::recursTopologicalSort(	vector< vector<int> >& precedence_graph,
																	vector<PtrPrimitive>& primitive_tab,
																	vector<bool>& already_rendered,
																	vector<bool>& already_visited,
																	vector<PtrPrimitive>& new_pr_tab,
																	int indx,
																	int& nb_cycles,
																	VRenderParams& vparams,
																	int info_cnt,int& nbrendered)
{
	// One must first render the primitives indicated by the precedence graph,
	// then render the current primitive. Skews are detected, but and treated.

	already_visited[indx] = true ;

	for(unsigned int j=0;j<precedence_graph[indx].size();++j)
	{
		// Both tests are important. If we ommit the second one, the recursion is
		// always performed down to the next cycle, although this is useless if
		// the current primitive was rendered already.

		if(!already_visited[precedence_graph[indx][j]])
		{
			if(!already_rendered[precedence_graph[indx][j]])
				recursTopologicalSort(	precedence_graph,primitive_tab,already_rendered,already_visited,
												new_pr_tab,precedence_graph[indx][j],nb_cycles,vparams,info_cnt,nbrendered) ;
		}
		else //  A cycle is detected, but in this version, it is not broken.
			++nb_cycles ;
	}

	if(!already_rendered[indx])
	{
		new_pr_tab.push_back(primitive_tab[indx]) ;

		if((++nbrendered)%info_cnt==0)
			vparams.progress(nbrendered/(float)primitive_tab.size(),string("Topological sort")) ;
	}

	already_rendered[indx] = true ;
	already_visited[indx] = false ;
}

void TopologicalSortUtils::recursTopologicalSort(	vector< vector<int> >& precedence_graph,
																	vector<PtrPrimitive>& primitive_tab,
																	vector<bool>& already_rendered,
																	vector<bool>& already_visited,
																	vector<PtrPrimitive>& new_pr_tab,
																	int indx,
																	vector<int>& ancestors,
																	int& ancestors_backward_index,
																	int& nb_cycles,
																	VRenderParams& vparams,
																	int info_cnt,int& nbrendered)
{
	// One must first render the primitives indicated by the precedence graph,
	// then render the current primitive. Skews are detected, but and treated.

	already_visited[indx] = true ;
	ancestors.push_back(indx) ;

	for(unsigned int j=0;j<precedence_graph[indx].size();++j)
	{
		// Both tests are important. If we ommit the second one, the recursion is
		// always performed down to the next cycle, although this is useless if
		// the current primitive was rendered already.

		if(!already_visited[precedence_graph[indx][j]])
		{
			if(!already_rendered[precedence_graph[indx][j]])
			{
				recursTopologicalSort(	precedence_graph,primitive_tab,already_rendered,already_visited,
												new_pr_tab,precedence_graph[indx][j],ancestors,ancestors_backward_index,nb_cycles,vparams,info_cnt,nbrendered) ;

				if(ancestors_backward_index != INT_MAX && ancestors.size() > (unsigned int)(ancestors_backward_index+1))
				{
#ifdef DEBUG_TS
					cout << "Returning early" << endl ;
#endif
					already_visited[indx] = false ;
					ancestors.pop_back() ;
					return;
				}
				if(ancestors_backward_index != INT_MAX) // we are returning from emergency. j must be re-tried
					--j ;
			}
		}
		else
		{
			//  A cycle is detected. It must be broken. The algorithm is the following: primitives of the cycle
			// are successively split by a chosen splitting plane and the precendence graph is updated
			// at the same time by re-computing primitive precedence. As soon as the cycle is broken,
			// the algorithm stops and calls recursively calls on the new precedence graph. This necessarily
			// happens because of the BSP-node nature of the current set of primitives.

			// 0 - stats
			++nb_cycles ;

			// 0.5 - determine cycle beginning

			int cycle_beginning_index = -1 ;
			for(int i=ancestors.size()-1; i >= 0 && cycle_beginning_index < 0;--i)
				if(ancestors[i] == precedence_graph[indx][j])
					cycle_beginning_index = i ;
#ifdef DEBUG_TS
			cout << "Unbreaking cycle : " ;
			for(unsigned int i=0;i<ancestors.size();++i)
				cout << ancestors[i] << " " ;
			cout << precedence_graph[indx][j] << endl ;
#endif
#ifdef DEBUG_TS
			assert(cycle_beginning_index >= 0) ;
#endif
			// 1 - determine splitting plane

			int split_prim_ancestor_indx = -1 ;
			int split_prim_indx = -1 ;

			// Go down ancestors tab, starting from the skewing primitive, and stopping at it.

			for(unsigned int i2=cycle_beginning_index;i2<ancestors.size() && split_prim_ancestor_indx < 0;++i2)
				if(primitive_tab[ancestors[i2]]->nbVertices() > 2)
				{
					split_prim_ancestor_indx = i2 ;
					split_prim_indx = ancestors[i2] ;
				}

#ifdef DEBUG_TS
			cout << "Split primitive index = " << split_prim_ancestor_indx << "(primitive = " << split_prim_indx << ")" << endl ;
#endif
			if(split_prim_indx < 0)	// no need to unskew cycles between segments and points
				continue ;

			// 2 - split all necessary primitives

			const Polygone *P = dynamic_cast<const Polygone *>(primitive_tab[split_prim_indx]) ;
			const NVector3& normal = NVector3(P->normal()) ;
			double c(P->c()) ;
			ancestors.push_back(precedence_graph[indx][j]) ;				// sentinel
			ancestors.push_back(ancestors[cycle_beginning_index+1]) ;	// sentinel
			bool cycle_broken = false ;

			for(unsigned int i3=cycle_beginning_index+1;i3<ancestors.size()-1 && !cycle_broken;++i3)
				if(ancestors[i3] != split_prim_indx)
				{
					bool prim_lower_ante_contains_im1 = false ;
					bool prim_upper_ante_contains_im1 = false ;
					bool prim_lower_prec_contains_ip1 = false ;
					bool prim_upper_prec_contains_ip1 = false ;

					Primitive *prim_upper = NULL ;
					Primitive *prim_lower = NULL ;

					PrimitivePositioning::splitPrimitive(primitive_tab[ancestors[i3]],normal,c,prim_upper,prim_lower) ;

					if(prim_upper == NULL || prim_lower == NULL)
						continue ;
#ifdef DEBUG_TS
					cout << "Splitted primitive " << ancestors[i3] << endl ;
#endif

					vector<int> prim_upper_prec ;
					vector<int> prim_lower_prec ;

					vector<int> old_prec = vector<int>(precedence_graph[ancestors[i3]]) ;

					int upper_indx = precedence_graph.size() ;
					int lower_indx = ancestors[i3] ;

					//  Updates the precedence graph downwards.

					for(unsigned int k=0;k<old_prec.size();++k)
					{
						int prp1 = PrimitivePositioning::computeRelativePosition(prim_upper,primitive_tab[old_prec[k]]) ;
#ifdef DEBUG_TS
						cout << "Compariing " << upper_indx << " and " << old_prec[k] << ": " ;
#endif
						// It can not be Upper, because it was lower from the original primitive, but it is not
						// necessary lower any longer because of the split.

						if(prp1 & PrimitivePositioning::Lower)
						{
#ifdef DEBUG_TS
							cout << " > " << endl ;
#endif
							prim_upper_prec.push_back(old_prec[k]) ;

							if(old_prec[k] == ancestors[i3+1])
								prim_upper_prec_contains_ip1 = true ;
						}
#ifdef DEBUG_TS
						else
							cout << " I " << endl ;
#endif

						int prp2 = PrimitivePositioning::computeRelativePosition(prim_lower,primitive_tab[old_prec[k]]) ;
#ifdef DEBUG_TS
						cout << "Compariing " << lower_indx << " and " << old_prec[k] << ": " ;
#endif
						if(prp2 & PrimitivePositioning::Lower)
						{
#ifdef DEBUG_TS
							cout << " > " << endl ;
#endif
							prim_lower_prec.push_back(old_prec[k]) ;

							if(old_prec[k] == ancestors[i3+1])
								prim_lower_prec_contains_ip1 = true ;
						}
#ifdef DEBUG_TS
						else
							cout << " I " << endl ;
#endif
					}

					// We also have to update the primitives which are upper to the
					// current one, because some of them may not be upper anymore.
					// This would requires either a O(n^2) algorithm, or to store an
					// dual precedence graph. For now it's O(n^2). This test can not
					// be skipped because upper can still be lower to ancestors[i-1].

					for(unsigned int l=0;l<precedence_graph.size();++l)
						if(l != (unsigned int)lower_indx)
							for(int k=0;k<(int)precedence_graph[l].size();++k)
								if(precedence_graph[l][k] == ancestors[i3])
								{
									int prp1 = PrimitivePositioning::computeRelativePosition(prim_upper,primitive_tab[l]) ;

									// It can not be Lower, because it was upper from the original primitive, but it is not
									// necessary upper any longer because of the split.

									if(prp1 & PrimitivePositioning::Upper)
									{
										// Still upper. Add the new index at end of the array

										precedence_graph[l].push_back(upper_indx) ;

										if(l == (unsigned int)ancestors[i3-1])
											prim_upper_ante_contains_im1 = true ;
									}
									// If the primitive is not upper anymore there is
									// nothing to change since the index has changed.

									int prp2 = PrimitivePositioning::computeRelativePosition(prim_lower,primitive_tab[l]) ;
#ifdef DEBUG_TS
									cout << "Compariing " << l << " and " << lower_indx  << ": " ;
#endif
									if(prp2 & PrimitivePositioning::Upper)
									{
#ifdef DEBUG_TS
										cout << " > " << endl ;
#endif
										if(l == (unsigned int)ancestors[i3-1])						 // The index is the same => nothing to change.
											prim_lower_ante_contains_im1 = true ;
									}
									else
									{
#ifdef DEBUG_TS
										cout << " I " << endl ;
#endif
										// Not upper anymore. We have to suppress this entry from the tab.

										precedence_graph[l][k] = precedence_graph[l][precedence_graph[l].size()-1] ;
										precedence_graph[l].pop_back() ;
										--k ;
									}

									break ;	// each entry is present only once.
								}

					// setup recorded new info

					primitive_tab.push_back(prim_upper) ;
					delete primitive_tab[lower_indx] ;
					primitive_tab[lower_indx] = prim_lower ;

					// Adds the info to the precedence graph

					precedence_graph.push_back(prim_upper_prec) ;
					precedence_graph[lower_indx] = prim_lower_prec ;

					// Adds new entries to the 'already_rendered' and 'already_visited' vectors
					already_visited.push_back(false) ;
					already_rendered.push_back(false) ;
#ifdef DEBUG_TS
					cout << "New precedence graph: " << endl ;
					printPrecedenceGraph(precedence_graph,primitive_tab) ;
#endif
					// Checks if the cycle is broken. Because the graph is only
					// updated downwards, we check wether lower (which still is
					// lower to ancestors[i-1]) is upper to ancestors[i+1], or
					// if upper is still .

					if(( !(prim_lower_ante_contains_im1 && prim_lower_prec_contains_ip1))
					  &&(!(prim_upper_ante_contains_im1 && prim_upper_prec_contains_ip1)))
						cycle_broken = true ;
				}

			ancestors.pop_back() ;
			ancestors.pop_back() ;

			// 3 - recurs call

			if(cycle_broken)
			{
				ancestors_backward_index = cycle_beginning_index ;
#ifdef DEBUG_TS
				cout << "Cycle broken. Jumping back to rank " << ancestors_backward_index << endl ;
#endif
				already_visited[indx] = false ;
				ancestors.pop_back() ;
				return;
			}
#ifdef DEBUG_TS
			else
				cout << "Cycle could not be broken !!" << endl ;
#endif
		}
	}

	if(!already_rendered[indx])
	{
#ifdef DEBUG_TS
		cout << "Returning ok. Rendered primitive " << indx << endl ;
#endif
		new_pr_tab.push_back(primitive_tab[indx]) ;

		if((++nbrendered)%info_cnt==0)
			vparams.progress(nbrendered/(float)primitive_tab.size(),string("Advanced topological sort")) ;
	}

	already_rendered[indx] = true ;
	ancestors_backward_index = INT_MAX ;
	already_visited[indx] = false ;
	ancestors.pop_back() ;
}
} // namespace