vertices.h
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-2009 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 <mjwybrow@users.sourceforge.net>
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 
35 #include "libavoid/geomtypes.h"
36 
37 namespace Avoid {
38 
39 class EdgeInf;
40 class Router;
41 
42 typedef std::list<EdgeInf *> EdgeInfList;
43 
44 typedef unsigned int ConnDirFlags;
45 typedef unsigned short VertIDProps;
46 
47 
48 class VertID
49 {
50  public:
51  unsigned int objID;
52  unsigned short vn;
53  // Properties:
54  VertIDProps props;
55 
56  static const unsigned short src;
57  static const unsigned short tar;
58 
59  static const VertIDProps PROP_ConnPoint;
60  static const VertIDProps PROP_OrthShapeEdge;
61  static const VertIDProps PROP_ConnectionPin;
62  static const VertIDProps PROP_ConnCheckpoint;
63 
64  VertID();
65  VertID(unsigned int id, unsigned short n, VertIDProps p = 0);
66  VertID(const VertID& other);
67  VertID& operator= (const VertID& rhs);
68  bool operator==(const VertID& rhs) const;
69  bool operator!=(const VertID& rhs) const;
70  bool operator<(const VertID& rhs) const;
71  VertID operator+(const int& rhs) const;
72  VertID operator-(const int& rhs) const;
73  VertID& operator++(int);
74  void print(FILE *file = stdout) const;
75  void db_print(void) const;
76  friend std::ostream& operator<<(std::ostream& os, const VertID& vID);
77 
78  // Property tests:
79  inline bool isOrthShapeEdge(void) const
80  {
81  return (props & PROP_OrthShapeEdge) ? true : false;
82  }
83  inline bool isConnPt(void) const
84  {
85  return (props & PROP_ConnPoint) ? true : false;
86  }
87  inline bool isConnectionPin(void) const
88  {
89  return (props & PROP_ConnectionPin) ? true : false;
90  }
91  inline bool isConnCheckpoint(void) const
92  {
93  return (props & PROP_ConnCheckpoint) ? true : false;
94  }
95 };
96 
97 
98 // An ID given to all dummy vertices inserted to allow creation of the
99 // orthogonal visibility graph since the vertices in the orthogonal graph
100 // mostly do not correspond to shape corners or connector endpoints.
101 //
102 static const VertID dummyOrthogID(0, 0);
103 static const VertID dummyOrthogShapeID(0, 0, VertID::PROP_OrthShapeEdge);
104 
105 
106 class VertInf
107 {
108  public:
109  VertInf(Router *router, const VertID& vid, const Point& vpoint,
110  const bool addToRouter = true);
111  ~VertInf();
112  void Reset(const VertID& vid, const Point& vpoint);
113  void Reset(const Point& vpoint);
114  void removeFromGraph(const bool isConnVert = true);
115  bool orphaned(void);
116 
117  unsigned int pathLeadsBackTo(const VertInf *start) const;
118 
119  // Checks if this vertex has the target as a visibility neighbour.
120  bool hasNeighbour(VertInf *target, bool orthogonal) const;
121 
122  Router *_router;
123  VertID id;
124  Point point;
125  VertInf *lstPrev;
126  VertInf *lstNext;
127  VertInf *shPrev;
128  VertInf *shNext;
129  EdgeInfList visList;
130  unsigned int visListSize;
131  EdgeInfList orthogVisList;
132  unsigned int orthogVisListSize;
133  EdgeInfList invisList;
134  unsigned int invisListSize;
135  VertInf *pathNext;
136  ConnDirFlags visDirections;
137  // Flags for orthogonal visibility properties, i.e., whether the
138  // line points to a shape edge, connection point or an obstacle.
139  unsigned int orthogVisPropFlags;
140 };
141 
142 
143 // Orthogonal visibility property flags
144 static const unsigned int XL_EDGE = 1;
145 static const unsigned int XL_CONN = 2;
146 static const unsigned int XH_EDGE = 4;
147 static const unsigned int XH_CONN = 8;
148 static const unsigned int YL_EDGE = 16;
149 static const unsigned int YL_CONN = 32;
150 static const unsigned int YH_EDGE = 64;
151 static const unsigned int YH_CONN = 128;
152 
153 
154 bool directVis(VertInf *src, VertInf *dst);
155 
156 
157 // A linked list of all the vertices in the router instance. All the
158 // connector endpoints are listed first, then all the shape vertices.
159 // Dummy vertices inserted for orthogonal routing are classed as shape
160 // vertices but have VertID(0, 0).
161 //
162 class VertInfList
163 {
164  public:
165  VertInfList();
166  void addVertex(VertInf *vert);
167  VertInf *removeVertex(VertInf *vert);
168  VertInf *getVertexByID(const VertID& id);
169  VertInf *getVertexByPos(const Point& p);
170  VertInf *shapesBegin(void);
171  VertInf *connsBegin(void);
172  VertInf *end(void);
173  unsigned int connsSize(void) const;
174  unsigned int shapesSize(void) const;
175  void stats(FILE *fp = stderr)
176  {
177  fprintf(fp, "Conns %d, shapes %d\n", _connVertices,
178  _shapeVertices);
179  }
180  private:
181  VertInf *_firstShapeVert;
182  VertInf *_firstConnVert;
183  VertInf *_lastShapeVert;
184  VertInf *_lastConnVert;
185  unsigned int _shapeVertices;
186  unsigned int _connVertices;
187 };
188 
189 
190 typedef std::set<unsigned int> ShapeSet;
191 typedef std::map<VertID, ShapeSet> ContainsMap;
192 
193 
194 }
195 
196 
197 #endif
198 
199