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>
34 namespace Avoid {
37 VertID::VertID()
38 {
39 }
42 VertID::VertID(unsigned int id, bool s, int n)
43 : objID(id)
44 , isShape(s)
45 , vn(n)
46 {
47 }
50 VertID::VertID(const VertID& other)
51 : objID(other.objID)
52 , isShape(other.isShape)
53 , vn(other.vn)
54 {
55 }
58 VertID& VertID::operator= (const VertID& rhs)
59 {
60 // Gracefully handle self assignment
61 //if (this == &rhs) return *this;
63 objID = rhs.objID;
64 isShape = rhs.isShape;
65 vn = rhs.vn;
67 return *this;
68 }
71 bool VertID::operator==(const VertID& rhs) const
72 {
73 if ((objID != rhs.objID) || (vn != rhs.vn))
74 {
75 return false;
76 }
77 assert(isShape == rhs.isShape);
78 return true;
79 }
82 bool VertID::operator!=(const VertID& rhs) const
83 {
84 if ((objID != rhs.objID) || (vn != rhs.vn))
85 {
86 return true;
87 }
88 assert(isShape == rhs.isShape);
89 return false;
90 }
93 bool VertID::operator<(const VertID& rhs) const
94 {
95 if ((objID < rhs.objID) ||
96 ((objID == rhs.objID) && (vn < rhs.vn)))
97 {
98 return true;
99 }
100 return false;
101 }
104 VertID VertID::operator+(const int& rhs) const
105 {
106 return VertID(objID, isShape, vn + rhs);
107 }
110 VertID VertID::operator-(const int& rhs) const
111 {
112 return VertID(objID, isShape, vn - rhs);
113 }
116 VertID& VertID::operator++(int)
117 {
118 vn += 1;
119 return *this;
120 }
123 void VertID::print(FILE *file) const
124 {
125 fprintf(file, "[%u,%d]", objID, vn);
126 }
129 void VertID::db_print(void) const
130 {
131 db_printf("[%u,%d]", objID, vn);
132 }
135 const int VertID::src = 1;
136 const int VertID::tar = 2;
139 VertInf::VertInf(Router *router, const VertID& vid, const Point& vpoint)
140 : _router(router)
141 , id(vid)
142 , point(vpoint)
143 , lstPrev(NULL)
144 , lstNext(NULL)
145 , shPrev(NULL)
146 , shNext(NULL)
147 , visListSize(0)
148 , invisListSize(0)
149 , pathNext(NULL)
150 , pathDist(0)
151 {
152 }
155 void VertInf::Reset(const Point& vpoint)
156 {
157 point = vpoint;
158 }
161 void VertInf::removeFromGraph(const bool isConnVert)
162 {
163 if (isConnVert)
164 {
165 assert(!(id.isShape));
166 }
168 VertInf *tmp = this;
170 // For each vertex.
171 EdgeInfList& visList = tmp->visList;
172 EdgeInfList::iterator finish = visList.end();
173 EdgeInfList::iterator edge;
174 while ((edge = visList.begin()) != finish)
175 {
176 // Remove each visibility edge
177 (*edge)->alertConns();
178 delete (*edge);
179 }
181 EdgeInfList& invisList = tmp->invisList;
182 finish = invisList.end();
183 while ((edge = invisList.begin()) != finish)
184 {
185 // Remove each invisibility edge
186 delete (*edge);
187 }
188 }
191 bool directVis(VertInf *src, VertInf *dst)
192 {
193 ShapeSet ss = ShapeSet();
195 Point& p = src->point;
196 Point& q = dst->point;
198 VertID& pID = src->id;
199 VertID& qID = dst->id;
201 // We better be part of the same instance of libavoid.
202 Router *router = src->_router;
203 assert(router == dst->_router);
205 ContainsMap& contains = router->contains;
206 if (!(pID.isShape))
207 {
208 ss.insert(contains[pID].begin(), contains[pID].end());
209 }
210 if (!(qID.isShape))
211 {
212 ss.insert(contains[qID].begin(), contains[qID].end());
213 }
215 // The "beginning" should be the first shape vertex, rather
216 // than an endpoint, which are also stored in "vertices".
217 VertInf *endVert = router->vertices.end();
218 for (VertInf *k = router->vertices.shapesBegin(); k != endVert;
219 k = k->lstNext)
220 {
221 if ((ss.find(k->id.objID) == ss.end()))
222 {
223 if (segmentIntersect(p, q, k->point, k->shNext->point))
224 {
225 return false;
226 }
227 }
228 }
229 return true;
230 }
233 VertInfList::VertInfList()
234 : _firstShapeVert(NULL)
235 , _firstConnVert(NULL)
236 , _lastShapeVert(NULL)
237 , _lastConnVert(NULL)
238 , _shapeVertices(0)
239 , _connVertices(0)
240 {
241 }
244 #define checkVertInfListConditions() \
245 do { \
246 assert((!_firstConnVert && (_connVertices == 0)) || \
247 ((_firstConnVert->lstPrev == NULL) && (_connVertices > 0))); \
248 assert((!_firstShapeVert && (_shapeVertices == 0)) || \
249 ((_firstShapeVert->lstPrev == NULL) && (_shapeVertices > 0))); \
250 assert(!_lastShapeVert || (_lastShapeVert->lstNext == NULL)); \
251 assert(!_lastConnVert || (_lastConnVert->lstNext == _firstShapeVert)); \
252 assert((!_firstConnVert && !_lastConnVert) || \
253 (_firstConnVert && _lastConnVert) ); \
254 assert((!_firstShapeVert && !_lastShapeVert) || \
255 (_firstShapeVert && _lastShapeVert) ); \
256 assert(!_firstShapeVert || _firstShapeVert->id.isShape); \
257 assert(!_lastShapeVert || _lastShapeVert->id.isShape); \
258 assert(!_firstConnVert || !(_firstConnVert->id.isShape)); \
259 assert(!_lastConnVert || !(_lastConnVert->id.isShape)); \
260 } while(0)
263 void VertInfList::addVertex(VertInf *vert)
264 {
265 checkVertInfListConditions();
266 assert(vert->lstPrev == NULL);
267 assert(vert->lstNext == NULL);
269 if (!(vert->id.isShape))
270 {
271 // A Connector vertex
272 if (_firstConnVert)
273 {
274 // Join with previous front
275 vert->lstNext = _firstConnVert;
276 _firstConnVert->lstPrev = vert;
278 // Make front
279 _firstConnVert = vert;
280 }
281 else
282 {
283 // Make front and back
284 _firstConnVert = vert;
285 _lastConnVert = vert;
287 // Link to front of shapes list
288 vert->lstNext = _firstShapeVert;
289 }
290 _connVertices++;
291 }
292 else // if (vert->id.shape > 0)
293 {
294 // A Shape vertex
295 if (_lastShapeVert)
296 {
297 // Join with previous back
298 vert->lstPrev = _lastShapeVert;
299 _lastShapeVert->lstNext = vert;
301 // Make back
302 _lastShapeVert = vert;
303 }
304 else
305 {
306 // Make first and last
307 _firstShapeVert = vert;
308 _lastShapeVert = vert;
310 // Join with conns list
311 if (_lastConnVert)
312 {
313 assert (_lastConnVert->lstNext == NULL);
315 _lastConnVert->lstNext = vert;
316 }
317 }
318 _shapeVertices++;
319 }
320 checkVertInfListConditions();
321 }
324 void VertInfList::removeVertex(VertInf *vert)
325 {
326 // Conditions for correct data structure
327 checkVertInfListConditions();
329 if (!(vert->id.isShape))
330 {
331 // A Connector vertex
332 if (vert == _firstConnVert)
333 {
335 if (vert == _lastConnVert)
336 {
337 _firstConnVert = NULL;
338 _lastConnVert = NULL;
339 }
340 else
341 {
342 // Set new first
343 _firstConnVert = _firstConnVert->lstNext;
345 if (_firstConnVert)
346 {
347 // Set previous
348 _firstConnVert->lstPrev = NULL;
349 }
350 }
351 }
352 else if (vert == _lastConnVert)
353 {
354 // Set new last
355 _lastConnVert = _lastConnVert->lstPrev;
357 // Make last point to shapes list
358 _lastConnVert->lstNext = _firstShapeVert;
359 }
360 else
361 {
362 vert->lstNext->lstPrev = vert->lstPrev;
363 vert->lstPrev->lstNext = vert->lstNext;
364 }
365 _connVertices--;
366 }
367 else // if (vert->id.shape > 0)
368 {
369 // A Shape vertex
370 if (vert == _lastShapeVert)
371 {
372 // Set new last
373 _lastShapeVert = _lastShapeVert->lstPrev;
375 if (vert == _firstShapeVert)
376 {
377 _firstShapeVert = NULL;
378 if (_lastConnVert)
379 {
380 _lastConnVert->lstNext = NULL;
381 }
382 }
384 if (_lastShapeVert)
385 {
386 _lastShapeVert->lstNext = NULL;
387 }
388 }
389 else if (vert == _firstShapeVert)
390 {
391 // Set new first
392 _firstShapeVert = _firstShapeVert->lstNext;
394 // Correct the last conn vertex
395 if (_lastConnVert)
396 {
397 _lastConnVert->lstNext = _firstShapeVert;
398 }
400 if (_firstShapeVert)
401 {
402 _firstShapeVert->lstPrev = NULL;
403 }
404 }
405 else
406 {
407 vert->lstNext->lstPrev = vert->lstPrev;
408 vert->lstPrev->lstNext = vert->lstNext;
409 }
410 _shapeVertices--;
411 }
412 vert->lstPrev = NULL;
413 vert->lstNext = NULL;
415 checkVertInfListConditions();
416 }
419 VertInf *VertInfList::shapesBegin(void)
420 {
421 return _firstShapeVert;
422 }
425 VertInf *VertInfList::connsBegin(void)
426 {
427 if (_firstConnVert)
428 {
429 return _firstConnVert;
430 }
431 // No connector vertices
432 return _firstShapeVert;
433 }
436 VertInf *VertInfList::end(void)
437 {
438 return NULL;
439 }
442 }