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