src/libavoid/vertices.cpp

   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 */
  24
  25
  26 #include <iostream>
  27 #include <cstdlib>
  28
  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"
  35
  36 using std::ostream;
  37
  38
  39 namespace Avoid {
  40
  41
  42 VertID::VertID()
  43 {
  44 }
  45
  46
  47 VertID::VertID(unsigned int id, bool s, int n)
  48     : objID(id)
  49     , isShape(s)
  50     , vn(n)
  51 {
  52 }
  53
  54
  55 VertID::VertID(const VertID& other)
  56     : objID(other.objID)
  57     , isShape(other.isShape)
  58     , vn(other.vn)
  59 {
  60 }
  61
  62
  63 VertID& VertID::operator= (const VertID& rhs)
  64 {
  65     // Gracefully handle self assignment
  66     //if (this == &rhs) return *this;
  67
  68     objID = rhs.objID;
  69     isShape = rhs.isShape;
  70     vn = rhs.vn;
  71
  72     return *this;
  73 }
  74
  75
  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 }
  86
  87
  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 }
  97
  98
  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 }
 108
 109
 110 VertID VertID::operator+(const int& rhs) const
 111 {
 112     return VertID(objID, isShape, vn + rhs);
 113 }
 114
 115
 116 VertID VertID::operator-(const int& rhs) const
 117 {
 118     return VertID(objID, isShape, vn - rhs);
 119 }
 120
 121
 122 VertID& VertID::operator++(int)
 123 {
 124     vn += 1;
 125     return *this;
 126 }
 127
 128
 129 void VertID::print(FILE *file) const
 130 {
 131     fprintf(file, "[%u,%d]", objID, vn);
 132 }
 133
 134 void VertID::db_print(void) const
 135 {
 136     db_printf("[%u,%d]", objID, vn);
 137 }
 138
 139
 140 const unsigned short VertID::src = 1;
 141 const unsigned short VertID::tar = 2;
 142
 143
 144 ostream& operator<<(ostream& os, const VertID& vID)
 145 {
 146     return os << '[' << vID.objID << ',' << vID.vn << ']';
 147 }
 148
 149
 150
 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;
 168
 169     if (addToRouter)
 170     {
 171         _router->vertices.addVertex(this);
 172     }
 173 }
 174
 175
 176 VertInf::~VertInf()
 177 {
 178 }
 179
 180
 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 }
 188
 189
 190 void VertInf::Reset(const Point& vpoint)
 191 {
 192     point = vpoint;
 193     point.id = id.objID;
 194     point.vn = id.vn;
 195 }
 196
 197
 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 }
 203
 204
 205 void VertInf::removeFromGraph(const bool isConnVert)
 206 {
 207     if (isConnVert)
 208     {
 209         COLA_ASSERT(!(id.isShape));
 210     }
 211
 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     }
 221
 222     finish = orthogVisList.end();
 223     while ((edge = orthogVisList.begin()) != finish)
 224     {
 225         // Remove each orthogonal visibility edge.
 226         (*edge)->alertConns();
 227         delete (*edge);
 228     }
 229
 230     finish = invisList.end();
 231     while ((edge = invisList.begin()) != finish)
 232     {
 233         // Remove each invisibility edge
 234         delete (*edge);
 235     }
 236 }
 237
 238
 239 bool directVis(VertInf *src, VertInf *dst)
 240 {
 241     ShapeSet ss = ShapeSet();
 242
 243     Point& p = src->point;
 244     Point& q = dst->point;
 245
 246     VertID& pID = src->id;
 247     VertID& qID = dst->id;
 248
 249     // We better be part of the same instance of libavoid.
 250     Router *router = src->_router;
 251     COLA_ASSERT(router == dst->_router);
 252
 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     }
 262
 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 }
 279
 280
 281 VertInfList::VertInfList()
 282     : _firstShapeVert(NULL),
 283       _firstConnVert(NULL),
 284       _lastShapeVert(NULL),
 285       _lastConnVert(NULL),
 286       _shapeVertices(0),
 287       _connVertices(0)
 288 {
 289 }
 290
 291
 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)
 309
 310
 311 void VertInfList::addVertex(VertInf *vert)
 312 {
 313     checkVertInfListConditions();
 314     COLA_ASSERT(vert->lstPrev == NULL);
 315     COLA_ASSERT(vert->lstNext == NULL);
 316
 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;
 325
 326             // Make front
 327             _firstConnVert = vert;
 328         }
 329         else
 330         {
 331             // Make front and back
 332             _firstConnVert = vert;
 333             _lastConnVert = vert;
 334
 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;
 348
 349             // Make back
 350             _lastShapeVert = vert;
 351         }
 352         else
 353         {
 354             // Make first and last
 355             _firstShapeVert = vert;
 356             _lastShapeVert = vert;
 357
 358             // Join with conns list
 359             if (_lastConnVert)
 360             {
 361                 assert (_lastConnVert->lstNext == NULL);
 362
 363                 _lastConnVert->lstNext = vert;
 364             }
 365         }
 366         _shapeVertices++;
 367     }
 368     checkVertInfListConditions();
 369 }
 370
 371
 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();
 382
 383     VertInf *following = vert->lstNext;
 384
 385     if (!(vert->id.isShape))
 386     {
 387         // A Connector vertex
 388         if (vert == _firstConnVert)
 389         {
 390
 391             if (vert == _lastConnVert)
 392             {
 393                 _firstConnVert = NULL;
 394                 _lastConnVert = NULL;
 395             }
 396             else
 397             {
 398                 // Set new first
 399                 _firstConnVert = _firstConnVert->lstNext;
 400
 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;
 412
 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;
 430
 431             if (vert == _firstShapeVert)
 432             {
 433                 _firstShapeVert = NULL;
 434                 if (_lastConnVert)
 435                 {
 436                     _lastConnVert->lstNext = NULL;
 437                 }
 438             }
 439
 440             if (_lastShapeVert)
 441             {
 442                 _lastShapeVert->lstNext = NULL;
 443             }
 444         }
 445         else if (vert == _firstShapeVert)
 446         {
 447             // Set new first
 448             _firstShapeVert = _firstShapeVert->lstNext;
 449
 450             // Correct the last conn vertex
 451             if (_lastConnVert)
 452             {
 453                 _lastConnVert->lstNext = _firstShapeVert;
 454             }
 455
 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;
 470
 471     checkVertInfListConditions();
 472
 473     return following;
 474 }
 475
 476
 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 }
 503
 504
 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 }
 517
 518
 519 VertInf *VertInfList::shapesBegin(void)
 520 {
 521     return _firstShapeVert;
 522 }
 523
 524
 525 VertInf *VertInfList::connsBegin(void)
 526 {
 527     if (_firstConnVert)
 528     {
 529         return _firstConnVert;
 530     }
 531     // No connector vertices
 532     return _firstShapeVert;
 533 }
 534
 535
 536 VertInf *VertInfList::end(void)
 537 {
 538     return NULL;
 539 }
 540
 541
 542 unsigned int VertInfList::connsSize(void) const
 543 {
 544     return _connVertices;
 545 }
 546
 547
 548 unsigned int VertInfList::shapesSize(void) const
 549 {
 550     return _shapeVertices;
 551 }
 552
 553
 554 }
 555
 556