diff options
Diffstat (limited to 'src/libavoid')
| -rw-r--r-- | src/libavoid/connector.cpp | 2 | ||||
| -rw-r--r-- | src/libavoid/orthogonal.cpp | 469 | ||||
| -rw-r--r-- | src/libavoid/router.cpp | 238 | ||||
| -rw-r--r-- | src/libavoid/vpsc.cpp | 109 |
4 files changed, 415 insertions, 403 deletions
diff --git a/src/libavoid/connector.cpp b/src/libavoid/connector.cpp index d9088dfe7..3dbd941a4 100644 --- a/src/libavoid/connector.cpp +++ b/src/libavoid/connector.cpp @@ -586,7 +586,7 @@ Router *ConnRef::router(void) const } -bool ConnRef::generatePath(Point p0, Point p1) +bool ConnRef::generatePath(Point /*p0*/, Point /*p1*/) { // XXX Code to determine when connectors really need to be rerouted // does not yet work for orthogonal connectors. diff --git a/src/libavoid/orthogonal.cpp b/src/libavoid/orthogonal.cpp index 747fd1f86..4a7b0af2d 100644 --- a/src/libavoid/orthogonal.cpp +++ b/src/libavoid/orthogonal.cpp @@ -12,12 +12,12 @@ * See the file LICENSE.LGPL distributed with the library. * * Licensees holding a valid commercial license may use this file in - * accordance with the commercial license agreement provided with the + * accordance with the commercial license agreement provided with the * library. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net> */ @@ -52,11 +52,11 @@ static const size_t XDIM = 0; static const size_t YDIM = 1; -class ShiftSegment +class ShiftSegment { public: // For shiftable segments. - ShiftSegment(ConnRef *conn, const size_t low, const size_t high, + ShiftSegment(ConnRef *conn, const size_t low, const size_t high, bool isSBend, const size_t dim, double minLim, double maxLim) : connRef(conn), indexLow(low), @@ -69,8 +69,9 @@ class ShiftSegment maxSpaceLimit(maxLim) { } + // For fixed segments. - ShiftSegment(ConnRef *conn, const size_t low, const size_t high, + ShiftSegment(ConnRef *conn, const size_t low, const size_t high, const size_t dim) : connRef(conn), indexLow(low), @@ -84,23 +85,28 @@ class ShiftSegment minSpaceLimit = lowPoint()[dim]; maxSpaceLimit = lowPoint()[dim]; } + Point& lowPoint(void) { return connRef->displayRoute().ps[indexLow]; } + Point& highPoint(void) { return connRef->displayRoute().ps[indexHigh]; } + const Point& lowPoint(void) const { return connRef->displayRoute().ps[indexLow]; } - const Point& highPoint(void) const + + const Point& highPoint(void) const { return connRef->displayRoute().ps[indexHigh]; } - const int fixedOrder(bool& isFixed) const + + int fixedOrder(bool& isFixed) const { if (fixed) { @@ -117,7 +123,8 @@ class ShiftSegment } return 0; } - const int order(void) const + + int order(void) const { if (lowC()) { @@ -129,17 +136,19 @@ class ShiftSegment } return 0; } + bool operator<(const ShiftSegment& rhs) const { const Point& lowPt = lowPoint(); const Point& rhsLowPt = rhs.lowPoint(); - + if (lowPt[dimension] != rhsLowPt[dimension]) { return lowPt[dimension] < rhsLowPt[dimension]; } return this < &rhs; } + // This counts segments that are colliear and share an endpoint as // overlapping. This allows them to be nudged apart where possible. bool overlapsWith(const ShiftSegment& rhs, const size_t dim) const @@ -171,7 +180,7 @@ class ShiftSegment double minSpaceLimit; double maxSpaceLimit; private: - const bool lowC(void) const + bool lowC(void) const { // This is true if this is a cBend and its adjoining points // are at lower positions. @@ -181,7 +190,8 @@ class ShiftSegment } return false; } - const bool highC(void) const + + bool highC(void) const { // This is true if this is a cBend and its adjoining points // are at higher positions. @@ -204,7 +214,7 @@ struct Node; struct CmpNodePos { bool operator()(const Node* u, const Node* v) const; }; typedef std::set<Node*,CmpNodePos> NodeSet; -struct Node +struct Node { ShapeRef *v; VertInf *c; @@ -221,10 +231,10 @@ struct Node pos(p), firstAbove(NULL), firstBelow(NULL) - { + { //COLA_ASSERT(r->width()<1e40); v->polygon().getBoundingRect(&min[0], &min[1], &max[0], &max[1]); - } + } Node(VertInf *c, const double p) : v(NULL), c(c), @@ -235,7 +245,7 @@ struct Node { min[0] = max[0] = c->point.x; min[1] = max[1] = c->point.y; - } + } Node(ShiftSegment *ss, const double p) : v(NULL), c(NULL), @@ -246,8 +256,8 @@ struct Node { // These values shouldn't ever be used, so they don't matter. min[0] = max[0] = min[1] = max[1] = 0; - } - ~Node() + } + ~Node() { } // Find the first Node above in the scanline that is a shape edge, @@ -260,7 +270,7 @@ struct Node { curr = curr->firstAbove; } - + if (curr) { return curr->max[dim]; @@ -277,14 +287,14 @@ struct Node { curr = curr->firstBelow; } - + if (curr) { return curr->min[dim]; } return DBL_MAX; } - // Mark all connector segments above in the scanline as being able + // Mark all connector segments above in the scanline as being able // to see to this shape edge. void markShiftSegmentsAbove(size_t dim) { @@ -293,13 +303,13 @@ struct Node { if (curr->ss && (curr->pos <= min[dim])) { - curr->ss->maxSpaceLimit = + curr->ss->maxSpaceLimit = std::min(min[dim], curr->ss->maxSpaceLimit); } curr = curr->firstAbove; } } - // Mark all connector segments below in the scanline as being able + // Mark all connector segments below in the scanline as being able // to see to this shape edge. void markShiftSegmentsBelow(size_t dim) { @@ -308,7 +318,7 @@ struct Node { if (curr->ss && (curr->pos >= max[dim])) { - curr->ss->minSpaceLimit = + curr->ss->minSpaceLimit = std::max(max[dim], curr->ss->minSpaceLimit); } curr = curr->firstBelow; @@ -320,8 +330,8 @@ struct Node bool clearVisibility = true; firstAbovePos = -DBL_MAX; firstBelowPos = DBL_MAX; - // We start looking left from the right side of the shape, - // and vice versa. + // We start looking left from the right side of the shape, + // and vice versa. lastAbovePos = max[dim]; lastBelowPos = min[dim]; @@ -353,7 +363,7 @@ struct Node } curr = curr->firstAbove; } - + // Find the first blocking edge below this point. Don't count the // edges as we are travelling out of shapes we are inside, but then // mark clearVisibility as false. @@ -385,35 +395,35 @@ struct Node return clearVisibility; } - double firstPointAbove(size_t dim) - { - Node *curr = firstAbove; - while (curr && (curr->max[dim] >= pos)) - { - curr = curr->firstAbove; - } - - if (curr) - { - return curr->max[dim]; - } - return -DBL_MAX; - } - double firstPointBelow(size_t dim) - { - Node *curr = firstBelow; - while (curr && (curr->min[dim] <= pos)) - { - curr = curr->firstBelow; - } - - if (curr) - { - return curr->min[dim]; - } - return DBL_MAX; - } - // This is a bit inefficient, but we won't need to do it once we have + double firstPointAbove(size_t dim) + { + Node *curr = firstAbove; + while (curr && (curr->max[dim] >= pos)) + { + curr = curr->firstAbove; + } + + if (curr) + { + return curr->max[dim]; + } + return -DBL_MAX; + } + double firstPointBelow(size_t dim) + { + Node *curr = firstBelow; + while (curr && (curr->min[dim] <= pos)) + { + curr = curr->firstBelow; + } + + if (curr) + { + return curr->min[dim]; + } + return DBL_MAX; + } + // This is a bit inefficient, but we won't need to do it once we have // connection points. bool isInsideShape(size_t dimension) { @@ -436,17 +446,17 @@ struct Node }; -bool CmpNodePos::operator() (const Node* u, const Node* v) const +bool CmpNodePos::operator() (const Node* u, const Node* v) const { - if (u->pos != v->pos) + if (u->pos != v->pos) { return u->pos < v->pos; } - + // Use the pointers to the base objects to differentiate them. - void *up = (u->v) ? (void *) u->v : + void *up = (u->v) ? (void *) u->v : ((u->c) ? (void *) u->c : (void *) u->ss); - void *vp = (v->v) ? (void *) v->v : + void *vp = (v->v) ? (void *) v->v : ((v->c) ? (void *) v->c : (void *) v->ss); return up < vp; } @@ -456,7 +466,7 @@ bool CmpNodePos::operator() (const Node* u, const Node* v) const typedef enum { Open = 1, SegOpen = 2, - ConnPoint = 3, + ConnPoint = 3, SegClose = 4, Close = 5 } EventType; @@ -464,7 +474,7 @@ typedef enum { struct Event { - Event(EventType t, Node *v, double p) + Event(EventType t, Node *v, double p) : type(t), v(v), pos(p) @@ -496,7 +506,7 @@ int compare_events(const void *a, const void *b) // Returns a bitfield of the direction of visibility (in this dimension) -// made up of ConnDirDown (for visibility towards lower position values) +// made up of ConnDirDown (for visibility towards lower position values) // and ConnDirUp (for visibility towards higher position values). // static ConnDirFlags getPosVertInfDirection(VertInf *v, size_t dim) @@ -526,13 +536,13 @@ static ConnDirFlags getPosVertInfDirection(VertInf *v, size_t dim) } else if (dirs == ConnDirDown) { - // For libavoid the Y-axis points downwards, so in terms of + // For libavoid the Y-axis points downwards, so in terms of // smaller or larger position values, Down is Up and vice versa. return ConnDirUp; } else if (dirs == ConnDirUp) { - // For libavoid the Y-axis points downwards, so in terms of + // For libavoid the Y-axis points downwards, so in terms of // smaller or larger position values, Down is Up and vice versa. return ConnDirDown; } @@ -551,8 +561,8 @@ struct PosVertInf dir(d) { } - - bool operator<(const PosVertInf& rhs) const + + bool operator<(const PosVertInf& rhs) const { if (pos != rhs.pos) { @@ -565,7 +575,7 @@ struct PosVertInf VertInf *vert; // A bitfield marking the direction of visibility (in this dimension) - // made up of ConnDirDown (for visibility towards lower position values) + // made up of ConnDirDown (for visibility towards lower position values) // and ConnDirUp (for visibility towards higher position values). // ConnDirFlags dir; @@ -573,7 +583,7 @@ struct PosVertInf struct CmpVertInf -{ +{ bool operator()(const VertInf* u, const VertInf* v) const { // Comparator for VertSet, an ordered set of VertInf pointers. @@ -596,17 +606,17 @@ struct CmpVertInf typedef std::set<VertInf *, CmpVertInf> VertSet; -// A set of points to break the line segment, +// A set of points to break the line segment, // along with vertices for these points. typedef std::set<PosVertInf> BreakpointSet; -// Temporary structure used to store the possible horizontal visibility +// Temporary structure used to store the possible horizontal visibility // lines arising from the vertical sweep. -class LineSegment +class LineSegment { public: - LineSegment(const double& b, const double& f, const double& p, - bool ss = false, VertInf *bvi = NULL, VertInf *fvi = NULL) + LineSegment(const double& b, const double& f, const double& p, + bool /*ss*/ = false, VertInf *bvi = NULL, VertInf *fvi = NULL) : begin(b), finish(f), pos(p), @@ -623,6 +633,7 @@ public: vertInfs.insert(fvi); } } + LineSegment(const double& bf, const double& p, VertInf *bfvi = NULL) : begin(bf), finish(bf), @@ -634,9 +645,9 @@ public: vertInfs.insert(bfvi); } } - + // Order by begin, pos, finish. - bool operator<(const LineSegment& rhs) const + bool operator<(const LineSegment& rhs) const { if (begin != rhs.begin) { @@ -662,7 +673,7 @@ public: // Lines are exactly equal. return true; } - + if (pos == rhs.pos) { if (((begin >= rhs.begin) && (begin <= rhs.finish)) || @@ -681,7 +692,7 @@ public: finish = std::max(finish, segment.finish); vertInfs.insert(segment.vertInfs.begin(), segment.vertInfs.end()); } - + VertInf *beginVertInf(void) const { if (vertInfs.empty()) @@ -750,12 +761,12 @@ public: } } - // Converts a section of the points list to a set of breakPoints. + // Converts a section of the points list to a set of breakPoints. // Returns the first of the intersection points occuring at finishPos. - VertSet::iterator addSegmentsUpTo(Router *router, double finishPos) + VertSet::iterator addSegmentsUpTo(Router */*router*/, double finishPos) { VertSet::iterator firstIntersectionPt = vertInfs.end(); - for (VertSet::iterator vert = vertInfs.begin(); + for (VertSet::iterator vert = vertInfs.begin(); vert != vertInfs.end(); ++vert) { if ((*vert)->point.x > finishPos) @@ -763,11 +774,11 @@ public: // We're done. break; } - + breakPoints.insert(PosVertInf((*vert)->point.x, (*vert), getPosVertInfDirection(*vert, XDIM))); - if ((firstIntersectionPt == vertInfs.end()) && + if ((firstIntersectionPt == vertInfs.end()) && ((*vert)->point.x == finishPos)) { firstIntersectionPt = vert; @@ -777,22 +788,22 @@ public: return firstIntersectionPt; } - // Add visibility edge(s) for this segment. There may be multiple if + // Add visibility edge(s) for this segment. There may be multiple if // one of the endpoints is shared by multiple connector endpoints. void addEdgeHorizontal(Router *router) { commitBegin(router); commitFinish(router); - + addSegmentsUpTo(router, finish); } // Add visibility edge(s) for this segment up until an intersection. // Then, move the segment beginning to the intersection point, so we // later only consider the remainder of the segment. - // There may be multiple segments added to the graph if the beginning + // There may be multiple segments added to the graph if the beginning // endpoint of the segment is shared by multiple connector endpoints. - VertSet addEdgeHorizontalTillIntersection(Router *router, + VertSet addEdgeHorizontalTillIntersection(Router *router, LineSegment& vertLine) { VertSet intersectionSet; @@ -801,14 +812,14 @@ public: // Does a vertex already exist for this point. commitPositionX(router, vertLine.pos); - - // Generate segments and set end iterator to the first point + + // Generate segments and set end iterator to the first point // at the intersection position. VertSet::iterator restBegin = addSegmentsUpTo(router, vertLine.pos); // Add the intersections points to intersectionSet. VertSet::iterator restEnd = restBegin; - while ((restEnd != vertInfs.end()) && + while ((restEnd != vertInfs.end()) && (*restEnd)->point.x == vertLine.pos) { ++restEnd; @@ -821,7 +832,7 @@ public: return intersectionSet; } - + // Insert vertical breakpoints. void insertBreakpointsBegin(Router *router, LineSegment& vertLine) { @@ -841,7 +852,7 @@ public: { if ((*v)->point.x == begin) { - vertLine.breakPoints.insert(PosVertInf(pos, *v, + vertLine.breakPoints.insert(PosVertInf(pos, *v, getPosVertInfDirection(*v, YDIM))); } } @@ -911,7 +922,7 @@ public: { // Here we have a pair of two endpoints that are both // connector endpoints and both are inside a shape. - + // Give vert visibility back to the first non-connector // endpoint vertex (i.e., the side of the shape). BreakpointSet::iterator side = last; @@ -926,16 +937,16 @@ public: bool canSeeDown = (vert->dir & ConnDirDown); if (canSeeDown && side->vert->id.isShape) { - EdgeInf *edge = new + EdgeInf *edge = new EdgeInf(side->vert, vert->vert, orthogonal); - edge->setDist(vert->vert->point[dim] - + edge->setDist(vert->vert->point[dim] - side->vert->point[dim]); } // Give last visibility back to the first non-connector // endpoint vertex (i.e., the side of the shape). side = vert; - while ((side != breakPoints.end()) && + while ((side != breakPoints.end()) && !side->vert->id.isShape) { ++side; @@ -943,17 +954,17 @@ public: bool canSeeUp = (last->dir & ConnDirUp); if (canSeeUp && (side != breakPoints.end())) { - EdgeInf *edge = new + EdgeInf *edge = new EdgeInf(last->vert, side->vert, orthogonal); - edge->setDist(side->vert->point[dim] - + edge->setDist(side->vert->point[dim] - last->vert->point[dim]); } } - + // The normal case. // - // Note: It's okay to give two connector endpoints visbility - // here since we only consider the partner endpoint as a + // Note: It's okay to give two connector endpoints visbility + // here since we only consider the partner endpoint as a // candidate while searching if it is the other endpoint of // the connector in question. // @@ -968,9 +979,9 @@ public: } if (generateEdge) { - EdgeInf *edge = + EdgeInf *edge = new EdgeInf(last->vert, vert->vert, orthogonal); - edge->setDist(vert->vert->point[dim] - + edge->setDist(vert->vert->point[dim] - last->vert->point[dim]); } @@ -997,12 +1008,12 @@ public: double finish; double pos; bool shapeSide; - + VertSet vertInfs; BreakpointSet breakPoints; private: - // MSVC wants to generate the assignment operator and the default - // constructor, but fails. Therefore we declare them private and + // MSVC wants to generate the assignment operator and the default + // constructor, but fails. Therefore we declare them private and // don't implement them. LineSegment & operator=(LineSegment const &); LineSegment(); @@ -1032,7 +1043,7 @@ class SegmentListWrapper } else { - // This is the first overlapping segment, so just + // This is the first overlapping segment, so just // merge the new segment with this one. curr->mergeVertInfs(segment); found = curr; @@ -1061,7 +1072,7 @@ class SegmentListWrapper // Given a router instance and a set of possible horizontal segments, and a // possible vertical visibility segment, compute and add edges to the // orthogonal visibility graph for all the visibility edges. -static void intersectSegments(Router *router, SegmentList& segments, +static void intersectSegments(Router *router, SegmentList& segments, LineSegment& vertLine) { COLA_ASSERT(vertLine.beginVertInf() == NULL); @@ -1104,9 +1115,9 @@ static void intersectSegments(Router *router, SegmentList& segments, { // Add horizontal visibility segment. horiLine.addEdgeHorizontal(router); - + horiLine.insertBreakpointsFinish(router, vertLine); - + size_t dim = XDIM; // x-dimension horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim); @@ -1123,7 +1134,7 @@ static void intersectSegments(Router *router, SegmentList& segments, if (inVertSegRegion) { // Add horizontal visibility segment. - VertSet intersectionVerts = + VertSet intersectionVerts = horiLine.addEdgeHorizontalTillIntersection( router, vertLine); @@ -1144,16 +1155,16 @@ static void intersectSegments(Router *router, SegmentList& segments, } -// Processes an event for the vertical sweep used for computing the static -// orthogonal visibility graph. This adds possible visibility sgments to +// Processes an event for the vertical sweep used for computing the static +// orthogonal visibility graph. This adds possible visibility sgments to // the segments list. // The first pass is adding the event to the scanline, the second is for // processing the event and the third for removing it from the scanline. -static void processEventVert(Router *router, NodeSet& scanline, +static void processEventVert(Router *router, NodeSet& scanline, SegmentListWrapper& segments, Event *e, unsigned int pass) { Node *v = e->v; - + if ( ((pass == 1) && (e->type == Open)) || ((pass == 2) && (e->type == ConnPoint)) ) { @@ -1163,21 +1174,21 @@ static void processEventVert(Router *router, NodeSet& scanline, NodeSet::iterator it = v->iter; // Work out neighbours - if (it != scanline.begin()) + if (it != scanline.begin()) { Node *u = *(--it); v->firstAbove = u; u->firstBelow = v; } it = v->iter; - if (++it != scanline.end()) + if (++it != scanline.end()) { Node *u = *it; v->firstBelow = u; u->firstAbove = v; } } - + if (pass == 2) { if ((e->type == Open) || (e->type == Close)) @@ -1198,18 +1209,18 @@ static void processEventVert(Router *router, NodeSet& scanline, if (minLimitMax >= maxLimitMin) { // Insert possible visibility segments. - VertInf *vI1 = new VertInf(router, dummyOrthogID, + VertInf *vI1 = new VertInf(router, dummyOrthogID, Point(minShape, lineY)); - VertInf *vI2 = new VertInf(router, dummyOrthogID, + VertInf *vI2 = new VertInf(router, dummyOrthogID, Point(maxShape, lineY)); - + // There are no overlapping shapes, so give full visibility. if (minLimit < minShape) { segments.insert(LineSegment(minLimit, minShape, lineY, true, NULL, vI1)); } - segments.insert(LineSegment(minShape, maxShape, lineY, + segments.insert(LineSegment(minShape, maxShape, lineY, true, vI1, vI2)); if (maxShape < maxLimit) { @@ -1245,12 +1256,12 @@ static void processEventVert(Router *router, NodeSet& scanline, LineSegment *line1 = NULL, *line2 = NULL; if (!inShape || (centreVert->visDirections & ConnDirLeft)) { - line1 = segments.insert(LineSegment(minLimit, cp.x, e->pos, + line1 = segments.insert(LineSegment(minLimit, cp.x, e->pos, true, NULL, centreVert)); } if (!inShape || (centreVert->visDirections & ConnDirRight)) { - line2 = segments.insert(LineSegment(cp.x, maxLimit, e->pos, + line2 = segments.insert(LineSegment(cp.x, maxLimit, e->pos, true, centreVert, NULL)); } if (!line1 && !line2) @@ -1258,7 +1269,7 @@ static void processEventVert(Router *router, NodeSet& scanline, // Add a point segment for the centre point. segments.insert(LineSegment(cp.x, e->pos, centreVert)); } - + if (!inShape) { // This is not contained within a shape so add a normal @@ -1279,13 +1290,13 @@ static void processEventVert(Router *router, NodeSet& scanline, } } } - + if ( ((pass == 3) && (e->type == Close)) || ((pass == 2) && (e->type == ConnPoint)) ) { // Clean up neighbour pointers. Node *l = v->firstAbove, *r = v->firstBelow; - if (l != NULL) + if (l != NULL) { l->firstBelow = v->firstBelow; } @@ -1310,16 +1321,16 @@ static void processEventVert(Router *router, NodeSet& scanline, } -// Processes an event for the vertical sweep used for computing the static -// orthogonal visibility graph. This adds possible visibility sgments to +// Processes an event for the vertical sweep used for computing the static +// orthogonal visibility graph. This adds possible visibility sgments to // the segments list. // The first pass is adding the event to the scanline, the second is for // processing the event and the third for removing it from the scanline. -static void processEventHori(Router *router, NodeSet& scanline, +static void processEventHori(Router */*router*/, NodeSet& scanline, SegmentListWrapper& segments, Event *e, unsigned int pass) { Node *v = e->v; - + if ( ((pass == 1) && (e->type == Open)) || ((pass == 2) && (e->type == ConnPoint)) ) { @@ -1329,21 +1340,21 @@ static void processEventHori(Router *router, NodeSet& scanline, NodeSet::iterator it = v->iter; // Work out neighbours - if (it != scanline.begin()) + if (it != scanline.begin()) { Node *u = *(--it); v->firstAbove = u; u->firstBelow = v; } it = v->iter; - if (++it != scanline.end()) + if (++it != scanline.end()) { Node *u = *it; v->firstBelow = u; u->firstAbove = v; } } - + if (pass == 2) { if ((e->type == Open) || (e->type == Close)) @@ -1370,13 +1381,13 @@ static void processEventHori(Router *router, NodeSet& scanline, { if ((minLimitMax > minLimit) && (minLimitMax >= minShape)) { - LineSegment vertSeg = + LineSegment vertSeg = LineSegment(minLimit, minLimitMax, lineX); segments.insert(vertSeg); } if ((maxLimitMin < maxLimit) && (maxLimitMin <= maxShape)) { - LineSegment vertSeg = + LineSegment vertSeg = LineSegment(maxLimitMin, maxLimit, lineX); segments.insert(vertSeg); } @@ -1392,7 +1403,7 @@ static void processEventHori(Router *router, NodeSet& scanline, double minLimit = v->firstPointAbove(1); double maxLimit = v->firstPointBelow(1); bool inShape = v->isInsideShape(1); - + if (!inShape || (centreVert->visDirections & ConnDirUp)) { segments.insert(LineSegment(minLimit, cp.y, e->pos)); @@ -1403,13 +1414,13 @@ static void processEventHori(Router *router, NodeSet& scanline, } } } - + if ( ((pass == 3) && (e->type == Close)) || ((pass == 2) && (e->type == ConnPoint)) ) { // Clean up neighbour pointers. Node *l = v->firstAbove, *r = v->firstBelow; - if (l != NULL) + if (l != NULL) { l->firstBelow = v->firstBelow; } @@ -1455,8 +1466,8 @@ extern void generateStaticOrthogonalVisGraph(Router *router) ++shRefIt; } - for (VertInf *curr = router->vertices.connsBegin(); - curr && (curr != router->vertices.shapesBegin()); + for (VertInf *curr = router->vertices.connsBegin(); + curr && (curr != router->vertices.shapesBegin()); curr = curr->lstNext) { Point& point = curr->point; @@ -1485,7 +1496,7 @@ extern void generateStaticOrthogonalVisGraph(Router *router) { for (unsigned j = posStartIndex; j < posFinishIndex; ++j) { - processEventVert(router, scanline, segments, + processEventVert(router, scanline, segments, events[j], pass); } } @@ -1500,7 +1511,7 @@ extern void generateStaticOrthogonalVisGraph(Router *router) posStartIndex = i; } - // Do the first sweep event handling -- building the correct + // Do the first sweep event handling -- building the correct // structure of the scanline. const int pass = 1; processEventVert(router, scanline, segments, events[i], pass); @@ -1529,8 +1540,8 @@ extern void generateStaticOrthogonalVisGraph(Router *router) ++shRefIt; } - for (VertInf *curr = router->vertices.connsBegin(); - curr && (curr != router->vertices.shapesBegin()); + for (VertInf *curr = router->vertices.connsBegin(); + curr && (curr != router->vertices.shapesBegin()); curr = curr->lstNext) { Point& point = curr->point; @@ -1555,11 +1566,11 @@ extern void generateStaticOrthogonalVisGraph(Router *router) { for (unsigned j = posStartIndex; j < posFinishIndex; ++j) { - processEventHori(router, scanline, vertSegments, + processEventHori(router, scanline, vertSegments, events[j], pass); } } - + // Process the merged line segments. vertSegments.list().sort(); for (SegmentList::iterator curr = vertSegments.list().begin(); @@ -1579,7 +1590,7 @@ extern void generateStaticOrthogonalVisGraph(Router *router) posStartIndex = i; } - // Do the first sweep event handling -- building the correct + // Do the first sweep event handling -- building the correct // structure of the scanline. const int pass = 1; processEventHori(router, scanline, vertSegments, events[i], pass); @@ -1593,13 +1604,13 @@ extern void generateStaticOrthogonalVisGraph(Router *router) // Add portions of the horizontal line that are after the final vertical // position we considered. - for (SegmentList::iterator it = segments.list().begin(); + for (SegmentList::iterator it = segments.list().begin(); it != segments.list().end(); ) { LineSegment& horiLine = *it; horiLine.addEdgeHorizontal(router); - + size_t dim = XDIM; // x-dimension horiLine.generateVisibilityEdgesFromBreakpointSet(router, dim); @@ -1615,20 +1626,20 @@ extern void generateStaticOrthogonalVisGraph(Router *router) -// Processes sweep events used to determine each horizontal and vertical -// line segment in a connector's channel of visibility. +// Processes sweep events used to determine each horizontal and vertical +// line segment in a connector's channel of visibility. // Four calls to this function are made at each position by the scanline: // 1) Handle all Close event processing. // 2) Remove Close event objects from the scanline. // 3) Add Open event objects to the scanline. // 4) Handle all Open event processing. // -static void processShiftEvent(Router *router, NodeSet& scanline, - ShiftSegmentList& segments, Event *e, size_t dim, - unsigned int pass) +static void processShiftEvent(Router */*router*/, NodeSet& scanline, + ShiftSegmentList& /*segments*/, Event *e, size_t dim, + unsigned int pass) { Node *v = e->v; - + if ( ((pass == 3) && (e->type == Open)) || ((pass == 3) && (e->type == SegOpen)) ) { @@ -1638,21 +1649,21 @@ static void processShiftEvent(Router *router, NodeSet& scanline, NodeSet::iterator it = v->iter; // Work out neighbours - if (it != scanline.begin()) + if (it != scanline.begin()) { Node *u = *(--it); v->firstAbove = u; u->firstBelow = v; } it = v->iter; - if (++it != scanline.end()) + if (++it != scanline.end()) { Node *u = *it; v->firstBelow = u; u->firstAbove = v; } } - + if ( ((pass == 4) && (e->type == Open)) || ((pass == 4) && (e->type == SegOpen)) || ((pass == 1) && (e->type == SegClose)) || @@ -1664,9 +1675,9 @@ static void processShiftEvent(Router *router, NodeSet& scanline, double minLimit = v->firstObstacleAbove(dim); double maxLimit = v->firstObstacleBelow(dim); - v->ss->minSpaceLimit = + v->ss->minSpaceLimit = std::max(minLimit, v->ss->minSpaceLimit); - v->ss->maxSpaceLimit = + v->ss->maxSpaceLimit = std::min(maxLimit, v->ss->maxSpaceLimit); } else @@ -1675,13 +1686,13 @@ static void processShiftEvent(Router *router, NodeSet& scanline, v->markShiftSegmentsBelow(dim); } } - + if ( ((pass == 2) && (e->type == SegClose)) || ((pass == 2) && (e->type == Close)) ) { // Clean up neighbour pointers. Node *l = v->firstAbove, *r = v->firstBelow; - if (l != NULL) + if (l != NULL) { l->firstBelow = v->firstBelow; } @@ -1698,7 +1709,7 @@ static void processShiftEvent(Router *router, NodeSet& scanline, } -static void buildOrthogonalChannelInfo(Router *router, +static void buildOrthogonalChannelInfo(Router *router, const size_t dim, ShiftSegmentList& segmentList) { if (router->routingPenalty(segmentPenalty) == 0) @@ -1710,15 +1721,15 @@ static void buildOrthogonalChannelInfo(Router *router, size_t altDim = (dim + 1) % 2; // For each connector. - for (ConnRefList::const_iterator curr = router->connRefs.begin(); - curr != router->connRefs.end(); ++curr) + for (ConnRefList::const_iterator curr = router->connRefs.begin(); + curr != router->connRefs.end(); ++curr) { if ((*curr)->routingType() != ConnType_Orthogonal) { continue; } Polygon& displayRoute = (*curr)->displayRoute(); - // Determine all line segments that we are interested in shifting. + // Determine all line segments that we are interested in shifting. // We don't consider the first or last segment of a path. for (size_t i = 1; i < displayRoute.size(); ++i) { @@ -1732,12 +1743,12 @@ static void buildOrthogonalChannelInfo(Router *router, indexLow = i; indexHigh = i - 1; } - COLA_ASSERT(displayRoute.at(indexLow)[altDim] < + COLA_ASSERT(displayRoute.at(indexLow)[altDim] < displayRoute.at(indexHigh)[altDim]); if ((i == 1) || ((i + 1) == displayRoute.size())) { - // The first and last segment of a connector can't be + // The first and last segment of a connector can't be // shifted. We call them fixed segments. Note: this // will change if we later allow connection channels. segmentList.push_back( @@ -1753,15 +1764,15 @@ static void buildOrthogonalChannelInfo(Router *router, double prevPos = displayRoute.ps[i - 2][dim]; double nextPos = displayRoute.ps[i + 1][dim]; if (((prevPos < displayRoute.ps[i][dim]) && - (nextPos > displayRoute.ps[i][dim])) + (nextPos > displayRoute.ps[i][dim])) || ((prevPos > displayRoute.ps[i][dim]) && (nextPos < displayRoute.ps[i][dim])) ) { isSBend = true; - // Determine limits if the s-bend is not due to an - // obstacle. In this case we need to limit the channel + // Determine limits if the s-bend is not due to an + // obstacle. In this case we need to limit the channel // to the span of the adjoining segments to this one. if ((prevPos < displayRoute.ps[i][dim]) && (nextPos > displayRoute.ps[i][dim])) @@ -1778,7 +1789,7 @@ static void buildOrthogonalChannelInfo(Router *router, else { // isCBend: Both adjoining segments are in the same - // direction. We indicate this for later by setting + // direction. We indicate this for later by setting // the maxLim or minLim to the segment position. if (prevPos < displayRoute.ps[i][dim]) { @@ -1790,7 +1801,7 @@ static void buildOrthogonalChannelInfo(Router *router, } } - segmentList.push_back(ShiftSegment(*curr, indexLow, + segmentList.push_back(ShiftSegment(*curr, indexLow, indexHigh, isSBend, dim, minLim, maxLim)); } } @@ -1800,7 +1811,7 @@ static void buildOrthogonalChannelInfo(Router *router, // There are no segments, so we can just return now. return; } - + // Do a sweep and shift these segments. const size_t n = router->shapeRefs.size(); const size_t cpn = segmentList.size(); @@ -1821,7 +1832,7 @@ static void buildOrthogonalChannelInfo(Router *router, ++shRefIt; } - for (ShiftSegmentList::iterator curr = segmentList.begin(); + for (ShiftSegmentList::iterator curr = segmentList.begin(); curr != segmentList.end(); ++curr) { const Point& lowPt = curr->lowPoint(); @@ -1853,7 +1864,7 @@ static void buildOrthogonalChannelInfo(Router *router, { for (unsigned j = posStartIndex; j < posFinishIndex; ++j) { - processShiftEvent(router, scanline, segmentList, events[j], + processShiftEvent(router, scanline, segmentList, events[j], dim, pass); } } @@ -1868,7 +1879,7 @@ static void buildOrthogonalChannelInfo(Router *router, posStartIndex = i; } - // Do the first sweep event handling -- building the correct + // Do the first sweep event handling -- building the correct // structure of the scanline. const int pass = 1; processShiftEvent(router, scanline, segmentList, events[i], @@ -1886,8 +1897,8 @@ static void buildOrthogonalChannelInfo(Router *router, static void simplifyOrthogonalRoutes(Router *router) { // Simplify routes. - for (ConnRefList::const_iterator curr = router->connRefs.begin(); - curr != router->connRefs.end(); ++curr) + for (ConnRefList::const_iterator curr = router->connRefs.begin(); + curr != router->connRefs.end(); ++curr) { if ((*curr)->routingType() != ConnType_Orthogonal) { @@ -1898,7 +1909,7 @@ static void simplifyOrthogonalRoutes(Router *router) } -static void buildOrthogonalNudgingOrderInfo(Router *router, +static void buildOrthogonalNudgingOrderInfo(Router *router, PtOrderMap& pointOrders) { // Simplify routes. @@ -1907,46 +1918,46 @@ static void buildOrthogonalNudgingOrderInfo(Router *router, int crossingsN = 0; // Do segment splitting. - for (ConnRefList::const_iterator curr = router->connRefs.begin(); - curr != router->connRefs.end(); ++curr) + for (ConnRefList::const_iterator curr = router->connRefs.begin(); + curr != router->connRefs.end(); ++curr) { if ((*curr)->routingType() != ConnType_Orthogonal) { continue; } ConnRef *conn = *curr; - - for (ConnRefList::const_iterator curr2 = router->connRefs.begin(); - curr2 != router->connRefs.end(); ++curr2) + + for (ConnRefList::const_iterator curr2 = router->connRefs.begin(); + curr2 != router->connRefs.end(); ++curr2) { if ((*curr2)->routingType() != ConnType_Orthogonal) { continue; } ConnRef *conn2 = *curr2; - + if (conn == conn2) { continue; } - + Avoid::Polygon& route = conn->displayRoute(); Avoid::Polygon& route2 = conn2->displayRoute(); splitBranchingSegments(route2, true, route); } } - for (ConnRefList::const_iterator curr = router->connRefs.begin(); - curr != router->connRefs.end(); ++curr) + for (ConnRefList::const_iterator curr = router->connRefs.begin(); + curr != router->connRefs.end(); ++curr) { if ((*curr)->routingType() != ConnType_Orthogonal) { continue; } ConnRef *conn = *curr; - - for (ConnRefList::const_iterator curr2 = curr; - curr2 != router->connRefs.end(); ++curr2) + + for (ConnRefList::const_iterator curr2 = curr; + curr2 != router->connRefs.end(); ++curr2) { if ((*curr2)->routingType() != ConnType_Orthogonal) { @@ -1958,7 +1969,7 @@ static void buildOrthogonalNudgingOrderInfo(Router *router, { continue; } - + Avoid::Polygon& route = conn->displayRoute(); Avoid::Polygon& route2 = conn2->displayRoute(); bool checkForBranchingSegments = false; @@ -1966,8 +1977,8 @@ static void buildOrthogonalNudgingOrderInfo(Router *router, for (size_t i = 1; i < route.size(); ++i) { const bool finalSegment = ((i + 1) == route.size()); - crossings += countRealCrossings(route2, true, route, i, - checkForBranchingSegments, finalSegment, NULL, + crossings += countRealCrossings(route2, true, route, i, + checkForBranchingSegments, finalSegment, NULL, &pointOrders, conn2, conn).first; } if (crossings > 0) @@ -1976,7 +1987,7 @@ static void buildOrthogonalNudgingOrderInfo(Router *router, } } } - + // Sort the point orders. PtOrderMap::iterator finish = pointOrders.end(); for (PtOrderMap::iterator it = pointOrders.begin(); it != finish; ++it) @@ -1992,7 +2003,7 @@ static void buildOrthogonalNudgingOrderInfo(Router *router, } -class CmpLineOrder +class CmpLineOrder { public: CmpLineOrder(PtOrderMap& ord, const size_t dim) @@ -2007,11 +2018,11 @@ class CmpLineOrder { *comparable = true; } - Point lhsLow = lhs.lowPoint(); - Point rhsLow = rhs.lowPoint(); + Point lhsLow = lhs.lowPoint(); + Point rhsLow = rhs.lowPoint(); #ifndef NDEBUG - const Point& lhsHigh = lhs.highPoint(); - const Point& rhsHigh = rhs.highPoint(); + const Point& lhsHigh = lhs.highPoint(); + const Point& rhsHigh = rhs.highPoint(); #endif size_t altDim = (dimension + 1) % 2; @@ -2022,9 +2033,9 @@ class CmpLineOrder { return lhsLow[dimension] < rhsLow[dimension]; } - - // If one of these is fixed, then determine order based on - // fixed segment, that is, order so the fixed segment doesn't + + // If one of these is fixed, then determine order based on + // fixed segment, that is, order so the fixed segment doesn't // block movement. bool oneIsFixed = false; const int lhsFixedOrder = lhs.fixedOrder(oneIsFixed); @@ -2034,8 +2045,8 @@ class CmpLineOrder return lhsFixedOrder < rhsFixedOrder; } - // C-bends that did not have a clear order with s-bends might - // not have a good ordering here, so compare their order in + // C-bends that did not have a clear order with s-bends might + // not have a good ordering here, so compare their order in // terms of C-bend direction and S-bends and use that if it // differs for the two segments. const int lhsOrder = lhs.order(); @@ -2056,7 +2067,7 @@ class CmpLineOrder { // A value for rhsPos or lhsPos mean the points are not directly // comparable, meaning they are at the same position but cannot - // overlap (they are just collinear. The relative order for + // overlap (they are just collinear. The relative order for // these segments is not important since we do not constrain // them against each other. //COLA_ASSERT(lhs.overlapsWith(rhs, dimension) == false); @@ -2076,13 +2087,13 @@ class CmpLineOrder }; -// We can use the normaal sort algorithm for lists since it is not possible -// to comapre all elements, but there will be an ordering defined between -// most of the elements. Hence we order these, using insertion sort, and -// the case of them not being able to be compared is handled by not setting +// We can use the normaal sort algorithm for lists since it is not possible +// to comapre all elements, but there will be an ordering defined between +// most of the elements. Hence we order these, using insertion sort, and +// the case of them not being able to be compared is handled by not setting // up any constraints between such segments when doing the nudging. // -static ShiftSegmentList linesort(ShiftSegmentList origList, +static ShiftSegmentList linesort(ShiftSegmentList origList, CmpLineOrder& comparison) { ShiftSegmentList resultList; @@ -2119,7 +2130,7 @@ static ShiftSegmentList linesort(ShiftSegmentList origList, typedef std::list<ShiftSegment *> ShiftSegmentPtrList; -static void nudgeOrthogonalRoutes(Router *router, size_t dimension, +static void nudgeOrthogonalRoutes(Router *router, size_t dimension, PtOrderMap& pointOrders, ShiftSegmentList& segmentList) { // Do the actual nudging. @@ -2160,7 +2171,7 @@ static void nudgeOrthogonalRoutes(Router *router, size_t dimension, } CmpLineOrder lineSortComp(pointOrders, dimension); currentRegion = linesort(currentRegion, lineSortComp); - + if (currentRegion.size() == 1) { // Save creating the solver instance if there is just one @@ -2188,7 +2199,7 @@ static void nudgeOrthogonalRoutes(Router *router, size_t dimension, currSegment != currentRegion.end(); ++currSegment) { Point& lowPt = currSegment->lowPoint(); - + // Create a solver variable for the position of this segment. int varID = freeID; double idealPos = lowPt[dimension]; @@ -2197,7 +2208,7 @@ static void nudgeOrthogonalRoutes(Router *router, size_t dimension, { COLA_ASSERT(currSegment->minSpaceLimit > -CHANNEL_MAX); COLA_ASSERT(currSegment->maxSpaceLimit < CHANNEL_MAX); - + // For s-bends, take the middle as ideal. idealPos = currSegment->minSpaceLimit + ((currSegment->maxSpaceLimit - @@ -2211,7 +2222,7 @@ static void nudgeOrthogonalRoutes(Router *router, size_t dimension, } else { - // Set a higher weight for c-bends to stop them sometimes + // Set a higher weight for c-bends to stop them sometimes // getting pushed out into channels by more-free connectors // to the "inner" side of them. weight = strongWeight; @@ -2234,10 +2245,10 @@ static void nudgeOrthogonalRoutes(Router *router, size_t dimension, if (currSegment->overlapsWith(*prevSeg, dimension) && (!(currSegment->fixed) || !(prevSeg->fixed))) { - // If there is a previous segment to the left that - // could overlap this in the shift direction, then + // If there is a previous segment to the left that + // could overlap this in the shift direction, then // constrain the two segments to be separated. - // Though don't add the constraint if both the + // Though don't add the constraint if both the // segments are fixed in place. cs.push_back(new Constraint(prevVar, vs[index], router->orthogonalNudgeDistance())); @@ -2251,21 +2262,21 @@ static void nudgeOrthogonalRoutes(Router *router, size_t dimension, if (!currSegment->fixed) { - // If this segment sees a channel boundary to its left, + // If this segment sees a channel boundary to its left, // then constrain its placement as such. if (currSegment->minSpaceLimit > -CHANNEL_MAX) { - vs.push_back(new Variable(fixedID, + vs.push_back(new Variable(fixedID, currSegment->minSpaceLimit, fixedWeight)); - cs.push_back(new Constraint(vs[vs.size() - 1], vs[index], + cs.push_back(new Constraint(vs[vs.size() - 1], vs[index], 0.0)); } - - // If this segment sees a channel boundary to its right, + + // If this segment sees a channel boundary to its right, // then constrain its placement as such. if (currSegment->maxSpaceLimit < CHANNEL_MAX) { - vs.push_back(new Variable(fixedID, + vs.push_back(new Variable(fixedID, currSegment->maxSpaceLimit, fixedWeight)); cs.push_back(new Constraint(vs[index], vs[vs.size() - 1], 0.0)); @@ -2281,7 +2292,7 @@ static void nudgeOrthogonalRoutes(Router *router, size_t dimension, IncSolver f(vs,cs); f.solve(); bool satisfied = true; - for (size_t i = 0; i < vs.size(); ++i) + for (size_t i = 0; i < vs.size(); ++i) { if (vs[i]->id == fixedID) { @@ -2323,7 +2334,7 @@ extern void improveOrthogonalRoutes(Router *router) { // Build nudging info. // XXX: We need to build the point orders separately in each - // dimension since things move. There is probably a more + // dimension since things move. There is probably a more // efficient way to do this. PtOrderMap pointOrders; buildOrthogonalNudgingOrderInfo(router, pointOrders); diff --git a/src/libavoid/router.cpp b/src/libavoid/router.cpp index 754c464b4..ab13a981b 100644 --- a/src/libavoid/router.cpp +++ b/src/libavoid/router.cpp @@ -12,12 +12,12 @@ * See the file LICENSE.LGPL distributed with the library. * * Licensees holding a valid commercial license may use this file in - * accordance with the commercial license agreement provided with the + * accordance with the commercial license agreement provided with the * library. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net> */ @@ -73,7 +73,7 @@ class ActionInfo { } ShapeRef *shape(void) const { - COLA_ASSERT((type == ShapeMove) || (type == ShapeAdd) || + COLA_ASSERT((type == ShapeMove) || (type == ShapeAdd) || (type == ShapeRemove)); return (static_cast<ShapeRef *> (objPtr)); } @@ -189,8 +189,8 @@ void Router::modifyConnector(ConnRef *conn, const unsigned int type, const ConnEnd& connEnd) { ActionInfo modInfo(ConnChange, conn); - - ActionInfoList::iterator found = + + ActionInfoList::iterator found = find(actionList.begin(), actionList.end(), modInfo); if (found == actionList.end()) { @@ -212,8 +212,8 @@ void Router::modifyConnector(ConnRef *conn, const unsigned int type, void Router::modifyConnector(ConnRef *conn) { ActionInfo modInfo(ConnChange, conn); - - ActionInfoList::iterator found = + + ActionInfoList::iterator found = find(actionList.begin(), actionList.end(), modInfo); if (found == actionList.end()) { @@ -231,7 +231,7 @@ void Router::removeQueuedConnectorActions(ConnRef *conn) { ActionInfo modInfo(ConnChange, conn); - ActionInfoList::iterator found = + ActionInfoList::iterator found = find(actionList.begin(), actionList.end(), modInfo); if (found != actionList.end()) { @@ -245,14 +245,14 @@ void Router::addShape(ShapeRef *shape) // There shouldn't be remove events or move events for the same shape // already in the action list. // XXX: Possibly we could handle this by ordering them intelligently. - COLA_ASSERT(find(actionList.begin(), actionList.end(), + COLA_ASSERT(find(actionList.begin(), actionList.end(), ActionInfo(ShapeRemove, shape)) == actionList.end()); - COLA_ASSERT(find(actionList.begin(), actionList.end(), + COLA_ASSERT(find(actionList.begin(), actionList.end(), ActionInfo(ShapeMove, shape)) == actionList.end()); ActionInfo addInfo(ShapeAdd, shape); - - ActionInfoList::iterator found = + + ActionInfoList::iterator found = find(actionList.begin(), actionList.end(), addInfo); if (found == actionList.end()) { @@ -268,14 +268,14 @@ void Router::addShape(ShapeRef *shape) void Router::removeShape(ShapeRef *shape) { - // There shouldn't be add events events for the same shape already + // There shouldn't be add events events for the same shape already // in the action list. // XXX: Possibly we could handle this by ordering them intelligently. - COLA_ASSERT(find(actionList.begin(), actionList.end(), + COLA_ASSERT(find(actionList.begin(), actionList.end(), ActionInfo(ShapeAdd, shape)) == actionList.end()); // Delete any ShapeMove entries for this shape in the action list. - ActionInfoList::iterator found = find(actionList.begin(), + ActionInfoList::iterator found = find(actionList.begin(), actionList.end(), ActionInfo(ShapeMove, shape)); if (found != actionList.end()) { @@ -306,16 +306,16 @@ void Router::moveShape(ShapeRef *shape, const double xDiff, const double yDiff) } -void Router::moveShape(ShapeRef *shape, const Polygon& newPoly, +void Router::moveShape(ShapeRef *shape, const Polygon& newPoly, const bool first_move) { // There shouldn't be remove events or add events for the same shape // already in the action list. // XXX: Possibly we could handle this by ordering them intelligently. - COLA_ASSERT(find(actionList.begin(), actionList.end(), + COLA_ASSERT(find(actionList.begin(), actionList.end(), ActionInfo(ShapeRemove, shape)) == actionList.end()); - - if (find(actionList.begin(), actionList.end(), + + if (find(actionList.begin(), actionList.end(), ActionInfo(ShapeAdd, shape)) != actionList.end()) { // The Add is enough, no need for the Move action too. @@ -325,7 +325,7 @@ void Router::moveShape(ShapeRef *shape, const Polygon& newPoly, ActionInfo moveInfo(ShapeMove, shape, newPoly, first_move); // Sanely cope with the case where the user requests moving the same // shape multiple times before rerouting connectors. - ActionInfoList::iterator found = + ActionInfoList::iterator found = find(actionList.begin(), actionList.end(), moveInfo); if (found != actionList.end()) @@ -339,7 +339,7 @@ void Router::moveShape(ShapeRef *shape, const Polygon& newPoly, // leave the firstMove setting alone. found->newPoly = newPoly; } - else + else { actionList.push_back(moveInfo); } @@ -380,7 +380,7 @@ void Router::destroyOrthogonalVisGraph(void) void Router::regenerateStaticBuiltGraph(void) { - // Here we do talks involved in updating the static-built visibility + // Here we do talks involved in updating the static-built visibility // graph (if necessary) before we do any routing. if (_staticGraphInvalidated) { @@ -391,7 +391,7 @@ void Router::regenerateStaticBuiltGraph(void) timers.Register(tmOrthogGraph, timerStart); // Regenerate a new visibility graph. generateStaticOrthogonalVisGraph(this); - + timers.Stop(); } _staticGraphInvalidated = false; @@ -401,11 +401,11 @@ void Router::regenerateStaticBuiltGraph(void) bool Router::shapeInQueuedActionList(ShapeRef *shape) const { - bool foundAdd = find(actionList.begin(), actionList.end(), + bool foundAdd = find(actionList.begin(), actionList.end(), ActionInfo(ShapeAdd, shape)) != actionList.end(); - bool foundRem = find(actionList.begin(), actionList.end(), + bool foundRem = find(actionList.begin(), actionList.end(), ActionInfo(ShapeRemove, shape)) != actionList.end(); - bool foundMove = find(actionList.begin(), actionList.end(), + bool foundMove = find(actionList.begin(), actionList.end(), ActionInfo(ShapeMove, shape)) != actionList.end(); return (foundAdd || foundRem || foundMove); @@ -456,21 +456,21 @@ bool Router::processTransaction(void) // o Remove entries related to this shape's vertices shape->removeFromGraph(); - + if (SelectiveReroute && (!isMove || notPartialTime || first_move)) { markConnectors(shape); } adjustContainsWithDel(pid); - + // Ignore this shape for visibility. // XXX: We don't really need to do this if we're not using Partial // Feedback. Without this the blocked edges still route // around the shape until it leaves the connector. shape->makeInactive(); } - + if (seenShapeMovesOrDeletes && _polyLineRouting) { if (InvisibilityGrph) @@ -478,7 +478,7 @@ bool Router::processTransaction(void) for (curr = actionList.begin(); curr != finish; ++curr) { ActionInfo& actInf = *curr; - if (!((actInf.type == ShapeRemove) || + if (!((actInf.type == ShapeRemove) || (actInf.type == ShapeMove))) { // Not a move or remove action, so don't do anything. @@ -513,7 +513,7 @@ bool Router::processTransaction(void) // Restore this shape for visibility. shape->makeActive(); - + if (isMove) { shape->setNewPoly(newPoly); @@ -559,7 +559,7 @@ bool Router::processTransaction(void) } // Clear the actionList. actionList.clear(); - + _staticGraphInvalidated = true; rerouteAndCallbackConnectors(); @@ -570,7 +570,7 @@ bool Router::processTransaction(void) void Router::addCluster(ClusterRef *cluster) { cluster->makeActive(); - + unsigned int pid = cluster->id(); ReferencingPolygon& poly = cluster->polygon(); @@ -581,9 +581,9 @@ void Router::addCluster(ClusterRef *cluster) void Router::delCluster(ClusterRef *cluster) { cluster->makeInactive(); - + unsigned int pid = cluster->id(); - + adjustClustersWithDel(pid); } @@ -605,9 +605,9 @@ unsigned int Router::assignId(const unsigned int suggestedId) { // If the suggestedId is zero, then we assign the object the next // smallest unassigned ID, otherwise we trust the ID given is unique. - unsigned int assignedId = (suggestedId == 0) ? + unsigned int assignedId = (suggestedId == 0) ? (_largestAssignedId + 1) : suggestedId; - + // Have the router record if this ID is larger than the _largestAssignedId. _largestAssignedId = std::max(_largestAssignedId, assignedId); @@ -619,17 +619,17 @@ unsigned int Router::assignId(const unsigned int suggestedId) // Returns whether the given ID is unique among all objects known by the - // router. Outputs a warning if the ID is found ore than once. + // router. Outputs a warning if the ID is found ore than once. // It is expected this is only going to be called from assertions while // debugging, so efficiency is not an issue and we just iterate over all // objects. -bool Router::idIsUnique(const unsigned int id) const +bool Router::idIsUnique(const unsigned int id) const { unsigned int count = 0; // Examine shapes. - for (ShapeRefList::const_iterator i = shapeRefs.begin(); - i != shapeRefs.end(); ++i) + for (ShapeRefList::const_iterator i = shapeRefs.begin(); + i != shapeRefs.end(); ++i) { if ((*i)->id() == id) { @@ -638,8 +638,8 @@ bool Router::idIsUnique(const unsigned int id) const } // Examine connectors. - for (ConnRefList::const_iterator i = connRefs.begin(); - i != connRefs.end(); ++i) + for (ConnRefList::const_iterator i = connRefs.begin(); + i != connRefs.end(); ++i) { if ((*i)->id() == id) { @@ -648,8 +648,8 @@ bool Router::idIsUnique(const unsigned int id) const } // Examine clusters. - for (ClusterRefList::const_iterator i = clusterRefs.begin(); - i != clusterRefs.end(); ++i) + for (ClusterRefList::const_iterator i = clusterRefs.begin(); + i != clusterRefs.end(); ++i) { if ((*i)->id() == id) { @@ -679,13 +679,13 @@ void Router::attachedConns(IntList &conns, const unsigned int shapeId, const unsigned int type) { ConnRefList::const_iterator fin = connRefs.end(); - for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i) + for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i) { - if ((type & runningTo) && ((*i)->_dstId == shapeId)) + if ((type & runningTo) && ((*i)->_dstId == shapeId)) { conns.push_back((*i)->_id); } - else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) + else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) { conns.push_back((*i)->_id); } @@ -699,9 +699,9 @@ void Router::attachedShapes(IntList &shapes, const unsigned int shapeId, const unsigned int type) { ConnRefList::const_iterator fin = connRefs.end(); - for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i) + for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i) { - if ((type & runningTo) && ((*i)->_dstId == shapeId)) + if ((type & runningTo) && ((*i)->_dstId == shapeId)) { if ((*i)->_srcId != 0) { @@ -709,7 +709,7 @@ void Router::attachedShapes(IntList &shapes, const unsigned int shapeId, shapes.push_back((*i)->_srcId); } } - else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) + else if ((type & runningFrom) && ((*i)->_srcId == shapeId)) { if ((*i)->_dstId != 0) { @@ -721,19 +721,19 @@ void Router::attachedShapes(IntList &shapes, const unsigned int shapeId, } - // It's intended this function is called after visibility changes - // resulting from shape movement have happened. It will alert + // It's intended this function is called after visibility changes + // resulting from shape movement have happened. It will alert // rerouted connectors (via a callback) that they need to be redrawn. void Router::rerouteAndCallbackConnectors(void) { std::set<ConnRef *> reroutedConns; ConnRefList::const_iterator fin = connRefs.end(); - - // Updating the orthogonal visibility graph if necessary. + + // Updating the orthogonal visibility graph if necessary. regenerateStaticBuiltGraph(); timers.Register(tmOrthogRoute, timerStart); - for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i) + for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i) { (*i)->_needs_repaint = false; bool rerouted = (*i)->generatePath(); @@ -751,7 +751,7 @@ void Router::rerouteAndCallbackConnectors(void) improveOrthogonalRoutes(this); // Alert connectors that they need redrawing. - for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i) + for (ConnRefList::const_iterator i = connRefs.begin(); i != fin; ++i) { (*i)->_needs_repaint = true; (*i)->performCallback(); @@ -770,18 +770,18 @@ void Router::improveCrossings(void) // No penalties, return. return; } - + // Find crossings and reroute connectors. _inCrossingPenaltyReroutingStage = true; ConnRefSet crossingConns; ConnRefList::iterator fin = connRefs.end(); - for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) + for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) { Avoid::Polygon& iRoute = (*i)->routeRef(); ConnRefList::iterator j = i; - for (++j; j != fin; ++j) + for (++j; j != fin; ++j) { - if ((crossingConns.find(*i) != crossingConns.end()) && + if ((crossingConns.find(*i) != crossingConns.end()) && (crossingConns.find(*j) != crossingConns.end())) { // We already know both these have crossings. @@ -795,13 +795,13 @@ void Router::improveCrossings(void) { const bool finalSegment = ((jInd + 1) == jRoute.size()); CrossingsInfoPair crossingInfo = countRealCrossings( - iRoute, true, jRoute, jInd, false, + iRoute, true, jRoute, jInd, false, finalSegment, NULL, NULL, *i, *j); - - if ((shared_path_penalty > 0) && - (crossingInfo.second & CROSSING_SHARES_PATH) && - (crossingInfo.second & CROSSING_SHARES_FIXED_SEGMENT) && - !(crossingInfo.second & CROSSING_SHARES_PATH_AT_END)) + + if ((shared_path_penalty > 0) && + (crossingInfo.second & CROSSING_SHARES_PATH) && + (crossingInfo.second & CROSSING_SHARES_FIXED_SEGMENT) && + !(crossingInfo.second & CROSSING_SHARES_PATH_AT_END)) { // We are penalising fixedSharedPaths and there is a // fixedSharedPath. @@ -823,7 +823,7 @@ void Router::improveCrossings(void) } } - for (ConnRefSet::iterator i = crossingConns.begin(); + for (ConnRefSet::iterator i = crossingConns.begin(); i != crossingConns.end(); ++i) { ConnRef *conn = *i; @@ -831,7 +831,7 @@ void Router::improveCrossings(void) // XXX: Could we free these routes here for extra savings? // conn->freeRoutes(); } - for (ConnRefSet::iterator i = crossingConns.begin(); + for (ConnRefSet::iterator i = crossingConns.begin(); i != crossingConns.end(); ++i) { ConnRef *conn = *i; @@ -862,9 +862,9 @@ void Router::newBlockingShape(const Polygon& poly, int pid) bool blocked = false; bool countBorder = false; - bool ep_in_poly1 = !(eID1.isShape) ? + bool ep_in_poly1 = !(eID1.isShape) ? inPoly(poly, e1, countBorder) : false; - bool ep_in_poly2 = !(eID2.isShape) ? + bool ep_in_poly2 = !(eID2.isShape) ? inPoly(poly, e2, countBorder) : false; if (ep_in_poly1 || ep_in_poly2) { @@ -879,7 +879,7 @@ void Router::newBlockingShape(const Polygon& poly, int pid) size_t pt_n = (pt_i == (poly.size() - 1)) ? 0 : pt_i + 1; const Point& pi = poly.ps[pt_i]; const Point& pn = poly.ps[pt_n]; - if (segmentShapeIntersect(e1, e2, pi, pn, + if (segmentShapeIntersect(e1, e2, pi, pn, seenIntersectionAtEndpoint)) { blocked = true; @@ -983,7 +983,7 @@ void Router::generateContains(VertInf *pt) // Computer enclosing Clusters ClusterRefList::const_iterator clFinish = clusterRefs.end(); - for (ClusterRefList::const_iterator i = clusterRefs.begin(); + for (ClusterRefList::const_iterator i = clusterRefs.begin(); i != clFinish; ++i) { if (inPolyGen((*i)->polygon(), pt->point)) @@ -994,7 +994,7 @@ void Router::generateContains(VertInf *pt) } -void Router::adjustClustersWithAdd(const PolygonInterface& poly, +void Router::adjustClustersWithAdd(const PolygonInterface& poly, const int p_cluster) { for (VertInf *k = vertices.connsBegin(); k != vertices.shapesBegin(); @@ -1422,11 +1422,11 @@ static void reduceRange(double& val) bool Router::existsOrthogonalPathOverlap(void) { ConnRefList::iterator fin = connRefs.end(); - for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) + for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) { Avoid::Polygon iRoute = (*i)->displayRoute(); ConnRefList::iterator j = i; - for (++j; j != fin; ++j) + for (++j; j != fin; ++j) { // Determine if this pair overlap Avoid::Polygon jRoute = (*j)->displayRoute(); @@ -1435,12 +1435,12 @@ bool Router::existsOrthogonalPathOverlap(void) { const bool finalSegment = ((jInd + 1) == jRoute.size()); CrossingsInfoPair crossingInfo = countRealCrossings( - iRoute, true, jRoute, jInd, true, + iRoute, true, jRoute, jInd, true, finalSegment, NULL, NULL, *i, *j); - - if ((crossingInfo.second & CROSSING_SHARES_PATH) && - (crossingInfo.second & CROSSING_SHARES_FIXED_SEGMENT) && - !(crossingInfo.second & CROSSING_SHARES_PATH_AT_END)) + + if ((crossingInfo.second & CROSSING_SHARES_PATH) && + (crossingInfo.second & CROSSING_SHARES_FIXED_SEGMENT) && + !(crossingInfo.second & CROSSING_SHARES_PATH_AT_END)) { // We looking for fixedSharedPaths and there is a // fixedSharedPath. @@ -1456,11 +1456,11 @@ bool Router::existsOrthogonalPathOverlap(void) bool Router::existsOrthogonalTouchingCorners(void) { ConnRefList::iterator fin = connRefs.end(); - for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) + for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) { Avoid::Polygon iRoute = (*i)->displayRoute(); ConnRefList::iterator j = i; - for (++j; j != fin; ++j) + for (++j; j != fin; ++j) { // Determine if this pair overlap Avoid::Polygon jRoute = (*j)->displayRoute(); @@ -1469,10 +1469,10 @@ bool Router::existsOrthogonalTouchingCorners(void) { const bool finalSegment = ((jInd + 1) == jRoute.size()); CrossingsInfoPair crossingInfo = countRealCrossings( - iRoute, true, jRoute, jInd, true, + iRoute, true, jRoute, jInd, true, finalSegment, NULL, NULL, *i, *j); - - if (crossingInfo.second & CROSSING_TOUCHES) + + if (crossingInfo.second & CROSSING_TOUCHES) { return true; } @@ -1514,7 +1514,7 @@ void Router::outputInstanceToSVG(std::string instanceName) reduceRange(p.x); reduceRange(p.y); - + if (p.x > -LIMIT) { minX = std::min(minX, p.x); @@ -1550,8 +1550,8 @@ void Router::outputInstanceToSVG(std::string instanceName) fprintf(fp, " PolyLineRouting | OrthogonalRouting);\n"); for (size_t p = 0; p < lastPenaltyMarker; ++p) { - fprintf(fp, " router->setRoutingPenalty((PenaltyType)%lu, %g);\n", - p, _routingPenalties[p]); + fprintf(fp, " router->setRoutingPenalty((PenaltyType)%lu, %g);\n", + static_cast<long unsigned int>(p), _routingPenalties[p]); } fprintf(fp, " router->setOrthogonalNudgeDistance(%g);\n\n", orthogonalNudgeDistance()); @@ -1559,12 +1559,12 @@ void Router::outputInstanceToSVG(std::string instanceName) while (shRefIt != shapeRefs.end()) { ShapeRef *shRef = *shRefIt; - fprintf(fp, " Polygon poly%u(%lu);\n", - shRef->id(), shRef->polygon().size()); + fprintf(fp, " Polygon poly%u(%lu);\n", + shRef->id(), static_cast<long unsigned int>(shRef->polygon().size())); for (size_t i = 0; i < shRef->polygon().size(); ++i) { - fprintf(fp, " poly%u.ps[%lu] = Point(%g, %g);\n", - shRef->id(), i, shRef->polygon().at(i).x, + fprintf(fp, " poly%u.ps[%lu] = Point(%g, %g);\n", + shRef->id(), static_cast<long unsigned int>(i), shRef->polygon().at(i).x, shRef->polygon().at(i).y); } fprintf(fp, " ShapeRef *shapeRef%u = new ShapeRef(router, poly%u, " @@ -1594,7 +1594,7 @@ void Router::outputInstanceToSVG(std::string instanceName) fprintf(fp, " connRef%u->setDestEndpoint(dstPt%u);\n", connRef->id(), connRef->id()); } - fprintf(fp, " connRef%u->setRoutingType((ConnType)%u);\n\n", + fprintf(fp, " connRef%u->setRoutingType((ConnType)%u);\n\n", connRef->id(), connRef->routingType()); ++revConnRefIt; } @@ -1605,20 +1605,20 @@ void Router::outputInstanceToSVG(std::string instanceName) fprintf(fp, "};\n"); fprintf(fp, "-->\n"); - + fprintf(fp, "<g inkscape:groupmode=\"layer\" " "inkscape:label=\"ShapesPoly\">\n"); shRefIt = shapeRefs.begin(); while (shRefIt != shapeRefs.end()) { ShapeRef *shRef = *shRefIt; - + fprintf(fp, "<path id=\"poly-%u\" style=\"stroke-width: 1px; " - "stroke: black; fill: blue; fill-opacity: 0.3;\" d=\"", + "stroke: black; fill: blue; fill-opacity: 0.3;\" d=\"", shRef->id()); for (size_t i = 0; i < shRef->polygon().size(); ++i) { - fprintf(fp, "%c %g,%g ", ((i == 0) ? 'M' : 'L'), + fprintf(fp, "%c %g,%g ", ((i == 0) ? 'M' : 'L'), shRef->polygon().at(i).x, shRef->polygon().at(i).y); } fprintf(fp, "Z\" />\n"); @@ -1635,7 +1635,7 @@ void Router::outputInstanceToSVG(std::string instanceName) ShapeRef *shRef = *shRefIt; double minX, minY, maxX, maxY; shRef->polygon().getBoundingRect(&minX, &minY, &maxX, &maxY); - + fprintf(fp, "<rect id=\"rect-%u\" x=\"%g\" y=\"%g\" width=\"%g\" height=\"%g\" " "style=\"stroke-width: 1px; stroke: black; fill: blue; fill-opacity: 0.3;\" />\n", shRef->id(), minX, minY, maxX - minX, maxY - minY); @@ -1664,16 +1664,16 @@ void Router::outputInstanceToSVG(std::string instanceName) std::pair<Point, Point> ptpair = t->points(); Point p1 = ptpair.first; Point p2 = ptpair.second; - + reduceRange(p1.x); reduceRange(p1.y); reduceRange(p2.x); reduceRange(p2.y); - + fprintf(fp, "<path d=\"M %g,%g L %g,%g\" " - "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n", + "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n", p1.x, p1.y, p2.x, p2.y, - (!(ids.first.isShape) || !(ids.second.isShape)) ? "green" : + (!(ids.first.isShape) || !(ids.second.isShape)) ? "green" : "red"); } fprintf(fp, "</g>\n"); @@ -1694,16 +1694,16 @@ void Router::outputInstanceToSVG(std::string instanceName) std::pair<Point, Point> ptpair = t->points(); Point p1 = ptpair.first; Point p2 = ptpair.second; - + reduceRange(p1.x); reduceRange(p1.y); reduceRange(p2.x); reduceRange(p2.y); - + fprintf(fp, "<path d=\"M %g,%g L %g,%g\" " - "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n", + "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n", p1.x, p1.y, p2.x, p2.y, - (!(ids.first.isShape) || !(ids.second.isShape)) ? "green" : + (!(ids.first.isShape) || !(ids.second.isShape)) ? "green" : "red"); } fprintf(fp, "</g>\n"); @@ -1718,18 +1718,18 @@ void Router::outputInstanceToSVG(std::string instanceName) std::pair<Point, Point> ptpair = t->points(); Point p1 = ptpair.first; Point p2 = ptpair.second; - + reduceRange(p1.x); reduceRange(p1.y); reduceRange(p2.x); reduceRange(p2.y); - + std::pair<VertID, VertID> ids = t->ids(); fprintf(fp, "<path d=\"M %g,%g L %g,%g\" " - "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n", + "style=\"fill: none; stroke: %s; stroke-width: 1px;\" />\n", p1.x, p1.y, p2.x, p2.y, - (!(ids.first.isShape) || !(ids.second.isShape)) ? "green" : + (!(ids.first.isShape) || !(ids.second.isShape)) ? "green" : "red"); } fprintf(fp, "</g>\n"); @@ -1742,7 +1742,7 @@ void Router::outputInstanceToSVG(std::string instanceName) while (connRefIt != connRefs.end()) { ConnRef *connRef = *connRefIt; - + PolyLine route = connRef->route(); if (!route.empty()) { @@ -1762,7 +1762,7 @@ void Router::outputInstanceToSVG(std::string instanceName) fprintf(fp, "style=\"fill: none; stroke: black; " "stroke-width: 1px;\" />\n"); } - + ++connRefIt; } fprintf(fp, "</g>\n"); @@ -1775,7 +1775,7 @@ void Router::outputInstanceToSVG(std::string instanceName) while (connRefIt != connRefs.end()) { ConnRef *connRef = *connRefIt; - + PolyLine route = connRef->displayRoute().curvedPolyline(8); if (!route.empty()) { @@ -1785,7 +1785,7 @@ void Router::outputInstanceToSVG(std::string instanceName) { if (route.ts[i] == 'C') { - fprintf(fp, "%c %g,%g %g,%g %g,%g", route.ts[i], + fprintf(fp, "%c %g,%g %g,%g %g,%g", route.ts[i], route.ps[i].x, route.ps[i].y, route.ps[i+1].x, route.ps[i+1].y, route.ps[i+2].x, route.ps[i+2].y); @@ -1793,7 +1793,7 @@ void Router::outputInstanceToSVG(std::string instanceName) } else { - fprintf(fp, "%c %g,%g ", route.ts[i], + fprintf(fp, "%c %g,%g ", route.ts[i], route.ps[i].x, route.ps[i].y); } } @@ -1807,7 +1807,7 @@ void Router::outputInstanceToSVG(std::string instanceName) fprintf(fp, "style=\"fill: none; stroke: black; " "stroke-width: 1px;\" />\n"); } - + ++connRefIt; } fprintf(fp, "</g>\n"); @@ -1820,7 +1820,7 @@ void Router::outputInstanceToSVG(std::string instanceName) while (connRefIt != connRefs.end()) { ConnRef *connRef = *connRefIt; - + PolyLine route = connRef->displayRoute(); if (!route.empty()) { @@ -1840,7 +1840,7 @@ void Router::outputInstanceToSVG(std::string instanceName) fprintf(fp, "style=\"fill: none; stroke: black; " "stroke-width: 1px;\" />\n"); } - + ++connRefIt; } fprintf(fp, "</g>\n"); diff --git a/src/libavoid/vpsc.cpp b/src/libavoid/vpsc.cpp index c9a072375..19d360375 100644 --- a/src/libavoid/vpsc.cpp +++ b/src/libavoid/vpsc.cpp @@ -12,12 +12,12 @@ * See the file LICENSE.LGPL distributed with the library. * * Licensees holding a valid commercial license may use this file in - * accordance with the commercial license agreement provided with the + * accordance with the commercial license agreement provided with the * library. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * * Author(s): Tim Dwyer <Tim.Dwyer@csse.monash.edu.au> * @@ -52,11 +52,11 @@ namespace Avoid { static const double ZERO_UPPERBOUND=-1e-10; static const double LAGRANGIAN_TOLERANCE=-1e-4; -IncSolver::IncSolver(vector<Variable*> const &vs, vector<Constraint *> const &cs) - : m(cs.size()), - cs(cs), - n(vs.size()), - vs(vs) +IncSolver::IncSolver(vector<Variable*> const &vs, vector<Constraint *> const &cs) + : m(cs.size()), + cs(cs), + n(vs.size()), + vs(vs) { for(unsigned i=0;i<n;++i) { vs[i]->in.clear(); @@ -232,7 +232,7 @@ bool IncSolver::solve() { #endif } copyResult(); - return bs->size()!=n; + return bs->size()!=n; } /* * incremental version of satisfy that allows refinement after blocks are @@ -244,8 +244,8 @@ bool IncSolver::solve() { * * Note: there is a special case to handle when the most violated constraint * is between two variables in the same block. Then, we must split the block - * over an active constraint between the two variables. We choose the - * constraint with the most negative lagrangian multiplier. + * over an active constraint between the two variables. We choose the + * constraint with the most negative lagrangian multiplier. */ bool IncSolver::satisfy() { #ifdef LIBVPSC_LOGGING @@ -256,8 +256,8 @@ bool IncSolver::satisfy() { //long splitCtr = 0; Constraint* v = NULL; //CBuffer buffer(inactive); - while((v=mostViolated(inactive)) - &&(v->equality || v->slack() < ZERO_UPPERBOUND && !v->active)) + while((v = mostViolated(inactive)) + && (v->equality || ((v->slack() < ZERO_UPPERBOUND) && !v->active))) { COLA_ASSERT(!v->active); Block *lb = v->left->block, *rb = v->right->block; @@ -411,7 +411,7 @@ Constraint* IncSolver::mostViolated(Constraints &l) { Constraint *c=*i; double slack = c->slack(); if(c->equality || slack < minSlack) { - minSlack=slack; + minSlack=slack; v=c; deletePoint=i; if(c->equality) break; @@ -421,7 +421,8 @@ Constraint* IncSolver::mostViolated(Constraints &l) { // move the last element over the deletePoint and resize // downwards. There is always at least 1 element in the // vector because of search. - if(deletePoint != end && (minSlack < ZERO_UPPERBOUND && !v->active || v->equality)) { + // TODO check this logic and add parens: + if((deletePoint != end) && ((minSlack < ZERO_UPPERBOUND) && !v->active || v->equality)) { *deletePoint = l[l.size()-1]; l.resize(l.size()-1); } @@ -457,7 +458,7 @@ Blocks::~Blocks(void) } /* - * returns a list of variables with total ordering determined by the constraint + * returns a list of variables with total ordering determined by the constraint * DAG */ list<Variable*> *Blocks::totalOrder() { @@ -482,7 +483,7 @@ void Blocks::dfsVisit(Variable *v, list<Variable*> *order) { if(!c->right->visited) { dfsVisit(c->right, order); } - } + } #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f<<" order="<<*v<<endl; @@ -493,7 +494,7 @@ void Blocks::dfsVisit(Variable *v, list<Variable*> *order) { * Processes incoming constraints, most violated to least, merging with the * neighbouring (left) block until no more violated constraints are found */ -void Blocks::mergeLeft(Block *r) { +void Blocks::mergeLeft(Block *r) { #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f<<"mergeLeft called on "<<*r<<endl; @@ -506,7 +507,7 @@ void Blocks::mergeLeft(Block *r) { f<<"mergeLeft on constraint: "<<*c<<endl; #endif r->deleteMinInConstraint(); - Block *l = c->left->block; + Block *l = c->left->block; if (l->in==NULL) l->setUpInConstraints(); double dist = c->right->offset - c->left->offset - c->gap; if (r->vars->size() < l->vars->size()) { @@ -519,22 +520,22 @@ void Blocks::mergeLeft(Block *r) { r->timeStamp=blockTimeCtr; removeBlock(l); c=r->findMinInConstraint(); - } + } #ifdef LIBVPSC_LOGGING f<<"merged "<<*r<<endl; #endif -} +} /* * Symmetrical to mergeLeft */ -void Blocks::mergeRight(Block *l) { +void Blocks::mergeRight(Block *l) { #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); f<<"mergeRight called on "<<*l<<endl; -#endif +#endif l->setUpOutConstraints(); Constraint *c = l->findMinOutConstraint(); - while (c != NULL && c->slack()<0) { + while (c != NULL && c->slack()<0) { #ifdef LIBVPSC_LOGGING f<<"mergeRight on constraint: "<<*c<<endl; #endif @@ -550,7 +551,7 @@ void Blocks::mergeRight(Block *l) { l->mergeOut(r); removeBlock(r); c=l->findMinOutConstraint(); - } + } #ifdef LIBVPSC_LOGGING f<<"merged "<<*l<<endl; #endif @@ -618,7 +619,7 @@ void PositionStats::addVariable(Variable* v) { /* #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); - f << "adding v[" << v->id << "], blockscale=" << scale << ", despos=" + f << "adding v[" << v->id << "], blockscale=" << scale << ", despos=" << v->desiredPosition << ", ai=" << ai << ", bi=" << bi << ", AB=" << AB << ", AD=" << AD << ", A2=" << A2; #endif @@ -692,12 +693,12 @@ void Block::setUpConstraintHeap(Heap* &h,bool in) { for (Cit j=cs->begin();j!=cs->end();++j) { Constraint *c=*j; c->timeStamp=blockTimeCtr; - if (c->left->block != this && in || c->right->block != this && !in) { + if (((c->left->block != this) && in) || ((c->right->block != this) && !in)) { h->push(c); } } } -} +} Block* Block::merge(Block* b, Constraint* c) { #ifdef LIBVPSC_LOGGING ofstream f(LOGFILE,ios::app); @@ -772,7 +773,7 @@ void Block::mergeIn(Block *b) { f<<" merged heap: "<<*in<<endl; #endif } -void Block::mergeOut(Block *b) { +void Block::mergeOut(Block *b) { findMinOutConstraint(); b->findMinOutConstraint(); while (!b->out->empty()) @@ -904,21 +905,21 @@ double Block::compute_dfdv(Variable* const v, Variable* const u) { } // The top level v and r are variables between which we want to find the -// constraint with the smallest lm. +// constraint with the smallest lm. // Similarly, m is initially NULL and is only assigned a value if the next // variable to be visited is r or if a possible min constraint is returned from // a nested call (rather than NULL). // Then, the search for the m with minimum lm occurs as we return from -// the recursion (checking only constraints traversed left-to-right +// the recursion (checking only constraints traversed left-to-right // in order to avoid creating any new violations). // We also do not consider equality constraints as potential split points bool Block::split_path( - Variable* r, - Variable* const v, - Variable* const u, + Variable* r, + Variable* const v, + Variable* const u, Constraint* &m, bool desperation=false - ) + ) { for(Cit it(v->in.begin());it!=v->in.end();++it) { Constraint *c=*it; @@ -963,43 +964,43 @@ bool Block::split_path( } /* Block::Pair Block::compute_dfdv_between( - Variable* r, Variable* const v, Variable* const u, + Variable* r, Variable* const v, Variable* const u, const Direction dir = NONE, bool changedDirection = false) { double dfdv=v->weight*(v->position() - v->desiredPosition); Constraint *m=NULL; for(Cit it(v->in.begin());it!=v->in.end();++it) { Constraint *c=*it; if(canFollowLeft(c,u)) { - if(dir==RIGHT) { - changedDirection = true; + if(dir==RIGHT) { + changedDirection = true; } if(c->left==r) { r=NULL; - if(!c->equality) m=c; + if(!c->equality) m=c; } Pair p=compute_dfdv_between(r,c->left,v, LEFT,changedDirection); dfdv -= c->lm = -p.first; - if(r && p.second) + if(r && p.second) m = p.second; } } for(Cit it(v->out.begin());it!=v->out.end();++it) { Constraint *c=*it; if(canFollowRight(c,u)) { - if(dir==LEFT) { - changedDirection = true; + if(dir==LEFT) { + changedDirection = true; } if(c->right==r) { - r=NULL; - if(!c->equality) m=c; + r=NULL; + if(!c->equality) m=c; } Pair p=compute_dfdv_between(r,c->right,v, RIGHT,changedDirection); dfdv += c->lm = p.first; - if(r && p.second) - m = changedDirection && !c->equality && c->lm < p.second->lm - ? c + if(r && p.second) + m = changedDirection && !c->equality && c->lm < p.second->lm + ? c : p.second; } } @@ -1084,7 +1085,7 @@ Constraint *Block::findMinLMBetween(Variable* const lv, Variable* const rv) { return min_lm; } -// populates block b by traversing the active constraint tree adding variables as they're +// populates block b by traversing the active constraint tree adding variables as they're // visited. Starts from variable v and does not backtrack over variable u. void Block::populateSplitBlock(Block *b, Variable* v, Variable const* u) { b->addVariable(v); @@ -1093,7 +1094,7 @@ void Block::populateSplitBlock(Block *b, Variable* v, Variable const* u) { populateSplitBlock(b, (*c)->left, v); } for (Cit c=v->out.begin();c!=v->out.end();++c) { - if (canFollowRight(*c,u)) + if (canFollowRight(*c,u)) populateSplitBlock(b, (*c)->right, v); } } @@ -1225,7 +1226,7 @@ Constraint::Constraint(Variable *left, Variable *right, double gap, bool equalit //right->in.push_back(this); } Constraint::~Constraint() { - // see constructor: the following is just way too slow. + // see constructor: the following is just way too slow. // Better to create a // new DAG on demand than maintain the lists dynamically. //Constraints::iterator i; @@ -1238,10 +1239,10 @@ Constraint::~Constraint() { //} //right->in.erase(i); } -double Constraint::slack() const { +double Constraint::slack() const { return unsatisfiable ? DBL_MAX - : right->scale * right->position() - - gap - left->scale * left->position(); + : right->scale * right->position() + - gap - left->scale * left->position(); } std::ostream& operator <<(std::ostream &os, const Constraint &c) { @@ -1269,11 +1270,11 @@ std::ostream& operator <<(std::ostream &os, const Constraint &c) bool CompareConstraints::operator() ( Constraint *const &l, Constraint *const &r ) const { - double const sl = + double const sl = l->left->block->timeStamp > l->timeStamp ||l->left->block==l->right->block ?-DBL_MAX:l->slack(); - double const sr = + double const sr = r->left->block->timeStamp > r->timeStamp ||r->left->block==r->right->block ?-DBL_MAX:r->slack(); |