1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 * Copyright (C) 2004-2006 Michael Wybrow <mjwybrow@users.sourceforge.net>
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 *
21 */
23 #include "libavoid/vertices.h"
24 #include "libavoid/geometry.h"
25 #include "libavoid/graph.h" // For alertConns
26 #include "libavoid/debug.h"
27 #include "libavoid/router.h"
29 #include <iostream>
30 #include <cstdlib>
31 #include <cassert>
33 using std::ostream;
36 namespace Avoid {
39 VertID::VertID()
40 {
41 }
44 VertID::VertID(unsigned int id, bool s, int n)
45 : objID(id)
46 , isShape(s)
47 , vn(n)
48 {
49 }
52 VertID::VertID(const VertID& other)
53 : objID(other.objID)
54 , isShape(other.isShape)
55 , vn(other.vn)
56 {
57 }
60 VertID& VertID::operator= (const VertID& rhs)
61 {
62 // Gracefully handle self assignment
63 //if (this == &rhs) return *this;
65 objID = rhs.objID;
66 isShape = rhs.isShape;
67 vn = rhs.vn;
69 return *this;
70 }
73 bool VertID::operator==(const VertID& rhs) const
74 {
75 if ((objID != rhs.objID) || (vn != rhs.vn))
76 {
77 return false;
78 }
79 assert(isShape == rhs.isShape);
80 return true;
81 }
84 bool VertID::operator!=(const VertID& rhs) const
85 {
86 if ((objID != rhs.objID) || (vn != rhs.vn))
87 {
88 return true;
89 }
90 assert(isShape == rhs.isShape);
91 return false;
92 }
95 bool VertID::operator<(const VertID& rhs) const
96 {
97 if ((objID < rhs.objID) ||
98 ((objID == rhs.objID) && (vn < rhs.vn)))
99 {
100 return true;
101 }
102 return false;
103 }
106 VertID VertID::operator+(const int& rhs) const
107 {
108 return VertID(objID, isShape, vn + rhs);
109 }
112 VertID VertID::operator-(const int& rhs) const
113 {
114 return VertID(objID, isShape, vn - rhs);
115 }
118 VertID& VertID::operator++(int)
119 {
120 vn += 1;
121 return *this;
122 }
125 void VertID::print(FILE *file) const
126 {
127 fprintf(file, "[%u,%d]", objID, vn);
128 }
130 void VertID::db_print(void) const
131 {
132 db_printf("[%u,%d]", objID, vn);
133 }
136 const int VertID::src = 1;
137 const int VertID::tar = 2;
140 ostream& operator<<(ostream& os, const VertID& vID)
141 {
142 return os << '[' << vID.objID << ',' << vID.vn << ']';
143 }
147 VertInf::VertInf(Router *router, const VertID& vid, const Point& vpoint)
148 : _router(router)
149 , id(vid)
150 , point(vpoint)
151 , lstPrev(NULL)
152 , lstNext(NULL)
153 , shPrev(NULL)
154 , shNext(NULL)
155 , visListSize(0)
156 , invisListSize(0)
157 , pathNext(NULL)
158 , pathDist(0)
159 {
160 }
163 void VertInf::Reset(const Point& vpoint)
164 {
165 point = vpoint;
166 }
169 void VertInf::removeFromGraph(const bool isConnVert)
170 {
171 if (isConnVert)
172 {
173 assert(!(id.isShape));
174 }
176 VertInf *tmp = this;
178 // For each vertex.
179 EdgeInfList& visList = tmp->visList;
180 EdgeInfList::iterator finish = visList.end();
181 EdgeInfList::iterator edge;
182 while ((edge = visList.begin()) != finish)
183 {
184 // Remove each visibility edge
185 (*edge)->alertConns();
186 delete (*edge);
187 }
189 EdgeInfList& invisList = tmp->invisList;
190 finish = invisList.end();
191 while ((edge = invisList.begin()) != finish)
192 {
193 // Remove each invisibility edge
194 delete (*edge);
195 }
196 }
199 bool directVis(VertInf *src, VertInf *dst)
200 {
201 ShapeSet ss = ShapeSet();
203 Point& p = src->point;
204 Point& q = dst->point;
206 VertID& pID = src->id;
207 VertID& qID = dst->id;
209 // We better be part of the same instance of libavoid.
210 Router *router = src->_router;
211 assert(router == dst->_router);
213 ContainsMap& contains = router->contains;
214 if (!(pID.isShape))
215 {
216 ss.insert(contains[pID].begin(), contains[pID].end());
217 }
218 if (!(qID.isShape))
219 {
220 ss.insert(contains[qID].begin(), contains[qID].end());
221 }
223 // The "beginning" should be the first shape vertex, rather
224 // than an endpoint, which are also stored in "vertices".
225 VertInf *endVert = router->vertices.end();
226 for (VertInf *k = router->vertices.shapesBegin(); k != endVert;
227 k = k->lstNext)
228 {
229 if ((ss.find(k->id.objID) == ss.end()))
230 {
231 if (segmentIntersect(p, q, k->point, k->shNext->point))
232 {
233 return false;
234 }
235 }
236 }
237 return true;
238 }
241 VertInfList::VertInfList()
242 : _firstShapeVert(NULL)
243 , _firstConnVert(NULL)
244 , _lastShapeVert(NULL)
245 , _lastConnVert(NULL)
246 , _shapeVertices(0)
247 , _connVertices(0)
248 {
249 }
252 #define checkVertInfListConditions() \
253 do { \
254 assert((!_firstConnVert && (_connVertices == 0)) || \
255 ((_firstConnVert->lstPrev == NULL) && (_connVertices > 0))); \
256 assert((!_firstShapeVert && (_shapeVertices == 0)) || \
257 ((_firstShapeVert->lstPrev == NULL) && (_shapeVertices > 0))); \
258 assert(!_lastShapeVert || (_lastShapeVert->lstNext == NULL)); \
259 assert(!_lastConnVert || (_lastConnVert->lstNext == _firstShapeVert)); \
260 assert((!_firstConnVert && !_lastConnVert) || \
261 (_firstConnVert && _lastConnVert) ); \
262 assert((!_firstShapeVert && !_lastShapeVert) || \
263 (_firstShapeVert && _lastShapeVert) ); \
264 assert(!_firstShapeVert || _firstShapeVert->id.isShape); \
265 assert(!_lastShapeVert || _lastShapeVert->id.isShape); \
266 assert(!_firstConnVert || !(_firstConnVert->id.isShape)); \
267 assert(!_lastConnVert || !(_lastConnVert->id.isShape)); \
268 } while(0)
271 void VertInfList::addVertex(VertInf *vert)
272 {
273 checkVertInfListConditions();
274 assert(vert->lstPrev == NULL);
275 assert(vert->lstNext == NULL);
277 if (!(vert->id.isShape))
278 {
279 // A Connector vertex
280 if (_firstConnVert)
281 {
282 // Join with previous front
283 vert->lstNext = _firstConnVert;
284 _firstConnVert->lstPrev = vert;
286 // Make front
287 _firstConnVert = vert;
288 }
289 else
290 {
291 // Make front and back
292 _firstConnVert = vert;
293 _lastConnVert = vert;
295 // Link to front of shapes list
296 vert->lstNext = _firstShapeVert;
297 }
298 _connVertices++;
299 }
300 else // if (vert->id.shape > 0)
301 {
302 // A Shape vertex
303 if (_lastShapeVert)
304 {
305 // Join with previous back
306 vert->lstPrev = _lastShapeVert;
307 _lastShapeVert->lstNext = vert;
309 // Make back
310 _lastShapeVert = vert;
311 }
312 else
313 {
314 // Make first and last
315 _firstShapeVert = vert;
316 _lastShapeVert = vert;
318 // Join with conns list
319 if (_lastConnVert)
320 {
321 assert (_lastConnVert->lstNext == NULL);
323 _lastConnVert->lstNext = vert;
324 }
325 }
326 _shapeVertices++;
327 }
328 checkVertInfListConditions();
329 }
332 void VertInfList::removeVertex(VertInf *vert)
333 {
334 // Conditions for correct data structure
335 checkVertInfListConditions();
337 if (!(vert->id.isShape))
338 {
339 // A Connector vertex
340 if (vert == _firstConnVert)
341 {
343 if (vert == _lastConnVert)
344 {
345 _firstConnVert = NULL;
346 _lastConnVert = NULL;
347 }
348 else
349 {
350 // Set new first
351 _firstConnVert = _firstConnVert->lstNext;
353 if (_firstConnVert)
354 {
355 // Set previous
356 _firstConnVert->lstPrev = NULL;
357 }
358 }
359 }
360 else if (vert == _lastConnVert)
361 {
362 // Set new last
363 _lastConnVert = _lastConnVert->lstPrev;
365 // Make last point to shapes list
366 _lastConnVert->lstNext = _firstShapeVert;
367 }
368 else
369 {
370 vert->lstNext->lstPrev = vert->lstPrev;
371 vert->lstPrev->lstNext = vert->lstNext;
372 }
373 _connVertices--;
374 }
375 else // if (vert->id.shape > 0)
376 {
377 // A Shape vertex
378 if (vert == _lastShapeVert)
379 {
380 // Set new last
381 _lastShapeVert = _lastShapeVert->lstPrev;
383 if (vert == _firstShapeVert)
384 {
385 _firstShapeVert = NULL;
386 if (_lastConnVert)
387 {
388 _lastConnVert->lstNext = NULL;
389 }
390 }
392 if (_lastShapeVert)
393 {
394 _lastShapeVert->lstNext = NULL;
395 }
396 }
397 else if (vert == _firstShapeVert)
398 {
399 // Set new first
400 _firstShapeVert = _firstShapeVert->lstNext;
402 // Correct the last conn vertex
403 if (_lastConnVert)
404 {
405 _lastConnVert->lstNext = _firstShapeVert;
406 }
408 if (_firstShapeVert)
409 {
410 _firstShapeVert->lstPrev = NULL;
411 }
412 }
413 else
414 {
415 vert->lstNext->lstPrev = vert->lstPrev;
416 vert->lstPrev->lstNext = vert->lstNext;
417 }
418 _shapeVertices--;
419 }
420 vert->lstPrev = NULL;
421 vert->lstNext = NULL;
423 checkVertInfListConditions();
424 }
427 VertInf *VertInfList::shapesBegin(void)
428 {
429 return _firstShapeVert;
430 }
433 VertInf *VertInfList::connsBegin(void)
434 {
435 if (_firstConnVert)
436 {
437 return _firstConnVert;
438 }
439 // No connector vertices
440 return _firstShapeVert;
441 }
444 VertInf *VertInfList::end(void)
445 {
446 return NULL;
447 }
450 }