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-2005 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/connector.h"
24 #include "libavoid/graph.h"
25 #include "libavoid/makepath.h"
26 #include "libavoid/visibility.h"
27 #include "libavoid/debug.h"
30 namespace Avoid {
33 ConnRefList connRefs;
36 ConnRef::ConnRef(const unsigned int id)
37 : _id(id)
38 , _srcId(0)
39 , _dstId(0)
40 , _needs_reroute_flag(true)
41 , _false_path(false)
42 , _active(false)
43 , _route_dist(0)
44 , _srcVert(NULL)
45 , _dstVert(NULL)
46 , _initialised(false)
47 , _callback(NULL)
48 , _connector(NULL)
49 {
50 // TODO: Store endpoints and details.
51 _route.pn = 0;
52 _route.ps = NULL;
53 }
56 ConnRef::ConnRef(const unsigned int id, const Point& src, const Point& dst)
57 : _id(id)
58 , _srcId(0)
59 , _dstId(0)
60 , _needs_reroute_flag(true)
61 , _false_path(false)
62 , _active(false)
63 , _route_dist(0)
64 , _srcVert(NULL)
65 , _dstVert(NULL)
66 , _initialised(false)
67 , _callback(NULL)
68 , _connector(NULL)
69 {
70 _route.pn = 0;
71 _route.ps = NULL;
73 if (IncludeEndpoints)
74 {
75 bool isShape = false;
76 _srcVert = new VertInf(VertID(id, isShape, 1), src);
77 _dstVert = new VertInf(VertID(id, isShape, 2), dst);
78 vertices.addVertex(_srcVert);
79 vertices.addVertex(_dstVert);
80 makeActive();
81 _initialised = true;
82 }
83 }
86 ConnRef::~ConnRef()
87 {
88 freeRoute();
90 if (_srcVert)
91 {
92 vertices.removeVertex(_srcVert);
93 delete _srcVert;
94 _srcVert = NULL;
95 }
97 if (_dstVert)
98 {
99 vertices.removeVertex(_dstVert);
100 delete _dstVert;
101 _dstVert = NULL;
102 }
104 if (_active)
105 {
106 makeInactive();
107 }
108 }
110 void ConnRef::updateEndPoint(const unsigned int type, const Point& point)
111 {
112 assert((type == (unsigned int) VertID::src) ||
113 (type == (unsigned int) VertID::tar));
114 //assert(IncludeEndpoints);
116 if (!_initialised)
117 {
118 makeActive();
119 _initialised = true;
120 }
122 VertInf *altered = NULL;
123 VertInf *partner = NULL;
124 bool isShape = false;
126 if (type == (unsigned int) VertID::src)
127 {
128 if (_srcVert)
129 {
130 _srcVert->Reset(point);
131 }
132 else
133 {
134 _srcVert = new VertInf(VertID(_id, isShape, type), point);
135 vertices.addVertex(_srcVert);
136 }
138 altered = _srcVert;
139 partner = _dstVert;
140 }
141 else // if (type == (unsigned int) VertID::dst)
142 {
143 if (_dstVert)
144 {
145 _dstVert->Reset(point);
146 }
147 else
148 {
149 _dstVert = new VertInf(VertID(_id, isShape, type), point);
150 vertices.addVertex(_dstVert);
151 }
153 altered = _dstVert;
154 partner = _srcVert;
155 }
157 bool knownNew = false;
158 vertexVisibility(altered, partner, knownNew, true);
159 }
162 void ConnRef::setEndPointId(const unsigned int type, const unsigned int id)
163 {
164 if (type == (unsigned int) VertID::src)
165 {
166 _srcId = id;
167 }
168 else // if (type == (unsigned int) VertID::dst)
169 {
170 _dstId = id;
171 }
172 }
175 void ConnRef::makeActive(void)
176 {
177 assert(!_active);
179 // Add to connRefs list.
180 _pos = connRefs.insert(connRefs.begin(), this);
181 _active = true;
182 }
185 void ConnRef::makeInactive(void)
186 {
187 assert(_active);
189 // Remove from connRefs list.
190 connRefs.erase(_pos);
191 _active = false;
192 }
195 void ConnRef::freeRoute(void)
196 {
197 if (_route.ps)
198 {
199 _route.pn = 0;
200 std::free(_route.ps);
201 _route.ps = NULL;
202 }
203 }
206 PolyLine& ConnRef::route(void)
207 {
208 return _route;
209 }
212 void ConnRef::calcRouteDist(void)
213 {
214 _route_dist = 0;
215 for (int i = 1; i < _route.pn; i++)
216 {
217 _route_dist += dist(_route.ps[i], _route.ps[i - 1]);
218 }
219 }
222 bool ConnRef::needsReroute(void)
223 {
224 return (_false_path || _needs_reroute_flag);
225 }
228 void ConnRef::moveRoute(const int& diff_x, const int& diff_y)
229 {
230 for (int i = 0; i < _route.pn; i++)
231 {
232 _route.ps[i].x += diff_x;
233 _route.ps[i].y += diff_y;
234 }
235 }
238 void ConnRef::lateSetup(const Point& src, const Point& dst)
239 {
240 assert(!_initialised);
242 bool isShape = false;
243 _srcVert = new VertInf(VertID(_id, isShape, 1), src);
244 _dstVert = new VertInf(VertID(_id, isShape, 2), dst);
245 vertices.addVertex(_srcVert);
246 vertices.addVertex(_dstVert);
247 makeActive();
248 _initialised = true;
249 }
252 VertInf *ConnRef::src(void)
253 {
254 return _srcVert;
255 }
258 VertInf *ConnRef::dst(void)
259 {
260 return _dstVert;
261 }
264 bool ConnRef::isInitialised(void)
265 {
266 return _initialised;
267 }
270 void ConnRef::unInitialise(void)
271 {
272 vertices.removeVertex(_srcVert);
273 vertices.removeVertex(_dstVert);
274 makeInactive();
275 _initialised = false;
276 }
279 void ConnRef::removeFromGraph(void)
280 {
281 for (VertInf *iter = _srcVert; iter != NULL; )
282 {
283 VertInf *tmp = iter;
284 iter = (iter == _srcVert) ? _dstVert : NULL;
286 // For each vertex.
287 EdgeInfList& visList = tmp->visList;
288 EdgeInfList::iterator finish = visList.end();
289 EdgeInfList::iterator edge;
290 while ((edge = visList.begin()) != finish)
291 {
292 // Remove each visibility edge
293 delete (*edge);
294 }
296 EdgeInfList& invisList = tmp->invisList;
297 finish = invisList.end();
298 while ((edge = invisList.begin()) != finish)
299 {
300 // Remove each invisibility edge
301 delete (*edge);
302 }
303 }
304 }
307 void ConnRef::setCallback(void (*cb)(void *), void *ptr)
308 {
309 _callback = cb;
310 _connector = ptr;
311 }
314 void ConnRef::handleInvalid(void)
315 {
316 if (_false_path || _needs_reroute_flag) {
317 if (_callback) {
318 _callback(_connector);
319 }
320 }
321 }
324 void ConnRef::makePathInvalid(void)
325 {
326 _needs_reroute_flag = true;
327 }
330 int ConnRef::generatePath(Point p0, Point p1)
331 {
332 if (!_false_path && !_needs_reroute_flag) {
333 // This connector is up to date.
334 return (int) false;
335 }
337 _false_path = false;
338 _needs_reroute_flag = false;
340 VertInf *src = _srcVert;
341 VertInf *tar = _dstVert;
343 if (!IncludeEndpoints)
344 {
345 lateSetup(p0, p1);
347 // Update as they have just been set by lateSetup.
348 src = _srcVert;
349 tar = _dstVert;
351 bool knownNew = true;
352 vertexVisibility(src, tar, knownNew);
353 vertexVisibility(tar, src, knownNew);
354 }
356 bool *flag = &(_needs_reroute_flag);
358 makePath(this, flag);
360 bool result = true;
362 int pathlen = 1;
363 for (VertInf *i = tar; i != src; i = i->pathNext)
364 {
365 pathlen++;
366 if (i == NULL)
367 {
368 db_printf("Warning: Path not found...\n");
369 pathlen = 2;
370 tar->pathNext = src;
371 if (InvisibilityGrph)
372 {
373 // TODO: Could we know this edge already?
374 EdgeInf *edge = EdgeInf::existingEdge(src, tar);
375 assert(edge != NULL);
376 edge->addCycleBlocker();
377 }
378 result = false;
379 break;
380 }
381 if (pathlen > 100)
382 {
383 fprintf(stderr, "ERROR: Should never be here...\n");
384 exit(1);
385 }
386 }
387 Point *path = (Point *) malloc(pathlen * sizeof(Point));
389 int j = pathlen - 1;
390 for (VertInf *i = tar; i != src; i = i->pathNext)
391 {
392 if (InvisibilityGrph)
393 {
394 // TODO: Again, we could know this edge without searching.
395 EdgeInf *edge = EdgeInf::existingEdge(i, i->pathNext);
396 edge->addConn(flag);
397 }
398 else
399 {
400 _false_path = true;
401 }
402 path[j--] = i->point;
403 }
404 path[0] = src->point;
407 // Would clear visibility for endpoints here if required.
409 PolyLine& output_route = route();
410 output_route.pn = pathlen;
411 output_route.ps = path;
413 return (int) result;
414 }
417 //============================================================================
419 const unsigned int ConnRef::runningTo = 1;
420 const unsigned int ConnRef::runningFrom = 2;
421 const unsigned int ConnRef::runningToAndFrom =
422 ConnRef::runningTo | ConnRef::runningFrom;
424 // XXX: attachedShapes and attachedConns both need to be rewritten
425 // for constant time lookup of attached objects once this info
426 // is stored better within libavoid.
429 // Returns a list of connector Ids of all the connectors of type
430 // 'type' attached to the shape with the ID 'shapeId'.
431 void attachedConns(IntList &conns, const unsigned int shapeId,
432 const unsigned int type)
433 {
434 ConnRefList::iterator fin = connRefs.end();
435 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
436 if ((type & ConnRef::runningTo) && ((*i)->_dstId == shapeId)) {
437 conns.push_back((*i)->_srcId);
438 }
439 else if ((type & ConnRef::runningFrom) && ((*i)->_srcId == shapeId)) {
440 conns.push_back((*i)->_dstId);
441 }
442 }
443 }
446 // Returns a list of shape Ids of all the shapes attached to the
447 // shape with the ID 'shapeId' with connection type 'type'.
448 void attachedShapes(IntList &shapes, const unsigned int shapeId,
449 const unsigned int type)
450 {
451 ConnRefList::iterator fin = connRefs.end();
452 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
453 if ((type & ConnRef::runningTo) && ((*i)->_dstId == shapeId)) {
454 if ((*i)->_srcId != 0)
455 {
456 // Only if there is a shape attached to the other end.
457 shapes.push_back((*i)->_srcId);
458 }
459 }
460 else if ((type & ConnRef::runningFrom) && ((*i)->_srcId == shapeId)) {
461 if ((*i)->_dstId != 0)
462 {
463 // Only if there is a shape attached to the other end.
464 shapes.push_back((*i)->_dstId);
465 }
466 }
467 }
468 }
471 // It's intended this function is called after shape movement has
472 // happened to alert connectors that they need to be rerouted.
473 void callbackAllInvalidConnectors(void)
474 {
475 ConnRefList::iterator fin = connRefs.end();
476 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
477 (*i)->handleInvalid();
478 }
479 }
482 }