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 */
26 #include <iostream>
27 #include <cstdlib>
29 #include "libavoid/vertices.h"
30 #include "libavoid/geometry.h"
31 #include "libavoid/graph.h" // For alertConns
32 #include "libavoid/debug.h"
33 #include "libavoid/router.h"
34 #include "libavoid/assertions.h"
36 using std::ostream;
39 namespace Avoid {
42 VertID::VertID()
43 {
44 }
47 VertID::VertID(unsigned int id, bool s, int n)
48 : objID(id)
49 , isShape(s)
50 , vn(n)
51 {
52 }
55 VertID::VertID(const VertID& other)
56 : objID(other.objID)
57 , isShape(other.isShape)
58 , vn(other.vn)
59 {
60 }
63 VertID& VertID::operator= (const VertID& rhs)
64 {
65 // Gracefully handle self assignment
66 //if (this == &rhs) return *this;
68 objID = rhs.objID;
69 isShape = rhs.isShape;
70 vn = rhs.vn;
72 return *this;
73 }
76 bool VertID::operator==(const VertID& rhs) const
77 {
78 if ((objID != rhs.objID) || (vn != rhs.vn))
79 {
80 return false;
81 }
82 // XXX RubberBand search breaks this:
83 // COLA_ASSERT(isShape == rhs.isShape);
84 return true;
85 }
88 bool VertID::operator!=(const VertID& rhs) const
89 {
90 if ((objID != rhs.objID) || (vn != rhs.vn))
91 {
92 return true;
93 }
94 COLA_ASSERT(isShape == rhs.isShape);
95 return false;
96 }
99 bool VertID::operator<(const VertID& rhs) const
100 {
101 if ((objID < rhs.objID) ||
102 ((objID == rhs.objID) && (vn < rhs.vn)))
103 {
104 return true;
105 }
106 return false;
107 }
110 VertID VertID::operator+(const int& rhs) const
111 {
112 return VertID(objID, isShape, vn + rhs);
113 }
116 VertID VertID::operator-(const int& rhs) const
117 {
118 return VertID(objID, isShape, vn - rhs);
119 }
122 VertID& VertID::operator++(int)
123 {
124 vn += 1;
125 return *this;
126 }
129 void VertID::print(FILE *file) const
130 {
131 fprintf(file, "[%u,%d]", objID, vn);
132 }
134 void VertID::db_print(void) const
135 {
136 db_printf("[%u,%d]", objID, vn);
137 }
140 const unsigned short VertID::src = 1;
141 const unsigned short VertID::tar = 2;
144 ostream& operator<<(ostream& os, const VertID& vID)
145 {
146 return os << '[' << vID.objID << ',' << vID.vn << ']';
147 }
151 VertInf::VertInf(Router *router, const VertID& vid, const Point& vpoint,
152 const bool addToRouter)
153 : _router(router),
154 id(vid),
155 point(vpoint),
156 lstPrev(NULL),
157 lstNext(NULL),
158 shPrev(NULL),
159 shNext(NULL),
160 visListSize(0),
161 orthogVisListSize(0),
162 invisListSize(0),
163 pathNext(NULL),
164 visDirections(ConnDirNone)
165 {
166 point.id = vid.objID;
167 point.vn = vid.vn;
169 if (addToRouter)
170 {
171 _router->vertices.addVertex(this);
172 }
173 }
176 VertInf::~VertInf()
177 {
178 }
181 void VertInf::Reset(const VertID& vid, const Point& vpoint)
182 {
183 id = vid;
184 point = vpoint;
185 point.id = id.objID;
186 point.vn = id.vn;
187 }
190 void VertInf::Reset(const Point& vpoint)
191 {
192 point = vpoint;
193 point.id = id.objID;
194 point.vn = id.vn;
195 }
198 // Returns true if this vertex is not involved in any (in)visibility graphs.
199 bool VertInf::orphaned(void)
200 {
201 return (visList.empty() && invisList.empty() && orthogVisList.empty());
202 }
205 void VertInf::removeFromGraph(const bool isConnVert)
206 {
207 if (isConnVert)
208 {
209 COLA_ASSERT(!(id.isShape));
210 }
212 // For each vertex.
213 EdgeInfList::const_iterator finish = visList.end();
214 EdgeInfList::const_iterator edge;
215 while ((edge = visList.begin()) != finish)
216 {
217 // Remove each visibility edge
218 (*edge)->alertConns();
219 delete (*edge);
220 }
222 finish = orthogVisList.end();
223 while ((edge = orthogVisList.begin()) != finish)
224 {
225 // Remove each orthogonal visibility edge.
226 (*edge)->alertConns();
227 delete (*edge);
228 }
230 finish = invisList.end();
231 while ((edge = invisList.begin()) != finish)
232 {
233 // Remove each invisibility edge
234 delete (*edge);
235 }
236 }
239 bool directVis(VertInf *src, VertInf *dst)
240 {
241 ShapeSet ss = ShapeSet();
243 Point& p = src->point;
244 Point& q = dst->point;
246 VertID& pID = src->id;
247 VertID& qID = dst->id;
249 // We better be part of the same instance of libavoid.
250 Router *router = src->_router;
251 COLA_ASSERT(router == dst->_router);
253 ContainsMap& contains = router->contains;
254 if (!(pID.isShape))
255 {
256 ss.insert(contains[pID].begin(), contains[pID].end());
257 }
258 if (!(qID.isShape))
259 {
260 ss.insert(contains[qID].begin(), contains[qID].end());
261 }
263 // The "beginning" should be the first shape vertex, rather
264 // than an endpoint, which are also stored in "vertices".
265 VertInf *endVert = router->vertices.end();
266 for (VertInf *k = router->vertices.shapesBegin(); k != endVert;
267 k = k->lstNext)
268 {
269 if ((ss.find(k->id.objID) == ss.end()))
270 {
271 if (segmentIntersect(p, q, k->point, k->shNext->point))
272 {
273 return false;
274 }
275 }
276 }
277 return true;
278 }
281 VertInfList::VertInfList()
282 : _firstShapeVert(NULL),
283 _firstConnVert(NULL),
284 _lastShapeVert(NULL),
285 _lastConnVert(NULL),
286 _shapeVertices(0),
287 _connVertices(0)
288 {
289 }
292 #define checkVertInfListConditions() \
293 do { \
294 COLA_ASSERT((!_firstConnVert && (_connVertices == 0)) || \
295 ((_firstConnVert->lstPrev == NULL) && (_connVertices > 0))); \
296 COLA_ASSERT((!_firstShapeVert && (_shapeVertices == 0)) || \
297 ((_firstShapeVert->lstPrev == NULL) && (_shapeVertices > 0))); \
298 COLA_ASSERT(!_lastShapeVert || (_lastShapeVert->lstNext == NULL)); \
299 COLA_ASSERT(!_lastConnVert || (_lastConnVert->lstNext == _firstShapeVert)); \
300 COLA_ASSERT((!_firstConnVert && !_lastConnVert) || \
301 (_firstConnVert && _lastConnVert) ); \
302 COLA_ASSERT((!_firstShapeVert && !_lastShapeVert) || \
303 (_firstShapeVert && _lastShapeVert) ); \
304 COLA_ASSERT(!_firstShapeVert || _firstShapeVert->id.isShape); \
305 COLA_ASSERT(!_lastShapeVert || _lastShapeVert->id.isShape); \
306 COLA_ASSERT(!_firstConnVert || !(_firstConnVert->id.isShape)); \
307 COLA_ASSERT(!_lastConnVert || !(_lastConnVert->id.isShape)); \
308 } while(0)
311 void VertInfList::addVertex(VertInf *vert)
312 {
313 checkVertInfListConditions();
314 COLA_ASSERT(vert->lstPrev == NULL);
315 COLA_ASSERT(vert->lstNext == NULL);
317 if (!(vert->id.isShape))
318 {
319 // A Connector vertex
320 if (_firstConnVert)
321 {
322 // Join with previous front
323 vert->lstNext = _firstConnVert;
324 _firstConnVert->lstPrev = vert;
326 // Make front
327 _firstConnVert = vert;
328 }
329 else
330 {
331 // Make front and back
332 _firstConnVert = vert;
333 _lastConnVert = vert;
335 // Link to front of shapes list
336 vert->lstNext = _firstShapeVert;
337 }
338 _connVertices++;
339 }
340 else // if (vert->id.shape > 0)
341 {
342 // A Shape vertex
343 if (_lastShapeVert)
344 {
345 // Join with previous back
346 vert->lstPrev = _lastShapeVert;
347 _lastShapeVert->lstNext = vert;
349 // Make back
350 _lastShapeVert = vert;
351 }
352 else
353 {
354 // Make first and last
355 _firstShapeVert = vert;
356 _lastShapeVert = vert;
358 // Join with conns list
359 if (_lastConnVert)
360 {
361 assert (_lastConnVert->lstNext == NULL);
363 _lastConnVert->lstNext = vert;
364 }
365 }
366 _shapeVertices++;
367 }
368 checkVertInfListConditions();
369 }
372 // Removes a vertex from the list and returns a pointer to the vertex
373 // following the removed one.
374 VertInf *VertInfList::removeVertex(VertInf *vert)
375 {
376 if (vert == NULL)
377 {
378 return NULL;
379 }
380 // Conditions for correct data structure
381 checkVertInfListConditions();
383 VertInf *following = vert->lstNext;
385 if (!(vert->id.isShape))
386 {
387 // A Connector vertex
388 if (vert == _firstConnVert)
389 {
391 if (vert == _lastConnVert)
392 {
393 _firstConnVert = NULL;
394 _lastConnVert = NULL;
395 }
396 else
397 {
398 // Set new first
399 _firstConnVert = _firstConnVert->lstNext;
401 if (_firstConnVert)
402 {
403 // Set previous
404 _firstConnVert->lstPrev = NULL;
405 }
406 }
407 }
408 else if (vert == _lastConnVert)
409 {
410 // Set new last
411 _lastConnVert = _lastConnVert->lstPrev;
413 // Make last point to shapes list
414 _lastConnVert->lstNext = _firstShapeVert;
415 }
416 else
417 {
418 vert->lstNext->lstPrev = vert->lstPrev;
419 vert->lstPrev->lstNext = vert->lstNext;
420 }
421 _connVertices--;
422 }
423 else // if (vert->id.shape > 0)
424 {
425 // A Shape vertex
426 if (vert == _lastShapeVert)
427 {
428 // Set new last
429 _lastShapeVert = _lastShapeVert->lstPrev;
431 if (vert == _firstShapeVert)
432 {
433 _firstShapeVert = NULL;
434 if (_lastConnVert)
435 {
436 _lastConnVert->lstNext = NULL;
437 }
438 }
440 if (_lastShapeVert)
441 {
442 _lastShapeVert->lstNext = NULL;
443 }
444 }
445 else if (vert == _firstShapeVert)
446 {
447 // Set new first
448 _firstShapeVert = _firstShapeVert->lstNext;
450 // Correct the last conn vertex
451 if (_lastConnVert)
452 {
453 _lastConnVert->lstNext = _firstShapeVert;
454 }
456 if (_firstShapeVert)
457 {
458 _firstShapeVert->lstPrev = NULL;
459 }
460 }
461 else
462 {
463 vert->lstNext->lstPrev = vert->lstPrev;
464 vert->lstPrev->lstNext = vert->lstNext;
465 }
466 _shapeVertices--;
467 }
468 vert->lstPrev = NULL;
469 vert->lstNext = NULL;
471 checkVertInfListConditions();
473 return following;
474 }
477 VertInf *VertInfList::getVertexByID(const VertID& id)
478 {
479 VertID searchID = id;
480 if (searchID.vn == kUnassignedVertexNumber)
481 {
482 unsigned int topbit = ((unsigned int) 1) << 31;
483 if (searchID.objID & topbit)
484 {
485 searchID.objID = searchID.objID & ~topbit;
486 searchID.vn = VertID::src;
487 }
488 else
489 {
490 searchID.vn = VertID::tar;
491 }
492 }
493 VertInf *last = end();
494 for (VertInf *curr = connsBegin(); curr != last; curr = curr->lstNext)
495 {
496 if (curr->id == searchID)
497 {
498 return curr;
499 }
500 }
501 return NULL;
502 }
505 VertInf *VertInfList::getVertexByPos(const Point& p)
506 {
507 VertInf *last = end();
508 for (VertInf *curr = shapesBegin(); curr != last; curr = curr->lstNext)
509 {
510 if (curr->point == p)
511 {
512 return curr;
513 }
514 }
515 return NULL;
516 }
519 VertInf *VertInfList::shapesBegin(void)
520 {
521 return _firstShapeVert;
522 }
525 VertInf *VertInfList::connsBegin(void)
526 {
527 if (_firstConnVert)
528 {
529 return _firstConnVert;
530 }
531 // No connector vertices
532 return _firstShapeVert;
533 }
536 VertInf *VertInfList::end(void)
537 {
538 return NULL;
539 }
542 unsigned int VertInfList::connsSize(void) const
543 {
544 return _connVertices;
545 }
548 unsigned int VertInfList::shapesSize(void) const
549 {
550 return _shapeVertices;
551 }
554 }