
#include "stdafx.h"
#include "afxcoll.h"
#include "afxtempl.h"
#include "float.h"

#include <map>

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

#define EDLS_S (ED_SMALLGAP)
#define EDLS_R (ED_SMALLGAP+1)
#define EDLS_D (ED_MAXCOORD-ED_MINCOORD)

/*
	In this file every comments refer to the horizontal case, that is, each	edge is
	horizontal.
*/

/*
	Every CAutoRouterEdge belongs to an edge of a CAutoRouterPath, CAutoRouterBox or CAutoRouterPort. This edge is
	Represented by a CAutoRouterPoint with its next point. The variable 'point' will refer
	to this CAutoRouterPoint.

	The coordinates of an edge are 'x1', 'x2' and 'y' where x1/x2 is the x-coordinate
	of the left/right point, and y is the common y-coordinate of the points.

	The edges are ordered according to their y-coordinates. The first edge has
	the least y-coordinate (topmost), and its pointer is in 'order_first'.
	We use the 'order' prefix in the variable names to refer to this order.

	We will walk from top to bottom (from the 'order_first' along the 'order_next').
	We keep track a "section" of some edges. If we have an infinite horizontal line,
	then the section consists of those edges that are above the line and not blocked
	by another edge which is closer to the line. Each edge in the section has
	a viewable portion from the line (the not blocked portion). The coordinates
	of this portion are 'section_x1' and 'section_x2'. We have an order of the edges
	belonging to the current section. The 'section_first' refers to the leftmost
	edge in the section, while the 'section_next' to the next from left to right.

	We say that the CAutoRouterEdge E1 "precede" the CAutoRouterEdge E2 if there is no other CAutoRouterEdge which
	totally	blocks S1 from S2. So a section consists of the preceding edges of an 
	infinite edge. We say that E1 is "adjacent" to E2, if E1 is the nearest edge
	to E2 which precede it. Clearly, every edge has at most one adjacent precedence.

	The edges of any CAutoRouterBox or CAutoRouterPort are fixed. We will continually fix the edges
	of the CAutoRouterPaths. But first we need some definition.

	We call a set of edges as a "block" if the topmost (first) and bottommost (last)
	edges of it are fixed while the edges between them are not. Furthermore, every
	edge is adjacent to	the next one in the order. Every edge in the block has an
	"index". The index of the first one (topmost) is 0, of the second is 1, and so on.
	We call the index of the last edge (# of edges - 1) as the index of the entire box.
	The "depth" of a block is the difference of the y-coordinates of the first and last
	edges of it. The "goal gap" of the block is the quotient of the depth and index
	of the block. If the difference of the y-coordinates of the adjacent edges in
	the block are all equal to the goal gap, then we say that the block is evenly
	distributed.

	So we search the block which has minimal goal gap. Then if it is not evenly
	distributed, then we shift the not fixed edges to the desired position. It is
	not hard to see	that if the block has minimal goal gap (among the all
	possibilities of blocks), then in this way we do not move any edges into boxes.
	Finally, we set the (inner) edges of the block to be fixed (except the topmost and 
	bottommost edges, since they are already fixed). And we again begin the search.
	If every edge is fixed, then we have finished. This is the basic idea. We will
	refine this algorithm.

	The variables related to the blocks are prefixed by 'block'. Note that the 
	variables of an edge are refer to that block in which this edge is inner! The
	'block_oldgap' is the goal gap of the block when it was last evenly distributed.

	The variables 'canstart' and 'canend' means that this egde can start and/or end
	a block. The top edge of a box only canend, while a fixed edge of a path can both
	start and end of a block.

*/


// --------------------------- CAutoRouterEdge

CAutoRouterEdge::CAutoRouterEdge()
{
	this->owner				= NULL;

	this->startpoint_prev	= NULL;
	this->startpoint		= NULL;
	this->endpoint			= NULL;
	this->endpoint_next		= NULL;

	this->position_y		= 0;
	this->position_x1		= 0;
	this->position_x2		= 0;
	this->bracket_closing	= 0;
	this->bracket_opening	= 0;

	this->order_prev		= NULL;
	this->order_next		= NULL;

	this->edge_fixed		= 0;
	this->edge_customFixed	= 0;
	this->edge_canpassed	= 0;

	this->position_y		= 0;

	this->block_prev		= NULL;
	this->block_next		= NULL;
	this->block_trace		= NULL;

	this->closest_prev		= NULL;
	this->closest_next		= NULL;
}

CAutoRouterEdge::~CAutoRouterEdge()
{
}

CObject* CAutoRouterEdge::GetOwner(void) const
{
	return owner;
}

void CAutoRouterEdge::SetOwner(CObject* owner)
{
	this->owner = owner;
}

CPoint CAutoRouterEdge::GetStartPointPrev(void) const
{
	return startpoint_prev == NULL ? emptyPoint : *startpoint_prev;
}

bool CAutoRouterEdge::IsStartPointPrevNull(void) const
{
	return startpoint_prev == NULL;
}

void CAutoRouterEdge::SetStartPointPrev(CPoint* point)
{
	startpoint_prev = point;
}

CPoint CAutoRouterEdge::GetStartPoint(void) const
{
	return startpoint == NULL ? emptyPoint : *startpoint;
}

bool CAutoRouterEdge::IsSameStartPointByPointer(const CPoint* point) const
{
	return startpoint == point;
}

bool CAutoRouterEdge::IsStartPointNull(void) const
{
	return startpoint == NULL;
}

void CAutoRouterEdge::SetStartPoint(CPoint* point)
{
	startpoint = point;
	RecalculateDirection();
}

void CAutoRouterEdge::SetStartPointX(int x)
{
	startpoint->x = x;
}

void CAutoRouterEdge::SetStartPointY(int y)
{
	startpoint->y = y;
}

CPoint CAutoRouterEdge::GetEndPoint(void) const
{
	return endpoint == NULL ? emptyPoint : *endpoint;
}

bool CAutoRouterEdge::IsEndPointNull(void) const
{
	return endpoint == NULL;
}

void CAutoRouterEdge::SetEndPoint(CPoint* point)
{
	endpoint = point;
	RecalculateDirection();
}

void CAutoRouterEdge::SetStartAndEndPoint(CPoint* startPoint, CPoint* endPoint)
{
	startpoint = startPoint;
	endpoint = endPoint;
	RecalculateDirection();
}

void CAutoRouterEdge::SetEndPointX(int x)
{
	endpoint->x = x;
}

void CAutoRouterEdge::SetEndPointY(int y)
{
	endpoint->y = y;
}

CPoint CAutoRouterEdge::GetEndPointNext(void) const
{
	return endpoint_next == NULL ? emptyPoint : *endpoint_next;
}

bool CAutoRouterEdge::IsEndPointNextNull(void) const
{
	return endpoint_next == NULL;
}

void CAutoRouterEdge::SetEndPointNext(CPoint* point)
{
	endpoint_next = point;
}

float CAutoRouterEdge::GetPositionY(void) const
{
	return position_y;
}

void CAutoRouterEdge::SetPositionY(float y)
{
	position_y = y;
}

void CAutoRouterEdge::AddToPositionY(float dy)
{
	position_y += dy;
}

int CAutoRouterEdge::GetPositionX1(void) const
{
	return position_x1;
}

void CAutoRouterEdge::SetPositionX1(int x1)
{
	position_x1 = x1;
}

int CAutoRouterEdge::GetPositionX2(void) const
{
	return position_x2;
}

void CAutoRouterEdge::SetPositionX2(int x2)
{
	position_x2 = x2;
}

bool CAutoRouterEdge::GetBracketClosing(void) const
{
	return bracket_closing;
}

void CAutoRouterEdge::SetBracketClosing(bool b)
{
	bracket_closing = b;
}

bool CAutoRouterEdge::GetBracketOpening(void) const
{
	return bracket_opening;
}

void CAutoRouterEdge::SetBracketOpening(bool b)
{
	bracket_opening = b;
}

CAutoRouterEdge* CAutoRouterEdge::GetOrderNext(void)
{
	return order_next;
}

void CAutoRouterEdge::SetOrderNext(CAutoRouterEdge* ordernext)
{
	order_next = ordernext;
}

CAutoRouterEdge* CAutoRouterEdge::GetOrderPrev(void)
{
	return order_prev;
}

void CAutoRouterEdge::SetOrderPrev(CAutoRouterEdge* orderprev)
{
	order_prev = orderprev;
}

long CAutoRouterEdge::GetSectionX1(void)
{
	return section_x1;
}

void CAutoRouterEdge::SetSectionX1(long x1)
{
	section_x1 = x1;
}

long CAutoRouterEdge::GetSectionX2(void)
{
	return section_x2;
}

void CAutoRouterEdge::SetSectionX2(long x2)
{
	section_x2 = x2;
}

CAutoRouterEdge* CAutoRouterEdge::GetSectionNext(void)
{
	return section_next;
}

CAutoRouterEdge** CAutoRouterEdge::GetSectionNextPtr(void)
{
	return &section_next;
}

void CAutoRouterEdge::SetSectionNext(CAutoRouterEdge* sectionnext)
{
	section_next = sectionnext;
}

CAutoRouterEdge* CAutoRouterEdge::GetSectionDown(void)
{
	return section_down;
}

CAutoRouterEdge** CAutoRouterEdge::GetSectionDownPtr(void)
{
	return &section_down;
}

void CAutoRouterEdge::SetSectionDown(CAutoRouterEdge* sectiondown)
{
	section_down = sectiondown;
}

bool CAutoRouterEdge::GetEdgeFixed(void)
{
	return edge_fixed;
}

void CAutoRouterEdge::SetEdgeFixed(bool ef)
{
	edge_fixed = ef;
}

bool CAutoRouterEdge::GetEdgeCustomFixed(void)
{
	return edge_customFixed;
}

void CAutoRouterEdge::SetEdgeCustomFixed(bool ecf)
{
	edge_customFixed = ecf;
}

bool CAutoRouterEdge::GetEdgeCanpassed(void)
{
	return edge_canpassed;
}

void CAutoRouterEdge::SetEdgeCanpassed(bool ecp)
{
	edge_canpassed = ecp;
}

RoutingDirection CAutoRouterEdge::GetDirection(void)
{
	return edge_direction;
}

void CAutoRouterEdge::SetDirection(RoutingDirection dir)
{
	edge_direction = dir;
}

void CAutoRouterEdge::RecalculateDirection(void)
{
	ASSERT(startpoint != NULL && endpoint != NULL);
	edge_direction = GetDir(*endpoint - *startpoint);
}

CAutoRouterEdge* CAutoRouterEdge::GetBlockPrev(void)
{
	return block_prev;
}

void CAutoRouterEdge::SetBlockPrev(CAutoRouterEdge* bp)
{
	block_prev = bp;
}

CAutoRouterEdge* CAutoRouterEdge::GetBlockNext(void)
{
	return block_next;
}

void CAutoRouterEdge::SetBlockNext(CAutoRouterEdge* bn)
{
	block_next = bn;
}

CAutoRouterEdge* CAutoRouterEdge::GetBlockTrace(void)
{
	return block_trace;
}

void CAutoRouterEdge::SetBlockTrace(CAutoRouterEdge* bt)
{
	block_trace = bt;
}

CAutoRouterEdge* CAutoRouterEdge::GetClosestPrev(void)
{
	return closest_prev;
}

void CAutoRouterEdge::SetClosestPrev(CAutoRouterEdge* cp)
{
	closest_prev = cp;
}

CAutoRouterEdge* CAutoRouterEdge::GetClosestNext(void)
{
	return closest_next;
}

void CAutoRouterEdge::SetClosestNext(CAutoRouterEdge* cn)
{
	closest_next = cn;
}


// --------------------------- CAutoRouterEdgeList


CAutoRouterEdgeList::CAutoRouterEdgeList(bool h)
{
	owner = NULL;

	ishorizontal = (h != 0);

	Init_Order();
	Init_Section();
}

CAutoRouterEdgeList::~CAutoRouterEdgeList()
{
	Check_Order();
	Check_Section();
}

void CAutoRouterEdgeList::SetOwner(CAutoRouterGraph* o)
{
	owner = o;
}

// --- Edges

typedef std::pair<long,long> Long_Pair;

bool CAutoRouterEdgeList::AddEdges(CAutoRouterPath* path)
{
	ASSERT_VALID(path);
	ASSERT( path->GetOwner() == owner );
	ASSERT_VALID( path->GetStartPort() );
	ASSERT_VALID( path->GetEndPort() );

	bool isPathAutoRouted = path->IsAutoRouted();
	// Apply custom edge modifications - step 2, part 1
	// (Step 1: Move the desired edges
	//  Step 2: Fix the desired edges)
	bool hasCustomEdge = false;
	std::map<long,long> customizedIndexes;	// convert array to a map for easier lookup
	std::vector<int> indexes;
	path->GetCustomizedEdgeIndexes(indexes);

	if (isPathAutoRouted) {
		std::vector<int>::iterator ii = indexes.begin();
		while (ii != indexes.end()) {
			hasCustomEdge = true;
			customizedIndexes.insert(Long_Pair(*ii, 0));
			++ii;
		}
	} else {
		hasCustomEdge = true;
	}

	std::map<long,long>::const_iterator indIter;
	CPointListPath& pointList = path->GetPointList();
	long currEdgeIndex = pointList.GetSize() - 2;

	CPoint* startpoint = NULL;
	CPoint* endpoint = NULL;

	POSITION pos = pointList.GetTailEdgePtrs(startpoint, endpoint);
	while( pos != NULL )
	{
		RoutingDirection dir = GetDir(*endpoint - *startpoint);

		bool skipEdge = false;
		if (dir == Dir_None)
			skipEdge = true;
		bool isMovable = path->IsMoveable();
		if( !isMovable && dir != Dir_Skew)
		{
			bool goodAngle = IsRightAngle(dir);
			ASSERT( goodAngle );
			if (!goodAngle)
				skipEdge = true;
		}

		if( !skipEdge &&
			(//dir == Dir_Skew || -> do not add skew lines now, auto routing cannot do anything with it
			 IsRightAngle(dir) && IsHorizontal(dir) == ishorizontal) )
		{
			CAutoRouterEdge* edge = new CAutoRouterEdge();

			edge->SetOwner(path);

			edge->SetStartAndEndPoint(startpoint, endpoint);
			edge->SetStartPointPrev(pointList.GetPointBeforeEdge(pos));
			edge->SetEndPointNext(pointList.GetPointAfterEdge(pos));

			// Apply custom edge modifications - step 2, part 2
			if (hasCustomEdge)
			{
				bool isEdgeCustomFixed = false;
				if (isPathAutoRouted) {
					indIter = customizedIndexes.find(currEdgeIndex);
					isEdgeCustomFixed = (indIter != customizedIndexes.end());
				} else {
					isEdgeCustomFixed = true;
				}
				edge->SetEdgeCustomFixed(isEdgeCustomFixed);
			}
			else
			{
				edge->SetEdgeCustomFixed(dir == Dir_Skew);
			}

			CAutoRouterPort* startPort = path->GetStartPort();
			ASSERT(startPort != NULL);
			bool isStartPortConnectToCenter = startPort->IsConnectToCenter();

			CAutoRouterPort* endPort = path->GetEndPort();
			ASSERT(endPort != NULL);
			bool isEndPortConnectToCenter = endPort->IsConnectToCenter();
			bool isPathFixed = path->IsFixed();
			edge->SetEdgeFixed(edge->GetEdgeCustomFixed() || isPathFixed || 
				(edge->IsStartPointPrevNull() && isStartPortConnectToCenter) ||
				(edge->IsEndPointNextNull() && isEndPortConnectToCenter));

			if (dir != Dir_Skew)
			{
				Position_LoadY(edge);
				Position_LoadB(edge);
			}
			else
			{
				edge->SetPositionY(0.0);
				edge->SetBracketOpening(false);
				edge->SetBracketClosing(false);
			}
			Insert(edge);
		}

		pointList.GetPrevEdgePtrs(pos, startpoint, endpoint);
		currEdgeIndex--;
	}

	return true;
}

CAutoRouterEdge* CAutoRouterEdgeList::GetEdge(CAutoRouterPath* path, const CPoint& startpoint, const CPoint& endpoint) const
{
	CAutoRouterEdge* edge = order_first;
	while( edge != NULL )
	{
		if( edge->GetStartPoint() == startpoint )
		{
			if( edge->GetOwner() == path )
				break;
		}

		edge = edge->GetOrderNext();
	}

	ASSERT( edge != NULL );
	return edge;
}

CAutoRouterEdge* CAutoRouterEdgeList::GetEdgeByPointer(const CPoint* startpoint, const CPoint* endpoint) const
{
	CAutoRouterEdge* edge = order_first;
	while( edge != NULL )
	{
		if( edge->IsSameStartPointByPointer(startpoint) )
		{
			break;
		}

		edge = edge->GetOrderNext();
	}

	ASSERT( edge != NULL );
	return edge;
}

CAutoRouterEdge* CAutoRouterEdgeList::GetEdgeAt(const CPoint& point, int nearness) const
{
	CAutoRouterEdge* edge = order_first;
	while( edge )
	{
		if( IsPointNearLine(point, edge->GetStartPoint(), edge->GetEndPoint(), nearness) )
			return edge;

		edge = edge->GetOrderNext();
	}

	return NULL;
}

#ifdef _DEBUG

void CAutoRouterEdgeList::AssertValidPathEdges(CAutoRouterPath* path, CPointListPath& points) const
{
	ASSERT( path != NULL );
	CAutoRouterGraph* ownerGraph = path->GetOwner();
	ASSERT( ownerGraph == owner );

	CPoint* startpoint = NULL;
	CPoint* endpoint = NULL;

	POSITION pos = points.GetTailEdgePtrs(startpoint, endpoint);
	while( pos != NULL )
	{
		RoutingDirection dir = GetDir(*endpoint - *startpoint);

		if( path->IsMoveable() )
			ASSERT( IsRightAngle(dir) );

		if( IsRightAngle(dir) && IsHorizontal(dir) == ishorizontal )
		{
			CAutoRouterEdge* edge = GetEdgeByPointer(startpoint, endpoint);
			ASSERT( edge != NULL );

			ASSERT( edge->GetOwner() == path );

			ASSERT( edge->GetStartPoint() == *startpoint );
			ASSERT( edge->GetEndPoint() == *endpoint );
			if (edge->IsStartPointPrevNull())
				ASSERT( points.GetPointBeforeEdge(pos) == NULL );
			else
				ASSERT( edge->GetStartPointPrev() == *(points.GetPointBeforeEdge(pos)) );
			if (edge->IsEndPointNextNull())
				ASSERT( points.GetPointAfterEdge(pos) == NULL );
			else
				ASSERT( edge->GetEndPointNext() == *(points.GetPointAfterEdge(pos)) );
		}

		points.GetPrevEdgePtrs(pos, startpoint, endpoint);
	}

	CAutoRouterEdge* edge = order_first;
	while( edge != NULL )
	{
		if( edge->GetOwner() == path )
		{
			POSITION pos = points.GetEdgePosForStartPoint(edge->GetStartPoint());
			ASSERT( pos != NULL );
			ASSERT( *(points.GetStartPoint(pos)) == edge->GetStartPoint() );
			ASSERT( *(points.GetEndPoint(pos)) == edge->GetEndPoint() );
			if (edge->IsStartPointPrevNull())
				ASSERT( points.GetPointBeforeEdge(pos) == NULL );
			else
				ASSERT( *(points.GetPointBeforeEdge(pos)) == edge->GetStartPointPrev() );
			if (edge->IsEndPointNextNull())
				ASSERT( points.GetPointAfterEdge(pos) == NULL );
			else
				ASSERT( *(points.GetPointAfterEdge(pos)) == edge->GetEndPointNext() );
		}

		edge = edge->GetOrderNext();
	}
}

void CAutoRouterEdgeList::DumpEdges(const CString& headMsg)
{
#ifdef _DEBUG_DEEP
	TRACE0(headMsg + "\n");
	CAutoRouterEdge* edge = order_first;
	int i = 0;
	while( edge != NULL )
	{
		TRACE1("\t %ld.: ", i);
		TRACE2("sp %ld, %ld ", edge->IsStartPointNull() ? -1 : edge->GetStartPoint().x, edge->IsStartPointNull() ? -1 : edge->GetStartPoint().y);
		TRACE2("ep %ld, %ld ", edge->IsEndPointNull() ? -1 : edge->GetEndPoint().x, edge->IsEndPointNull() ? -1 : edge->GetEndPoint().y);
		TRACE2("spp %ld, %ld ", edge->IsStartPointPrevNull() ? -1 : edge->GetStartPointPrev().x, edge->IsStartPointPrevNull() ? -1 : edge->GetStartPointPrev().y);
		TRACE2("epn %ld, %ld\n", edge->IsEndPointNextNull() ? -1 : edge->GetEndPointNext().x, edge->IsEndPointNextNull() ? -1 : edge->GetEndPointNext().y);
		TRACE0("\t\t");
		TRACE3("py %f px1 %ld px2 %ld ", edge->GetPositionY(), edge->GetPositionX1(), edge->GetPositionX2());
		TRACE2("bc %ld bo %ld ", edge->GetBracketClosing(), edge->GetBracketOpening());
		TRACE2("sx1 %ld sx2 %ld ", edge->GetSectionX1(), edge->GetSectionX2());
		TRACE2("f %d cp %d\n", edge->GetEdgeFixed(), edge->GetEdgeCanpassed());

		edge = edge->GetOrderNext();
		i++;
	}
#endif
}

#endif

void CAutoRouterEdgeList::AddEdges(CAutoRouterPort* port)
{
	ASSERT_VALID(port);
	ASSERT( port->GetOwner()->GetOwner() == owner );

	if (port->IsConnectToCenter() || port->GetOwner()->IsAtomic())
		return;

	CPoint* selfpoints = port->GetSelfPoints();

	for(int i = 0; i < 4; i++)
	{
		CPoint* startpoint_prev = &(selfpoints[(i + 3) % 4]);
		CPoint* startpoint = &(selfpoints[i]);
		CPoint* endpoint = &(selfpoints[(i + 1) % 4]);
		CPoint* endpoint_next = &(selfpoints[(i + 2) % 4]);

		RoutingDirection dir = GetDir(*endpoint - *startpoint);
		ASSERT( IsRightAngle(dir) );

		bool canHaveStartEndPointHorizontal = port->CanHaveStartEndPointHorizontal(ishorizontal);
		if( IsHorizontal(dir) == ishorizontal && canHaveStartEndPointHorizontal )
		{
			CAutoRouterEdge* edge = new CAutoRouterEdge();

			edge->SetOwner(port);

			edge->SetStartAndEndPoint(startpoint, endpoint);
			edge->SetStartPointPrev(startpoint_prev);
			edge->SetEndPointNext(endpoint_next);

			edge->SetEdgeFixed(true);

			Position_LoadY(edge);
			Position_LoadB(edge);

			if( edge->GetBracketClosing() )
				edge->AddToPositionY(0.999F);

			Insert(edge);
		}
	}
}

void CAutoRouterEdgeList::AddEdges(CAutoRouterBox* box)
{
	ASSERT_VALID(box);
	ASSERT( box->GetOwner() == owner );

	CPoint* selfpoints = box->GetSelfPoints();

	for(int i = 0; i < 4; i++)
	{
		CPoint* startpoint_prev = &(selfpoints[(i + 3) % 4]);
		CPoint* startpoint = &(selfpoints[i]);
		CPoint* endpoint = &(selfpoints[(i + 1) % 4]);
		CPoint* endpoint_next = &(selfpoints[(i + 2) % 4]);

		RoutingDirection dir = GetDir(*endpoint - *startpoint);
		ASSERT( IsRightAngle(dir) );

		if( IsHorizontal(dir) == ishorizontal )
		{
			CAutoRouterEdge* edge = new CAutoRouterEdge();

			edge->SetOwner(box);

			edge->SetStartAndEndPoint(startpoint, endpoint);
			edge->SetStartPointPrev(startpoint_prev);
			edge->SetEndPointNext(endpoint_next);

			edge->SetEdgeFixed(true);

			Position_LoadY(edge);
			Position_LoadB(edge);

			if( edge->GetBracketClosing() )
				edge->AddToPositionY(0.999F);
		
			Insert(edge);
		}
	}
}

void CAutoRouterEdgeList::AddEdges(CAutoRouterGraph* graph)
{
	ASSERT_VALID(graph);
	ASSERT( graph == owner );

	CPoint* selfpoints = graph->GetSelfPoints();

	for(int i = 0; i < 4; i++)
	{
		CPoint* startpoint_prev = &(selfpoints[(i + 3) % 4]);
		CPoint* startpoint = &(selfpoints[i]);
		CPoint* endpoint = &(selfpoints[(i + 1) % 4]);
		CPoint* endpoint_next = &(selfpoints[(i + 2) % 4]);

		RoutingDirection dir = GetDir(*endpoint - *startpoint);
		ASSERT( IsRightAngle(dir) );

		if( IsHorizontal(dir) == ishorizontal )
		{
			CAutoRouterEdge* edge = new CAutoRouterEdge();

			edge->SetOwner(graph);

			edge->SetStartAndEndPoint(startpoint, endpoint);
			edge->SetStartPointPrev(startpoint_prev);
			edge->SetEndPointNext(endpoint_next);

			edge->SetEdgeFixed(true);

			Position_LoadY(edge);
			Insert(edge);
		}
	}
}

void CAutoRouterEdgeList::DeleteEdges(CObject* object)
{
	CAutoRouterEdge* edge = order_first;
	while( edge != NULL )
	{
		if( edge->GetOwner() == object )
		{
			CAutoRouterEdge* next = edge->GetOrderNext();
			Delete(edge);
			edge = next;
		}
		else
			edge = edge->GetOrderNext();
	}
}

void CAutoRouterEdgeList::DeleteAllEdges()
{
	while( order_first )
		Delete(order_first);
}

bool CAutoRouterEdgeList::IsEmpty() const
{
	return order_first == NULL;
}

// --- Position

long CAutoRouterEdgeList::Position_GetRealY(const CAutoRouterEdge* edge) const
{
	if( ishorizontal )
	{
		ASSERT( edge->GetStartPoint().y == edge->GetEndPoint().y );
		return edge->GetStartPoint().y;
	}

	ASSERT( edge->GetStartPoint().x == edge->GetEndPoint().x );
	return edge->GetStartPoint().x;
}

void CAutoRouterEdgeList::Position_SetRealY(CAutoRouterEdge* edge, long y) const
{
	ASSERT( edge != NULL && !edge->IsStartPointNull() && !edge->IsEndPointNull() );

	if( ishorizontal )
	{
		ASSERT( edge->GetStartPoint().y == edge->GetEndPoint().y );
		edge->SetStartPointY(y);
		edge->SetEndPointY(y);
	}
	else
	{
		ASSERT( edge->GetStartPoint().x == edge->GetEndPoint().x );
		edge->SetStartPointX(y);
		edge->SetEndPointX(y);
	}
}

void CAutoRouterEdgeList::Position_GetRealX(const CAutoRouterEdge* edge, long& x1, long& x2) const
{
	ASSERT( edge != NULL && !edge->IsStartPointNull() && !edge->IsEndPointNull() );

	if( ishorizontal )
	{
		ASSERT( edge->GetStartPoint().y == edge->GetEndPoint().y );
		if( edge->GetStartPoint().x < edge->GetEndPoint().x )
		{
			x1 = edge->GetStartPoint().x;
			x2 = edge->GetEndPoint().x;
		}
		else
		{
			x1 = edge->GetEndPoint().x;
			x2 = edge->GetStartPoint().x;
		}
	}
	else
	{
		ASSERT( edge->GetStartPoint().x == edge->GetEndPoint().x );
		if( edge->GetStartPoint().y < edge->GetEndPoint().y )
		{
			x1 = edge->GetStartPoint().y;
			x2 = edge->GetEndPoint().y;
		}
		else
		{
			x1 = edge->GetEndPoint().y;
			x2 = edge->GetStartPoint().y;
		}
	}
}

void CAutoRouterEdgeList::Position_GetRealO(const CAutoRouterEdge* edge, long& o1, long& o2) const
{
	ASSERT( edge != NULL && !edge->IsStartPointNull() && !edge->IsEndPointNull() );

	if( ishorizontal )
	{
		ASSERT( edge->GetStartPoint().y == edge->GetEndPoint().y );
		if( edge->GetStartPoint().x < edge->GetEndPoint().x )
		{
			o1 = edge->IsStartPointPrevNull() ? 0 : edge->GetStartPointPrev().y - edge->GetStartPoint().y;
			o2 = edge->IsEndPointNextNull() ? 0 : edge->GetEndPointNext().y - edge->GetEndPoint().y;
		}
		else
		{
			o1 = edge->IsEndPointNextNull() ? 0 : edge->GetEndPointNext().y - edge->GetEndPoint().y;
			o2 = edge->IsStartPointPrevNull() ? 0 : edge->GetStartPointPrev().y - edge->GetStartPoint().y;
		}
	}
	else
	{
		ASSERT( edge->GetStartPoint().x == edge->GetEndPoint().x );
		if( edge->GetStartPoint().y < edge->GetEndPoint().y )
		{
			o1 = edge->IsStartPointPrevNull() ? 0 : edge->GetStartPointPrev().x - edge->GetStartPoint().x;
			o2 = edge->IsEndPointNextNull() ? 0 : edge->GetEndPointNext().x - edge->GetEndPoint().x;
		}
		else
		{
			o1 = edge->IsEndPointNextNull() ? 0 : edge->GetEndPointNext().x - edge->GetEndPoint().x;
			o2 = edge->IsStartPointPrevNull() ? 0 : edge->GetStartPointPrev().x - edge->GetStartPoint().x;
		}
	}
}

void CAutoRouterEdgeList::Position_LoadY(CAutoRouterEdge* edge) const
{
	ASSERT( edge != NULL && edge->GetOrderNext() == NULL && edge->GetOrderPrev() == NULL );

	edge->SetPositionY((float) Position_GetRealY(edge));
}

void CAutoRouterEdgeList::Position_LoadB(CAutoRouterEdge* edge) const
{
	ASSERT( edge != NULL );

	edge->SetBracketOpening(!edge->GetEdgeFixed() && Bracket_IsOpening(edge));
	edge->SetBracketClosing(!edge->GetEdgeFixed() && Bracket_IsClosing(edge));
}

void CAutoRouterEdgeList::PositionAll_StoreY() const
{
	CAutoRouterEdge* edge = order_first;
	while( edge )
	{
		Position_SetRealY(edge, (long) edge->GetPositionY());

		edge = edge->GetOrderNext();
	}
}

void CAutoRouterEdgeList::PositionAll_LoadX() const
{
	CAutoRouterEdge* edge = order_first;
	while( edge )
	{
		long ex1, ex2;
		Position_GetRealX(edge, ex1, ex2);
		edge->SetPositionX1(ex1);
		edge->SetPositionX2(ex2);

		edge = edge->GetOrderNext();
	}
}

#ifdef _DEBUG

void CAutoRouterEdgeList::AssertValidPositions() const
{
	CAutoRouterEdge* edge = order_first;
	while( edge )
	{
		long y = Position_GetRealY(edge);
		ASSERT( edge->GetPositionY() - 1 <= y && y <= edge->GetPositionY() + 1 );

		if( edge->GetOrderPrev() )
		{
			ASSERT( edge->GetOrderPrev()->GetPositionY() <= edge->GetPositionY() );
			ASSERT( Position_GetRealY(edge->GetOrderPrev()) <= y );
		}

		if( edge->GetOrderNext() )
		{
			ASSERT( edge->GetPositionY() <= edge->GetOrderNext()->GetPositionY() );
			ASSERT( y <= Position_GetRealY(edge->GetOrderNext()) );
		}

		edge = edge->GetOrderNext();
	}
}

#endif

// --- Order

void CAutoRouterEdgeList::Init_Order()
{
	order_first = NULL;
	order_last = NULL;
}

void CAutoRouterEdgeList::Check_Order()
{
	ASSERT( order_first == NULL && order_last == NULL );
}

void CAutoRouterEdgeList::InsertBefore(CAutoRouterEdge* edge, CAutoRouterEdge* before)
{
	ASSERT( edge != NULL && before != NULL && edge != before );
	ASSERT( edge->GetOrderNext() == NULL && edge->GetOrderPrev() == NULL );

	edge->SetOrderPrev(before->GetOrderPrev());
	edge->SetOrderNext(before);

	if( before->GetOrderPrev() )
	{
		ASSERT( before->GetOrderPrev()->GetOrderNext() == before );
		before->GetOrderPrev()->SetOrderNext(edge);

		ASSERT( order_first != before );
	}
	else
	{
		ASSERT( order_first == before );
		order_first = edge;
	}

	before->SetOrderPrev(edge);
}

void CAutoRouterEdgeList::InsertAfter(CAutoRouterEdge* edge, CAutoRouterEdge* after)
{
	ASSERT( edge != NULL && after != NULL && edge != after );
	ASSERT( edge->GetOrderNext() == NULL && edge->GetOrderPrev() == NULL );

	edge->SetOrderNext(after->GetOrderNext());
	edge->SetOrderPrev(after);

	if( after->GetOrderNext() )
	{
		ASSERT( after->GetOrderNext()->GetOrderPrev() == after );
		after->GetOrderNext()->SetOrderPrev(edge);

		ASSERT( order_last != after );
	}
	else
	{
		ASSERT( order_last == after );
		order_last = edge;
	}

	after->SetOrderNext(edge);
}

void CAutoRouterEdgeList::InsertLast(CAutoRouterEdge* edge)
{
	ASSERT( edge != NULL );
	ASSERT( edge->GetOrderPrev() == NULL && edge->GetOrderNext() == NULL );

	edge->SetOrderPrev(order_last);

	if( order_last )
	{
		ASSERT( order_last->GetOrderNext() == NULL );
		ASSERT( order_first != NULL );

		order_last->SetOrderNext(edge);
		order_last = edge;
	}
	else
	{
		ASSERT( order_first == NULL );

		order_first = edge;
		order_last = edge;
	}
}

void CAutoRouterEdgeList::Insert(CAutoRouterEdge* edge)
{
	ASSERT( edge != NULL );
	ASSERT( edge->GetOrderPrev() == NULL && edge->GetOrderNext() == NULL );

	float y = edge->GetPositionY();
	ASSERT( ED_MINCOORD <= y && y <= ED_MAXCOORD );

	CAutoRouterEdge* insert = order_first;
	// FIXME: std::sort would be better than insertion sort
	while( insert && insert->GetPositionY() < y )
		insert = insert->GetOrderNext();

	if( insert )
		InsertBefore(edge, insert);
	else
		InsertLast(edge);
}

void CAutoRouterEdgeList::Remove(CAutoRouterEdge* edge)
{
	ASSERT( edge != NULL );

	if( order_first == edge )
		order_first = edge->GetOrderNext();

	if( edge->GetOrderNext() )
		edge->GetOrderNext()->SetOrderPrev(edge->GetOrderPrev());

	if( order_last == edge )
		order_last = edge->GetOrderPrev();

	if( edge->GetOrderPrev() )
		edge->GetOrderPrev()->SetOrderNext(edge->GetOrderNext());

	edge->SetOrderNext(NULL);
	edge->SetOrderPrev(NULL);
}

void CAutoRouterEdgeList::Delete(CAutoRouterEdge* edge)
{
	ASSERT( edge != NULL );

	Remove(edge);

	edge->SetOwner(NULL);

	delete edge;
}

CAutoRouterEdge* CAutoRouterEdgeList::SlideButNotPassEdges(CAutoRouterEdge* edge, float y)
{
	ASSERT( edge != NULL );
	ASSERT( ED_MINCOORD < y && y < ED_MAXCOORD );

	float oldy = edge->GetPositionY();
	ASSERT( ED_MINCOORD < oldy && oldy < ED_MAXCOORD );

	if( oldy == y )
		return NULL;

	long x1 = edge->GetPositionX1();
	long x2 = edge->GetPositionX2();
	CAutoRouterEdge* ret = NULL;

	CAutoRouterEdge* insert = edge;
	if( oldy < y )
	{
		while( insert->GetOrderNext() )
		{
			insert = insert->GetOrderNext();

			if( y < insert->GetPositionY() )
				break;

			if( !insert->GetEdgeCanpassed() && Intersect(x1, x2, insert->GetPositionX1(), insert->GetPositionX2() ) )
			{
				ret = insert;
				y = insert->GetPositionY();
				break;
			}
		}

		if( edge != insert && insert->GetOrderPrev() != edge )
		{
			Remove(edge);
			InsertBefore(edge, insert);
		}
	}
	else
	{
		while( insert->GetOrderPrev() )
		{
			insert = insert->GetOrderPrev();

			if( y > insert->GetPositionY() )
				break;

			if( !insert->GetEdgeCanpassed() && Intersect(x1, x2, insert->GetPositionX1(), insert->GetPositionX2() ) )
			{
				ret = insert;
				y = insert->GetPositionY();
				break;
			}
		}

		if( edge != insert && insert->GetOrderNext() != edge )
		{
			Remove(edge);
			InsertAfter(edge, insert);
		}

	}

#ifdef _DEBUG
	if( edge->GetOrderNext() )
		ASSERT( y <= edge->GetOrderNext()->GetPositionY() );

	if( edge->GetOrderPrev() )
		ASSERT( edge->GetOrderPrev()->GetPositionY() <= y );
#endif

	edge->SetPositionY(y);

	return ret;
}

#ifdef _DEBUG

void CAutoRouterEdgeList::AssertValidOrder() const
{
	ASSERT( order_first != NULL && order_last != NULL );
	ASSERT( order_first->GetOrderPrev() == NULL );
	ASSERT( order_last->GetOrderNext() == NULL );

	float y = ED_MINCOORD;

	TRACE("CAutoRouterEdgeList::AssertValidOrder (horizontal=%d) START\n", ishorizontal);

	CAutoRouterEdge* edge = order_first;
	while( edge != order_last )
	{
		TRACE("edge=%p, position_y=%f\n", edge, edge->GetPositionY());

		ASSERT( edge != NULL );
		ASSERT( y <= edge->GetPositionY() );
		ASSERT( edge->GetOrderNext()->GetOrderPrev() == edge );

		y = edge->GetPositionY();
		edge = edge->GetOrderNext();
	}

	TRACE("edge=%p, position_y=%f\n", edge, edge->GetPositionY());
	TRACE("CAutoRouterEdgeList::AssertValidOrder (horizontal=%d) END\n", ishorizontal);

	ASSERT( y <= ED_MAXCOORD );
}

#endif

// --- Section

void CAutoRouterEdgeList::Init_Section()
{
	section_first = NULL;
	section_blocker = NULL;
	section_ptr2blocked = NULL;
}

void CAutoRouterEdgeList::Check_Section()
{
	ASSERT( section_blocker == NULL && section_ptr2blocked == NULL );
}

void CAutoRouterEdgeList::Section_Reset()
{
	ASSERT( section_blocker == NULL && section_ptr2blocked == NULL );

	section_first = NULL;
}

void CAutoRouterEdgeList::Section_BeginScan(CAutoRouterEdge* blocker)
{
	ASSERT( section_blocker == NULL && section_ptr2blocked == NULL );

	section_blocker = blocker;

	section_blocker->SetSectionX1(section_blocker->GetPositionX1());
	section_blocker->SetSectionX2(section_blocker->GetPositionX2());

	section_blocker->SetSectionNext(NULL);
	section_blocker->SetSectionDown(NULL);
}

#define section_blocked (*section_ptr2blocked)
bool CAutoRouterEdgeList::Section_HasBlockedEdge()
{
	ASSERT( section_blocker != NULL );

	long b1 = section_blocker->GetSectionX1();
	long b2 = section_blocker->GetSectionX2();
	ASSERT( b1 <= b2 );

	if( section_ptr2blocked == NULL )
	{
		section_ptr2blocked = &section_first;
	}
	else
	{
		CAutoRouterEdge* current_edge = section_blocked;

		ASSERT( current_edge != NULL );

		CAutoRouterEdge* e = current_edge->GetSectionDown();
		CAutoRouterEdge* o = NULL;

		long a1 = current_edge->GetSectionX1();
		long a2 = current_edge->GetSectionX2();
		ASSERT( a1 <= a2 );

		ASSERT( b1 <= a2 &&  a1 <= b2 );							// not case 1 or 6

		if( a1 < b1 && b2 < a2 )									// case 3
		{
			section_ptr2blocked = current_edge->GetSectionDownPtr();
		}
		else if( b1 <= a1 && a2 <= b2 )								// case 4
		{
			if( e )
			{
				while( e->GetSectionNext() )
					e = e->GetSectionNext();

				e->SetSectionNext(current_edge->GetSectionNext());
				section_blocked = current_edge->GetSectionDown();
			}
			else
				section_blocked = current_edge->GetSectionNext();
		}
		else if( b1 <= a1 && b2 < a2 )								// case 5
		{
			ASSERT( a1 <= b2 );

			a1 = b2 + 1;

			while( e && e->GetSectionX1() <= a1 )
			{	
				ASSERT( e->GetSectionX1() <= e->GetSectionX2() );

				if( a1 <= e->GetSectionX2() )
					a1 = e->GetSectionX2() + 1;

				o = e;
				e = e->GetSectionNext();
			}

			if( o )
			{
				section_blocked = current_edge->GetSectionDown();
				o->SetSectionNext(current_edge);
				current_edge->SetSectionDown(e);
			}

			ASSERT( b2 < a1 );
			current_edge->SetSectionX1(a1);
		}
		else														// case 2
		{
			ASSERT( a1 < b1 && b1 <= a2 && a2 <= b2 );

			section_ptr2blocked = current_edge->GetSectionDownPtr();

			while( e )
			{
				o = e;
				e = e->GetSectionNext();

				if( o->GetSectionX2() + 1 < b1 && ( e == NULL || o->GetSectionX2() + 1 < e->GetSectionX1() ) )
					section_ptr2blocked = o->GetSectionNextPtr();
			}

			if( section_blocked )
			{
				ASSERT( o != NULL );
				o->SetSectionNext(current_edge->GetSectionNext());

				current_edge->SetSectionX2(
					(section_blocked->GetSectionX1() < b1 ? section_blocked->GetSectionX1() : b1) - 1);

				current_edge->SetSectionNext(section_blocked);
				section_blocked = NULL;
			}
			else
				current_edge->SetSectionX2(b1 - 1);

			section_ptr2blocked = current_edge->GetSectionNextPtr();
		}
	}

	ASSERT( section_ptr2blocked != NULL );
	while( section_blocked )
	{
		long a1 = section_blocked->GetSectionX1();
		long a2 = section_blocked->GetSectionX2();

		if( a2 < b1 )												// case 1
		{
			section_ptr2blocked = section_blocked->GetSectionNextPtr();

			ASSERT( section_ptr2blocked != NULL );
			continue;
		}
		else if( b2 < a1 )											// case 6
			break;
		
		if( a1 < b1 && b2 < a2 )									// case 3
		{
			long x = b1;

			CAutoRouterEdge* e = section_blocked->GetSectionDown();
			for(;;)
			{
				if( e == NULL || x < e->GetSectionX1() )
					return true;
				else if( x <= e->GetSectionX2() )
				{
					x = e->GetSectionX2() + 1;
					if( b2 < x )
						break;
				}

				e = e->GetSectionNext();
			}

			section_ptr2blocked = section_blocked->GetSectionDownPtr();
			continue;
		}

		return true;
	}

	ASSERT( section_blocker->GetSectionNext() == NULL && section_blocker->GetSectionDown() == NULL );

	section_blocker->SetSectionNext(section_blocked);
	section_blocked = section_blocker;

	section_blocker = NULL;
	section_ptr2blocked = NULL;

	return false;
}
#undef section_blocked

CAutoRouterEdge* CAutoRouterEdgeList::Section_GetBlockedEdge()
{
	ASSERT( section_blocker != NULL && section_ptr2blocked != NULL && *section_ptr2blocked != NULL );
#ifdef _DEBUG_DEEP
	AssertValidSection();
#endif

	return *section_ptr2blocked;
}

bool CAutoRouterEdgeList::Section_IsImmediate()
{
	ASSERT( section_blocker != NULL && section_ptr2blocked != NULL && *section_ptr2blocked != NULL );

	CAutoRouterEdge* section_blocked = *section_ptr2blocked;
	CAutoRouterEdge* e = section_blocked->GetSectionDown();

	long a1 = section_blocked->GetSectionX1();
	long a2 = section_blocked->GetSectionX2();
	long p1 = section_blocked->GetPositionX1();
	long p2 = section_blocked->GetPositionX2();
	long b1 = section_blocker->GetSectionX1();
	long b2 = section_blocker->GetSectionX2();

	ASSERT( b1 <= a2 && a1 <= b2 );									// not case 1 or 6

	// NOTE WE CHANGED THE CONDITIONS (A1<=B1 AND B2<=A2)
	// BECAUSE HERE WE NEED THIS!

	if( a1 <= b1 )
	{
		while( e != NULL && e->GetSectionX2() < b1 )
			e = e->GetSectionNext();

		if( b2 <= a2 )
			return e == NULL || b2 < e->GetSectionX1();				// case 3
			
		return e == NULL && a2 == p2;								// case 2
	}

	if( b2 <= a2 )
		return a1 == p1 && (e == NULL || b2 < e->GetSectionX1());	// case 5

	return e == NULL && a1 == p1 && a2 == p2;						// case 4
}

#ifdef _DEBUG

void CAutoRouterEdgeList::Section_AssertLevel(CAutoRouterEdge* level, long x1, long x2) const
{
	while( level )
	{
		ASSERT( level->GetPositionX1() <= level->GetSectionX1() && level->GetSectionX2() <= level->GetPositionX2() );
		ASSERT( x1 < level->GetSectionX1() && level->GetSectionX1() <= level->GetSectionX2() && level->GetSectionX2() < x2 );
		ASSERT( level->GetSectionNext() == NULL || level->GetSectionX2() < level->GetSectionNext()->GetSectionX1() );

		Section_AssertLevel(level->GetSectionDown(), level->GetSectionX1(), level->GetSectionX2());

		level = level->GetSectionNext();
	}
}

void CAutoRouterEdgeList::AssertValidSection() const
{
	Section_AssertLevel(section_first, ED_MINCOORD-1, ED_MAXCOORD+1);
}

void CAutoRouterEdgeList::AssertSectionReady() const
{
	ASSERT( section_blocker == NULL && section_ptr2blocked == NULL );
}

#endif

// --- Bracket

bool CAutoRouterEdgeList::Bracket_IsClosing(const CAutoRouterEdge* edge) const
{
	ASSERT( edge != NULL );
	ASSERT( !edge->IsStartPointNull() && !edge->IsEndPointNull() );

	CPoint start = edge->GetStartPoint();
	CPoint end = edge->GetEndPoint();

#ifdef _DEBUG
	if( ishorizontal )
	{
		ASSERT( start.y == end.y );

		if( !edge->IsStartPointPrevNull() )
			ASSERT( edge->GetStartPointPrev().x == start.x );

		if( !edge->IsEndPointNextNull() )
			ASSERT( edge->GetEndPointNext().x == end.x );
	}
	else
	{
		ASSERT( start.x == end.x );

		if( !edge->IsStartPointPrevNull() )
			ASSERT( edge->GetStartPointPrev().y == start.y );

		if( !edge->IsEndPointNextNull() )
			ASSERT( edge->GetEndPointNext().y == end.y );
	}
#endif

	if( edge->IsStartPointPrevNull() || edge->IsEndPointNextNull() )
		return false;

	return ishorizontal ?
		(edge->GetStartPointPrev().y < start.y && edge->GetEndPointNext().y < end.y ) :
		(edge->GetStartPointPrev().x < start.x && edge->GetEndPointNext().x < end.x );
}

bool CAutoRouterEdgeList::Bracket_IsOpening(const CAutoRouterEdge* edge) const
{
	ASSERT( edge != NULL );
	ASSERT( !edge->IsStartPointNull() && !edge->IsEndPointNull() );

	CPoint start = edge->GetStartPoint();
	CPoint end = edge->GetEndPoint();
#ifdef _DEBUG
	if( ishorizontal )
	{
		ASSERT( start.y == end.y );

		if( !edge->IsStartPointPrevNull() )
			ASSERT( edge->GetStartPointPrev().x == start.x );

		if( !edge->IsEndPointNextNull() )
			ASSERT( edge->GetEndPointNext().x == end.x );
	}
	else
	{
		ASSERT( start.x == end.x );

		if( !edge->IsStartPointPrevNull() )
			ASSERT( edge->GetStartPointPrev().y == start.y );

		if( !edge->IsEndPointNextNull() )
			ASSERT( edge->GetEndPointNext().y == end.y );
	}
#endif

	if( edge->IsStartPointPrevNull() || edge->IsEndPointNextNull() )
		return false;

	return ishorizontal ?
		(edge->GetStartPointPrev().y > start.y && edge->GetEndPointNext().y > end.y ) :
		(edge->GetStartPointPrev().x > start.x && edge->GetEndPointNext().x > end.x );
}

bool CAutoRouterEdgeList::Bracket_IsSmallGap(const CAutoRouterEdge* blocked, const CAutoRouterEdge* blocker) const
{
	return Bracket_IsOpening(blocked) || Bracket_IsClosing(blocker);
}

bool CAutoRouterEdgeList::Bracket_ShouldBeSwitched(const CAutoRouterEdge* edge, const CAutoRouterEdge* next) const
{
	ASSERT( edge != NULL && next != NULL );

	long ex1, ex2, eo1, eo2;
	Position_GetRealX(edge, ex1, ex2);
	Position_GetRealO(edge, eo1, eo2);

	long nx1, nx2, no1, no2;
	Position_GetRealX(next, nx1, nx2);
	Position_GetRealO(next, no1, no2);

	int c1, c2;

	if( (nx1 < ex1 && ex1 < nx2 && eo1 > 0 ) || (ex1 < nx1 && nx1 < ex2 && no1 < 0) )
		c1 = +1;
	else if( ex1 == nx1 && eo1 == 0 && no1 == 0 )
		c1 = 0;
	else
		c1 = -9;

	if( (nx1 < ex2 && ex2 < nx2 && eo2 > 0 ) || (ex1 < nx2 && nx2 < ex2 && no2 < 0) )
		c2 = +1;
	else if( ex2 == nx2 && eo2 == 0 && no2 == 0 )
		c2 = 0;
	else
		c2 = -9;

	return (c1 + c2) > 0;
}

// --- Block

#define FLT_EQU(A,B)	(((A) - 0.1F < (B)) && ((B) < (A) + 0.1F))

#define S EDLS_S
#define R EDLS_R
#define D EDLS_D

inline float Block_GetF(float d, int b, int s)
{
	float f = d/(b+s);

	if( b == 0 && R <= f )
		f += (D-R);
	else if( S < f && s > 0 )
		f = ((D-S)*d - S*(D-R)*s) / ((D-S)*b + (R-S)*s);

	return f;
}

inline float Block_GetG(float d, int b, int s)
{
	float g = d/(b+s);

	if( S < g && b > 0 )
		g = ((R-S)*d + S*(D-R)*b) / ((D-S)*b + (R-S)*s);

	return g;
}

#undef S
#undef R
#undef D

bool CAutoRouterEdgeList::Block_PushBackward(CAutoRouterEdge* blocked, CAutoRouterEdge* blocker)
{
	bool modified = false;

	ASSERT( blocked != NULL && blocker != NULL );
	ASSERT( blocked->GetPositionY() <= blocker->GetPositionY() );
	ASSERT( blocked->GetBlockPrev() != NULL );

	float f = 0;
	float g = 0;

	CAutoRouterEdge* edge = blocked;
	CAutoRouterEdge* trace = blocker;

	float d = trace->GetPositionY() - edge->GetPositionY();
	ASSERT( d >= 0 );

	int s = (edge->GetBracketOpening() || trace->GetBracketClosing());
	int b = 1 - s;

	for(;;)
	{
		edge->SetBlockTrace(trace);
		trace = edge;
		edge = edge->GetBlockPrev();

		if( edge == NULL )
			break;

		float d2 = trace->GetPositionY() - edge->GetPositionY();
		ASSERT( d2 >= 0 );

		if( edge->GetBracketOpening() || trace->GetBracketClosing() )
		{
			g = Block_GetG(d,b,s);
			if( d2 <= g )
			{
				f = Block_GetF(d,b,s);
				break;
			}
			s++;
		}
		else
		{
			f = Block_GetF(d,b,s);
			if( d2 <= f )
			{
				g = Block_GetG(d,b,s);
				break;
			}
			b++;
		}

		d += d2;
	}

	if( b+s > 1 )
	{
		if( edge == NULL )
		{
			f = Block_GetF(d,b,s);
			g = Block_GetG(d,b,s);
		}

		ASSERT( FLT_EQU(d, f*b + g*s) );

		edge = trace;
		ASSERT( edge != NULL && edge != blocked );

		float y = edge->GetPositionY();

		do
		{
			ASSERT( edge != NULL && edge->GetBlockTrace() != NULL );
			trace = edge->GetBlockTrace();

			y += (edge->GetBracketOpening() || trace->GetBracketClosing()) ? g : f;

			if( y + 0.001F < trace->GetPositionY() )
			{
				modified = true;
				if( SlideButNotPassEdges(trace, y) )
					trace->SetBlockPrev(NULL);
			}

			edge = trace;
		} while( edge != blocked );
#ifdef _DEBUG
		y += (edge->GetBracketOpening() || blocker->GetBracketClosing()) ? g : f;
		ASSERT( FLT_EQU(y, blocker->GetPositionY()) );
#endif
	}

	return modified;
}

bool CAutoRouterEdgeList::Block_PushForward(CAutoRouterEdge* blocked, CAutoRouterEdge* blocker)
{
	bool modified = false;

	ASSERT( blocked != NULL && blocker != NULL );
	ASSERT( blocked->GetPositionY() >= blocker->GetPositionY() );
	ASSERT( blocked->GetBlockNext() != NULL );

	float f = 0;
	float g = 0;

	CAutoRouterEdge* edge = blocked;
	CAutoRouterEdge* trace = blocker;

	float d = edge->GetPositionY() - trace->GetPositionY();
	ASSERT( d >= 0 );

	int s = (trace->GetBracketOpening() || edge->GetBracketClosing());
	int b = 1 - s;

	for(;;)
	{
		edge->SetBlockTrace(trace);
		trace = edge;
		edge = edge->GetBlockNext();

		if( edge == NULL )
			break;

		float d2 = edge->GetPositionY() - trace->GetPositionY();
		ASSERT( d2 >= 0 );

		if( trace->GetBracketOpening() || edge->GetBracketClosing() )
		{
			g = Block_GetG(d,b,s);
			if( d2 <= g )
			{
				f = Block_GetF(d,b,s);
				break;
			}
			s++;
		}
		else
		{
			f = Block_GetF(d,b,s);
			if( d2 <= f )
			{
				g = Block_GetG(d,b,s);
				break;
			}
			b++;
		}

		d += d2;
	}

	if( b+s > 1 )
	{
		if( edge == NULL )
		{
			f = Block_GetF(d,b,s);
			g = Block_GetG(d,b,s);
		}

		ASSERT( FLT_EQU(d, f*b + g*s) );

		edge = trace;
		ASSERT( edge != NULL && edge != blocked );

		float y = edge->GetPositionY();

		do
		{
			ASSERT( edge != NULL && edge->GetBlockTrace() != NULL );
			trace = edge->GetBlockTrace();

			y -= (trace->GetBracketOpening() || edge->GetBracketClosing()) ? g : f;

			if( trace->GetPositionY() < y - 0.001F )
			{
				modified = true;
				if( SlideButNotPassEdges(trace, y) )
					trace->SetBlockNext(NULL);
			}

			edge = trace;
		} while( edge != blocked );
#ifdef _DEBUG
		y -= (blocker->GetBracketOpening() || edge->GetBracketClosing()) ? g : f;
		ASSERT( FLT_EQU(y, blocker->GetPositionY()) );
#endif
	}

	return modified;
}

bool CAutoRouterEdgeList::Block_ScanForward()
{
#ifdef _DEBUG_DEEP
	AssertValidOrder();
	AssertSectionReady();
	AssertValidPositions();
#endif

	PositionAll_LoadX();

	bool modified = false;

	Section_Reset();
	CAutoRouterEdge* blocker = order_first;
	while( blocker )
	{
		CAutoRouterEdge* bmin = NULL;
		CAutoRouterEdge* smin = NULL;
		float bmin_f = ED_MINCOORD - 1;
		float smin_f = ED_MINCOORD - 1;

		Section_BeginScan(blocker);
		while( Section_HasBlockedEdge() )
		{
			if( Section_IsImmediate() )
			{
				CAutoRouterEdge* blocked = Section_GetBlockedEdge();
				ASSERT( blocked != NULL );

				if( blocked->GetBlockPrev() != NULL )
					modified |= Block_PushBackward(blocked, blocker);

				if( !blocker->GetEdgeFixed() )
				{
					if( blocked->GetBracketOpening() || blocker->GetBracketClosing() )
					{
						if( smin_f < blocked->GetPositionY() )
						{
							smin_f = blocked->GetPositionY();
							smin = blocked;
						}
					}
					else
					{
						if( bmin_f < blocked->GetPositionY() )
						{
							bmin_f = blocked->GetPositionY();
							bmin = blocked;
						}
					}
				}
			}
		}

		if( bmin )
		{
			if( smin )
			{
				blocker->SetClosestPrev(smin_f > bmin_f ? smin : bmin);

				bmin_f = blocker->GetPositionY() - bmin_f;
				smin_f = Block_GetF(blocker->GetPositionY() - smin_f, 0, 1);

				blocker->SetBlockPrev(smin_f < bmin_f ? smin : bmin);
			}
			else
			{
				blocker->SetBlockPrev(bmin);
				blocker->SetClosestPrev(bmin);
			}
		}
		else
		{
			blocker->SetBlockPrev(smin);
			blocker->SetClosestPrev(smin);
		}

#ifdef _DEBUG
		if( !blocker->GetEdgeFixed() )
		{
			CAutoRouterPath* ownerPath = static_cast<CAutoRouterPath*>(blocker->GetOwner());
			if (ownerPath->IsHighLighted())
			{
				ASSERT(false);
				break;
			}
		}
#endif

		blocker = blocker->GetOrderNext();
	}

	PositionAll_StoreY();

#ifdef _DEBUG_DEEP
	AssertValidOrder();
	AssertSectionReady();
	AssertValidPositions();
#endif

	return modified;
}

bool CAutoRouterEdgeList::Block_ScanBackward()
{
#ifdef _DEBUG_DEEP
	AssertValidOrder();
	AssertSectionReady();
	AssertValidPositions();
#endif

	PositionAll_LoadX();

	bool modified = false;

	Section_Reset();
	CAutoRouterEdge* blocker = order_last;
	while( blocker )
	{
		CAutoRouterEdge* bmin = NULL;
		CAutoRouterEdge* smin = NULL;
		float bmin_f = ED_MAXCOORD + 1;
		float smin_f = ED_MAXCOORD + 1;

		Section_BeginScan(blocker);
		while( Section_HasBlockedEdge() )
		{
			if( Section_IsImmediate() )
			{
				CAutoRouterEdge* blocked = Section_GetBlockedEdge();
				ASSERT( blocked != NULL );

				if( blocked->GetBlockNext() != NULL )
					modified |= Block_PushForward(blocked, blocker);

				if( !blocker->GetEdgeFixed() )
				{
					if( blocker->GetBracketOpening() || blocked->GetBracketClosing() )
					{
						if( smin_f > blocked->GetPositionY() )
						{
							smin_f = blocked->GetPositionY();
							smin = blocked;
						}
					}
					else
					{
						if( bmin_f > blocked->GetPositionY() )
						{
							bmin_f = blocked->GetPositionY();
							bmin = blocked;
						}
					}
				}
			}
		}

		if( bmin )
		{
			if( smin )
			{
				blocker->SetClosestNext(smin_f < bmin_f ? smin : bmin);

				bmin_f = bmin_f - blocker->GetPositionY();
				smin_f = Block_GetF(smin_f - blocker->GetPositionY(), 0, 1);

				blocker->SetBlockNext(smin_f < bmin_f ? smin : bmin);
			}
			else
			{
				blocker->SetBlockNext(bmin);
				blocker->SetClosestNext(bmin);
			}
		}
		else
		{
			blocker->SetBlockNext(smin);
			blocker->SetClosestNext(smin);
		}

#ifdef _DEBUG
		if( !blocker->GetEdgeFixed() )
		{
			CAutoRouterPath* ownerPath = static_cast<CAutoRouterPath*>(blocker->GetOwner());
			if (ownerPath->IsHighLighted())
			{
				ASSERT(false);
				break;
			}
		}
#endif

		blocker = blocker->GetOrderPrev();
	}

	PositionAll_StoreY();

#ifdef _DEBUG_DEEP
	AssertValidOrder();
	AssertSectionReady();
	AssertValidPositions();
#endif

	return modified;
}

bool CAutoRouterEdgeList::Block_SwitchWrongs()
{
	bool was = false;

	PositionAll_LoadX();

	CAutoRouterEdge* second = order_first;
	while( second != NULL )
	{
		if( second->GetClosestPrev() != NULL && second->GetClosestPrev()->GetClosestNext() != second &&
			second->GetClosestNext() != NULL && second->GetClosestNext()->GetClosestPrev() == second )
			
		{
			ASSERT( !second->GetEdgeFixed() );

			CAutoRouterEdge* edge = second;
			CAutoRouterEdge* next = edge->GetClosestNext();

			while( next != NULL && edge == next->GetClosestPrev() )
			{
				ASSERT( edge != NULL && !edge->GetEdgeFixed() );
				ASSERT( next != NULL && !next->GetEdgeFixed() );

				float ey = edge->GetPositionY();
				float ny = next->GetPositionY();

				ASSERT( ey <= ny );

				if( ey + 1 <= ny && Bracket_ShouldBeSwitched(edge, next) )
				{
					was = true;

					ASSERT( !edge->GetEdgeCanpassed() && !next->GetEdgeCanpassed() );
					edge->SetEdgeCanpassed(true);
					next->SetEdgeCanpassed(true);

					int a = SlideButNotPassEdges(edge, (ny+ey)/2 + 0.001F) != NULL;
					a |= SlideButNotPassEdges(next, (ny+ey)/2 - 0.001F) != NULL;

					if( a )
					{
						edge->SetClosestPrev(NULL);
						edge->SetClosestNext(NULL);
						next->SetClosestPrev(NULL);
						next->SetClosestNext(NULL);

						edge->SetEdgeCanpassed(false);
						next->SetEdgeCanpassed(false);
						break;
					}

					if( edge->GetClosestPrev() != NULL && edge->GetClosestPrev()->GetClosestNext() == edge )
						edge->GetClosestPrev()->SetClosestNext(next);

					if( next->GetClosestNext() != NULL && next->GetClosestNext()->GetClosestPrev() == next)
						next->GetClosestNext()->SetClosestPrev(edge);

					edge->SetClosestNext(next->GetClosestNext());
					next->SetClosestNext(edge);
					next->SetClosestPrev(edge->GetClosestPrev());
					edge->SetClosestPrev(next);

					edge->SetEdgeCanpassed(false);
					next->SetEdgeCanpassed(false);

					ASSERT( !Bracket_ShouldBeSwitched(next, edge) );

					if( next->GetClosestPrev() != NULL && next->GetClosestPrev()->GetClosestNext() == next )
						edge = next->GetClosestPrev();
					else
						next = edge->GetClosestNext();
				}
				else
				{
					edge = next;
					next = next->GetClosestNext();
				}
			}
		}

		second = second->GetOrderNext();
	}

	if( was )
		PositionAll_StoreY();

	return was;
}

