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

#include "ArGraph.h"
#include "ArEdgeLs.h"

#ifdef _DEBUG
// #define _DEBUG_DEEP
#endif

#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 SArEdge belongs to an edge of a CArPath, CArBox or CArPort. This edge is
	Represented by a CArPoint with its next point. The variable 'point' will refer
	to this CArPoint.

	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_fist'.
	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 SArEdge E1 "precede" the SArEdge E2 if there is no other SArEdge 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 CArBox or CArPort are fixed. We will continually fix the edges
	of the CArPaths. 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 and
	a block. The top edgeof a box only canend, while a fixed edge of a path can both
	start and end of a block.

*/


// --------------------------- CArEdgeList


CArEdgeList::CArEdgeList(int h)
{
	owner = NULL;

	ishorizontal = (h != 0);

	Con_Order();
	Con_Section();
}

CArEdgeList::~CArEdgeList()
{
	Des_Order();
	Des_Section();
}

// --- Edges

SArEdge* CArEdgeList::CreateEdge() const
{
	SArEdge* edge = new SArEdge;
	ASSERT( edge != NULL );

	edge->owner = NULL;
	
	edge->startpoint_prev = NULL;
	edge->startpoint = NULL;
	edge->endpoint = NULL;
	edge->endpoint_next = NULL;

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

	edge->order_prev = NULL;
	edge->order_next = NULL;

	edge->edge_fixed = 0;
	edge->edge_canpassed = 0;

	edge->position_y = 0;

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

	edge->closest_prev = NULL;
	edge->closest_next = NULL;

	return edge;
}

void CArEdgeList::AddEdges(CArPath* path)
{
	ASSERT_VALID(path);
	ASSERT( path->GetOwner() == owner );
	ASSERT_VALID( path->GetStartPort() );
	ASSERT_VALID( path->GetEndPort() );

	CPoint* startpoint;
	CPoint* endpoint;

	POSITION pos = path->GetTailEdgePtrs(startpoint, endpoint);
	while( pos != NULL )
	{
		EArDir dir = GetDir(*endpoint - *startpoint);

#ifdef _DEBUG
		if( path->IsMoveable() )
			ASSERT( IsRightAngle(dir) );
#endif

		if( IsRightAngle(dir) && IsHorizontal(dir) == ishorizontal )
		{
			SArEdge* edge = CreateEdge();

			edge->owner = path;

			edge->startpoint = startpoint;
			edge->endpoint = endpoint;
			edge->startpoint_prev = path->GetPointBeforeEdge(pos);
			edge->endpoint_next = path->GetPointAfterEdge(pos);

			edge->edge_fixed = path->IsFixed() || 
				(edge->startpoint_prev == NULL && path->GetStartPort()->IsConnectToCenter()) ||
				(edge->endpoint_next == NULL && path->GetEndPort()->IsConnectToCenter());

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

		path->GetPrevEdgePtrs(pos, startpoint, endpoint);
	}
}

SArEdge* CArEdgeList::GetEdge(CPoint* startpoint, CPoint* endpoint) const
{
	ASSERT( startpoint != NULL && endpoint != NULL );

	SArEdge* edge = order_first;
	while( edge != NULL )
	{
		if( edge->startpoint == startpoint )
		{
			ASSERT( edge->endpoint == endpoint );
			break;
		}

		edge = edge->order_next;
	}

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

SArEdge* CArEdgeList::GetEdgeAt(CPoint point, int nearness) const
{
	SArEdge* edge = order_first;
	while( edge )
	{
		if( IsPointNearLine(point, *edge->startpoint, *edge->endpoint, nearness) )
			return edge;

		edge = edge->order_next;
	}

	return NULL;
}

#ifdef _DEBUG

void CArEdgeList::AssertValidPathEdges(CArPath* path) const
{
	ASSERT( path != NULL );
	ASSERT( path->GetOwner() == owner );

	CPoint* startpoint;
	CPoint* endpoint;

	POSITION pos = path->GetTailEdgePtrs(startpoint, endpoint);
	while( pos != NULL )
	{
		EArDir dir = GetDir(*endpoint - *startpoint);

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

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

			ASSERT( edge->owner == path );

			ASSERT( edge->startpoint == startpoint );
			ASSERT( edge->endpoint == endpoint );
			ASSERT( edge->startpoint_prev == path->GetPointBeforeEdge(pos) );
			ASSERT( edge->endpoint_next == path->GetPointAfterEdge(pos) );
		}

		path->GetPrevEdgePtrs(pos, startpoint, endpoint);
	}

	SArEdge* edge = order_first;
	while( edge != NULL )
	{
		if( edge->owner == path )
		{
			POSITION pos = path->GetEdgePosForStartPoint(edge->startpoint);
			ASSERT( pos != NULL );
			ASSERT( path->GetStartPoint(pos)== edge->startpoint );
			ASSERT( path->GetEndPoint(pos)== edge->endpoint );
			ASSERT( path->GetPointBeforeEdge(pos)== edge->startpoint_prev );
			ASSERT( path->GetPointAfterEdge(pos)== edge->endpoint_next );
		}

		edge = edge->order_next;
	}
}

#endif

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

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

	for(int i = 0; i < 4; i++)
	{
		CPoint* startpoint_prev = port->selfpoints + ((i+3)%4);
		CPoint* startpoint = port->selfpoints + (i);
		CPoint* endpoint = port->selfpoints + ((i+1)%4);
		CPoint* endpoint_next = port->selfpoints + ((i+2)%4);

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

		if( IsHorizontal(dir) == ishorizontal && port->CanHaveStartEndPointHorizontal(ishorizontal) )
		{
			SArEdge* edge = CreateEdge();

			edge->owner = port;

			edge->startpoint = startpoint;
			edge->endpoint = endpoint;
			edge->startpoint_prev = startpoint_prev;
			edge->endpoint_next = endpoint_next;

			edge->edge_fixed = 1;

			Position_LoadY(edge);
			Position_LoadB(edge);

			if( edge->bracket_closing )
				edge->position_y += 0.999F;

			Insert(edge);
		}
	}
}

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

	for(int i = 0; i < 4; i++)
	{
		CPoint* startpoint_prev = box->selfpoints + ((i+3)%4);
		CPoint* startpoint = box->selfpoints + (i);
		CPoint* endpoint = box->selfpoints + ((i+1)%4);
		CPoint* endpoint_next = box->selfpoints + ((i+2)%4);

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

		if( IsHorizontal(dir) == ishorizontal )
		{
			SArEdge* edge = CreateEdge();

			edge->owner = box;

			edge->startpoint = startpoint;
			edge->endpoint = endpoint;
			edge->startpoint_prev = startpoint_prev;
			edge->endpoint_next = endpoint_next;

			edge->edge_fixed = 1;

			Position_LoadY(edge);
			Position_LoadB(edge);

			if( edge->bracket_closing )
				edge->position_y += 0.999F;
		
			Insert(edge);
		}
	}
}

void CArEdgeList::AddEdges(CArGraph* graph)
{
	ASSERT_VALID(graph);
	ASSERT( graph == owner );

	for(int i = 0; i < 4; i++)
	{
		CPoint* startpoint_prev = graph->selfpoints + ((i+3)%4);
		CPoint* startpoint = graph->selfpoints + (i);
		CPoint* endpoint = graph->selfpoints + ((i+1)%4);
		CPoint* endpoint_next = graph->selfpoints + ((i+2)%4);

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

		if( IsHorizontal(dir) == ishorizontal )
		{
			SArEdge* edge = CreateEdge();

			edge->owner = graph;

			edge->startpoint = startpoint;
			edge->endpoint = endpoint;
			edge->startpoint_prev = startpoint_prev;
			edge->endpoint_next = endpoint_next;

			edge->edge_fixed = 1;

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

void CArEdgeList::DeleteEdges(CObject* object)
{
	ASSERT( object != NULL );

	SArEdge* edge = order_first;
	while( edge != NULL )
	{
		if( edge->owner == object )
		{
			SArEdge* next = edge->order_next;
			Delete(edge);
			edge = next;
		}
		else
			edge = edge->order_next;
	}
}

void CArEdgeList::DeleteAllEdges()
{
	while( order_first )
		Delete(order_first);

	ASSERT( order_last == NULL );
}

int CArEdgeList::IsEmpty() const
{
	ASSERT( (order_first != NULL) + (order_last != NULL) != 1 );

	return order_first == NULL;
}

// --- Position

long CArEdgeList::Position_GetRealY(const SArEdge* edge) const
{
	ASSERT( edge != NULL && edge->startpoint != NULL && edge->endpoint != NULL );

	if( ishorizontal )
	{
		ASSERT( edge->startpoint->y == edge->endpoint->y );
		return edge->startpoint->y;
	}

	ASSERT( edge->startpoint->x == edge->endpoint->x );
	return edge->startpoint->x;
}

void CArEdgeList::Position_SetRealY(SArEdge* edge, long y) const
{
	ASSERT( edge != NULL && edge->startpoint != NULL && edge->endpoint != NULL );

	if( ishorizontal )
	{
		ASSERT( edge->startpoint->y == edge->endpoint->y );
		edge->startpoint->y = y;
		edge->endpoint->y = y;
	}
	else
	{
		ASSERT( edge->startpoint->x == edge->endpoint->x );
		edge->startpoint->x = y;
		edge->endpoint->x = y;
	}
}

void CArEdgeList::Position_GetRealX(const SArEdge* edge, long& x1, long& x2) const
{
	ASSERT( edge != NULL && edge->startpoint != NULL && edge->endpoint != NULL );

	if( ishorizontal )
	{
		ASSERT( edge->startpoint->y == edge->endpoint->y );
		if( edge->startpoint->x < edge->endpoint->x )
		{
			x1 = edge->startpoint->x;
			x2 = edge->endpoint->x;
		}
		else
		{
			x1 = edge->endpoint->x;
			x2 = edge->startpoint->x;
		}
	}
	else
	{
		ASSERT( edge->startpoint->x == edge->endpoint->x );
		if( edge->startpoint->y < edge->endpoint->y )
		{
			x1 = edge->startpoint->y;
			x2 = edge->endpoint->y;
		}
		else
		{
			x1 = edge->endpoint->y;
			x2 = edge->startpoint->y;
		}
	}
}

void CArEdgeList::Position_GetRealO(const SArEdge* edge, long& o1, long& o2) const
{
	ASSERT( edge != NULL && edge->startpoint != NULL && edge->endpoint != NULL );

	if( ishorizontal )
	{
		ASSERT( edge->startpoint->y == edge->endpoint->y );
		if( edge->startpoint->x < edge->endpoint->x )
		{
			o1 = edge->startpoint_prev == NULL ? 0 : edge->startpoint_prev->y - edge->startpoint->y;
			o2 = edge->endpoint_next == NULL ? 0 : edge->endpoint_next->y - edge->endpoint->y;
		}
		else
		{
			o1 = edge->endpoint_next == NULL ? 0 : edge->endpoint_next->y - edge->endpoint->y;
			o2 = edge->startpoint_prev == NULL ? 0 : edge->startpoint_prev->y - edge->startpoint->y;
		}
	}
	else
	{
		ASSERT( edge->startpoint->x == edge->endpoint->x );
		if( edge->startpoint->y < edge->endpoint->y )
		{
			o1 = edge->startpoint_prev == NULL ? 0 : edge->startpoint_prev->x - edge->startpoint->x;
			o2 = edge->endpoint_next == NULL ? 0 : edge->endpoint_next->x - edge->endpoint->x;
		}
		else
		{
			o1 = edge->endpoint_next == NULL ? 0 : edge->endpoint_next->x - edge->endpoint->x;
			o2 = edge->startpoint_prev == NULL ? 0 : edge->startpoint_prev->x - edge->startpoint->x;
		}
	}
}

void CArEdgeList::Position_LoadY(SArEdge* edge) const
{
	ASSERT( edge != NULL && edge->order_next == NULL && edge->order_prev == NULL );

	edge->position_y = (float) Position_GetRealY(edge);
}

void CArEdgeList::Position_LoadB(SArEdge* edge) const
{
	ASSERT( edge != NULL );

	edge->bracket_opening = !edge->edge_fixed && Bracket_IsOpening(edge);
	edge->bracket_closing = !edge->edge_fixed && Bracket_IsClosing(edge);
}

void CArEdgeList::PositionAll_StoreY() const
{
	SArEdge* edge = order_first;
	while( edge )
	{
		Position_SetRealY(edge, (long) edge->position_y);

		edge = edge->order_next;
	}
}

void CArEdgeList::PositionAll_LoadX() const
{
	SArEdge* edge = order_first;
	while( edge )
	{
		Position_GetRealX(edge, edge->position_x1, edge->position_x2);

		edge = edge->order_next;
	}
}

#ifdef _DEBUG

void CArEdgeList::AssertValidPositions() const
{
	SArEdge* edge = order_first;
	while( edge )
	{
		long y = Position_GetRealY(edge);
		ASSERT( edge->position_y - 1 <= y && y <= edge->position_y + 1 );

		if( edge->order_prev )
		{
			ASSERT( edge->order_prev->position_y <= edge->position_y );
			ASSERT( Position_GetRealY(edge->order_prev) <= y );
		}

		if( edge->order_next )
		{
			ASSERT( edge->position_y <= edge->order_next->position_y );
			ASSERT( y <= Position_GetRealY(edge->order_next) );
		}

		edge = edge->order_next;
	}
}

#endif

// --- Order

void CArEdgeList::Con_Order()
{
	order_first = NULL;
	order_last = NULL;
}

void CArEdgeList::Des_Order()
{
	ASSERT( order_first == NULL && order_last == NULL );
}

void CArEdgeList::InsertBefore(SArEdge* edge, SArEdge* before)
{
	ASSERT( edge != NULL && before != NULL && edge != before );
	ASSERT( edge->order_next == NULL && edge->order_prev == NULL );

	edge->order_prev = before->order_prev;
	edge->order_next = before;

	if( before->order_prev )
	{
		ASSERT( before->order_prev->order_next == before );
		before->order_prev->order_next = edge;

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

	before->order_prev = edge;
}

void CArEdgeList::InsertAfter(SArEdge* edge, SArEdge* after)
{
	ASSERT( edge != NULL && after != NULL && edge != after );
	ASSERT( edge->order_next == NULL && edge->order_prev == NULL );

	edge->order_next = after->order_next;
	edge->order_prev = after;

	if( after->order_next )
	{
		ASSERT( after->order_next->order_prev == after );
		after->order_next->order_prev = edge;

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

	after->order_next = edge;
}

void CArEdgeList::InsertLast(SArEdge* edge)
{
	ASSERT( edge != NULL );
	ASSERT( edge->order_prev == NULL && edge->order_next == NULL );

	edge->order_prev = order_last;

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

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

		order_first = edge;
		order_last = edge;
	}
}

void CArEdgeList::Insert(SArEdge* edge)
{
	ASSERT( edge != NULL );
	ASSERT( edge->order_prev == NULL && edge->order_next == NULL );

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

	SArEdge* insert = order_first;
	while( insert && insert->position_y < y )
		insert = insert->order_next;

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

void CArEdgeList::Remove(SArEdge* edge)
{
	ASSERT( edge != NULL );

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

	if( edge->order_next )
		edge->order_next->order_prev = edge->order_prev;

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

	if( edge->order_prev )
		edge->order_prev->order_next = edge->order_next;

	edge->order_next = NULL;
	edge->order_prev = NULL;
}

void CArEdgeList::Delete(SArEdge* edge)
{
	ASSERT( edge != NULL );

	Remove(edge);
	delete edge;
}

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

#ifdef _DEBUG
	if( !edge->edge_fixed && ((CArPath*)edge->owner)->IsHighLighted() )
		ASSERT(true);
#endif

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

	if( oldy == y )
		return NULL;

	long x1 = edge->position_x1;
	long x2 = edge->position_x2;
	SArEdge* ret = NULL;

	SArEdge* insert = edge;
	if( oldy < y )
	{
		while( insert->order_next )
		{
			insert = insert->order_next;

			if( y < insert->position_y )
				break;

			if( !insert->edge_canpassed && Intersect(x1, x2, insert->position_x1, insert->position_x2 ) )
			{
				ret = insert;
				y = insert->position_y;
				break;
			}
		}

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

			if( y > insert->position_y )
				break;

			if( !insert->edge_canpassed && Intersect(x1, x2, insert->position_x1, insert->position_x2 ) )
			{
				ret = insert;
				y = insert->position_y;
				break;
			}
		}

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

	}

#ifdef _DEBUG
	if( edge->order_next )
		ASSERT( y <= edge->order_next->position_y );

	if( edge->order_prev )
		ASSERT( edge->order_prev->position_y <= y );
#endif

	edge->position_y = y;

	return ret;
}

#ifdef _DEBUG

void CArEdgeList::AssertValidOrder() const
{
	ASSERT( order_first != NULL && order_last != NULL );
	ASSERT( order_first->order_prev == NULL );
	ASSERT( order_last->order_next == NULL );

	float y = ED_MINCOORD;

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

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

		ASSERT( edge != NULL );
		ASSERT( y <= edge->position_y );
		ASSERT( edge->order_next->order_prev == edge );

		y = edge->position_y;
		edge = edge->order_next;
	}

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

	ASSERT( y <= ED_MAXCOORD );
}

#endif

// --- Section

void CArEdgeList::Con_Section()
{
	section_first = NULL;
	section_blocker = NULL;
	section_ptr2blocked = NULL;
}

void CArEdgeList::Des_Section()
{
	ASSERT( section_blocker == NULL && section_ptr2blocked == NULL );
}

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

	section_first = NULL;
}

void CArEdgeList::Section_BeginScan(SArEdge* blocker)
{
	ASSERT( section_blocker == NULL && section_ptr2blocked == NULL );

	section_blocker = blocker;

	section_blocker->section_x1 = section_blocker->position_x1;
	section_blocker->section_x2 = section_blocker->position_x2;

	section_blocker->section_next = NULL;
	section_blocker->section_down = NULL;
}

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

	long b1 = section_blocker->section_x1;
	long b2 = section_blocker->section_x2;
	ASSERT( b1 <= b2 );

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

		ASSERT( current_edge != NULL );

		SArEdge* e = current_edge->section_down;
		SArEdge* o = NULL;

		long a1 = current_edge->section_x1;
		long a2 = current_edge->section_x2;
		ASSERT( a1 <= a2 );

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

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

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

			a1 = b2 + 1;

			while( e && e->section_x1 <= a1 )
			{	
				ASSERT( e->section_x1 <= e->section_x2 );

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

				o = e;
				e = e->section_next;
			}

			if( o )
			{
				section_blocked = current_edge->section_down;
				o->section_next = current_edge;
				current_edge->section_down = e;
			}

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

			section_ptr2blocked = &(current_edge->section_down);

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

				if( o->section_x2 + 1 < b1 && ( e == NULL || o->section_x2 + 1 < e->section_x1 ) )
					section_ptr2blocked = &(o->section_next);
			}

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

				current_edge->section_x2 = 
					(section_blocked->section_x1 < b1 ? section_blocked->section_x1 : b1) - 1;

				current_edge->section_next = section_blocked;
				section_blocked = NULL;
			}
			else
				current_edge->section_x2 = b1 - 1;

			section_ptr2blocked = &(current_edge->section_next);
		}
	}

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

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

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

			SArEdge* e = section_blocked->section_down;
			for(;;)
			{
				if( e == NULL || x < e->section_x1 )
					return 1;
				else if( x <= e->section_x2 )
				{
					x = e->section_x2 + 1;
					if( b2 < x )
						break;
				}

				e = e->section_next;
			}

			section_ptr2blocked = &(section_blocked->section_down);
			continue;
		}

		return 1;
	}

	ASSERT( section_blocker->section_next == NULL && section_blocker->section_down == NULL );

	section_blocker->section_next = section_blocked;
	section_blocked = section_blocker;

	section_blocker = NULL;
	section_ptr2blocked = NULL;

	return 0;
}
#undef section_blocked

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

	return *section_ptr2blocked;
}

int CArEdgeList::Section_IsImmediate()
{
	ASSERT( section_blocker != NULL && section_ptr2blocked != NULL && *section_ptr2blocked != NULL );

	SArEdge* section_blocked = *section_ptr2blocked;
	SArEdge* e = section_blocked->section_down;

	long a1 = section_blocked->section_x1;
	long a2 = section_blocked->section_x2;
	long p1 = section_blocked->position_x1;
	long p2 = section_blocked->position_x2;
	long b1 = section_blocker->section_x1;
	long b2 = section_blocker->section_x2;

	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->section_x2 < b1 )
			e = e->section_next;

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

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

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

#ifdef _DEBUG

void CArEdgeList::Section_AssertLevel(SArEdge* level, long x1, long x2) const
{
	while( level )
	{
		ASSERT( level->position_x1 <= level->section_x1 && level->section_x2 <= level->position_x2 );
		ASSERT( x1 < level->section_x1 && level->section_x1 <= level->section_x2 && level->section_x2 < x2 );
		ASSERT( level->section_next == NULL || level->section_x2 < level->section_next->section_x1 );

		Section_AssertLevel(level->section_down, level->section_x1, level->section_x2);

		level = level->section_next;
	}
}

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

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

#endif

// --- Bracket

int CArEdgeList::Bracket_IsClosing(const SArEdge* edge) const
{
	ASSERT( edge != NULL && edge->startpoint != NULL && edge->endpoint != NULL );

	return IsClosingBracket(edge->startpoint_prev, edge->startpoint, edge->endpoint, edge->endpoint_next, ishorizontal);
}

int CArEdgeList::Bracket_IsOpening(const SArEdge* edge) const
{
	ASSERT( edge != NULL && edge->startpoint != NULL && edge->endpoint != NULL );

	return IsOpeningBracket(edge->startpoint_prev, edge->startpoint, edge->endpoint, edge->endpoint_next, ishorizontal);
}

int CArEdgeList::Bracket_IsSmallGap(const SArEdge* blocked, const SArEdge* blocker) const
{
	return Bracket_IsOpening(blocked) || Bracket_IsClosing(blocker);
}

int CArEdgeList::Bracket_ShouldBeSwitched(const SArEdge* edge, const SArEdge* 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

int CArEdgeList::Block_PushBackward(SArEdge* blocked, SArEdge* blocker)
{
	int modified = 0;

	ASSERT( blocked != NULL && blocker != NULL );
	ASSERT( blocked->position_y <= blocker->position_y );
	ASSERT( blocked->block_prev != NULL );

	float f = 0;
	float g = 0;

	SArEdge* edge = blocked;
	SArEdge* trace = blocker;

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

	int s = (edge->bracket_opening || trace->bracket_closing);
	int b = 1 - s;

	for(;;)
	{
		edge->block_trace = trace;
		trace = edge;
		edge = edge->block_prev;

		if( edge == NULL )
			break;

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

		if( edge->bracket_opening || trace->bracket_closing )
		{
			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->position_y;

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

			y += (edge->bracket_opening || trace->bracket_closing) ? g : f;

			if( y + 0.001F < trace->position_y )
			{
				modified = 1;
				if( SlideButNotPassEdges(trace, y) )
					trace->block_prev = NULL;
			}

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

	return modified;
}

int CArEdgeList::Block_PushForward(SArEdge* blocked, SArEdge* blocker)
{
	int modified = 0;

	ASSERT( blocked != NULL && blocker != NULL );
	ASSERT( blocked->position_y >= blocker->position_y );
	ASSERT( blocked->block_next != NULL );

	float f = 0;
	float g = 0;

	SArEdge* edge = blocked;
	SArEdge* trace = blocker;

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

	int s = (trace->bracket_opening || edge->bracket_closing);
	int b = 1 - s;

	for(;;)
	{
		edge->block_trace = trace;
		trace = edge;
		edge = edge->block_next;

		if( edge == NULL )
			break;

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

		if( trace->bracket_opening || edge->bracket_closing )
		{
			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->position_y;

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

			y -= (trace->bracket_opening || edge->bracket_closing) ? g : f;

			if( trace->position_y < y - 0.001F )
			{
				modified = 1;
				if( SlideButNotPassEdges(trace, y) )
					trace->block_next = NULL;
			}

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

	return modified;
}

int CArEdgeList::Block_ScanForward()
{
#ifdef _DEBUG_DEEP
	AssertValidOrder();
	AssertSectionReady();
	AssertValidPositions();
#endif

	PositionAll_LoadX();

	int modified = 0;

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

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

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

			if( !blocker->edge_fixed )
			{
				if( blocked->bracket_opening || blocker->bracket_closing )
				{
					if( smin_f < blocked->position_y )
					{
						smin_f = blocked->position_y;
						smin = blocked;
					}
				}
				else
				{
					if( bmin_f < blocked->position_y )
					{
						bmin_f = blocked->position_y;
						bmin = blocked;
					}
				}
			}
		}

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

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

				blocker->block_prev = smin_f < bmin_f ? smin : bmin;
			}
			else
			{
				blocker->block_prev = bmin;
				blocker->closest_prev = bmin;
			}
		}
		else
		{
			blocker->block_prev = smin;
			blocker->closest_prev = smin;
		}

#ifdef _DEBUG
		if( !blocker->edge_fixed && ((CArPath*)blocker->owner)->IsHighLighted() )
			break;
#endif

		blocker = blocker->order_next;
	}

	PositionAll_StoreY();

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

	return modified;
}

int CArEdgeList::Block_ScanBackward()
{
#ifdef _DEBUG_DEEP
	AssertValidOrder();
	AssertSectionReady();
	AssertValidPositions();
#endif

	PositionAll_LoadX();

	int modified = 0;

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

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

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

			if( !blocker->edge_fixed )
			{
				if( blocker->bracket_opening || blocked->bracket_closing )
				{
					if( smin_f > blocked->position_y )
					{
						smin_f = blocked->position_y;
						smin = blocked;
					}
				}
				else
				{
					if( bmin_f > blocked->position_y )
					{
						bmin_f = blocked->position_y;
						bmin = blocked;
					}
				}
			}
		}

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

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

				blocker->block_next = smin_f < bmin_f ? smin : bmin;
			}
			else
			{
				blocker->block_next = bmin;
				blocker->closest_next = bmin;
			}
		}
		else
		{
			blocker->block_next = smin;
			blocker->closest_next = smin;
		}

#ifdef _DEBUG
		if( !blocker->edge_fixed && ((CArPath*)blocker->owner)->IsHighLighted() )
			break;
#endif

		blocker = blocker->order_prev;
	}

	PositionAll_StoreY();

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

	return modified;
}

int CArEdgeList::Block_SwitchWrongs()
{
	int was = 0;

	PositionAll_LoadX();

	SArEdge* second = order_first;
	while( second != NULL )
	{
		if( second->closest_prev != NULL && second->closest_prev->closest_next != second &&
			second->closest_next != NULL && second->closest_next->closest_prev == second )
			
		{
			ASSERT( !second->edge_fixed );

			SArEdge* edge = second;
			SArEdge* next = edge->closest_next;

			while( next != NULL && edge == next->closest_prev )
			{
				ASSERT( edge != NULL && !edge->edge_fixed );
				ASSERT( next != NULL && !next->edge_fixed );

				float ey = edge->position_y;
				float ny = next->position_y;

				ASSERT( ey <= ny );

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

					ASSERT( !edge->edge_canpassed && !next->edge_canpassed );
					edge->edge_canpassed = 1;
					next->edge_canpassed = 1;

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

					if( a )
					{
						edge->closest_prev = NULL;
						edge->closest_next = NULL;
						next->closest_prev = NULL;
						next->closest_next = NULL;

						edge->edge_canpassed = 0;
						next->edge_canpassed = 0;
						break;
					}

					if( edge->closest_prev != NULL && edge->closest_prev->closest_next == edge )
						edge->closest_prev->closest_next = next;

					if( next->closest_next != NULL && next->closest_next->closest_prev == next)
						next->closest_next->closest_prev = edge;

					edge->closest_next = next->closest_next;
					next->closest_next = edge;
					next->closest_prev = edge->closest_prev;
					edge->closest_prev = next;

					edge->edge_canpassed = 0;
					next->edge_canpassed = 0;

					ASSERT( !Bracket_ShouldBeSwitched(next, edge) );

					if( next->closest_prev != NULL && next->closest_prev->closest_next == next )
						edge = next->closest_prev;
					else
						next = edge->closest_next;
				}
				else
				{
					edge = next;
					next = next->closest_next;
				}
			}
		}

		second = second->order_next;
	}

	if( was )
		PositionAll_StoreY();

	return was;
}

