diff options
Diffstat (limited to 'src/libavoid/vertices.h')
| -rw-r--r-- | src/libavoid/vertices.h | 94 |
1 files changed, 83 insertions, 11 deletions
diff --git a/src/libavoid/vertices.h b/src/libavoid/vertices.h index 619692c23..aac43bb4c 100644 --- a/src/libavoid/vertices.h +++ b/src/libavoid/vertices.h @@ -3,7 +3,7 @@ * * libavoid - Fast, Incremental, Object-avoiding Line Router * - * Copyright (C) 2004-2009 Monash University + * Copyright (C) 2004-2013 Monash University * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public @@ -19,7 +19,7 @@ * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * - * Author(s): Michael Wybrow <mjwybrow@users.sourceforge.net> + * Author(s): Michael Wybrow */ @@ -31,31 +31,42 @@ #include <map> #include <iostream> #include <cstdio> +#include <utility> #include "libavoid/geomtypes.h" namespace Avoid { class EdgeInf; +class VertInf; class Router; typedef std::list<EdgeInf *> EdgeInfList; +typedef std::pair<VertInf *, VertInf *> VertexPair; typedef unsigned int ConnDirFlags; +typedef unsigned short VertIDProps; class VertID { public: unsigned int objID; - bool isShape; unsigned short vn; + // Properties: + VertIDProps props; static const unsigned short src; static const unsigned short tar; + + static const VertIDProps PROP_ConnPoint; + static const VertIDProps PROP_OrthShapeEdge; + static const VertIDProps PROP_ConnectionPin; + static const VertIDProps PROP_ConnCheckpoint; + static const VertIDProps PROP_DummyPinHelper; VertID(); - VertID(unsigned int id, bool s, int n); + VertID(unsigned int id, unsigned short n, VertIDProps p = 0); VertID(const VertID& other); VertID& operator= (const VertID& rhs); bool operator==(const VertID& rhs) const; @@ -67,6 +78,28 @@ class VertID void print(FILE *file = stdout) const; void db_print(void) const; friend std::ostream& operator<<(std::ostream& os, const VertID& vID); + + // Property tests: + inline bool isOrthShapeEdge(void) const + { + return (props & PROP_OrthShapeEdge) ? true : false; + } + inline bool isConnPt(void) const + { + return (props & PROP_ConnPoint) ? true : false; + } + inline bool isConnectionPin(void) const + { + return (props & PROP_ConnectionPin) ? true : false; + } + inline bool isConnCheckpoint(void) const + { + return (props & PROP_ConnCheckpoint) ? true : false; + } + inline bool isDummyPinHelper(void) const + { + return (props & PROP_DummyPinHelper) ? true : false; + } }; @@ -74,8 +107,10 @@ class VertID // orthogonal visibility graph since the vertices in the orthogonal graph // mostly do not correspond to shape corners or connector endpoints. // -static const VertID dummyOrthogID(0, true, 0); +static const VertID dummyOrthogID(0, 0); +static const VertID dummyOrthogShapeID(0, 0, VertID::PROP_OrthShapeEdge); +class ANode; class VertInf { @@ -88,6 +123,22 @@ class VertInf void removeFromGraph(const bool isConnVert = true); bool orphaned(void); + unsigned int pathLeadsBackTo(const VertInf *start) const; + void setVisibleDirections(const ConnDirFlags directions); + ConnDirFlags directionFrom(const VertInf *other) const; + // Checks if this vertex has the target as a visibility neighbour. + EdgeInf *hasNeighbour(VertInf *target, bool orthogonal) const; + void orphan(void); + + VertInf **makeTreeRootPointer(VertInf *root); + VertInf *treeRoot(void) const; + VertInf **treeRootPointer(void) const; + void setTreeRootPointer(VertInf **pointer); + void clearTreeRootPointer(void); + + void setSPTFRoot(VertInf *root); + VertInf *sptfRoot(void) const; + Router *_router; VertID id; Point point; @@ -102,16 +153,42 @@ class VertInf EdgeInfList invisList; unsigned int invisListSize; VertInf *pathNext; + + // The tree root and distance value used when computing MTSTs. + // XXX: Maybe these should be allocated as a separate struct + // and referenced via a pointer. This would be slower due + // to memory allocation, but would save 2 x 8 = 24 bytes per + // VertInf on 64-bit machines. + VertInf *m_orthogonalPartner; + VertInf **m_treeRoot; + double sptfDist; + ConnDirFlags visDirections; + std::list<ANode *> aStarDoneNodes; + std::list<ANode *> aStarPendingNodes; + // Flags for orthogonal visibility properties, i.e., whether the + // line points to a shape edge, connection point or an obstacle. + unsigned int orthogVisPropFlags; }; +// Orthogonal visibility property flags +static const unsigned int XL_EDGE = 1; +static const unsigned int XL_CONN = 2; +static const unsigned int XH_EDGE = 4; +static const unsigned int XH_CONN = 8; +static const unsigned int YL_EDGE = 16; +static const unsigned int YL_CONN = 32; +static const unsigned int YH_EDGE = 64; +static const unsigned int YH_CONN = 128; + + bool directVis(VertInf *src, VertInf *dst); // A linked list of all the vertices in the router instance. All the // connector endpoints are listed first, then all the shape vertices. -// Dunnny vertices inserted for orthogonal routing are classed as shape +// Dummy vertices inserted for orthogonal routing are classed as shape // vertices but have VertID(0, 0). // class VertInfList @@ -127,11 +204,6 @@ class VertInfList VertInf *end(void); unsigned int connsSize(void) const; unsigned int shapesSize(void) const; - void stats(FILE *fp = stderr) - { - fprintf(fp, "Conns %u, shapes %u\n", _connVertices, - _shapeVertices); - } private: VertInf *_firstShapeVert; VertInf *_firstConnVert; |