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