← Back to branch summary

~ubuntu-branches/ubuntu/precise/inkscape/precise-updates

« back to all changes in this revision

Viewing changes to src/libavoid/vertices.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Alex Valavanis
  • Date: 2010-09-12 19:44:58 UTC
  • mfrom: (1.1.12 upstream) (45.1.3 maverick)
  • Revision ID: james.westby@ubuntu.com-20100912194458-4sjwmbl7dlsrk5dc
Tags: 0.48.0-1ubuntu1
https://launchpad.net/bugs/628048
https://launchpad.net/bugs/401567
https://launchpad.net/bugs/456248
https://launchpad.net/bugs/463602
https://launchpad.net/bugs/591986
https://launchpad.net/bugs/513319
* Merge with Debian unstable (LP: #628048, LP: #401567, LP: #456248, 
  LP: #463602, LP: #591986)
* debian/control: 
  - Ubuntu maintainers
  - Promote python-lxml, python-numpy, python-uniconvertor to Recommends.
  - Demote pstoedit to Suggests (universe package).
  - Suggests ttf-dejavu instead of ttf-bitstream-vera (LP: #513319)
* debian/rules:
  - Run intltool-update on build (Ubuntu-specific).
  - Add translation domain to .desktop files (Ubuntu-specific).
* debian/dirs:
  - Add usr/share/pixmaps.  Allow inkscape.xpm installation
* drop 50-poppler-API.dpatch (now upstream)
* drop 51-paste-in-unwritable-directory.dpatch (now upstream) 

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/libavoid/vertices.cpp
2
2
 * vim: ts=4 sw=4 et tw=0 wm=0
3
3
 *
4
4
 * libavoid - Fast, Incremental, Object-avoiding Line Router
5
 
 * Copyright (C) 2004-2006  Michael Wybrow <mjwybrow@users.sourceforge.net>
 
5
 *
 
6
 * Copyright (C) 2004-2009  Monash University
6
7
 *
7
8
 * This library is free software; you can redistribute it and/or
8
9
 * modify it under the terms of the GNU Lesser General Public
9
10
 * License as published by the Free Software Foundation; either
10
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.
11
17
 *
12
18
 * This library is distributed in the hope that it will be useful,
13
19
 * 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
 
 *
 
20
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 
21
 *
 
22
 * Author(s):   Michael Wybrow <mjwybrow@users.sourceforge.net>
21
23
*/
22
24
 
 
25
 
 
26
#include <iostream>
 
27
#include <cstdlib>
 
28
 
23
29
#include "libavoid/vertices.h"
24
30
#include "libavoid/geometry.h"
25
31
#include "libavoid/graph.h"  // For alertConns
26
32
#include "libavoid/debug.h"
27
33
#include "libavoid/router.h"
28
 
 
29
 
#include <iostream>
30
 
#include <cstdlib>
31
 
#include <cassert>
 
34
#include "libavoid/assertions.h"
32
35
 
33
36
using std::ostream;
34
37
 
76
79
    {
77
80
        return false;
78
81
    }
79
 
    assert(isShape == rhs.isShape);
 
82
    // XXX RubberBand search breaks this:
 
83
    // COLA_ASSERT(isShape == rhs.isShape);
80
84
    return true;
81
85
}
82
86
 
87
91
    {
88
92
        return true;
89
93
    }
90
 
    assert(isShape == rhs.isShape);
 
94
    COLA_ASSERT(isShape == rhs.isShape);
91
95
    return false;
92
96
}
93
97
 
133
137
}
134
138
 
135
139
 
136
 
const int VertID::src = 1;
137
 
const int VertID::tar = 2;
 
140
const unsigned short VertID::src = 1;
 
141
const unsigned short VertID::tar = 2;
138
142
 
139
143
 
140
144
ostream& operator<<(ostream& os, const VertID& vID)
144
148
 
145
149
 
146
150
 
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
 
{
 
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;
160
187
}
161
188
 
162
189
 
163
190
void VertInf::Reset(const Point& vpoint)
164
191
{
165
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());
166
202
}
167
203
 
168
204
 
170
206
{
171
207
    if (isConnVert)
172
208
    {
173
 
        assert(!(id.isShape));
 
209
        COLA_ASSERT(!(id.isShape));
174
210
    }
175
211
 
176
 
    VertInf *tmp = this;
177
 
 
178
212
    // For each vertex.
179
 
    EdgeInfList& visList = tmp->visList;
180
 
    EdgeInfList::iterator finish = visList.end();
181
 
    EdgeInfList::iterator edge;
 
213
    EdgeInfList::const_iterator finish = visList.end();
 
214
    EdgeInfList::const_iterator edge;
182
215
    while ((edge = visList.begin()) != finish)
183
216
    {
184
217
        // Remove each visibility edge
186
219
        delete (*edge);
187
220
    }
188
221
 
189
 
    EdgeInfList& invisList = tmp->invisList;
 
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
 
190
230
    finish = invisList.end();
191
231
    while ((edge = invisList.begin()) != finish)
192
232
    {
208
248
 
209
249
    // We better be part of the same instance of libavoid.
210
250
    Router *router = src->_router;
211
 
    assert(router == dst->_router);
 
251
    COLA_ASSERT(router == dst->_router);
212
252
 
213
253
    ContainsMap& contains = router->contains;
214
254
    if (!(pID.isShape))
239
279
 
240
280
 
241
281
VertInfList::VertInfList()
242
 
    : _firstShapeVert(NULL)
243
 
    , _firstConnVert(NULL)
244
 
    , _lastShapeVert(NULL)
245
 
    , _lastConnVert(NULL)
246
 
    , _shapeVertices(0)
247
 
    , _connVertices(0)
 
282
    : _firstShapeVert(NULL),
 
283
      _firstConnVert(NULL),
 
284
      _lastShapeVert(NULL),
 
285
      _lastConnVert(NULL),
 
286
      _shapeVertices(0),
 
287
      _connVertices(0)
248
288
{
249
289
}
250
290
 
251
291
 
252
292
#define checkVertInfListConditions() \
253
293
        do { \
254
 
            assert((!_firstConnVert && (_connVertices == 0)) || \
 
294
            COLA_ASSERT((!_firstConnVert && (_connVertices == 0)) || \
255
295
                    ((_firstConnVert->lstPrev == NULL) && (_connVertices > 0))); \
256
 
            assert((!_firstShapeVert && (_shapeVertices == 0)) || \
 
296
            COLA_ASSERT((!_firstShapeVert && (_shapeVertices == 0)) || \
257
297
                    ((_firstShapeVert->lstPrev == NULL) && (_shapeVertices > 0))); \
258
 
            assert(!_lastShapeVert || (_lastShapeVert->lstNext == NULL)); \
259
 
            assert(!_lastConnVert || (_lastConnVert->lstNext == _firstShapeVert)); \
260
 
            assert((!_firstConnVert && !_lastConnVert) || \
 
298
            COLA_ASSERT(!_lastShapeVert || (_lastShapeVert->lstNext == NULL)); \
 
299
            COLA_ASSERT(!_lastConnVert || (_lastConnVert->lstNext == _firstShapeVert)); \
 
300
            COLA_ASSERT((!_firstConnVert && !_lastConnVert) || \
261
301
                    (_firstConnVert &&  _lastConnVert) ); \
262
 
            assert((!_firstShapeVert && !_lastShapeVert) || \
 
302
            COLA_ASSERT((!_firstShapeVert && !_lastShapeVert) || \
263
303
                    (_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)); \
 
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)); \
268
308
        } while(0)
269
309
 
270
310
 
271
311
void VertInfList::addVertex(VertInf *vert)
272
312
{
273
313
    checkVertInfListConditions();
274
 
    assert(vert->lstPrev == NULL);
275
 
    assert(vert->lstNext == NULL);
 
314
    COLA_ASSERT(vert->lstPrev == NULL);
 
315
    COLA_ASSERT(vert->lstNext == NULL);
276
316
 
277
317
    if (!(vert->id.isShape))
278
318
    {
329
369
}
330
370
 
331
371
 
332
 
void VertInfList::removeVertex(VertInf *vert)
 
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)
333
375
{
 
376
    if (vert == NULL)
 
377
    {
 
378
        return NULL;
 
379
    }
334
380
    // Conditions for correct data structure
335
381
    checkVertInfListConditions();
 
382
    
 
383
    VertInf *following = vert->lstNext;
336
384
 
337
385
    if (!(vert->id.isShape))
338
386
    {
421
469
    vert->lstNext = NULL;
422
470
 
423
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;
424
516
}
425
517
 
426
518
 
447
539
}
448
540
 
449
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
 
450
554
}
451
555
 
452
556