// AutoRouterGraph.cpp : Implementation of CAutoRouterGraph

#include "stdafx.h"
#include "AutoRouterGraph.h"
#include "AutoRouterBox.h"
#include "AutoRouterPort.h"
#include "AutoRouterPath.h"
#include "AutoRouterEdge.h"


// --- CAutoRouterGraph

CAutoRouterGraph::CAutoRouterGraph():
	horizontal(true),
	vertical(false)
{
	horizontal.SetOwner(this);
	vertical.SetOwner(this);

	CalculateSelfPoints();
	AddSelfEdges();
}

// --- Boxes

void CAutoRouterGraph::Remove(CAutoRouterBox* box)
{
	DeleteBoxAndPortEdges(box);

	std::vector<CAutoRouterPath*>::iterator iter;
	iter = paths.begin();
	
	while(iter != paths.end())
	{
		bool iteratorChanged = false;

		CAutoRouterPath* path = *iter;

		CAutoRouterPort* startPort = path->GetStartPort();
		ASSERT(startPort != NULL);
		CAutoRouterBox* startbox = startPort->GetOwner();

		CAutoRouterPort* endPort = path->GetEndPort();
		ASSERT(endPort != NULL);
		CAutoRouterBox* endbox = endPort->GetOwner();

		if( (startbox == box || endbox == box) )
		{
			//DeletePath:
			if (path->HasOwner())
			{
				DeleteEdges(path);
				path->SetOwner(NULL);

				iter = paths.erase(iter);
				iteratorChanged = true;
			}

			path->Destroy();	// ??
		}

		if (!iteratorChanged)
			++iter;
	}

	box->SetOwner(NULL);

	std::vector<CAutoRouterBox*>::iterator iter2 = std::find(boxes.begin(), boxes.end(), box);

	if (iter2 != boxes.end())
	{
		boxes.erase(iter2);
	}
	else
	{
		//error
		ASSERT(false);
	}
}

void CAutoRouterGraph::DeleteAllBoxes()
{
	for (CAutoRouterBoxList::size_type i = 0; i < boxes.size(); i++)
	{
		//DeleteBoxAndPortEdges(boxes[i]);	// no need: there's a DeleteAllEdges in DeleteAll
		boxes[i]->Destroy();
		delete boxes[i];
	}

	boxes.clear();
}

CAutoRouterBox* CAutoRouterGraph::GetBoxAt(const CPoint& point, int nearness) const
{
	std::vector<CAutoRouterBox*>::const_iterator iter = boxes.begin();
	while (iter != boxes.end())
	{
		if ((*iter)->IsBoxAt(point, nearness))
			return (*iter);

		++iter;
	}

	return NULL;
}

void CAutoRouterGraph::SetPortAttr(CAutoRouterPort* port, unsigned int attr)
{
	DisconnectPathsFrom(port);
	port->SetAttributes(attr);
}

bool CAutoRouterGraph::IsRectClipBoxes(const CRect& rect) const
{
	for (CAutoRouterBoxList::size_type i = 0; i < boxes.size(); i++)
	{
		const CRect boxRect = boxes[i]->GetRect();
		if( IsRectClip(rect, boxRect) )
			return true;
	}
	return false;
}

bool CAutoRouterGraph::IsLineClipBoxes(const CPoint& p1, const CPoint& p2) const
{
	CRect rect(p1, p2);
	rect.NormalizeRect();
	ASSERT( rect.left == rect.right || rect.top == rect.bottom );

	if( rect.left == rect.right)
		rect.right++;
	if( rect.top == rect.bottom )
		rect.bottom++;

	return IsRectClipBoxes(rect);
}

bool CAutoRouterGraph::CanBoxAt(const CRect& rect) const
{
	return !IsRectClipBoxes(InflatedRect(rect, 1));
}

void CAutoRouterGraph::Add(CAutoRouterPath* path)
{
	ASSERT( path != NULL );
	ASSERT(!path->HasOwner());

	path->SetOwner(this);

	paths.push_back(path);

	AddEdges(path);

#ifdef _DEBUG
	AssertValidPath(path);
#endif
}

void CAutoRouterGraph::Remove(CAutoRouterPath* path)
{
	DeleteEdges(path);

	path->SetOwner(NULL);

	std::vector<CAutoRouterPath*>::iterator iter = std::find(paths.begin(), paths.end(), path);

	if (iter != paths.end())
	{
		paths.erase(iter);
	}
	else
	{
		//error
		ASSERT(false);
	}
}

void CAutoRouterGraph::DeleteAllPaths()
{
	std::vector<CAutoRouterPath*>::iterator iter;
	iter = paths.begin();

	while (iter != paths.end())
	{
		//DeleteEdges(*iter);	// no need: there's a DeleteAllEdges in DeleteAll

		(*iter)->SetOwner(NULL);
		(*iter)->Destroy();
		delete (*iter);
		++iter;
	}

	paths.clear();
}

CAutoRouterEdge* CAutoRouterGraph::GetListEdgeAt(const CPoint& point, int nearness) const
{
	CAutoRouterEdge* edge;

	edge = horizontal.GetEdgeAt(point, nearness);
	if( edge )
		return edge;

	return vertical.GetEdgeAt(point, nearness);
}

// --- Boxes && Paths

CRect CAutoRouterGraph::GetSurroundRect(void) const
{
	CRect rect(0,0,0,0);

	for (CAutoRouterBoxList::size_type i = 0; i < boxes.size(); i++)
	{
		rect |= boxes[i]->GetRect();
	}

	for (CAutoRouterPathList::size_type i = 0; i < paths.size(); i++)
	{
		rect |= paths[i]->GetSurroundRect();
	}

	return rect;
}

CAutoRouterBox* CAutoRouterGraph::GetOutOfBox(CPoint& point, RoutingDirection dir) const
{
	ASSERT( IsRightAngle(dir) );

	CAutoRouterBox* boxby = NULL;

	std::vector<CAutoRouterBox*>::const_iterator iter = boxes.begin();

	while (iter != boxes.end())
	{
		const CRect boxRect = (*iter)->GetRect();
		if( boxRect.PtInRect(point) )
		{
			boxby = *iter;
			iter = boxes.begin();

			GetPointCoord(point, dir) = GetRectOuterCoord(boxRect, dir);
		}
		++iter;
	}

	return boxby;
}

CAutoRouterBox* CAutoRouterGraph::GoToNextBox(CPoint& point, RoutingDirection dir, long stophere) const
{
	ASSERT( IsRightAngle(dir) );
	ASSERT( GetPointCoord(point, dir) != stophere );

	CAutoRouterBox* boxby = NULL;

	std::vector<CAutoRouterBox*>::const_iterator iter = boxes.begin();

	while (iter != boxes.end())
	{
		const CRect boxRect = (*iter)->GetRect();
		if( IsPointInDirFrom(point, boxRect, ReverseDir(dir)) &&
			IsPointBetweenSides(point, boxRect, dir) &&
			IsCoordInDirFrom(stophere, GetRectOuterCoord(boxRect, ReverseDir(dir)), dir) )
		{
			stophere = GetRectOuterCoord(boxRect, ReverseDir(dir));
			boxby = *iter;
		}
		++iter;
	}

	GetPointCoord(point, dir) = stophere;

	return boxby;
}

void CAutoRouterGraph::GetLimitsOfEdge(const CPoint& startPt, const CPoint& endPt, long& min, long& max) const
{
	long t;
	CPoint start = startPt;
	CPoint end = endPt;

	std::vector<CAutoRouterBox*>::const_iterator iter = boxes.begin();

	if( start.y == end.y )
	{
		if( start.x > end.x )
		{
			t = start.x;
			start.x = end.x;
			end.x = t;
		}

		while( iter != boxes.end())
		{
			const CRect rect = (*iter)->GetRect();
			++iter;

			if(start.x < rect.right && rect.left <= end.x)
			{
				if( rect.bottom <= start.y && rect.bottom > min )
					min = rect.bottom;
				if( rect.top > start.y && rect.top < max )
					max = rect.top;
			}
		}
	}
	else
	{
		ASSERT( start.x == end.x );

		if( start.y > end.y )
		{
			t = start.y;
			start.y = end.y;
			end.y = t;
		}

		while( iter != boxes.end())
		{
			const CRect rect = (*iter)->GetRect();
			++iter;

			if(start.y < rect.bottom && rect.top <= end.y)
			{
				if( rect.right <= start.x && rect.right > min )
					min = rect.right;
				if( rect.left > start.x && rect.left < max )
					max = rect.left;
			}
		}
	}

	max--;
}

bool CAutoRouterGraph::Connect(CAutoRouterPath* path)
{
	CAutoRouterPort* startport = path->GetStartPort();
	CAutoRouterPort* endport = path->GetEndPort();

	RoutingDirection startdir = path->GetStartDir();
	bool startportHasLimited = false;
	bool startportCanHave = true;
	if (startdir != Dir_None) {
		startportHasLimited = startport->HasLimitedDirs();
		startportCanHave = startport->CanHaveStartEndPointOn(startdir, true);
	}
	if( startdir == Dir_None ||							// recalc startdir if empty
		startportHasLimited && !startportCanHave)		// or is limited and userpref is invalid
	{
		startdir = startport->GetStartEndDirTo(endport->GetCenter(), true);
	}

	RoutingDirection enddir = path->GetEndDir();
	bool endportHasLimited = false;
	bool endportCanHave = true;
	if (enddir != Dir_None) {
		endportHasLimited = endport->HasLimitedDirs();
		endportCanHave = endport->CanHaveStartEndPointOn(enddir, false);
	}
	if( enddir == Dir_None ||							// like above
		endportHasLimited && !endportCanHave)
	{
		enddir = endport->GetStartEndDirTo(startport->GetCenter(), false, startport == endport ? startdir : Dir_None );
	}

	CPoint startpoint = startport->CreateStartEndPointOn(startdir);
	CPoint endpoint = endport->CreateStartEndPointOn(enddir);

	if( startpoint == endpoint )
		startpoint = StepOneInDir(startpoint, NextClockwiseDir(startdir));

	return Connect(path, startpoint, endpoint);
}

bool CAutoRouterGraph::Connect(CAutoRouterPath* path, CPoint& startpoint, CPoint& endpoint)
{
	ASSERT( path != NULL && path->GetOwner() == this );
	ASSERT( !path->IsConnected() );
	ASSERT( startpoint != endpoint );

	CAutoRouterPort* startPort = path->GetStartPort();
	ASSERT(startPort != NULL);
	RoutingDirection startdir = startPort->OnWhichEdge(startpoint);

	CAutoRouterPort* endPort = path->GetEndPort();
	ASSERT(endPort != NULL);
	RoutingDirection enddir = endPort->OnWhichEdge(endpoint);
	ASSERT( IsRightAngle(startdir) && IsRightAngle(enddir) );

	CPoint start = startpoint;
	GetOutOfBox(start, startdir);
	ASSERT( start != startpoint );

	CPoint end = endpoint;
	GetOutOfBox(end, enddir);
	ASSERT( end != endpoint );

	ASSERT( path->IsEmpty() );

	CPointListPath ret;
	bool isAutoRouted = path->IsAutoRouted();
	if (isAutoRouted)
		ConnectPoints(ret, start, end, startdir, enddir);

	if (!isAutoRouted)
	{
		CPointListPath ret2;
		path->ApplyCustomizationsBeforeAutoConnectPoints(ret2);

		if (ret2.GetCount() > 0)
		{
			ret.RemoveAll();
			POSITION pos = ret2.GetHeadPosition();
			while( pos != NULL )
			{
				ret.AddTail(ret2.GetNext(pos));
			}
		}
	}

	path->DeleteAll();

	path->AddTail(startpoint);
	POSITION pos = ret.GetHeadPosition();
	while( pos != NULL )
	{
		CPoint p = ret.GetNext(pos);
		path->AddTail(p);
	}
	path->AddTail(endpoint);

	if (isAutoRouted) {
		path->SimplifyTrivially();
		SimplifyPathPoints(path);
		CenterStairsInPathPoints(path, startdir, enddir);
	}
	path->SetState(ARPATHST_Connected);

	// Apply custom edge modifications - step 1
	// (Step 1: Move the desired edges - see in CAutoRouterGraph::Connect(CAutoRouterPath* path, CPoint& startpoint, CPoint& endpoint)
	//  Step 2: Fix the desired edges - see in CAutoRouterEdgeList::AddEdges(CAutoRouterPath* path))
	if (isAutoRouted)
		path->ApplyCustomizationsAfterAutoConnectPointsAndStuff();

	return AddEdges(path);
}

void CAutoRouterGraph::ConnectPoints(CPointListPath& ret, CPoint& start, CPoint& end, RoutingDirection hintstartdir, RoutingDirection hintenddir)
{
	ASSERT( ret.IsEmpty() );

	CPoint& thestart = start;
	POSITION retend = NULL;

	while( start != end )
	{
		RoutingDirection dir1 = ExGetMajorDir(end-start);
		RoutingDirection dir2 = ExGetMinorDir(end-start);
		ASSERT( dir1 != Dir_None );

		ASSERT( dir1 == GetMajorDir(end-start) );
		ASSERT( dir2 == Dir_None || dir2 == GetMinorDir(end-start) );

		if( retend == NULL && dir2 == hintstartdir && dir2 != Dir_None )
		{
			// i.e. std::swap(dir1, dir2);
			dir2 = dir1;
			dir1 = hintstartdir;
		}

		if (retend == NULL)
			retend = ret.AddTail(start);
		else
			retend = ret.InsertAfter(retend, start);
		CPoint old = start;

		CAutoRouterBox* box = GoToNextBox(start, dir1, end);
		if( start == old )
		{
			ASSERT( box != NULL );
			const CRect rect = box->GetRect();

			if( dir2 == Dir_None )
				dir2 = NextClockwiseDir(dir1);

			ASSERT( dir1 != dir2 && dir1 != Dir_None && dir2 != Dir_None );

			if( IsPointInDirFrom(end, rect, dir2) )
			{
				ASSERT( !IsPointInDirFrom(start, rect, dir2) );
				GoToNextBox(start, dir2, end);
				// this assert fails if two boxes are adjacent, and a connection wants to go between
				ASSERT( IsPointInDirFrom(start, rect, dir2) );
			}
			else
			{
				ASSERT( IsPointBetweenSides(end, rect, dir1) );
				ASSERT( !IsPointIn(end, rect) );

				int rev = 0;

				if( ReverseDir(dir2) == hintenddir )
					rev = 1;
				else if( dir2 != hintenddir )
				{
					if( IsPointBetweenSides(thestart, rect, dir1) )
					{
						if(	IsPointInDirFrom(rect.TopLeft() + rect.BottomRight(), start + end, dir2) )
							rev = 1;
					}
					else
						if( IsPointInDirFrom(start, thestart, dir2) )
							rev = 1;
				}

				if( rev )
				{
					dir2 = ReverseDir(dir2);
				}

				GetPointCoord(start, dir2) = GetRectOuterCoord(rect, dir2);

				ASSERT( start != old );
				ASSERT(retend != NULL);
				retend = ret.InsertAfter(retend, start);

				old = start;

				GetPointCoord(start, dir1) = GetRectOuterCoord(rect, dir1);
				ASSERT( IsPointInDirFrom(end, start, dir1) );
				if( GetPointCoord(start, dir1) != GetPointCoord(end, dir1) )
					GoToNextBox(start, dir1, end);
			}

			ASSERT( start != old );
		}
	}

	ret.AddTail(end);
}

void CAutoRouterGraph::DisconnectAll()
{
	std::vector<CAutoRouterPath*>::iterator iter;
	iter = paths.begin();
	
	while(iter != paths.end())
	{
		Disconnect(*iter);
		++iter;
	}
}

void CAutoRouterGraph::Disconnect(CAutoRouterPath* path)
{
	if( path->IsConnected() )
		DeleteEdges(path);

	path->DeleteAll();
}

void CAutoRouterGraph::DisconnectPathsClipping(const CRect& rect)
{
	std::vector<CAutoRouterPath*>::reverse_iterator iter;
	iter = paths.rbegin();

	while(iter != paths.rend())
	{
		if( (*iter)->IsPathClip(rect) )
			Disconnect(*iter);
		++iter;
	}
}

void CAutoRouterGraph::DisconnectPathsFrom(CAutoRouterBox* box)
{
	std::vector<CAutoRouterPath*>::reverse_iterator iter;
	iter = paths.rbegin();

	while(iter != paths.rend())
	{
		CAutoRouterPath* path = *iter;

		CAutoRouterPort* startPort = path->GetStartPort();
		ASSERT(startPort != NULL);
		CAutoRouterBox* startbox = startPort->GetOwner();
		ASSERT(startbox != NULL);

		CAutoRouterPort* endPort = path->GetEndPort();
		ASSERT(endPort != NULL);
		CAutoRouterBox* endbox = endPort->GetOwner();
		ASSERT(endbox != NULL);

		if( (startbox == box || endbox == box) )
			Disconnect(path);

		++iter;
	}
}

void CAutoRouterGraph::DisconnectPathsFrom(CAutoRouterPort* port)
{
	std::vector<CAutoRouterPath*>::reverse_iterator iter;
	iter = paths.rbegin();
	
	while(iter != paths.rend())
	{
		CAutoRouterPath* path = *iter;

		CAutoRouterPort* startport = path->GetStartPort();
		CAutoRouterPort* endport = path->GetEndPort();

		if( (startport == port || endport == port) )
			Disconnect(path);

		++iter;
	}
}

// --- Edges

void CAutoRouterGraph::AddSelfEdges(void)
{
	horizontal.AddEdges(this);
	vertical.AddEdges(this);
}

void CAutoRouterGraph::AddEdges(CAutoRouterGraph* graph)
{
	horizontal.AddEdges(graph);
	vertical.AddEdges(graph);
}

void CAutoRouterGraph::AddEdges(CAutoRouterBox* box)
{
	horizontal.AddEdges(box);
	vertical.AddEdges(box);
}

void CAutoRouterGraph::AddEdges(CAutoRouterPort* port)
{
	horizontal.AddEdges(port);
	vertical.AddEdges(port);
}

bool CAutoRouterGraph::AddEdges(CAutoRouterPath* path)
{
	return horizontal.AddEdges(path) && vertical.AddEdges(path);
}

void CAutoRouterGraph::DeleteEdges(CObject* object)
{
	horizontal.DeleteEdges(object);
	vertical.DeleteEdges(object);
}

void CAutoRouterGraph::AddAllEdges()
{
	ASSERT( horizontal.IsEmpty() && vertical.IsEmpty() );

	std::vector<CAutoRouterBox*>::iterator iter;
	iter = boxes.begin();

	while (iter != boxes.end())
	{
		AddBoxAndPortEdges(*iter);
		++iter;
	}

	std::vector<CAutoRouterPath*>::iterator iterP;
	iterP = paths.begin();

	while (iterP != paths.end())
	{
		AddEdges(*iterP);
		iterP++;
	}
}

void CAutoRouterGraph::DeleteAllEdges()
{
	horizontal.DeleteAllEdges();
	vertical.DeleteAllEdges();
}

void CAutoRouterGraph::AddBoxAndPortEdges(CAutoRouterBox* box)
{
	ASSERT( box != NULL );

	AddEdges(box);

	const CAutoRouterPortList& pl = box->GetPortList();
	std::vector<CAutoRouterPort*>::const_iterator ii = pl.begin();
	while( ii != pl.end() ) {
		AddEdges(*ii);
		++ii;
	}
}

void CAutoRouterGraph::DeleteBoxAndPortEdges(CAutoRouterBox* box)
{
	ASSERT( box != NULL );

	DeleteEdges(box);

	const CAutoRouterPortList& pl = box->GetPortList();
	std::vector<CAutoRouterPort*>::const_iterator ii = pl.begin();
	while( ii != pl.end() ) {
		DeleteEdges(*ii);
		++ii;
	}
}

CAutoRouterEdgeList& CAutoRouterGraph::GetEdgeList(bool ishorizontal)
{
	return ishorizontal ? horizontal : vertical;
}

// --- Path && Edges

bool CAutoRouterGraph::CanDeleteTwoEdgesAt(CAutoRouterPath* path, CPointListPath& points, POSITION pos) const
{
#ifdef _DEBUG
	ASSERT( path->GetOwner() == this );
	path->AssertValid();
	ASSERT( path->IsConnected() );
	points.AssertValidPos(pos);
#ifdef _DEBUG_DEEP
//	horizontal.AssertValidPathEdges(path, points);
//	vertical.AssertValidPathEdges(path, points);
#endif
#endif

	POSITION pointpos = pos;
	CPoint point = points.GetNext(pos);
	POSITION npointpos = pos;
	if( npointpos == NULL )
		return false;
	CPoint npoint = points.GetNext(pos);
	POSITION nnpointpos = pos;
	if( nnpointpos == NULL )
		return false;

	pos = pointpos;
	points.GetPrev(pos);
	POSITION ppointpos = pos; if( ppointpos == NULL ) return false;
	CPoint ppoint = points.GetPrev(pos);
	POSITION pppointpos = pos; if( pppointpos == NULL ) return false;
	if( npoint == point) return false; // direction of zero-length edges can't be determined, so don't delete them

	ASSERT( pppointpos != NULL && ppointpos != NULL && pointpos != NULL && npointpos != NULL && nnpointpos != NULL );

	RoutingDirection dir = GetDir(npoint - point);
	ASSERT( IsRightAngle(dir) );
	bool ishorizontal = IsHorizontal(dir);

	CPoint newpoint;
	GetPointCoord(newpoint, ishorizontal) = GetPointCoord(npoint, ishorizontal);
	GetPointCoord(newpoint, !ishorizontal) = GetPointCoord(ppoint, !ishorizontal);

	ASSERT( GetDir(newpoint - ppoint) == dir );

	if( IsLineClipBoxes(newpoint, npoint) ) return false;
	if( IsLineClipBoxes(newpoint, ppoint) ) return false;

	return true;
}

void CAutoRouterGraph::DeleteTwoEdgesAt(CAutoRouterPath* path, CPointListPath& points, POSITION pos)
{
#ifdef _DEBUG
	ASSERT( path->GetOwner() == this );
	path->AssertValid();
	ASSERT( path->IsConnected() );
	points.AssertValidPos(pos);
#ifdef _DEBUG_DEEP
//	horizontal.AssertValidPathEdges(path, points);
//	vertical.AssertValidPathEdges(path, points);
#endif
#endif

	POSITION pointpos = pos;
	CPoint* point = &(points.GetNext(pos));
	POSITION npointpos = pos;
	CPoint* npoint = &(points.GetNext(pos));
	POSITION nnpointpos = pos;
	CPoint* nnpoint = &(points.GetNext(pos));
	POSITION nnnpointpos = pos;
	pos = pointpos;
	points.GetPrev(pos);
	POSITION ppointpos = pos;
	CPoint* ppoint = &(points.GetPrev(pos));
	POSITION pppointpos = pos;
	CPoint* pppoint = &(points.GetAt(pos));

	ASSERT( pppointpos != NULL && ppointpos != NULL && pointpos != NULL && npointpos != NULL && nnpointpos != NULL );
	ASSERT( pppoint != NULL && ppoint != NULL && point != NULL && npoint != NULL && nnpoint != NULL );

	RoutingDirection dir = GetDir(*npoint - *point);
	ASSERT( IsRightAngle(dir) );
	bool ishorizontal = IsHorizontal(dir);

	CPoint newpoint;
	GetPointCoord(newpoint, ishorizontal) = GetPointCoord(*npoint, ishorizontal);
	GetPointCoord(newpoint, !ishorizontal) = GetPointCoord(*ppoint, !ishorizontal);

	ASSERT( GetDir(newpoint - *ppoint) == dir );

	ASSERT( !IsLineClipBoxes(newpoint, *npoint) );
	ASSERT( !IsLineClipBoxes(newpoint, *ppoint) );

	CAutoRouterEdgeList& hlist = GetEdgeList(ishorizontal);
	CAutoRouterEdgeList& vlist = GetEdgeList(!ishorizontal);

	CAutoRouterEdge* ppedge = hlist.GetEdgeByPointer(pppoint, ppoint);
	CAutoRouterEdge* pedge = vlist.GetEdgeByPointer(ppoint, point);
	CAutoRouterEdge* nedge = hlist.GetEdgeByPointer(point, npoint);
	CAutoRouterEdge* nnedge = vlist.GetEdgeByPointer(npoint, nnpoint);

	ASSERT( ppedge != NULL && pedge != NULL && nedge != NULL && nnedge != NULL );

	vlist.Delete(pedge);
	hlist.Delete(nedge);

	points.RemoveAt(pointpos);
	points.RemoveAt(npointpos);
	points.SetAt(ppointpos, newpoint);

	ASSERT( ppedge->GetEndPoint() == *ppoint && ppedge->GetEndPointNext() == *point );
	ppedge->SetEndPointNext(nnpoint);

	ASSERT( nnedge->GetStartPoint() == *npoint && nnedge->GetStartPointPrev() == *point );
	nnedge->SetStartPoint(ppoint);
	nnedge->SetStartPointPrev(pppoint);

	if( nnnpointpos != NULL )
	{
		CAutoRouterEdge* nnnedge = hlist.GetEdgeByPointer(nnpoint, &(points.GetAt(nnnpointpos)));
		ASSERT( nnnedge != NULL );
		ASSERT( nnnedge->GetStartPointPrev() == *npoint && nnnedge->GetStartPoint() == *nnpoint );
		nnnedge->SetStartPointPrev(ppoint);
	}

	if( *nnpoint == newpoint )
		DeleteSamePointsAt(path, points, ppointpos);

#ifdef _DEBUG_DEEP
	path->AssertValid();
	horizontal.AssertValidPathEdges(path, points);
	vertical.AssertValidPathEdges(path, points);
#endif
}

void CAutoRouterGraph::DeleteSamePointsAt(CAutoRouterPath* path, CPointListPath& points, POSITION pos)
{
#ifdef _DEBUG
	ASSERT( path->GetOwner() == this );
	path->AssertValid();
	ASSERT( path->IsConnected() );
	points.AssertValidPos(pos);
#endif

	POSITION pointpos = pos;
	CPoint* point = &(points.GetNext(pos));
	POSITION npointpos = pos;
	CPoint* npoint = &(points.GetNext(pos));
	POSITION nnpointpos = pos;
	CPoint* nnpoint = &(points.GetNext(pos));
	POSITION nnnpointpos = pos;
	pos = pointpos;
	points.GetPrev(pos);
	POSITION ppointpos = pos;
	CPoint* ppoint = &(points.GetPrev(pos));
	POSITION pppointpos = pos;
	CPoint* pppoint = pos == NULL ? NULL : &(points.GetAt(pos));

	ASSERT( ppointpos != NULL && pointpos != NULL && npointpos != NULL && nnpointpos != NULL );
	ASSERT( ppoint != NULL && point != NULL && npoint != NULL && nnpoint != NULL );
	ASSERT( *point == *npoint && *point != *ppoint );

	RoutingDirection dir = GetDir(*point - *ppoint);
	ASSERT( IsRightAngle(dir) );
	bool ishorizontal = IsHorizontal(dir);

	CAutoRouterEdgeList& hlist = GetEdgeList(ishorizontal);
	CAutoRouterEdgeList& vlist = GetEdgeList(!ishorizontal);

	CAutoRouterEdge* pedge = hlist.GetEdgeByPointer(ppoint, point);
	CAutoRouterEdge* nedge = vlist.GetEdgeByPointer(point, npoint);
	CAutoRouterEdge* nnedge = hlist.GetEdgeByPointer(npoint, nnpoint);

	ASSERT( pedge != NULL && nedge != NULL && nnedge != NULL );

	vlist.Delete(pedge);
	hlist.Delete(nedge);

	points.RemoveAt(pointpos);
	points.RemoveAt(npointpos);

	if( pppointpos != NULL )
	{
		CAutoRouterEdge* ppedge = vlist.GetEdgeByPointer(pppoint, ppoint);
		ASSERT( ppedge != NULL && ppedge->GetEndPoint() == *ppoint && ppedge->GetEndPointNext() == *point );
		ppedge->SetEndPointNext(nnpoint);
	}

	ASSERT( nnedge->GetStartPoint() == *npoint && nnedge->GetStartPointPrev() == *point );
	nnedge->SetStartPoint(ppoint);
	nnedge->SetStartPointPrev(pppoint);

	if( nnnpointpos != NULL )
	{
		CAutoRouterEdge* nnnedge = vlist.GetEdgeByPointer(nnpoint, &(points.GetAt(nnnpointpos)));
		ASSERT( nnnedge != NULL && nnnedge->GetStartPointPrev() == *npoint && nnnedge->GetStartPoint() == *nnpoint );
		nnnedge->SetStartPointPrev(ppoint);
	}

#ifdef _DEBUG_DEEP
	path->AssertValid();
//	horizontal.AssertValidPathEdges(path, points);
//	vertical.AssertValidPathEdges(path, points);
#endif
}

bool CAutoRouterGraph::SimplifyPaths()
{
	bool was = false;

	std::vector<CAutoRouterPath*>::iterator iter;
	iter = paths.begin();

	while (iter != paths.end())
	{
		CAutoRouterPath* path = *iter;
		++iter;

		if (path->IsAutoRouted()) {
			CPointListPath& pointList = path->GetPointList();
			POSITION pointpos = pointList.GetHeadPosition();

			while( pointpos != NULL )
			{
				if( CanDeleteTwoEdgesAt(path, pointList, pointpos) )
				{
					DeleteTwoEdgesAt(path, pointList, pointpos);
					was = true;
					break;
				}
				pointList.GetNext(pointpos);
			}
		}
	}

	return was;
}

void CAutoRouterGraph::CenterStairsInPathPoints(CAutoRouterPath* path, RoutingDirection hintstartdir, RoutingDirection hintenddir)
{
	ASSERT( path != NULL );
	ASSERT( !path->IsConnected() );

	CPointListPath& pointList = path->GetPointList();
	ASSERT( pointList.GetCount() >= 2 );

#ifdef _DEBUG
	path->AssertValidPoints();
#endif

	CPoint p1;
	CPoint p2;
	CPoint p3;
	CPoint p4;

	POSITION p1p = NULL;
	POSITION p2p = NULL;
	POSITION p3p = NULL;
	POSITION p4p = NULL;

	RoutingDirection d12 = Dir_None;
	RoutingDirection d23 = Dir_None;
	RoutingDirection d34 = Dir_None;

	const CPoint outOfBoxStartPoint = path->GetOutOfBoxStartPoint(hintstartdir);
	const CPoint outOfBoxEndPoint = path->GetOutOfBoxEndPoint(hintenddir);

	POSITION pos = pointList.GetHeadPosition();
	ASSERT( pos != NULL );

	p1p = pos;
	p1 = pointList.GetNext(pos);

	while( pos != NULL )
	{
		p4p = p3p;
		p3p = p2p;
		p2p = p1p;
		p1p = pos;

		p4 = p3;
		p3 = p2;
		p2 = p1;
		p1 = pointList.GetNext(pos);

		d34 = d23;
		d23 = d12;

		if( p2p != NULL )
		{
			d12 = GetDir(p2 - p1);
#ifdef _DEBUG
			ASSERT( IsRightAngle(d12) );
			if( p3p != NULL )
				ASSERT( AreInRightAngle(d12, d23) );
#endif
		}

		if( p4p != NULL && d12 == d34 )
		{
			ASSERT( p1p != NULL && p2p != NULL && p3p != NULL && p4p != NULL );

			CPoint np2 = p2;
			CPoint np3 = p3;
			bool h = IsHorizontal(d12);

			long p4x = GetPointCoord(p4, h);
			long p3x = GetPointCoord(p3, h);
			long p1x = GetPointCoord(p1, h);

			if( p1x < p4x )
			{
				long t = p1x;
				p1x = p4x;
				p4x = t;
			}

			if( p4x < p3x && p3x < p1x )
			{
				long m = (p4x + p1x)/2;
				GetPointCoord(np2, h) = m;
				GetPointCoord(np3, h) = m;

				GetLimitsOfEdge(np2, np3, p4x, p1x);

				m = (p4x + p1x)/2;
				GetPointCoord(np2, h) = m;
				GetPointCoord(np3, h) = m;

				if( !IsLineClipBoxes(np2, np3) &&
					!IsLineClipBoxes(p1p == pointList.GetTailPosition() ? outOfBoxEndPoint : p1, np2) &&
					!IsLineClipBoxes(p4p == pointList.GetHeadPosition() ? outOfBoxStartPoint : p4, np3) )
				{
					p2 = np2;
					p3 = np3;
					pointList.SetAt(p2p, p2);
					pointList.SetAt(p3p, p3);
				}
			}
		}
	}

#ifdef _DEBUG
	path->AssertValidPoints();
#endif
}

void CAutoRouterGraph::SimplifyPathPoints(CAutoRouterPath* path)
{
	ASSERT( path != NULL );
	ASSERT( !path->IsConnected() );

	CPointListPath& pointList = path->GetPointList();
	ASSERT( pointList.GetCount() >= 2 );

#ifdef _DEBUG
	path->AssertValidPoints();
#endif

	CPoint p1;
	CPoint p2;
	CPoint p3;
	CPoint p4;
	CPoint p5;

	POSITION p1p = NULL;
	POSITION p2p = NULL;
	POSITION p3p = NULL;
	POSITION p4p = NULL;
	POSITION p5p = NULL;

	POSITION pos = pointList.GetHeadPosition();
	ASSERT( pos != NULL );

	p1p = pos;
	p1 = pointList.GetNext(pos);

	while( pos != NULL )
	{
		p5p = p4p;
		p4p = p3p;
		p3p = p2p;
		p2p = p1p;
		p1p = pos;

		p5 = p4;
		p4 = p3;
		p3 = p2;
		p2 = p1;
		p1 = pointList.GetNext(pos);

		if( p5p != NULL )
		{
			ASSERT( p1p != NULL && p2p != NULL && p3p != NULL && p4p != NULL && p5p != NULL );
			ASSERT( p1 != p2 && p2 != p3 && p3 != p4 && p4 != p5 );

			RoutingDirection d = GetDir(p2 - p1);
			ASSERT( IsRightAngle(d) );
			bool h = IsHorizontal(d);

			CPoint np3;
			GetPointCoord(np3, h) = GetPointCoord(p5, h);
			GetPointCoord(np3, !h) = GetPointCoord(p1, !h);

			if( !IsLineClipBoxes(p2, np3) && !IsLineClipBoxes(np3, p4) )
			{
				pointList.RemoveAt(p2p);
				pointList.RemoveAt(p4p);
				pointList.SetAt(p3p, np3);
				if( np3 == p1 )
					pointList.RemoveAt(p1p);
				if( np3 == p5 )
					pointList.RemoveAt(p5p);

				p1p = NULL;
				p2p = NULL;
				p3p = NULL;
				p4p = NULL;

				pos = pointList.GetHeadPosition();
			}
		}
	}

#ifdef _DEBUG
	path->AssertValidPoints();
#endif
}

void CAutoRouterGraph::ConnectAllDisconnectedPaths()
{
	std::vector<CAutoRouterPath*>::iterator iter;

	bool success = false;
	bool giveup = false;
	while (!success && !giveup) {
		success = true;
		iter = paths.begin();
		while (iter != paths.end() && success)
		{
			CAutoRouterPath* path = *iter;

			if( !path->IsConnected() )
			{
				success = Connect(path);
				if (!success) {
					// Something is messed up, probably an existing edge customization results in a zero length edge
					// In that case we try to delete any customization for this path to recover from the problem
					if (path->AreTherePathCustomizations())
						path->RemovePathCustomizations();
					else
						giveup = true;
				}
			}

			++iter;
		}
		if (!success && !giveup)
			DisconnectAll();	// There was an error, delete halfway results to be able to start a new pass
	}
}

// --- SelfPoints

void CAutoRouterGraph::CalculateSelfPoints()
{
	selfpoints[0].x = ED_MINCOORD;
	selfpoints[0].y = ED_MINCOORD;

	selfpoints[1].x = ED_MAXCOORD;
	selfpoints[1].y = ED_MINCOORD;

	selfpoints[2].x = ED_MAXCOORD;
	selfpoints[2].y = ED_MAXCOORD;

	selfpoints[3].x = ED_MINCOORD;
	selfpoints[3].y = ED_MAXCOORD;
}

CAutoRouterBox* CAutoRouterGraph::CreateBox(void) const
{
	CAutoRouterBox* box = new CAutoRouterBox();
	ASSERT( box != NULL );

	return box;
}

void CAutoRouterGraph::AddBox(CAutoRouterBox* box)
{
	ASSERT(box != NULL);
	if (box == NULL)
		return;

	const CRect rect = box->GetRect();

	DisconnectPathsClipping(rect);

	box->SetOwner(this);

	boxes.push_back(box);

	AddBoxAndPortEdges(box);
}

void CAutoRouterGraph::DeleteBox(CAutoRouterBox* box)
{
	ASSERT(box != NULL);
	if (box == NULL)
		return;

	if( box->HasOwner() )
	{
		Remove(box);
	}
	
	box->Destroy();
	delete box;
}

void CAutoRouterGraph::ShiftBoxBy(CAutoRouterBox* box, const CPoint& offset)
{
	ASSERT(box != NULL);
	if (box == NULL)
		return;

	DeleteBoxAndPortEdges(box);
	box->ShiftBy(offset);
	AddBoxAndPortEdges(box);

	const CRect rect = box->GetRect();
	DisconnectPathsClipping(rect);
	DisconnectPathsFrom(box);
}

long CAutoRouterGraph::AutoRoute(long aspect)
{
	ConnectAllDisconnectedPaths();

	int updated = 0;
	int last = 0;
	int c = 100;		// max # of total op
	int dm = 10;		// max # of distribution op
	int d = 0;

	while( c > 0 )
	{
		if( c > 0 )
		{
			if( last == 1 )
				break;

			c--;
			if( SimplifyPaths() )
			{
				updated = 1;
				last = 1;
			}
		}

		if( c > 0 )
		{
			if( last == 2 )
				break;

			c--;
			if( horizontal.Block_ScanBackward() )
			{
				updated = 1;

				do {
					c--;
				} while( c > 0 && horizontal.Block_ScanBackward() );

				if( last < 2 || last > 5 )
					d = 0;
				else if( ++d >= dm )
					break;

				last = 2;
			}
		}

		if( c > 0 )
		{
			if( last == 3 )
				break;

			c--;
			if( horizontal.Block_ScanForward() )
			{
				updated = 1;

				do {
					c--;
				} while( c > 0 && horizontal.Block_ScanForward() );

				if( last < 2 || last > 5 )
					d = 0;
				else if( ++d >= dm )
					break;

				last = 3;
			}
		}

		if( c > 0 )
		{
			if( last == 4 )
				break;

			c--;
			if( vertical.Block_ScanBackward() )
			{
				updated = 1;

				do
				c--;
				while( c > 0 && vertical.Block_ScanBackward() );

				if( last < 2 || last > 5 )
					d = 0;
				else if( ++d >= dm )
					break;

				last = 4;
			}
		}

		if( c > 0 )
		{
			if( last == 5 )
				break;

			c--;
			if( vertical.Block_ScanForward() )
			{
				updated = 1;

				do
				c--;
				while( c > 0 && vertical.Block_ScanForward() );

				if( last < 2 || last > 5 )
					d = 0;
				else if( ++d >= dm )
					break;

				last = 5;
			}
		}

		if( c > 0 )
		{
			if( last == 6 )
				break;

			c--;
			if( horizontal.Block_SwitchWrongs() )
			{
				updated = 1;
				last = 6;
			}
		}

		if( c > 0 )
		{
			if( last == 7 )
				break;

			c--;
			if( vertical.Block_SwitchWrongs() )
			{
				updated = 1;
				last = 7;
			}
		}

		if( last == 0 )
			break;
	}

	if( c <= 0 )
	{
		// MessageBeep(MB_ICONEXCLAMATION);
		updated = -1;
	}

	// Check customized connection if there's any clip against boxes
	{
		std::vector<CAutoRouterPath*>::iterator pathiter;
		pathiter = paths.begin();

		HRESULT hr = S_OK;
		while (pathiter != paths.end())
		{
			CAutoRouterPath* path = *pathiter;

			if (path->IsAutoRouted()) {	// comment this if you want the check to run for fully customizable connections
				if (path->AreTherePathCustomizations())
				{
					const CRect startBoxRect = path->GetStartBox();
					const CRect endBoxRect = path->GetEndBox();

					std::vector<CAutoRouterBox*>::const_iterator boxiter = boxes.begin();

					while (boxiter != boxes.end())
					{
						const CRect boxRect = (*boxiter)->GetRect();
						bool isStartOrEndRect = (!startBoxRect.IsRectEmpty() && IsRectIn(startBoxRect, boxRect) ||
												 !endBoxRect.IsRectEmpty() && IsRectIn(endBoxRect, boxRect));
						if (path->IsPathClip(boxRect, isStartOrEndRect))
						{
							path->MarkPathCustomizationsForDeletion(aspect);
							updated = -2;
						}

						++boxiter;
					}
				}
			}

			++pathiter;
		}
	}

	return updated;
}

void CAutoRouterGraph::DeletePath(CAutoRouterPath* path)
{
	ASSERT(path != NULL);
	if (path == NULL)
		return;

	if( path->HasOwner() )
	{
		ASSERT( path->GetOwner() == this );

		Remove(path);
	}

	path->Destroy();
	delete path;
}

void CAutoRouterGraph::DeleteAll(bool addBackSelfEdges)
{
	DeleteAllPaths();
	DeleteAllBoxes();
	DeleteAllEdges();
	if (addBackSelfEdges)
		AddSelfEdges();
}

CAutoRouterPath* CAutoRouterGraph::GetPathAt(const CPoint& point, long nearness)
{
	std::vector<CAutoRouterPath*>::iterator iter;
	iter = paths.begin();

	while (iter != paths.end())
	{
		CAutoRouterPath* path = *iter;

		if( path->IsPathAt(point, nearness) )
			return path;

		++iter;
	}

	return NULL;
}

CAutoRouterPath* CAutoRouterGraph::AddPath(bool isAutoRouted, CAutoRouterPort* startport, CAutoRouterPort* endport)
{
	CAutoRouterPath* path = new CAutoRouterPath();

	path->SetAutoRouting(isAutoRouted);
	path->SetStartPort(startport);
	path->SetEndPort(endport);
	Add(path);

	return path;
}

bool CAutoRouterGraph::IsEdgeFixed(CAutoRouterPath* path, const CPoint& startpoint, const CPoint& endpoint)
{
	RoutingDirection d = GetDir(endpoint - startpoint);
	bool h = IsHorizontal(d);

	CAutoRouterEdgeList& elist = GetEdgeList(h);

	CAutoRouterEdge* edge = elist.GetEdge(path, startpoint, endpoint);
	if (edge != NULL)
		return edge->GetEdgeFixed() && !edge->GetEdgeCustomFixed();

	ASSERT(false);
	return true;
}

CPoint* CAutoRouterGraph::GetSelfPoints(void) const
{
	return (CPoint*)selfpoints;
}

void CAutoRouterGraph::Destroy(void)
{
	DeleteAll(false);

	horizontal.SetOwner(NULL);
	vertical.SetOwner(NULL);
}

#ifdef _DEBUG
void CAutoRouterGraph::AssertValid() const
{
	std::vector<CAutoRouterBox*>::const_iterator iter = boxes.begin();

	while (iter != boxes.end())
	{
		AssertValidBox(*iter);
		++iter;
	}

	std::vector<CAutoRouterPath*>::const_iterator iter2 = paths.begin();
	
	while(iter2 != paths.end())
	{
		AssertValidPath(*iter2);
		++iter2;
	}
}

void CAutoRouterGraph::AssertValidBox(CAutoRouterBox* box) const
{
	box->AssertValid();
	ASSERT( box->GetOwner() == this );

	std::vector<CAutoRouterBox*>::const_iterator iter = std::find(boxes.begin(), boxes.end(), box);
	ASSERT (iter != boxes.end());
}

void CAutoRouterGraph::AssertValidPath(CAutoRouterPath* path) const
{
	path->AssertValid();
	ASSERT( path->GetOwner() == this );

	std::vector<CAutoRouterPath*>::const_iterator iter = std::find(paths.begin(), paths.end(), path);
	ASSERT (iter != paths.end());

	CPointListPath& pointList = path->GetPointList();

	CAutoRouterPort* startPort = path->GetStartPort();
	ASSERT(startPort != NULL);
	startPort->AssertValid();
	CAutoRouterBox* ownerBox = startPort->GetOwner();
	CAutoRouterGraph* boxOwnerGraph = ownerBox->GetOwner();
	ASSERT( boxOwnerGraph == this );
	ownerBox->AssertValidPort(startPort);

	if( path->IsConnected() )
		startPort->AssertValidStartEndPoint(pointList.GetHead(), Dir_None, 1);

	CAutoRouterPort* endPort = path->GetEndPort();
	ASSERT(endPort != NULL);
	endPort->AssertValid();
	CAutoRouterBox* ownerBox2 = endPort->GetOwner();
	ASSERT( ownerBox2->GetOwner() == this );
	ownerBox2->AssertValidPort(endPort);

	if( path->IsConnected() )
	{
		endPort->AssertValidStartEndPoint(pointList.GetTail(), Dir_None, 0);
	}
	else
	{
		ASSERT( path->HasNoPoint() );
	}

	path->AssertValidPoints();

	if( !pointList.IsEmpty() )
	{
		ASSERT( pointList.GetCount() >= 2 );
		POSITION pos = pointList.GetHeadPosition();
		ASSERT( pos != NULL );

		ASSERT( IsPointInBox(pointList.GetNext(pos)) );

		while( pos != NULL )
		{
			CPoint p = pointList.GetNext(pos);
			if( pos != NULL )
				ASSERT( !IsPointInBox(p) );
			else
				ASSERT( IsPointInBox(p) );
		}
	}
}

void CAutoRouterGraph::DumpPaths(int pos, int c)
{
	TRACE2("Paths dump pos %ld, c %ld:\n", pos, c);
	std::vector<CAutoRouterPath*>::iterator iter;
	iter = paths.begin();
	int i = 0;

	while (iter != paths.end())
	{
		TRACE1("%ld. Path:\n", i);
		(*iter)->GetPointList().DumpPoints("DumpPaths");

		++iter;
		i++;
	}

	DumpEdgeLists();
}

void CAutoRouterGraph::DumpEdgeLists(void)
{
#ifdef _DEBUG_DEEP
	horizontal.DumpEdges("Horizontal edges:");
	vertical.DumpEdges("Vertical edges:");
#endif
}
#endif

// CAutoRouterGraph
