// AutoRouterGraph.cpp : Implementation of CAutoRouterGraph

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


// #define ASSERT(x) do { if (!(x)) DebugBreak(); } while (false)

// --- 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
				// or this assert fails if two boxes are overlapping. This can happen if the decorator got bigger (e.g. due to ports change) and now the boxes overlap (and we forgot to reset the model grid)
				ASSERT( IsPointInDirFrom(start, rect, dir2) );
				// avoid infinite loop by giving up
				if (!IsPointInDirFrom(start, rect, dir2)) {
					retend = ret.InsertAfter(retend, end);
					return;
				}
			}
			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
