src/libavoid/connector.cpp

   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 */
  22
  23 #include "libavoid/graph.h"
  24 #include "libavoid/connector.h"
  25 #include "libavoid/makepath.h"
  26 #include "libavoid/visibility.h"
  27 #include "libavoid/debug.h"
  28 #include "libavoid/router.h"
  29
  30
  31 namespace Avoid {
  32
  33
  34 ConnRef::ConnRef(Router *router, const unsigned int id)
  35     : _router(router)
  36     , _id(id)
  37     , _type(ConnType_PolyLine)
  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     , _hateCrossings(false)
  50 {
  51     // TODO: Store endpoints and details.
  52     _route.pn = 0;
  53     _route.ps = NULL;
  54 }
  55
  56
  57 ConnRef::ConnRef(Router *router, const unsigned int id,
  58         const Point& src, const Point& dst)
  59     : _router(router)
  60     , _id(id)
  61     , _type(ConnType_PolyLine)
  62     , _srcId(0)
  63     , _dstId(0)
  64     , _needs_reroute_flag(true)
  65     , _false_path(false)
  66     , _active(false)
  67     , _route_dist(0)
  68     , _srcVert(NULL)
  69     , _dstVert(NULL)
  70     , _initialised(false)
  71     , _callback(NULL)
  72     , _connector(NULL)
  73     , _hateCrossings(false)
  74 {
  75     _route.pn = 0;
  76     _route.ps = NULL;
  77
  78     if (_router->IncludeEndpoints)
  79     {
  80         bool isShape = false;
  81         _srcVert = new VertInf(_router, VertID(id, isShape, 1), src);
  82         _dstVert = new VertInf(_router, VertID(id, isShape, 2), dst);
  83         _router->vertices.addVertex(_srcVert);
  84         _router->vertices.addVertex(_dstVert);
  85         makeActive();
  86         _initialised = true;
  87     }
  88 }
  89
  90
  91 ConnRef::~ConnRef()
  92 {
  93     freeRoute();
  94
  95     if (_srcVert)
  96     {
  97         _router->vertices.removeVertex(_srcVert);
  98         delete _srcVert;
  99         _srcVert = NULL;
 100     }
 101
 102     if (_dstVert)
 103     {
 104         _router->vertices.removeVertex(_dstVert);
 105         delete _dstVert;
 106         _dstVert = NULL;
 107     }
 108
 109     if (_active)
 110     {
 111         makeInactive();
 112     }
 113 }
 114
 115
 116 void ConnRef::setType(unsigned int type)
 117 {
 118     _type = type;
 119 }
 120
 121
 122 void ConnRef::updateEndPoint(const unsigned int type, const Point& point)
 123 {
 124     assert((type == (unsigned int) VertID::src) ||
 125            (type == (unsigned int) VertID::tar));
 126
 127     // XXX: This was commented out.  Is there a case where it isn't true?
 128     assert(_router->IncludeEndpoints);
 129
 130     if (!_initialised)
 131     {
 132         makeActive();
 133         _initialised = true;
 134     }
 135
 136     VertInf *altered = NULL;
 137     VertInf *partner = NULL;
 138     bool isShape = false;
 139
 140     if (type == (unsigned int) VertID::src)
 141     {
 142         if (_srcVert)
 143         {
 144             _srcVert->Reset(point);
 145         }
 146         else
 147         {
 148             _srcVert = new VertInf(_router, VertID(_id, isShape, type), point);
 149             _router->vertices.addVertex(_srcVert);
 150         }
 151
 152         altered = _srcVert;
 153         partner = _dstVert;
 154     }
 155     else // if (type == (unsigned int) VertID::dst)
 156     {
 157         if (_dstVert)
 158         {
 159             _dstVert->Reset(point);
 160         }
 161         else
 162         {
 163             _dstVert = new VertInf(_router, VertID(_id, isShape, type), point);
 164             _router->vertices.addVertex(_dstVert);
 165         }
 166
 167         altered = _dstVert;
 168         partner = _srcVert;
 169     }
 170
 171     // XXX: Seems to be faster to just remove the edges and recreate
 172     bool isConn = true;
 173     altered->removeFromGraph(isConn);
 174     bool knownNew = true;
 175     vertexVisibility(altered, partner, knownNew, true);
 176 }
 177
 178
 179 void ConnRef::setEndPointId(const unsigned int type, const unsigned int id)
 180 {
 181     if (type == (unsigned int) VertID::src)
 182     {
 183         _srcId = id;
 184     }
 185     else  // if (type == (unsigned int) VertID::dst)
 186     {
 187         _dstId = id;
 188     }
 189 }
 190
 191
 192 unsigned int ConnRef::getSrcShapeId(void)
 193 {
 194     return _srcId;
 195 }
 196
 197
 198 unsigned int ConnRef::getDstShapeId(void)
 199 {
 200     return _dstId;
 201 }
 202
 203
 204 void ConnRef::makeActive(void)
 205 {
 206     assert(!_active);
 207
 208     // Add to connRefs list.
 209     _pos = _router->connRefs.insert(_router->connRefs.begin(), this);
 210     _active = true;
 211 }
 212
 213
 214 void ConnRef::makeInactive(void)
 215 {
 216     assert(_active);
 217
 218     // Remove from connRefs list.
 219     _router->connRefs.erase(_pos);
 220     _active = false;
 221 }
 222
 223
 224 void ConnRef::freeRoute(void)
 225 {
 226     if (_route.ps)
 227     {
 228         _route.pn = 0;
 229         std::free(_route.ps);
 230         _route.ps = NULL;
 231     }
 232 }
 233
 234
 235 PolyLine& ConnRef::route(void)
 236 {
 237     return _route;
 238 }
 239
 240
 241 void ConnRef::calcRouteDist(void)
 242 {
 243     _route_dist = 0;
 244     for (int i = 1; i < _route.pn; i++)
 245     {
 246         _route_dist += dist(_route.ps[i], _route.ps[i - 1]);
 247     }
 248 }
 249
 250
 251 bool ConnRef::needsReroute(void)
 252 {
 253     return (_false_path || _needs_reroute_flag);
 254 }
 255
 256
 257 void ConnRef::lateSetup(const Point& src, const Point& dst)
 258 {
 259     assert(!_initialised);
 260
 261     bool isShape = false;
 262     _srcVert = new VertInf(_router, VertID(_id, isShape, 1), src);
 263     _dstVert = new VertInf(_router, VertID(_id, isShape, 2), dst);
 264     _router->vertices.addVertex(_srcVert);
 265     _router->vertices.addVertex(_dstVert);
 266     makeActive();
 267     _initialised = true;
 268 }
 269
 270
 271 unsigned int ConnRef::id(void)
 272 {
 273     return _id;
 274 }
 275
 276
 277 VertInf *ConnRef::src(void)
 278 {
 279     return _srcVert;
 280 }
 281
 282
 283 VertInf *ConnRef::dst(void)
 284 {
 285     return _dstVert;
 286 }
 287
 288
 289 bool ConnRef::isInitialised(void)
 290 {
 291     return _initialised;
 292 }
 293
 294
 295 void ConnRef::unInitialise(void)
 296 {
 297     _router->vertices.removeVertex(_srcVert);
 298     _router->vertices.removeVertex(_dstVert);
 299     makeInactive();
 300     _initialised = false;
 301 }
 302
 303
 304 void ConnRef::removeFromGraph(void)
 305 {
 306     for (VertInf *iter = _srcVert; iter != NULL; )
 307     {
 308         VertInf *tmp = iter;
 309         iter = (iter == _srcVert) ? _dstVert : NULL;
 310
 311         // For each vertex.
 312         EdgeInfList& visList = tmp->visList;
 313         EdgeInfList::iterator finish = visList.end();
 314         EdgeInfList::iterator edge;
 315         while ((edge = visList.begin()) != finish)
 316         {
 317             // Remove each visibility edge
 318             delete (*edge);
 319         }
 320
 321         EdgeInfList& invisList = tmp->invisList;
 322         finish = invisList.end();
 323         while ((edge = invisList.begin()) != finish)
 324         {
 325             // Remove each invisibility edge
 326             delete (*edge);
 327         }
 328     }
 329 }
 330
 331
 332 void ConnRef::setCallback(void (*cb)(void *), void *ptr)
 333 {
 334     _callback = cb;
 335     _connector = ptr;
 336 }
 337
 338
 339 void ConnRef::handleInvalid(void)
 340 {
 341     if (_false_path || _needs_reroute_flag) {
 342         if (_callback) {
 343             _callback(_connector);
 344         }
 345     }
 346 }
 347
 348
 349 void ConnRef::makePathInvalid(void)
 350 {
 351     _needs_reroute_flag = true;
 352 }
 353
 354
 355 Router *ConnRef::router(void)
 356 {
 357     return _router;
 358 }
 359
 360
 361 int ConnRef::generatePath(Point p0, Point p1)
 362 {
 363     if (!_false_path && !_needs_reroute_flag) {
 364         // This connector is up to date.
 365         return (int) false;
 366     }
 367
 368     _false_path = false;
 369     _needs_reroute_flag = false;
 370
 371     VertInf *src = _srcVert;
 372     VertInf *tar = _dstVert;
 373
 374     if ( !(_router->IncludeEndpoints) )
 375     {
 376         lateSetup(p0, p1);
 377
 378         // Update as they have just been set by lateSetup.
 379         src = _srcVert;
 380         tar = _dstVert;
 381
 382         bool knownNew = true;
 383         bool genContains = true;
 384         vertexVisibility(src, tar, knownNew, genContains);
 385         vertexVisibility(tar, src, knownNew, genContains);
 386     }
 387
 388     bool *flag = &(_needs_reroute_flag);
 389
 390     makePath(this, flag);
 391
 392     bool result = true;
 393
 394     int pathlen = 1;
 395     for (VertInf *i = tar; i != src; i = i->pathNext)
 396     {
 397         pathlen++;
 398         if (i == NULL)
 399         {
 400             db_printf("Warning: Path not found...\n");
 401             pathlen = 2;
 402             tar->pathNext = src;
 403             if (_router->InvisibilityGrph)
 404             {
 405                 // TODO:  Could we know this edge already?
 406                 EdgeInf *edge = EdgeInf::existingEdge(src, tar);
 407                 assert(edge != NULL);
 408                 edge->addCycleBlocker();
 409             }
 410             result = false;
 411             break;
 412         }
 413         if (pathlen > 100)
 414         {
 415             fprintf(stderr, "ERROR: Should never be here...\n");
 416             exit(1);
 417         }
 418     }
 419     Point *path = (Point *) malloc(pathlen * sizeof(Point));
 420
 421     int j = pathlen - 1;
 422     for (VertInf *i = tar; i != src; i = i->pathNext)
 423     {
 424         if (_router->InvisibilityGrph)
 425         {
 426             // TODO: Again, we could know this edge without searching.
 427             EdgeInf *edge = EdgeInf::existingEdge(i, i->pathNext);
 428             edge->addConn(flag);
 429         }
 430         else
 431         {
 432             _false_path = true;
 433         }
 434         path[j] = i->point;
 435         path[j].id = i->id.objID;
 436         j--;
 437     }
 438     path[0] = src->point;
 439
 440
 441     // Would clear visibility for endpoints here if required.
 442
 443     PolyLine& output_route = route();
 444     output_route.pn = pathlen;
 445     output_route.ps = path;
 446
 447     if ( !(_router->IncludeEndpoints) )
 448     {
 449         assert(_initialised);
 450         unInitialise();
 451     }
 452
 453     return (int) result;
 454 }
 455
 456
 457 void ConnRef::setHateCrossings(bool value)
 458 {
 459     _hateCrossings = value;
 460 }
 461
 462
 463 bool ConnRef::doesHateCrossings(void)
 464 {
 465     return _hateCrossings;
 466 }
 467
 468
 469 //============================================================================
 470
 471 }
 472
 473