← Back to branch summary

~ubuntu-branches/ubuntu/utopic/inkscape/utopic-proposed

« back to all changes in this revision

Viewing changes to .pc/0004-Fix_FTBFS_on_gcc-4.8.patch/src/libvpsc/block.cpp

  • Committer: Package Import Robot
  • Author(s): Mattia Rizzolo
  • Date: 2014-01-14 15:44:58 UTC
  • mfrom: (2.5.10 sid)
  • Revision ID: package-import@ubuntu.com-20140114154458-3283675h9vtv5ccc
Tags: 0.48.4-3ubuntu1
https://launchpad.net/bugs/1225013
https://launchpad.net/bugs/811634
* Merge from Debian unstable (LP: #1225013).  Remaining changes:
  - debian/control:
    + Set Ubuntu Developer as maintainer,
    + build-depend on dh-translation to handle Ubuntu translation,
    + build against liblcsm2 instead of liblcsm1,
    + demote pstoedit from Recommends to Suggests (because it's on universe),
    + add a ${python:Depends}.
  - debian/patches/0006_add_unity_quicklist_support.patch: add.
  - debian/patches/series: update.
  - debian/rules:
    + add dh_translation to handle Ubuntu translation,
    + add python2 to dh addon.
* Debian changes:
  - debian/control: make description more user-friendly (LP: #811634)

Show diffs side-by-side

added added

removed removed

Lines of Context:
.pc/0004-Fix_FTBFS_on_gcc-4.8.patch/src/libvpsc/block.cpp
 
1
/**
 
2
 * \brief A block is a group of variables that must be moved together to improve
 
3
 * the goal function without violating already active constraints.
 
4
 * The variables in a block are spanned by a tree of active constraints.
 
5
 *
 
6
 * Authors:
 
7
 *   Tim Dwyer <tgdwyer@gmail.com>
 
8
 *
 
9
 * Copyright (C) 2005 Authors
 
10
 *
 
11
 * Released under GNU LGPL.  Read the file 'COPYING' for more information.
 
12
 */
 
13
#include <cassert>
 
14
#include "pairingheap/PairingHeap.h"
 
15
#include "constraint.h"
 
16
#include "block.h"
 
17
#include "blocks.h"
 
18
#ifdef RECTANGLE_OVERLAP_LOGGING
 
19
#include <fstream>
 
20
using std::ios;
 
21
using std::ofstream;
 
22
using std::endl;
 
23
#endif
 
24
using std::vector;
 
25
 
 
26
namespace vpsc {
 
27
void Block::addVariable(Variable* const v) {
 
28
        v->block=this;
 
29
        vars->push_back(v);
 
30
        weight+=v->weight;
 
31
        wposn += v->weight * (v->desiredPosition - v->offset);
 
32
        posn=wposn/weight;
 
33
}
 
34
Block::Block(Variable* const v) {
 
35
        timeStamp=0;
 
36
        posn=weight=wposn=0;
 
37
        in=NULL;
 
38
        out=NULL;
 
39
        deleted=false;
 
40
        vars=new vector<Variable*>;
 
41
        if(v!=NULL) {
 
42
                v->offset=0;
 
43
                addVariable(v);
 
44
        }
 
45
}
 
46
 
 
47
double Block::desiredWeightedPosition() {
 
48
        double wp = 0;
 
49
        for (Vit v=vars->begin();v!=vars->end();++v) {
 
50
                wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight;
 
51
        }
 
52
        return wp;
 
53
}
 
54
Block::~Block(void)
 
55
{
 
56
        delete vars;
 
57
        delete in;
 
58
        delete out;
 
59
}
 
60
void Block::setUpInConstraints() {
 
61
        setUpConstraintHeap(in,true);
 
62
}
 
63
void Block::setUpOutConstraints() {
 
64
        setUpConstraintHeap(out,false);
 
65
}
 
66
void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) {
 
67
        delete h;
 
68
        h = new PairingHeap<Constraint*>(&compareConstraints);
 
69
        for (Vit i=vars->begin();i!=vars->end();++i) {
 
70
                Variable *v=*i;
 
71
                vector<Constraint*> *cs=in?&(v->in):&(v->out);
 
72
                for (Cit j=cs->begin();j!=cs->end();++j) {
 
73
                        Constraint *c=*j;
 
74
                        c->timeStamp=blockTimeCtr;
 
75
                        if (c->left->block != this && in || c->right->block != this && !in) {
 
76
                                h->insert(c);
 
77
                        }
 
78
                }
 
79
        }
 
80
}       
 
81
void Block::merge(Block* b, Constraint* c) {
 
82
#ifdef RECTANGLE_OVERLAP_LOGGING
 
83
        ofstream f(LOGFILE,ios::app);
 
84
        f<<"  merging on: "<<*c<<",c->left->offset="<<c->left->offset<<",c->right->offset="<<c->right->offset<<endl;
 
85
#endif
 
86
        double dist = c->right->offset - c->left->offset - c->gap;
 
87
        Block *l=c->left->block;
 
88
        Block *r=c->right->block;
 
89
        if (vars->size() < b->vars->size()) {
 
90
                r->merge(l,c,dist);
 
91
        } else {
 
92
                l->merge(r,c,-dist);
 
93
        }
 
94
#ifdef RECTANGLE_OVERLAP_LOGGING
 
95
        f<<"  merged block="<<(b->deleted?*this:*b)<<endl;
 
96
#endif
 
97
}
 
98
/**
 
99
 * Merges b into this block across c.  Can be either a
 
100
 * right merge or a left merge
 
101
 * @param b block to merge into this
 
102
 * @param c constraint being merged
 
103
 * @param distance separation required to satisfy c
 
104
 */
 
105
void Block::merge(Block *b, Constraint *c, double dist) {
 
106
#ifdef RECTANGLE_OVERLAP_LOGGING
 
107
        ofstream f(LOGFILE,ios::app);
 
108
        f<<"    merging: "<<*b<<"dist="<<dist<<endl;
 
109
#endif
 
110
        c->active=true;
 
111
        wposn+=b->wposn-dist*b->weight;
 
112
        weight+=b->weight;
 
113
        posn=wposn/weight;
 
114
        for(Vit i=b->vars->begin();i!=b->vars->end();++i) {
 
115
                Variable *v=*i;
 
116
                v->block=this;
 
117
                v->offset+=dist;
 
118
                vars->push_back(v);
 
119
        }
 
120
        b->deleted=true;
 
121
}
 
122
 
 
123
void Block::mergeIn(Block *b) {
 
124
#ifdef RECTANGLE_OVERLAP_LOGGING
 
125
        ofstream f(LOGFILE,ios::app);
 
126
        f<<"  merging constraint heaps... "<<endl;
 
127
#endif
 
128
        // We check the top of the heaps to remove possible internal constraints
 
129
        findMinInConstraint();
 
130
        b->findMinInConstraint();
 
131
        in->merge(b->in);
 
132
#ifdef RECTANGLE_OVERLAP_LOGGING
 
133
        f<<"  merged heap: "<<*in<<endl;
 
134
#endif
 
135
}
 
136
void Block::mergeOut(Block *b) {        
 
137
        findMinOutConstraint();
 
138
        b->findMinOutConstraint();
 
139
        out->merge(b->out);
 
140
}
 
141
Constraint *Block::findMinInConstraint() {
 
142
        Constraint *v = NULL;
 
143
        vector<Constraint*> outOfDate;
 
144
        while (!in->isEmpty()) {
 
145
                v = in->findMin();
 
146
                Block *lb=v->left->block;
 
147
                Block *rb=v->right->block;
 
148
                // rb may not be this if called between merge and mergeIn
 
149
#ifdef RECTANGLE_OVERLAP_LOGGING
 
150
                ofstream f(LOGFILE,ios::app);
 
151
                f<<"  checking constraint ... "<<*v;
 
152
                f<<"    timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl;
 
153
#endif
 
154
                if(lb == rb) {
 
155
                        // constraint has been merged into the same block
 
156
#ifdef RECTANGLE_OVERLAP_LOGGING
 
157
                        if(v->slack()<0) {
 
158
                                f<<"  violated internal constraint found! "<<*v<<endl;
 
159
                                f<<"     lb="<<*lb<<endl;
 
160
                                f<<"     rb="<<*rb<<endl;
 
161
                        }
 
162
#endif
 
163
                        in->deleteMin();
 
164
#ifdef RECTANGLE_OVERLAP_LOGGING
 
165
                        f<<" ... skipping internal constraint"<<endl;
 
166
#endif
 
167
                } else if(v->timeStamp < lb->timeStamp) {
 
168
                        // block at other end of constraint has been moved since this
 
169
                        in->deleteMin();
 
170
                        outOfDate.push_back(v);
 
171
#ifdef RECTANGLE_OVERLAP_LOGGING
 
172
                        f<<"    reinserting out of date (reinsert later)"<<endl;
 
173
#endif
 
174
                } else {
 
175
                        break;
 
176
                }
 
177
        }
 
178
        for(Cit i=outOfDate.begin();i!=outOfDate.end();++i) {
 
179
                v=*i;
 
180
                v->timeStamp=blockTimeCtr;
 
181
                in->insert(v);
 
182
        }
 
183
        if(in->isEmpty()) {
 
184
                v=NULL;
 
185
        } else {
 
186
                v=in->findMin();
 
187
        }
 
188
        return v;
 
189
}
 
190
Constraint *Block::findMinOutConstraint() {
 
191
        if(out->isEmpty()) return NULL;
 
192
        Constraint *v = out->findMin();
 
193
        while (v->left->block == v->right->block) {
 
194
                out->deleteMin();
 
195
                if(out->isEmpty()) return NULL;
 
196
                v = out->findMin();
 
197
        }
 
198
        return v;
 
199
}
 
200
void Block::deleteMinInConstraint() {
 
201
        in->deleteMin();
 
202
#ifdef RECTANGLE_OVERLAP_LOGGING
 
203
        ofstream f(LOGFILE,ios::app);
 
204
        f<<"deleteMinInConstraint... "<<endl;
 
205
        f<<"  result: "<<*in<<endl;
 
206
#endif
 
207
}
 
208
void Block::deleteMinOutConstraint() {
 
209
        out->deleteMin();
 
210
}
 
211
inline bool Block::canFollowLeft(Constraint *c, const Variable* const last) {
 
212
        return c->left->block==this && c->active && last!=c->left;
 
213
}
 
214
inline bool Block::canFollowRight(Constraint *c, const Variable* const last) {
 
215
        return c->right->block==this && c->active && last!=c->right;
 
216
}
 
217
 
 
218
// computes the derivative of v and the lagrange multipliers
 
219
// of v's out constraints (as the recursive sum of those below.
 
220
// Does not backtrack over u.
 
221
// also records the constraint with minimum lagrange multiplier
 
222
// in min_lm
 
223
double Block::compute_dfdv(Variable* const v, Variable* const u,
 
224
                Constraint *&min_lm) {
 
225
        double dfdv=v->weight*(v->position() - v->desiredPosition);
 
226
        for(Cit it=v->out.begin();it!=v->out.end();++it) {
 
227
                Constraint *c=*it;
 
228
                if(canFollowRight(c,u)) {
 
229
                        dfdv+=c->lm=compute_dfdv(c->right,v,min_lm);
 
230
                        if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
 
231
                }
 
232
        }
 
233
        for(Cit it=v->in.begin();it!=v->in.end();++it) {
 
234
                Constraint *c=*it;
 
235
                if(canFollowLeft(c,u)) {
 
236
                        dfdv-=c->lm=-compute_dfdv(c->left,v,min_lm);
 
237
                        if(!c->equality&&(min_lm==NULL||c->lm<min_lm->lm)) min_lm=c;
 
238
                }
 
239
        }
 
240
        return dfdv;
 
241
}
 
242
 
 
243
 
 
244
// computes dfdv for each variable and uses the sum of dfdv on either side of
 
245
// the constraint c to compute the lagrangian multiplier lm_c.
 
246
// The top level v and r are variables between which we want to find the
 
247
// constraint with the smallest lm.  
 
248
// When we find r we pass NULL to subsequent recursive calls, 
 
249
// thus r=NULL indicates constraints are not on the shortest path.
 
250
// Similarly, m is initially NULL and is only assigned a value if the next
 
251
// variable to be visited is r or if a possible min constraint is returned from
 
252
// a nested call (rather than NULL).
 
253
// Then, the search for the m with minimum lm occurs as we return from
 
254
// the recursion (checking only constraints traversed left-to-right 
 
255
// in order to avoid creating any new violations).
 
256
// We also do not consider equality constraints as potential split points
 
257
Block::Pair Block::compute_dfdv_between(
 
258
                Variable* r, Variable* const v, Variable* const u, 
 
259
                const Direction dir = NONE, bool changedDirection = false) {
 
260
        double dfdv=v->weight*(v->position() - v->desiredPosition);
 
261
        Constraint *m=NULL;
 
262
        for(Cit it(v->in.begin());it!=v->in.end();++it) {
 
263
                Constraint *c=*it;
 
264
                if(canFollowLeft(c,u)) {
 
265
                        if(dir==RIGHT) { 
 
266
                                changedDirection = true; 
 
267
                        }
 
268
                        if(c->left==r) {
 
269
                                r=NULL;
 
270
                                if(!c->equality) m=c; 
 
271
                        }
 
272
                        Pair p=compute_dfdv_between(r,c->left,v,
 
273
                                        LEFT,changedDirection);
 
274
                        dfdv -= c->lm = -p.first;
 
275
                        if(r && p.second) 
 
276
                                m = p.second;
 
277
                }
 
278
        }
 
279
        for(Cit it(v->out.begin());it!=v->out.end();++it) {
 
280
                Constraint *c=*it;
 
281
                if(canFollowRight(c,u)) {
 
282
                        if(dir==LEFT) { 
 
283
                                changedDirection = true; 
 
284
                        }
 
285
                        if(c->right==r) {
 
286
                                r=NULL; 
 
287
                                if(!c->equality) m=c; 
 
288
                        }
 
289
                        Pair p=compute_dfdv_between(r,c->right,v,
 
290
                                        RIGHT,changedDirection);
 
291
                        dfdv += c->lm = p.first;
 
292
                        if(r && p.second) 
 
293
                                m = changedDirection && !c->equality && c->lm < p.second->lm 
 
294
                                        ? c 
 
295
                                        : p.second;
 
296
                }
 
297
        }
 
298
        return Pair(dfdv,m);
 
299
}
 
300
 
 
301
// resets LMs for all active constraints to 0 by
 
302
// traversing active constraint tree starting from v,
 
303
// not back tracking over u
 
304
void Block::reset_active_lm(Variable* const v, Variable* const u) {
 
305
        for(Cit it=v->out.begin();it!=v->out.end();++it) {
 
306
                Constraint *c=*it;
 
307
                if(canFollowRight(c,u)) {
 
308
                        c->lm=0;
 
309
                        reset_active_lm(c->right,v);
 
310
                }
 
311
        }
 
312
        for(Cit it=v->in.begin();it!=v->in.end();++it) {
 
313
                Constraint *c=*it;
 
314
                if(canFollowLeft(c,u)) {
 
315
                        c->lm=0;
 
316
                        reset_active_lm(c->left,v);
 
317
                }
 
318
        }
 
319
}
 
320
/**
 
321
 * finds the constraint with the minimum lagrange multiplier, that is, the constraint
 
322
 * that most wants to split
 
323
 */
 
324
Constraint *Block::findMinLM() {
 
325
        Constraint *min_lm=NULL;
 
326
        reset_active_lm(vars->front(),NULL);
 
327
        compute_dfdv(vars->front(),NULL,min_lm);
 
328
        return min_lm;
 
329
}
 
330
Constraint *Block::findMinLMBetween(Variable* const lv, Variable* const rv) {
 
331
        Constraint *min_lm=NULL;
 
332
        reset_active_lm(vars->front(),NULL);
 
333
        min_lm=compute_dfdv_between(rv,lv,NULL).second;
 
334
        return min_lm;
 
335
}
 
336
 
 
337
// populates block b by traversing the active constraint tree adding variables as they're 
 
338
// visited.  Starts from variable v and does not backtrack over variable u.
 
339
void Block::populateSplitBlock(Block *b, Variable* const v, Variable* const u) {
 
340
        b->addVariable(v);
 
341
        for (Cit c=v->in.begin();c!=v->in.end();++c) {
 
342
                if (canFollowLeft(*c,u))
 
343
                        populateSplitBlock(b, (*c)->left, v);
 
344
        }
 
345
        for (Cit c=v->out.begin();c!=v->out.end();++c) {
 
346
                if (canFollowRight(*c,u)) 
 
347
                        populateSplitBlock(b, (*c)->right, v);
 
348
        }
 
349
}
 
350
// Search active constraint tree from u to see if there is a directed path to v.
 
351
// Returns true if path is found with all constraints in path having their visited flag
 
352
// set true.
 
353
bool Block::isActiveDirectedPathBetween(Variable* u, Variable *v) {
 
354
        if(u==v) return true;
 
355
        for (Cit c=u->out.begin();c!=u->out.end();++c) {
 
356
                if(canFollowRight(*c,NULL)) {
 
357
                        if(isActiveDirectedPathBetween((*c)->right,v)) {
 
358
                                (*c)->visited=true;
 
359
                                return true;
 
360
                        }
 
361
                        (*c)->visited=false;
 
362
                }
 
363
        }
 
364
        return false;
 
365
}
 
366
/**
 
367
 * Block needs to be split because of a violated constraint between vl and vr.
 
368
 * We need to search the active constraint tree between l and r and find the constraint
 
369
 * with min lagrangrian multiplier and split at that point.
 
370
 * Returns the split constraint
 
371
 */
 
372
Constraint* Block::splitBetween(Variable* const vl, Variable* const vr,
 
373
                Block* &lb, Block* &rb) {
 
374
#ifdef RECTANGLE_OVERLAP_LOGGING
 
375
        ofstream f(LOGFILE,ios::app);
 
376
        f<<"  need to split between: "<<*vl<<" and "<<*vr<<endl;
 
377
#endif
 
378
        Constraint *c=findMinLMBetween(vl, vr);
 
379
#ifdef RECTANGLE_OVERLAP_LOGGING
 
380
        f<<"  going to split on: "<<*c<<endl;
 
381
#endif
 
382
        split(lb,rb,c);
 
383
        deleted = true;
 
384
        return c;
 
385
}
 
386
/**
 
387
 * Creates two new blocks, l and r, and splits this block across constraint c,
 
388
 * placing the left subtree of constraints (and associated variables) into l
 
389
 * and the right into r.
 
390
 */
 
391
void Block::split(Block* &l, Block* &r, Constraint* c) {
 
392
        c->active=false;
 
393
        l=new Block();
 
394
        populateSplitBlock(l,c->left,c->right);
 
395
        r=new Block();
 
396
        populateSplitBlock(r,c->right,c->left);
 
397
}
 
398
 
 
399
/**
 
400
 * Computes the cost (squared euclidean distance from desired positions) of the
 
401
 * current positions for variables in this block
 
402
 */
 
403
double Block::cost() {
 
404
        double c = 0;
 
405
        for (Vit v=vars->begin();v!=vars->end();++v) {
 
406
                double diff = (*v)->position() - (*v)->desiredPosition;
 
407
                c += (*v)->weight * diff * diff;
 
408
        }
 
409
        return c;
 
410
}
 
411
ostream& operator <<(ostream &os, const Block& b)
 
412
{
 
413
        os<<"Block:";
 
414
        for(Block::Vit v=b.vars->begin();v!=b.vars->end();++v) {
 
415
                os<<" "<<**v;
 
416
        }
 
417
        if(b.deleted) {
 
418
                os<<" Deleted!";
 
419
        }
 
420
    return os;
 
421
}
 
422
}