/**********************************************************************
 * $Id: LineSequencer.cpp 1820 2006-09-06 16:54:23Z mloskot $
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.refractions.net
 *
 * Copyright (C) 2006 Refractions Research Inc.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation. 
 * See the COPYING file for more information.
 *
 **********************************************************************
 *
 * Last port: operation/linemerge/LineSequencer.java rev. 1.5 (JTS-1.7)
 *
 **********************************************************************/

#include <geos/operation/linemerge/LineSequencer.h>
#include <geos/operation/linemerge/LineMergeEdge.h>
#include <geos/geom/Geometry.h>
#include <geos/geom/GeometryFactory.h>
#include <geos/geom/MultiLineString.h>
#include <geos/geom/Coordinate.h>
#include <geos/geom/CoordinateSequence.h>
#include <geos/geom/LineString.h>
#include <geos/planargraph/Node.h>
#include <geos/planargraph/DirectedEdge.h>
#include <geos/planargraph/Subgraph.h>
#include <geos/planargraph/algorithm/ConnectedSubgraphFinder.h>
#include <geos/util/Assert.h>

#include <cassert>
#include <limits>
#include <vector>

using namespace std;
//using namespace geos::planargraph;
using namespace geos::geom;
//using namespace geos::planargraph::algorithm;

namespace geos {
namespace operation { // geos.operation
namespace linemerge { // geos.operation.linemerge

/* static */
bool
LineSequencer::isSequenced(const Geometry* geom)
{
	const MultiLineString *mls;

	if ( ! (mls=dynamic_cast<const MultiLineString *>(geom)) )
	{
		return true;
	}

	// the nodes in all subgraphs which have been completely scanned
	Coordinate::ConstSet prevSubgraphNodes;
	Coordinate::ConstVect currNodes;

	const Coordinate* lastNode = NULL;

	for (unsigned int i=0, n=mls->getNumGeometries(); i<n; ++i)
	{
		assert(dynamic_cast<const LineString*>(mls->getGeometryN(i)));

		const LineString& line = \
			static_cast<const LineString&>(*(mls->getGeometryN(i)));

		const Coordinate* startNode = &(line.getCoordinateN(0));
		const Coordinate* endNode = &(line.getCoordinateN(line.getNumPoints() - 1));

		/**
		 * If this linestring is connected to a previous subgraph,
		 * geom is not sequenced
		 */
		if (prevSubgraphNodes.find(startNode) != prevSubgraphNodes.end())
		{
			return false;
		}
		if (prevSubgraphNodes.find(endNode) != prevSubgraphNodes.end())
		{
			return false;
		}

		if (lastNode != NULL)
		{
			if (! startNode->equals2D(*lastNode))
			{
				// start new connected sequence
				prevSubgraphNodes.insert(currNodes.begin(),
						currNodes.end());
				currNodes.clear();
			}
		}
		currNodes.push_back(startNode);
		currNodes.push_back(endNode);
		lastNode = endNode;
	}
	return true;
} 

/* private */
bool
LineSequencer::hasSequence(planargraph::Subgraph& graph)
{
	int oddDegreeCount = 0;
	for (planargraph::NodeMap::container::const_iterator
		it=graph.nodeBegin(), endIt=graph.nodeEnd();
		it!=endIt;
		++it)
	{
		planargraph::Node* node = it->second;
		if (node->getDegree() % 2 == 1)
		oddDegreeCount++;
	}
	return oddDegreeCount <= 2;
}


/*private*/
LineSequencer::Sequences*
LineSequencer::findSequences()
{
	Sequences *sequences = new Sequences();
	planargraph::algorithm::ConnectedSubgraphFinder csFinder(graph);
	vector<planargraph::Subgraph*>subgraphs;
	csFinder.getConnectedSubgraphs(subgraphs);
	for (vector<planargraph::Subgraph*>::const_iterator
		it=subgraphs.begin(), endIt=subgraphs.end();
		it!=endIt;
		++it )
	{
		planargraph::Subgraph* subgraph = *it;
		if (hasSequence(*subgraph)) {
			planargraph::DirectedEdge::NonConstList* seq=findSequence(*subgraph);
			sequences->push_back(seq);
		}
		else {
			// if any subgraph cannot be sequenced, abort
			return NULL;
		}
	}
	return sequences;
}

/*private*/
void
LineSequencer::addLine(const LineString *lineString)
{
	if (factory == NULL) {
		factory = lineString->getFactory();
	}
	graph.addEdge(lineString);
	++lineCount;
}

/* private */
void
LineSequencer::computeSequence()
{
	if (isRun) return;
	isRun = true;

	Sequences* sequences(findSequences());
	if (sequences == NULL) return;

	sequencedGeometry = auto_ptr<Geometry>(buildSequencedGeometry(*sequences));
	isSequenceableVar = true;

	// Lines were missing from result
	assert(lineCount == sequencedGeometry->getNumGeometries());

	// Result is not linear
	assert(dynamic_cast<LineString *>(sequencedGeometry.get())
		|| dynamic_cast<MultiLineString *>(sequencedGeometry.get())); 
}

/*private*/
Geometry*
LineSequencer::buildSequencedGeometry(const Sequences& sequences)
{
	auto_ptr<Geometry::NonConstVect> lines(new Geometry::NonConstVect);

	for (Sequences::const_iterator
		i1=sequences.begin(), i1End=sequences.end();
		i1 != i1End;
		++i1)
	{
		planargraph::DirectedEdge::NonConstList& seq = *(*i1);
		for(planargraph::DirectedEdge::NonConstList::iterator i2=seq.begin(),
			i2End=seq.end(); i2 != i2End; ++i2)
		{
			const planargraph::DirectedEdge* de = *i2;
			assert(dynamic_cast<LineMergeEdge* >(de->getEdge()));
			LineMergeEdge* e = static_cast<LineMergeEdge* >(de->getEdge());
			const LineString* line = e->getLine();

			// lineToAdd will be a *copy* of input things
			LineString* lineToAdd;

			if ( ! de->getEdgeDirection() && ! line->isClosed() ) {
				lineToAdd = reverse(line);
			} else {
				Geometry* lineClone = line->clone();
				assert(dynamic_cast<LineString *>(lineClone));
				lineToAdd = static_cast<LineString *>(lineClone); 
			}

			lines->push_back(lineToAdd);
		}
	}

	if ( lines->size() == 0 ) {
		return NULL;
	} else {
		Geometry::NonConstVect *l=lines.get();
		lines.release();
		return factory->buildGeometry(l);
	}
}

/*static private*/
LineString *
LineSequencer::reverse(const LineString *line)
{
	CoordinateSequence* cs=line->getCoordinates();
	CoordinateSequence::reverse(cs);
	return line->getFactory()->createLineString(cs);
}

/*private static*/
const planargraph::Node*
LineSequencer::findLowestDegreeNode(const planargraph::Subgraph& graph)
{
	size_t minDegree = numeric_limits<size_t>::max(); 
	const planargraph::Node* minDegreeNode = NULL;
	for (planargraph::NodeMap::container::const_iterator
		it = graph.nodeBegin(), itEnd = graph.nodeEnd();
		it != itEnd;
		++it )
	{
		const planargraph::Node* node = (*it).second;
		if (minDegreeNode == NULL || node->getDegree() < minDegree)
		{
			minDegree = node->getDegree();
			minDegreeNode = node;
		}
	}
	return minDegreeNode;
}

/*private static*/
const planargraph::DirectedEdge*
LineSequencer::findUnvisitedBestOrientedDE(const planargraph::Node* node)
{
	using planargraph::DirectedEdge;
	using planargraph::DirectedEdgeStar;

	const DirectedEdge* wellOrientedDE = NULL;
	const DirectedEdge* unvisitedDE = NULL;
	const DirectedEdgeStar* des=node->getOutEdges();
	for (DirectedEdge::NonConstVect::const_iterator i=des->begin(),
		e=des->end();
		i!=e;
		++i)
	{
		planargraph::DirectedEdge* de = *i;
		if (! de->getEdge()->isVisited()) {
			unvisitedDE = de;
			if (de->getEdgeDirection()) wellOrientedDE = de;
		}
	}
	if (wellOrientedDE != NULL)
		return wellOrientedDE;
	return unvisitedDE;
}


/*private*/
void
LineSequencer::addReverseSubpath(const planargraph::DirectedEdge *de,
		planargraph::DirectedEdge::NonConstList& deList,
		planargraph::DirectedEdge::NonConstList::iterator lit,
		bool expectedClosed)
{
	using planargraph::Node;
	using planargraph::DirectedEdge;

	// trace an unvisited path *backwards* from this de
	Node* endNode = de->getToNode();

	Node* fromNode = NULL;
	while (true) {
		deList.insert(lit, de->getSym());
		de->getEdge()->setVisited(true);
		fromNode = de->getFromNode();
		const DirectedEdge* unvisitedOutDE = findUnvisitedBestOrientedDE(fromNode);

		// this must terminate, since we are continually marking edges as visited
		if (unvisitedOutDE == NULL) break;
		de = unvisitedOutDE->getSym();
	}
	if ( expectedClosed ) {
		// the path should end at the toNode of this de,
		// otherwise we have an error
		util::Assert::isTrue(fromNode == endNode, "path not contiguos");
		//assert(fromNode == endNode);
	}

}

/*private*/
planargraph::DirectedEdge::NonConstList* 
LineSequencer::findSequence(planargraph::Subgraph& graph)
{
	using planargraph::DirectedEdge;
	using planargraph::Node;
	using planargraph::GraphComponent;

	GraphComponent::setVisited(graph.edgeBegin(),
			graph.edgeEnd(), false);

	const Node* startNode = findLowestDegreeNode(graph);

	const DirectedEdge *startDE = *(startNode->getOutEdges()->begin());
	const DirectedEdge *startDESym = startDE->getSym();

	DirectedEdge::NonConstList *seq = new DirectedEdge::NonConstList();

	DirectedEdge::NonConstList::iterator lit=seq->begin();
	addReverseSubpath(startDESym, *seq, lit, false);

	lit=seq->end();
	while (lit != seq->begin()) {
		const DirectedEdge* prev = *(--lit);
		const DirectedEdge* unvisitedOutDE = findUnvisitedBestOrientedDE(prev->getFromNode());
		if (unvisitedOutDE != NULL)
			addReverseSubpath(unvisitedOutDE->getSym(), *seq, lit, true);
	}

	// At this point, we have a valid sequence of graph DirectedEdges,
	// but it is not necessarily appropriately oriented relative to
	// the underlying geometry.
	DirectedEdge::NonConstList* orientedSeq = orient(seq);

	if (orientedSeq != seq) delete seq;

	return orientedSeq;
}

/* private */
planargraph::DirectedEdge::NonConstList* 
LineSequencer::orient(planargraph::DirectedEdge::NonConstList* seq) 
{
	using namespace geos::planargraph;

	const DirectedEdge* startEdge = seq->front();
	const DirectedEdge* endEdge = seq->back();
	Node* startNode = startEdge->getFromNode();
	Node* endNode = endEdge->getToNode();

	bool flipSeq = false;
	bool hasDegree1Node = \
		startNode->getDegree() == 1 || endNode->getDegree() == 1;

	if (hasDegree1Node)
	{
		bool hasObviousStartNode = false;

		// test end edge before start edge, to make result stable
		// (ie. if both are good starts, pick the actual start
		if (endEdge->getToNode()->getDegree() == 1 &&
				endEdge->getEdgeDirection() == false)
		{
			hasObviousStartNode = true;
			flipSeq = true;
		}
		if (startEdge->getFromNode()->getDegree() == 1 && 
				startEdge->getEdgeDirection() == true)
		{
			hasObviousStartNode = true;
			flipSeq = false;
		}

		// since there is no obvious start node,
		// use any node of degree 1
		if (! hasObviousStartNode)
		{
			// check if the start node should actually
			// be the end node
			if (startEdge->getFromNode()->getDegree() == 1)
				flipSeq = true;
			// if the end node is of degree 1, it is
			// properly the end node
		}

	}


	// if there is no degree 1 node, just use the sequence as is
	// (Could insert heuristic of taking direction of majority of
	// lines as overall direction)

	if (flipSeq)
	{
		return reverse(*seq);
	}
	return seq;
}

/* private */
planargraph::DirectedEdge::NonConstList* 
LineSequencer::reverse(planargraph::DirectedEdge::NonConstList& seq)
{
	using namespace geos::planargraph;

	DirectedEdge::NonConstList* newSeq = new DirectedEdge::NonConstList();
	DirectedEdge::NonConstList::iterator it=seq.begin(), itEnd=seq.end();
	for (; it!=itEnd; ++it) {
		const DirectedEdge *de = *it;
		newSeq->push_front(de->getSym());
	}
	return newSeq;
}

 

} // namespace geos.operation.linemerge
} // namespace geos.operation
} // namespace geos

/**********************************************************************
 * $Log$
 * Revision 1.10  2006/06/12 10:49:43  strk
 * unsigned int => size_t
 *
 * Revision 1.9  2006/03/24 11:04:44  strk
 * Changed assert() with Assert::isTrue in addReverseSubpath
 *
 * Revision 1.8  2006/03/24 10:44:07  strk
 * Fixed to build with -DNDEBUG
 *
 * Revision 1.7  2006/03/22 10:13:54  strk
 * opLinemerge.h split
 *
 * Revision 1.6  2006/03/21 21:42:54  strk
 * planargraph.h header split, planargraph:: classes renamed to match JTS symbols
 *
 **********************************************************************/