e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan#include <algorithm>

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan#include <cmath>

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow#include "libavoid/shape.h"

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow#include "libavoid/router.h"

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow#include "libavoid/visibility.h"

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow#include "libavoid/connector.h"

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow#include "libavoid/debug.h"

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan#include "libavoid/orthogonal.h"

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan#include "libavoid/assertions.h"

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrownamespace Avoid {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanenum ActionType {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ShapeMove,

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ShapeAdd,

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ShapeRemove,

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ConnChange

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan};

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracantypedef std::list<std::pair<unsigned int, ConnEnd> > ConnUpdateList;

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanclass ActionInfo {

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow public:

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo(ActionType t, ShapeRef *s, const Polygon& p, bool fM)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan : type(t),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan objPtr(s),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan newPoly(p),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan firstMove(fM)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(type == ShapeMove);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo(ActionType t, ShapeRef *s)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan : type(t),

28f6e3c9c01c504cf6971b80ff7014aaf794a773Kris objPtr(s),

28f6e3c9c01c504cf6971b80ff7014aaf794a773Kris newPoly(),

28f6e3c9c01c504cf6971b80ff7014aaf794a773Kris firstMove(0)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(type != ConnChange);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo(ActionType t, ConnRef *c)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan : type(t),

28f6e3c9c01c504cf6971b80ff7014aaf794a773Kris objPtr(c),

28f6e3c9c01c504cf6971b80ff7014aaf794a773Kris newPoly(),

28f6e3c9c01c504cf6971b80ff7014aaf794a773Kris firstMove(0)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(type == ConnChange);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ~ActionInfo()

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ShapeRef *shape(void) const

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz COLA_ASSERT((type == ShapeMove) || (type == ShapeAdd) ||

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan (type == ShapeRemove));

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return (static_cast<ShapeRef *> (objPtr));

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ConnRef *conn(void) const

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(type == ConnChange);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return (static_cast<ConnRef *> (objPtr));

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool operator==(const ActionInfo& rhs) const

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return (type == rhs.type) && (objPtr == rhs.objPtr);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool operator<(const ActionInfo& rhs) const

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (type != rhs.type)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return type < rhs.type;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return objPtr < rhs.objPtr;

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionType type;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan void *objPtr;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan Polygon newPoly;

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow bool firstMove;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ConnUpdateList conns;

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow};

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. CracanRouter::Router(const unsigned int flags)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan : visOrthogGraph(true),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan PartialTime(false),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan SimpleRouting(false),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ClusteredRouting(true),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Poly-line algorithm options:

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan IgnoreRegions(true),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan UseLeesAlgorithm(true),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan InvisibilityGrph(true),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // General algorithm options:

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan SelectiveReroute(true),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan PartialFeedback(false),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan RubberBandRouting(false),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Instrumentation:

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan st_checked_edges(0),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan#ifdef LIBAVOID_SDL

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan avoid_screen(NULL),

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow#endif

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _largestAssignedId(0),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _consolidateActions(true),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _orthogonalNudgeDistance(4.0),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Mode options:

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _polyLineRouting(false),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _orthogonalRouting(false),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _staticGraphInvalidated(true),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _inCrossingPenaltyReroutingStage(false)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // At least one of the Routing modes must be set.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(flags & (PolyLineRouting | OrthogonalRouting));

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (flags & PolyLineRouting)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _polyLineRouting = true;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (flags & OrthogonalRouting)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _orthogonalRouting = true;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan for (size_t p = 0; p < lastPenaltyMarker; ++p)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _routingPenalties[p] = 0.0;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _routingPenalties[clusterCrossingPenalty] = 4000;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. CracanRouter::~Router()

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Delete remaining connectors.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ConnRefList::iterator conn = connRefs.begin();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan while (conn != connRefs.end())

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan db_printf("Deleting connector %u in ~Router()\n", (*conn)->id());

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan delete *conn;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan conn = connRefs.begin();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Remove remaining shapes.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ShapeRefList::iterator shape = shapeRefs.begin();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan while (shape != shapeRefs.end())

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ShapeRef *shapePtr = *shape;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan db_printf("Deleting shape %u in ~Router()\n", shapePtr->id());

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (shapePtr->isActive())

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan shapePtr->removeFromGraph();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan shapePtr->makeInactive();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan delete shapePtr;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan shape = shapeRefs.begin();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Cleanup orphaned orthogonal graph vertices.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan destroyOrthogonalVisGraph();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(connRefs.size() == 0);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(shapeRefs.size() == 0);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(visGraph.size() == 0);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(invisGraph.size() == 0);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

346e04ed09c725332769b32af3467056b50cb3bfmjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::modifyConnector(ConnRef *conn, const unsigned int type,

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan const ConnEnd& connEnd)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo modInfo(ConnChange, conn);

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz ActionInfoList::iterator found =

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan find(actionList.begin(), actionList.end(), modInfo);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (found == actionList.end())

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan modInfo.conns.push_back(std::make_pair(type, connEnd));

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan actionList.push_back(modInfo);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow else

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan found->conns.push_back(std::make_pair(type, connEnd));

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (!_consolidateActions)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan processTransaction();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::modifyConnector(ConnRef *conn)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo modInfo(ConnChange, conn);

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz ActionInfoList::iterator found =

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan find(actionList.begin(), actionList.end(), modInfo);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (found == actionList.end())

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan actionList.push_back(modInfo);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (!_consolidateActions)

b78c2dddf7cf723ab55760e964e2ab3b95001749mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan processTransaction();

b78c2dddf7cf723ab55760e964e2ab3b95001749mjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

b78c2dddf7cf723ab55760e964e2ab3b95001749mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::removeQueuedConnectorActions(ConnRef *conn)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo modInfo(ConnChange, conn);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz ActionInfoList::iterator found =

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan find(actionList.begin(), actionList.end(), modInfo);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (found != actionList.end())

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan actionList.erase(found);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

346e04ed09c725332769b32af3467056b50cb3bfmjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::addShape(ShapeRef *shape)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // There shouldn't be remove events or move events for the same shape

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // already in the action list.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // XXX: Possibly we could handle this by ordering them intelligently.

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz COLA_ASSERT(find(actionList.begin(), actionList.end(),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo(ShapeRemove, shape)) == actionList.end());

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz COLA_ASSERT(find(actionList.begin(), actionList.end(),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo(ShapeMove, shape)) == actionList.end());

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo addInfo(ShapeAdd, shape);

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz ActionInfoList::iterator found =

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan find(actionList.begin(), actionList.end(), addInfo);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (found == actionList.end())

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan actionList.push_back(addInfo);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (!_consolidateActions)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan processTransaction();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::removeShape(ShapeRef *shape)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz // There shouldn't be add events events for the same shape already

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // in the action list.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // XXX: Possibly we could handle this by ordering them intelligently.

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz COLA_ASSERT(find(actionList.begin(), actionList.end(),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo(ShapeAdd, shape)) == actionList.end());

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Delete any ShapeMove entries for this shape in the action list.

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz ActionInfoList::iterator found = find(actionList.begin(),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan actionList.end(), ActionInfo(ShapeMove, shape));

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (found != actionList.end())

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan actionList.erase(found);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Add the ShapeRemove entry.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo remInfo(ShapeRemove, shape);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan found = find(actionList.begin(), actionList.end(), remInfo);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (found == actionList.end())

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan actionList.push_back(remInfo);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (!_consolidateActions)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan processTransaction();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::moveShape(ShapeRef *shape, const double xDiff, const double yDiff)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan Polygon newPoly = shape->polygon();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan newPoly.translate(xDiff, yDiff);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan moveShape(shape, newPoly);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruzvoid Router::moveShape(ShapeRef *shape, const Polygon& newPoly,

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan const bool first_move)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // There shouldn't be remove events or add events for the same shape

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // already in the action list.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // XXX: Possibly we could handle this by ordering them intelligently.

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz COLA_ASSERT(find(actionList.begin(), actionList.end(),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo(ShapeRemove, shape)) == actionList.end());

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if (find(actionList.begin(), actionList.end(),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo(ShapeAdd, shape)) != actionList.end())

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // The Add is enough, no need for the Move action too.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo moveInfo(ShapeMove, shape, newPoly, first_move);

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow // Sanely cope with the case where the user requests moving the same

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow // shape multiple times before rerouting connectors.

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz ActionInfoList::iterator found =

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan find(actionList.begin(), actionList.end(), moveInfo);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (found != actionList.end())

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (!SimpleRouting)

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan db_printf("warning: multiple moves requested for shape %d "

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan "within a single transaction.\n", (int) shape->id());

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Just update the ActionInfo with the second polygon, but

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // leave the firstMove setting alone.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan found->newPoly = newPoly;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz else

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan actionList.push_back(moveInfo);

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow }

346e04ed09c725332769b32af3467056b50cb3bfmjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (!_consolidateActions)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan processTransaction();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::setStaticGraphInvalidated(const bool invalidated)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _staticGraphInvalidated = invalidated;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::destroyOrthogonalVisGraph(void)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Remove orthogonal visibility graph edges.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan visOrthogGraph.clear();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Remove the now orphaned vertices.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan VertInf *curr = vertices.shapesBegin();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan while (curr)

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (curr->orphaned() && (curr->id == dummyOrthogID))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan VertInf *following = vertices.removeVertex(curr);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan delete curr;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan curr = following;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan continue;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan curr = curr->lstNext;

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow }

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow}

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::regenerateStaticBuiltGraph(void)

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow{

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz // Here we do talks involved in updating the static-built visibility

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // graph (if necessary) before we do any routing.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (_staticGraphInvalidated)

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (_orthogonalRouting)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan destroyOrthogonalVisGraph();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan timers.Register(tmOrthogGraph, timerStart);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Regenerate a new visibility graph.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan generateStaticOrthogonalVisGraph(this);

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan timers.Stop();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _staticGraphInvalidated = false;

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanbool Router::shapeInQueuedActionList(ShapeRef *shape) const

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz bool foundAdd = find(actionList.begin(), actionList.end(),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo(ShapeAdd, shape)) != actionList.end();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz bool foundRem = find(actionList.begin(), actionList.end(),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo(ShapeRemove, shape)) != actionList.end();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz bool foundMove = find(actionList.begin(), actionList.end(),

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo(ShapeMove, shape)) != actionList.end();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return (foundAdd || foundRem || foundMove);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanbool Router::transactionUse(void) const

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return _consolidateActions;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::setTransactionUse(const bool transactions)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _consolidateActions = transactions;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanbool Router::processTransaction(void)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool notPartialTime = !(PartialFeedback && PartialTime);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool seenShapeMovesOrDeletes = false;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // If SimpleRouting, then don't update here.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (actionList.empty() || SimpleRouting)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return false;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan actionList.sort();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfoList::iterator curr;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfoList::iterator finish = actionList.end();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan for (curr = actionList.begin(); curr != finish; ++curr)

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo& actInf = *curr;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (!((actInf.type == ShapeRemove) || (actInf.type == ShapeMove)))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Not a move or remove action, so don't do anything.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan continue;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan seenShapeMovesOrDeletes = true;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ShapeRef *shape = actInf.shape();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool isMove = (actInf.type == ShapeMove);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool first_move = actInf.firstMove;

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow unsigned int pid = shape->id();

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow // o Remove entries related to this shape's vertices

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow shape->removeFromGraph();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (SelectiveReroute && (!isMove || notPartialTime || first_move))

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow markConnectors(shape);

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow }

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow adjustContainsWithDel(pid);

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow // Ignore this shape for visibility.

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow // XXX: We don't really need to do this if we're not using Partial

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow // Feedback. Without this the blocked edges still route

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow // around the shape until it leaves the connector.

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow shape->makeInactive();

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow }

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (seenShapeMovesOrDeletes && _polyLineRouting)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (InvisibilityGrph)

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan for (curr = actionList.begin(); curr != finish; ++curr)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo& actInf = *curr;

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if (!((actInf.type == ShapeRemove) ||

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan (actInf.type == ShapeMove)))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Not a move or remove action, so don't do anything.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan continue;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // o Check all edges that were blocked by this shape.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan checkAllBlockedEdges(actInf.shape()->id());

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan else

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // check all edges not in graph

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan checkAllMissingEdges();

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

346e04ed09c725332769b32af3467056b50cb3bfmjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan for (curr = actionList.begin(); curr != finish; ++curr)

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo& actInf = *curr;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (!((actInf.type == ShapeAdd) || (actInf.type == ShapeMove)))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Not a move or add action, so don't do anything.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan continue;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ShapeRef *shape = actInf.shape();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan Polygon& newPoly = actInf.newPoly;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool isMove = (actInf.type == ShapeMove);

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow unsigned int pid = shape->id();

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow // Restore this shape for visibility.

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow shape->makeActive();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (isMove)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan shape->setNewPoly(newPoly);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan const Polygon& shapePoly = shape->polygon();

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan adjustContainsWithAdd(shapePoly, pid);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (_polyLineRouting)

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // o Check all visibility edges to see if this one shape

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // blocks them.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (!isMove || notPartialTime)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan newBlockingShape(shapePoly, pid);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // o Calculate visibility for the new vertices.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (UseLeesAlgorithm)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan shapeVisSweep(shape);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan else

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan shapeVis(shape);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Update connector endpoints.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan for (curr = actionList.begin(); curr != finish; ++curr)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ActionInfo& actInf = *curr;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (actInf.type != ConnChange)

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan continue;

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan for (ConnUpdateList::iterator conn = actInf.conns.begin();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan conn != actInf.conns.end(); ++conn)

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan actInf.conn()->updateEndPoint(conn->first, conn->second);

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Clear the actionList.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan actionList.clear();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _staticGraphInvalidated = true;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan rerouteAndCallbackConnectors();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return true;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::addCluster(ClusterRef *cluster)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan cluster->makeActive();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan unsigned int pid = cluster->id();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ReferencingPolygon& poly = cluster->polygon();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan adjustClustersWithAdd(poly, pid);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::delCluster(ClusterRef *cluster)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan cluster->makeInactive();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan unsigned int pid = cluster->id();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan adjustClustersWithDel(pid);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::setOrthogonalNudgeDistance(const double dist)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(dist >= 0);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _orthogonalNudgeDistance = dist;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracandouble Router::orthogonalNudgeDistance(void) const

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return _orthogonalNudgeDistance;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanunsigned int Router::assignId(const unsigned int suggestedId)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // If the suggestedId is zero, then we assign the object the next

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // smallest unassigned ID, otherwise we trust the ID given is unique.

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz unsigned int assignedId = (suggestedId == 0) ?

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan (_largestAssignedId + 1) : suggestedId;

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Have the router record if this ID is larger than the _largestAssignedId.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _largestAssignedId = std::max(_largestAssignedId, assignedId);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // If assertions are enabled, then we check that this ID really is unique.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(idIsUnique(assignedId));

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return assignedId;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Returns whether the given ID is unique among all objects known by the

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz // router. Outputs a warning if the ID is found ore than once.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // It is expected this is only going to be called from assertions while

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // debugging, so efficiency is not an issue and we just iterate over all

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // objects.

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruzbool Router::idIsUnique(const unsigned int id) const

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan unsigned int count = 0;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Examine shapes.

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz for (ShapeRefList::const_iterator i = shapeRefs.begin();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz i != shapeRefs.end(); ++i)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if ((*i)->id() == id)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan count++;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Examine connectors.

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz for (ConnRefList::const_iterator i = connRefs.begin();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz i != connRefs.end(); ++i)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if ((*i)->id() == id)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan count++;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Examine clusters.

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz for (ClusterRefList::const_iterator i = clusterRefs.begin();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz i != clusterRefs.end(); ++i)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if ((*i)->id() == id)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan count++;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (count > 1)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan db_printf("Warning:\tlibavoid object ID %d not unique.\n", id);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return false;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return true;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // Returns a list of connector Ids of all the connectors of type

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // 'type' attached to the shape with the ID 'shapeId'.

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrowvoid Router::attachedConns(IntList &conns, const unsigned int shapeId,

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow const unsigned int type)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ConnRefList::const_iterator fin = connRefs.end();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if ((type & runningTo) && ((*i)->_dstId == shapeId))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

3e13eaaba774420d7892b7cb61aed1fb22144307mjwybrow conns.push_back((*i)->_id);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz else if ((type & runningFrom) && ((*i)->_srcId == shapeId))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

3e13eaaba774420d7892b7cb61aed1fb22144307mjwybrow conns.push_back((*i)->_id);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // Returns a list of shape Ids of all the shapes attached to the

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // shape with the ID 'shapeId' with connection type 'type'.

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrowvoid Router::attachedShapes(IntList &shapes, const unsigned int shapeId,

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow const unsigned int type)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ConnRefList::const_iterator fin = connRefs.end();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if ((type & runningTo) && ((*i)->_dstId == shapeId))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if ((*i)->_srcId != 0)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // Only if there is a shape attached to the other end.

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow shapes.push_back((*i)->_srcId);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz else if ((type & runningFrom) && ((*i)->_srcId == shapeId))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if ((*i)->_dstId != 0)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // Only if there is a shape attached to the other end.

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow shapes.push_back((*i)->_dstId);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz // It's intended this function is called after visibility changes

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz // resulting from shape movement have happened. It will alert

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // rerouted connectors (via a callback) that they need to be redrawn.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::rerouteAndCallbackConnectors(void)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan std::set<ConnRef *> reroutedConns;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ConnRefList::const_iterator fin = connRefs.end();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz // Updating the orthogonal visibility graph if necessary.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan regenerateStaticBuiltGraph();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan timers.Register(tmOrthogRoute, timerStart);

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan (*i)->_needs_repaint = false;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool rerouted = (*i)->generatePath();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (rerouted)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan reroutedConns.insert(*i);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan timers.Stop();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Find and reroute crossing connectors if crossing penalties are set.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan improveCrossings();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Perform centring and nudging for othogonal routes.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan improveOrthogonalRoutes(this);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Alert connectors that they need redrawing.

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan (*i)->_needs_repaint = true;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan (*i)->performCallback();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracantypedef std::set<ConnRef *> ConnRefSet;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::improveCrossings(void)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan const double crossing_penalty = routingPenalty(crossingPenalty);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan const double shared_path_penalty = routingPenalty(fixedSharedPathPenalty);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if ((crossing_penalty == 0) && (shared_path_penalty == 0))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // No penalties, return.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Find crossings and reroute connectors.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _inCrossingPenaltyReroutingStage = true;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ConnRefSet crossingConns;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow ConnRefList::iterator fin = connRefs.end();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan Avoid::Polygon& iRoute = (*i)->routeRef();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ConnRefList::iterator j = i;

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz for (++j; j != fin; ++j)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if ((crossingConns.find(*i) != crossingConns.end()) &&

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan (crossingConns.find(*j) != crossingConns.end()))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // We already know both these have crossings.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan continue;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Determine if this pair cross.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan Avoid::Polygon& jRoute = (*j)->routeRef();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool meetsPenaltyCriteria = false;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan for (size_t jInd = 1; jInd < jRoute.size(); ++jInd)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan const bool finalSegment = ((jInd + 1) == jRoute.size());

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan CrossingsInfoPair crossingInfo = countRealCrossings(

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz iRoute, true, jRoute, jInd, false,

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan finalSegment, NULL, NULL, *i, *j);

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if ((shared_path_penalty > 0) &&

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz (crossingInfo.second & CROSSING_SHARES_PATH) &&

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz (crossingInfo.second & CROSSING_SHARES_FIXED_SEGMENT) &&

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz !(crossingInfo.second & CROSSING_SHARES_PATH_AT_END))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // We are penalising fixedSharedPaths and there is a

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // fixedSharedPath.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan meetsPenaltyCriteria = true;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan break;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan else if ((crossing_penalty > 0) && (crossingInfo.first > 0))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // We are penalising crossings and this is a crossing.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan meetsPenaltyCriteria = true;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan break;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (meetsPenaltyCriteria)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan crossingConns.insert(*i);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan crossingConns.insert(*j);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz for (ConnRefSet::iterator i = crossingConns.begin();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan i != crossingConns.end(); ++i)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ConnRef *conn = *i;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan conn->makePathInvalid();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // XXX: Could we free these routes here for extra savings?

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // conn->freeRoutes();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz for (ConnRefSet::iterator i = crossingConns.begin();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan i != crossingConns.end(); ++i)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ConnRef *conn = *i;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan conn->generatePath();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _inCrossingPenaltyReroutingStage = false;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::newBlockingShape(const Polygon& poly, int pid)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // o Check all visibility edges to see if this one shape

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // blocks them.

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow EdgeInf *finish = visGraph.end();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow for (EdgeInf *iter = visGraph.begin(); iter != finish ; )

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow EdgeInf *tmp = iter;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow iter = iter->lstNext;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if (tmp->getDist() != 0)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow std::pair<VertID, VertID> ids(tmp->ids());

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow VertID eID1 = ids.first;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow VertID eID2 = ids.second;

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow std::pair<Point, Point> points(tmp->points());

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow Point e1 = points.first;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow Point e2 = points.second;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow bool blocked = false;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool countBorder = false;

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz bool ep_in_poly1 = !(eID1.isShape) ?

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan inPoly(poly, e1, countBorder) : false;

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz bool ep_in_poly2 = !(eID2.isShape) ?

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan inPoly(poly, e2, countBorder) : false;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if (ep_in_poly1 || ep_in_poly2)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // Don't check edges that have a connector endpoint

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // and are inside the shape being added.

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow continue;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool seenIntersectionAtEndpoint = false;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan for (size_t pt_i = 0; pt_i < poly.size(); ++pt_i)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan size_t pt_n = (pt_i == (poly.size() - 1)) ? 0 : pt_i + 1;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan const Point& pi = poly.ps[pt_i];

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan const Point& pn = poly.ps[pt_n];

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz if (segmentShapeIntersect(e1, e2, pi, pn,

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan seenIntersectionAtEndpoint))

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow blocked = true;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow break;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if (blocked)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow db_printf("\tRemoving newly blocked edge (by shape %3d)"

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow "... \n\t\t", pid);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow tmp->alertConns();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow tmp->db_print();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if (InvisibilityGrph)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow tmp->addBlocker(pid);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow else

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow delete tmp;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrowvoid Router::checkAllBlockedEdges(int pid)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(InvisibilityGrph);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow for (EdgeInf *iter = invisGraph.begin(); iter != invisGraph.end() ; )

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow EdgeInf *tmp = iter;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow iter = iter->lstNext;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

346e04ed09c725332769b32af3467056b50cb3bfmjwybrow if (tmp->_blocker == -1)

346e04ed09c725332769b32af3467056b50cb3bfmjwybrow {

346e04ed09c725332769b32af3467056b50cb3bfmjwybrow tmp->alertConns();

346e04ed09c725332769b32af3467056b50cb3bfmjwybrow tmp->checkVis();

346e04ed09c725332769b32af3467056b50cb3bfmjwybrow }

346e04ed09c725332769b32af3467056b50cb3bfmjwybrow else if (tmp->_blocker == pid)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow tmp->checkVis();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrowvoid Router::checkAllMissingEdges(void)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(!InvisibilityGrph);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan VertInf *first = vertices.connsBegin();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow VertInf *pend = vertices.end();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow for (VertInf *i = first; i != pend; i = i->lstNext)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow VertID iID = i->id;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // Check remaining, earlier vertices

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow for (VertInf *j = first ; j != i; j = j->lstNext)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow VertID jID = j->id;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if (!(iID.isShape) && (iID.objID != jID.objID))

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // Don't keep visibility between edges of different conns

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow continue;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // See if the edge is already there?

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow bool found = (EdgeInf::existingEdge(i, j) != NULL);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if (!found)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // Didn't already exist, check.

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow bool knownNew = true;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow EdgeInf::checkEdgeVisibility(i, j, knownNew);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrowvoid Router::generateContains(VertInf *pt)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow contains[pt->id].clear();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan enclosingClusters[pt->id].clear();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Don't count points on the border as being inside.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool countBorder = false;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Compute enclosing shapes.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ShapeRefList::const_iterator finish = shapeRefs.end();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan for (ShapeRefList::const_iterator i = shapeRefs.begin(); i != finish; ++i)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (inPoly((*i)->polygon(), pt->point, countBorder))

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow contains[pt->id].insert((*i)->id());

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Computer enclosing Clusters

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ClusterRefList::const_iterator clFinish = clusterRefs.end();

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruz for (ClusterRefList::const_iterator i = clusterRefs.begin();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan i != clFinish; ++i)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (inPolyGen((*i)->polygon(), pt->point))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan enclosingClusters[pt->id].insert((*i)->id());

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

cc618cb0faf84b6f5ab2cc9802b29d03f6a22f97Jon A. Cruzvoid Router::adjustClustersWithAdd(const PolygonInterface& poly,

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan const int p_cluster)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow k = k->lstNext)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (inPolyGen(poly, k->point))

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan enclosingClusters[k->id].insert(p_cluster);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::adjustClustersWithDel(const int p_cluster)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan for (ContainsMap::iterator k = enclosingClusters.begin();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan k != enclosingClusters.end(); ++k)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan (*k).second.erase(p_cluster);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::adjustContainsWithAdd(const Polygon& poly, const int p_shape)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Don't count points on the border as being inside.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan bool countBorder = false;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow k = k->lstNext)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (inPoly(poly, k->point, countBorder))

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan contains[k->id].insert(p_shape);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::adjustContainsWithDel(const int p_shape)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan for (ContainsMap::iterator k = contains.begin(); k != contains.end(); ++k)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan (*k).second.erase(p_shape);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow#ifdef SELECTIVE_DEBUG

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrowstatic double AngleAFromThreeSides(const double a, const double b,

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow const double c)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // returns angle A, the angle opposite from side a, in radians

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow return acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b * c));

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow#endif

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrowvoid Router::markConnectors(ShapeRef *shape)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (RubberBandRouting)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // When rubber-band routing, we do no reroute connectors that

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // may have a better route, only invalid connectors.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(SelectiveReroute);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan ConnRefList::const_iterator end = connRefs.end();

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan for (ConnRefList::const_iterator it = connRefs.begin(); it != end; ++it)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow ConnRef *conn = (*it);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (conn->_route.empty())

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // Ignore uninitialised connectors.

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow continue;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow else if (conn->_needs_reroute_flag)

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow {

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow // Already marked, so skip.

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow continue;

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow Point start = conn->_route.ps[0];

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan Point end = conn->_route.ps[conn->_route.size() - 1];

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double conndist = conn->_route_dist;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double estdist;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double e1, e2;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow VertInf *beginV = shape->firstVert();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow VertInf *endV = shape->lastVert()->lstNext;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow for (VertInf *i = beginV; i != endV; i = i->lstNext)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow const Point& p1 = i->point;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow const Point& p2 = i->shNext->point;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double offy;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double a;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double b;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double c;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double d;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double min;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double max;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if (p1.y == p2.y)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // Standard case

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow offy = p1.y;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow a = start.x;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow b = start.y - offy;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow c = end.x;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow d = end.y - offy;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

b78c2dddf7cf723ab55760e964e2ab3b95001749mjwybrow min = std::min(p1.x, p2.x);

b78c2dddf7cf723ab55760e964e2ab3b95001749mjwybrow max = std::max(p1.x, p2.x);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow else if (p1.x == p2.x)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // Other Standard case

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow offy = p1.x;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow a = start.y;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow b = start.x - offy;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow c = end.y;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow d = end.x - offy;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

b78c2dddf7cf723ab55760e964e2ab3b95001749mjwybrow min = std::min(p1.y, p2.y);

b78c2dddf7cf723ab55760e964e2ab3b95001749mjwybrow max = std::max(p1.y, p2.y);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow else

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // Need to do rotation

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow Point n_p2(p2.x - p1.x, p2.y - p1.y);

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow Point n_start(start.x - p1.x, start.y - p1.y);

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow Point n_end(end.x - p1.x, end.y - p1.y);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan //db_printf("n_p2: (%.1f, %.1f)\n", n_p2.x, n_p2.y);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan //db_printf("n_start: (%.1f, %.1f)\n", n_start.x, n_start.y);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan //db_printf("n_end: (%.1f, %.1f)\n", n_end.x, n_end.y);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double theta = 0 - atan2(n_p2.y, n_p2.x);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan //db_printf("theta = %.2f\n", theta * (180 / PI));

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

b5e66c5e6adbe1f6d2adc9d5fe7ed26b66fb1bccmjwybrow Point r_p1(0, 0);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow Point r_p2 = n_p2;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow start = n_start;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow end = n_end;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double cosv = cos(theta);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double sinv = sin(theta);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow r_p2.x = cosv * n_p2.x - sinv * n_p2.y;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow r_p2.y = cosv * n_p2.y + sinv * n_p2.x;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow start.x = cosv * n_start.x - sinv * n_start.y;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow start.y = cosv * n_start.y + sinv * n_start.x;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow end.x = cosv * n_end.x - sinv * n_end.y;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow end.y = cosv * n_end.y + sinv * n_end.x;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan //db_printf("r_p2: (%.1f, %.1f)\n", r_p2.x, r_p2.y);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan //db_printf("r_start: (%.1f, %.1f)\n", start.x, start.y);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan //db_printf("r_end: (%.1f, %.1f)\n", end.x, end.y);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // This might be slightly off.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (fabs(r_p2.y) > 0.0001)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan db_printf("r_p2.y: %f != 0\n", r_p2.y);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow r_p2.y = 0;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow offy = r_p1.y;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow a = start.x;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow b = start.y - offy;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow c = end.x;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow d = end.y - offy;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

b78c2dddf7cf723ab55760e964e2ab3b95001749mjwybrow min = std::min(r_p1.x, r_p2.x);

b78c2dddf7cf723ab55760e964e2ab3b95001749mjwybrow max = std::max(r_p1.x, r_p2.x);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow double x;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if ((b + d) == 0)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow db_printf("WARNING: (b + d) == 0\n");

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow d = d * -1;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if ((b == 0) && (d == 0))

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow db_printf("WARNING: b == d == 0\n");

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if (((a < min) && (c < min)) ||

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow ((a > max) && (c > max)))

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // It's going to get adjusted.

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow x = a;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow else

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow continue;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow else

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow x = ((b*c) + (a*d)) / (b + d);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan //db_printf("%.1f, %.1f, %.1f, %.1f\n", a, b, c, d);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan //db_printf("x = %.1f\n", x);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

b78c2dddf7cf723ab55760e964e2ab3b95001749mjwybrow x = std::max(min, x);

b78c2dddf7cf723ab55760e964e2ab3b95001749mjwybrow x = std::min(max, x);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan //db_printf("x = %.1f\n", x);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow Point xp;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if (p1.x == p2.x)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow xp.x = offy;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow xp.y = x;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow else

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow xp.x = x;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow xp.y = offy;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan //db_printf("(%.1f, %.1f)\n", xp.x, xp.y);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan e1 = euclideanDist(start, xp);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan e2 = euclideanDist(xp, end);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow estdist = e1 + e2;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan //db_printf("is %.1f < %.1f\n", estdist, conndist);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if (estdist < conndist)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow#ifdef SELECTIVE_DEBUG

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow //double angle = AngleAFromThreeSides(dist(start, end),

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // e1, e2);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan db_printf("[%3d] - Possible better path found (%.1f < %.1f)\n",

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow conn->_id, estdist, conndist);

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow#endif

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow conn->_needs_reroute_flag = true;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow break;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow}

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. CracanConnType Router::validConnType(const ConnType select) const

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (select != ConnType_None)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if ((select == ConnType_Orthogonal) && _orthogonalRouting)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return ConnType_Orthogonal;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan else if ((select == ConnType_PolyLine) && _polyLineRouting)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return ConnType_PolyLine;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (_polyLineRouting)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return ConnType_PolyLine;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan else if (_orthogonalRouting)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return ConnType_Orthogonal;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return ConnType_None;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracanvoid Router::setRoutingPenalty(const PenaltyType penType, const double penVal)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(penType < lastPenaltyMarker);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan if (penVal < 0)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan // Set some sensible penalty.

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan switch (penType)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan case segmentPenalty:

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _routingPenalties[penType] = 50;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan break;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan case fixedSharedPathPenalty:

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _routingPenalties[penType] = 110;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan break;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan case anglePenalty:

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _routingPenalties[penType] = 50;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan break;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan case crossingPenalty:

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _routingPenalties[penType] = 200;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan break;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan case clusterCrossingPenalty:

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _routingPenalties[penType] = 4000;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan break;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan default:

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _routingPenalties[penType] = 50;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan break;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan else

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan {

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan _routingPenalties[penType] = penVal;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan }

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracandouble Router::routingPenalty(const PenaltyType penType) const

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(penType < lastPenaltyMarker);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return _routingPenalties[penType];

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracandouble& Router::penaltyRef(const PenaltyType penType)

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan{

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan COLA_ASSERT(penType < lastPenaltyMarker);

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan return _routingPenalties[penType];

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan}

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrowvoid Router::printInfo(void)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow{

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow FILE *fp = stdout;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow fprintf(fp, "\nVisibility Graph info:\n");

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow fprintf(fp, "----------------------\n");

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow unsigned int currshape = 0;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow int st_shapes = 0;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow int st_vertices = 0;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow int st_endpoints = 0;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow int st_valid_shape_visedges = 0;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow int st_valid_endpt_visedges = 0;

42b53baed61b6b06f33ecfa440a747382eb350dfArcadie M. Cracan int st_orthogonal_visedges = 0;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow int st_invalid_visedges = 0;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow VertInf *finish = vertices.end();

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow for (VertInf *t = vertices.connsBegin(); t != finish; t = t->lstNext)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow VertID pID = t->id;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if ((pID.isShape) && (pID.objID != currshape))

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow currshape = pID.objID;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow st_shapes++;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow if (pID.isShape)

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow st_vertices++;

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow }

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow else

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow {

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow // The shape 0 ones are temporary and not considered.

e8325ddfe05ac8dd00fbf1e25a583ee33887c031mjwybrow st_endpoints++;