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  * 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/vertices.h"
  24 #include "libavoid/geometry.h"
  25 #include "libavoid/graph.h"  // For alertConns
  26 #include "libavoid/debug.h"
  27 #include "libavoid/router.h"
  28
  29 #include <iostream>
  30 #include <cstdlib>
  31 #include <cassert>
  32
  33
  34 namespace Avoid {
  35
  36
  37 VertID::VertID()
  38 {
  39 }
  40
  41
  42 VertID::VertID(unsigned int id, bool s, int n)
  43     : objID(id)
  44     , isShape(s)
  45     , vn(n)
  46 {
  47 }
  48
  49
  50 VertID::VertID(const VertID& other)
  51     : objID(other.objID)
  52     , isShape(other.isShape)
  53     , vn(other.vn)
  54 {
  55 }
  56
  57
  58 VertID& VertID::operator= (const VertID& rhs)
  59 {
  60     // Gracefully handle self assignment
  61     //if (this == &rhs) return *this;
  62
  63     objID = rhs.objID;
  64     isShape = rhs.isShape;
  65     vn = rhs.vn;
  66
  67     return *this;
  68 }
  69
  70
  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 }
  80
  81
  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 }
  91
  92
  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 }
 102
 103
 104 VertID VertID::operator+(const int& rhs) const
 105 {
 106     return VertID(objID, isShape, vn + rhs);
 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++(int)
 117 {
 118     vn += 1;
 119     return *this;
 120 }
 121
 122
 123 void VertID::print(FILE *file) const
 124 {
 125     fprintf(file, "[%u,%d]", objID, vn);
 126 }
 127
 128
 129 void VertID::db_print(void) const
 130 {
 131     db_printf("[%u,%d]", objID, vn);
 132 }
 133
 134
 135 const int VertID::src = 1;
 136 const int VertID::tar = 2;
 137
 138
 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 }
 153
 154
 155 void VertInf::Reset(const Point& vpoint)
 156 {
 157     point = vpoint;
 158 }
 159
 160
 161 void VertInf::removeFromGraph(const bool isConnVert)
 162 {
 163     if (isConnVert)
 164     {
 165         assert(!(id.isShape));
 166     }
 167
 168     VertInf *tmp = this;
 169
 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     }
 180
 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 }
 189
 190
 191 bool directVis(VertInf *src, VertInf *dst)
 192 {
 193     ShapeSet ss = ShapeSet();
 194
 195     Point& p = src->point;
 196     Point& q = dst->point;
 197
 198     VertID& pID = src->id;
 199     VertID& qID = dst->id;
 200
 201     // We better be part of the same instance of libavoid.
 202     Router *router = src->_router;
 203     assert(router == dst->_router);
 204
 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     }
 214
 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 }
 231
 232
 233 VertInfList::VertInfList()
 234     : _firstShapeVert(NULL)
 235     , _firstConnVert(NULL)
 236     , _lastShapeVert(NULL)
 237     , _lastConnVert(NULL)
 238     , _shapeVertices(0)
 239     , _connVertices(0)
 240 {
 241 }
 242
 243
 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)
 261
 262
 263 void VertInfList::addVertex(VertInf *vert)
 264 {
 265     checkVertInfListConditions();
 266     assert(vert->lstPrev == NULL);
 267     assert(vert->lstNext == NULL);
 268
 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;
 277
 278             // Make front
 279             _firstConnVert = vert;
 280         }
 281         else
 282         {
 283             // Make front and back
 284             _firstConnVert = vert;
 285             _lastConnVert = vert;
 286
 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;
 300
 301             // Make back
 302             _lastShapeVert = vert;
 303         }
 304         else
 305         {
 306             // Make first and last
 307             _firstShapeVert = vert;
 308             _lastShapeVert = vert;
 309
 310             // Join with conns list
 311             if (_lastConnVert)
 312             {
 313                 assert (_lastConnVert->lstNext == NULL);
 314
 315                 _lastConnVert->lstNext = vert;
 316             }
 317         }
 318         _shapeVertices++;
 319     }
 320     checkVertInfListConditions();
 321 }
 322
 323
 324 void VertInfList::removeVertex(VertInf *vert)
 325 {
 326     // Conditions for correct data structure
 327     checkVertInfListConditions();
 328
 329     if (!(vert->id.isShape))
 330     {
 331         // A Connector vertex
 332         if (vert == _firstConnVert)
 333         {
 334
 335             if (vert == _lastConnVert)
 336             {
 337                 _firstConnVert = NULL;
 338                 _lastConnVert = NULL;
 339             }
 340             else
 341             {
 342                 // Set new first
 343                 _firstConnVert = _firstConnVert->lstNext;
 344
 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;
 356
 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;
 374
 375             if (vert == _firstShapeVert)
 376             {
 377                 _firstShapeVert = NULL;
 378                 if (_lastConnVert)
 379                 {
 380                     _lastConnVert->lstNext = NULL;
 381                 }
 382             }
 383
 384             if (_lastShapeVert)
 385             {
 386                 _lastShapeVert->lstNext = NULL;
 387             }
 388         }
 389         else if (vert == _firstShapeVert)
 390         {
 391             // Set new first
 392             _firstShapeVert = _firstShapeVert->lstNext;
 393
 394             // Correct the last conn vertex
 395             if (_lastConnVert)
 396             {
 397                 _lastConnVert->lstNext = _firstShapeVert;
 398             }
 399
 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;
 414
 415     checkVertInfListConditions();
 416 }
 417
 418
 419 VertInf *VertInfList::shapesBegin(void)
 420 {
 421     return _firstShapeVert;
 422 }
 423
 424
 425 VertInf *VertInfList::connsBegin(void)
 426 {
 427     if (_firstConnVert)
 428     {
 429         return _firstConnVert;
 430     }
 431     // No connector vertices
 432     return _firstShapeVert;
 433 }
 434
 435
 436 VertInf *VertInfList::end(void)
 437 {
 438     return NULL;
 439 }
 440
 441
 442 }
 443
 444