1 /* 2 * vim: ts=4 sw=4 et tw=0 wm=0 3 * 4 * libavoid - Fast, Incremental, Object-avoiding Line Router 5 * 6 * Copyright (C) 2004-2013 Monash University 7 * 8 * This library is free software; you can redistribute it and/or 9 * modify it under the terms of the GNU Lesser General Public 10 * License as published by the Free Software Foundation; either 11 * version 2.1 of the License, or (at your option) any later version. 12 * See the file LICENSE.LGPL distributed with the library. 13 * 14 * Licensees holding a valid commercial license may use this file in 15 * accordance with the commercial license agreement provided with the 16 * library. 17 * 18 * This library is distributed in the hope that it will be useful, 19 * but WITHOUT ANY WARRANTY; without even the implied warranty of 20 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 21 * 22 * Author(s): Michael Wybrow 23 */ 24 25 26 #ifndef AVOID_VERTICES_H 27 #define AVOID_VERTICES_H 28 29 #include <list> 30 #include <set> 31 #include <map> 32 #include <iostream> 33 #include <cstdio> 34 #include <utility> 35 36 #include "libavoid/geomtypes.h" 37 38 namespace Avoid { 39 40 class EdgeInf; 41 class VertInf; 42 class Router; 43 44 typedef std::list<EdgeInf *> EdgeInfList; 45 typedef std::pair<VertInf *, VertInf *> VertexPair; 46 47 typedef unsigned int ConnDirFlags; 48 typedef unsigned short VertIDProps; 49 50 51 class VertID 52 { 53 public: 54 unsigned int objID; 55 unsigned short vn; 56 // Properties: 57 VertIDProps props; 58 59 static const unsigned short src; 60 static const unsigned short tar; 61 62 static const VertIDProps PROP_ConnPoint; 63 static const VertIDProps PROP_OrthShapeEdge; 64 static const VertIDProps PROP_ConnectionPin; 65 static const VertIDProps PROP_ConnCheckpoint; 66 static const VertIDProps PROP_DummyPinHelper; 67 68 VertID(); 69 VertID(unsigned int id, unsigned short n, VertIDProps p = 0); 70 VertID(const VertID& other); 71 VertID& operator= (const VertID& rhs); 72 bool operator==(const VertID& rhs) const; 73 bool operator!=(const VertID& rhs) const; 74 bool operator<(const VertID& rhs) const; 75 VertID operator+(const int& rhs) const; 76 VertID operator-(const int& rhs) const; 77 VertID& operator++(int); 78 void print(FILE *file = stdout) const; 79 void db_print(void) const; 80 friend std::ostream& operator<<(std::ostream& os, const VertID& vID); 81 82 // Property tests: isOrthShapeEdge(void)83 inline bool isOrthShapeEdge(void) const 84 { 85 return (props & PROP_OrthShapeEdge) ? true : false; 86 } isConnPt(void)87 inline bool isConnPt(void) const 88 { 89 return (props & PROP_ConnPoint) ? true : false; 90 } isConnectionPin(void)91 inline bool isConnectionPin(void) const 92 { 93 return (props & PROP_ConnectionPin) ? true : false; 94 } isConnCheckpoint(void)95 inline bool isConnCheckpoint(void) const 96 { 97 return (props & PROP_ConnCheckpoint) ? true : false; 98 } isDummyPinHelper(void)99 inline bool isDummyPinHelper(void) const 100 { 101 return (props & PROP_DummyPinHelper) ? true : false; 102 } 103 }; 104 105 106 // An ID given to all dummy vertices inserted to allow creation of the 107 // orthogonal visibility graph since the vertices in the orthogonal graph 108 // mostly do not correspond to shape corners or connector endpoints. 109 // 110 static const VertID dummyOrthogID(0, 0); 111 static const VertID dummyOrthogShapeID(0, 0, VertID::PROP_OrthShapeEdge); 112 113 class ANode; 114 115 class VertInf 116 { 117 public: 118 VertInf(Router *router, const VertID& vid, const Point& vpoint, 119 const bool addToRouter = true); 120 ~VertInf(); 121 void Reset(const VertID& vid, const Point& vpoint); 122 void Reset(const Point& vpoint); 123 void removeFromGraph(const bool isConnVert = true); 124 bool orphaned(void); 125 126 unsigned int pathLeadsBackTo(const VertInf *start) const; 127 void setVisibleDirections(const ConnDirFlags directions); 128 ConnDirFlags directionFrom(const VertInf *other) const; 129 // Checks if this vertex has the target as a visibility neighbour. 130 EdgeInf *hasNeighbour(VertInf *target, bool orthogonal) const; 131 void orphan(void); 132 133 VertInf **makeTreeRootPointer(VertInf *root); 134 VertInf *treeRoot(void) const; 135 VertInf **treeRootPointer(void) const; 136 void setTreeRootPointer(VertInf **pointer); 137 void clearTreeRootPointer(void); 138 139 void setSPTFRoot(VertInf *root); 140 VertInf *sptfRoot(void) const; 141 142 Router *_router; 143 VertID id; 144 Point point; 145 VertInf *lstPrev; 146 VertInf *lstNext; 147 VertInf *shPrev; 148 VertInf *shNext; 149 EdgeInfList visList; 150 unsigned int visListSize; 151 EdgeInfList orthogVisList; 152 unsigned int orthogVisListSize; 153 EdgeInfList invisList; 154 unsigned int invisListSize; 155 VertInf *pathNext; 156 157 // The tree root and distance value used when computing MTSTs. 158 // XXX: Maybe these should be allocated as a separate struct 159 // and referenced via a pointer. This would be slower due 160 // to memory allocation, but would save 2 x 8 = 24 bytes per 161 // VertInf on 64-bit machines. 162 VertInf *m_orthogonalPartner; 163 VertInf **m_treeRoot; 164 double sptfDist; 165 166 ConnDirFlags visDirections; 167 std::list<ANode *> aStarDoneNodes; 168 std::list<ANode *> aStarPendingNodes; 169 // Flags for orthogonal visibility properties, i.e., whether the 170 // line points to a shape edge, connection point or an obstacle. 171 unsigned int orthogVisPropFlags; 172 }; 173 174 175 // Orthogonal visibility property flags 176 static const unsigned int XL_EDGE = 1; 177 static const unsigned int XL_CONN = 2; 178 static const unsigned int XH_EDGE = 4; 179 static const unsigned int XH_CONN = 8; 180 static const unsigned int YL_EDGE = 16; 181 static const unsigned int YL_CONN = 32; 182 static const unsigned int YH_EDGE = 64; 183 static const unsigned int YH_CONN = 128; 184 185 186 bool directVis(VertInf *src, VertInf *dst); 187 188 189 // A linked list of all the vertices in the router instance. All the 190 // connector endpoints are listed first, then all the shape vertices. 191 // Dummy vertices inserted for orthogonal routing are classed as shape 192 // vertices but have VertID(0, 0). 193 // 194 class VertInfList 195 { 196 public: 197 VertInfList(); 198 void addVertex(VertInf *vert); 199 VertInf *removeVertex(VertInf *vert); 200 VertInf *getVertexByID(const VertID& id); 201 VertInf *getVertexByPos(const Point& p); 202 VertInf *shapesBegin(void); 203 VertInf *connsBegin(void); 204 VertInf *end(void); 205 unsigned int connsSize(void) const; 206 unsigned int shapesSize(void) const; 207 private: 208 VertInf *_firstShapeVert; 209 VertInf *_firstConnVert; 210 VertInf *_lastShapeVert; 211 VertInf *_lastConnVert; 212 unsigned int _shapeVertices; 213 unsigned int _connVertices; 214 }; 215 216 217 typedef std::set<unsigned int> ShapeSet; 218 typedef std::map<VertID, ShapeSet> ContainsMap; 219 220 221 } 222 223 224 #endif 225 226 227