1 /**
2 * \brief Remove overlaps function
3 *
4 * Authors:
5 * Tim Dwyer <tgdwyer@gmail.com>
6 *
7 * Copyright (C) 2005 Authors
8 *
9 * Released under GNU GPL. Read the file 'COPYING' for more information.
10 */
11 #include <cassert>
12 #include "constraint.h"
13 #include "block.h"
14 #include "blocks.h"
15 #include "pairingheap/PairingHeap.h"
16 #ifdef RECTANGLE_OVERLAP_LOGGING
17 #include <fstream>
18 using std::ios;
19 using std::ofstream;
20 using std::endl;
21 #endif
22 using std::vector;
24 void Block::addVariable(Variable *v) {
25 v->block=this;
26 vars->push_back(v);
27 weight+=v->weight;
28 wposn += v->weight * (v->desiredPosition - v->offset);
29 posn=wposn/weight;
30 }
31 Block::Block(Variable *v) {
32 timeStamp=0;
33 posn=weight=wposn=0;
34 in=NULL;
35 out=NULL;
36 deleted=false;
37 vars=new vector<Variable*>;
38 if(v!=NULL) {
39 v->offset=0;
40 addVariable(v);
41 }
42 }
44 double Block::desiredWeightedPosition() {
45 double wp = 0;
46 for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();v++) {
47 wp += ((*v)->desiredPosition - (*v)->offset) * (*v)->weight;
48 }
49 return wp;
50 }
51 Block::~Block(void)
52 {
53 delete vars;
54 delete in;
55 delete out;
56 }
57 void Block::setUpInConstraints() {
58 setUpConstraintHeap(in,true);
59 }
60 void Block::setUpOutConstraints() {
61 setUpConstraintHeap(out,false);
62 }
63 void Block::setUpConstraintHeap(PairingHeap<Constraint*>* &h,bool in) {
64 delete h;
65 h = new PairingHeap<Constraint*>(&compareConstraints);
66 for (vector<Variable*>::iterator i=vars->begin();i!=vars->end();i++) {
67 Variable *v=*i;
68 vector<Constraint*> *cs=in?&(v->in):&(v->out);
69 for (vector<Constraint*>::iterator j=cs->begin();j!=cs->end();j++) {
70 Constraint *c=*j;
71 c->timeStamp=blockTimeCtr;
72 if (c->left->block != this && in || c->right->block != this && !in) {
73 h->insert(c);
74 }
75 }
76 }
77 }
78 /**
79 * Merges b into this block across c. Can be either a
80 * right merge or a left merge
81 * @param b block to merge into this
82 * @param c constraint being merged
83 * @param distance separation required to satisfy c
84 */
85 void Block::merge(Block *b, Constraint *c, double dist) {
86 c->active=true;
87 wposn+=b->wposn-dist*b->weight;
88 weight+=b->weight;
89 posn=wposn/weight;
90 for(vector<Variable*>::iterator i=b->vars->begin();i!=b->vars->end();i++) {
91 Variable *v=*i;
92 v->block=this;
93 v->offset+=dist;
94 vars->push_back(v);
95 }
96 }
98 void Block::mergeIn(Block *b) {
99 #ifdef RECTANGLE_OVERLAP_LOGGING
100 ofstream f(LOGFILE,ios::app);
101 f<<" merging constraint heaps... "<<endl;
102 #endif
103 // We check the top of the heaps to remove possible internal constraints
104 findMinInConstraint();
105 b->findMinInConstraint();
106 in->merge(b->in);
107 #ifdef RECTANGLE_OVERLAP_LOGGING
108 f<<" merged heap: "<<*in<<endl;
109 #endif
110 }
111 void Block::mergeOut(Block *b) {
112 findMinOutConstraint();
113 b->findMinOutConstraint();
114 out->merge(b->out);
115 }
116 Constraint *Block::findMinInConstraint() {
117 Constraint *v = NULL;
118 vector<Constraint*> outOfDate;
119 while (!in->isEmpty()) {
120 v = in->findMin();
121 Block *lb=v->left->block;
122 Block *rb=v->right->block;
123 // rb may not be this if called between merge and mergeIn
124 #ifdef RECTANGLE_OVERLAP_LOGGING
125 ofstream f(LOGFILE,ios::app);
126 f<<" checking constraint ... "<<*v;
127 f<<" timestamps: left="<<lb->timeStamp<<" right="<<rb->timeStamp<<" constraint="<<v->timeStamp<<endl;
128 #endif
129 if(lb == rb) {
130 // constraint has been merged into the same block
131 #ifdef RECTANGLE_OVERLAP_LOGGING
132 if(v->slack()<0) {
133 f<<" violated internal constraint found! "<<*v<<endl;
134 f<<" lb="<<*lb<<endl;
135 f<<" rb="<<*rb<<endl;
136 }
137 #endif
138 in->deleteMin();
139 #ifdef RECTANGLE_OVERLAP_LOGGING
140 f<<" ... skipping internal constraint"<<endl;
141 #endif
142 } else if(v->timeStamp < lb->timeStamp) {
143 // block at other end of constraint has been moved since this
144 in->deleteMin();
145 outOfDate.push_back(v);
146 #ifdef RECTANGLE_OVERLAP_LOGGING
147 f<<" reinserting out of date (reinsert later)"<<endl;
148 #endif
149 } else {
150 break;
151 }
152 }
153 for(vector<Constraint*>::iterator i=outOfDate.begin();i!=outOfDate.end();i++) {
154 v=*i;
155 v->timeStamp=blockTimeCtr;
156 in->insert(v);
157 }
158 if(in->isEmpty()) {
159 v=NULL;
160 } else {
161 v=in->findMin();
162 }
163 return v;
164 }
165 Constraint *Block::findMinOutConstraint() {
166 if(out->isEmpty()) return NULL;
167 Constraint *v = out->findMin();
168 while (v->left->block == v->right->block) {
169 out->deleteMin();
170 if(out->isEmpty()) return NULL;
171 v = out->findMin();
172 }
173 return v;
174 }
175 void Block::deleteMinInConstraint() {
176 in->deleteMin();
177 #ifdef RECTANGLE_OVERLAP_LOGGING
178 ofstream f(LOGFILE,ios::app);
179 f<<"deleteMinInConstraint... "<<endl;
180 f<<" result: "<<*in<<endl;
181 #endif
182 }
183 void Block::deleteMinOutConstraint() {
184 out->deleteMin();
185 }
186 inline bool Block::canFollowLeft(Constraint *c, Variable *last) {
187 return c->left->block==this && c->active && last!=c->left;
188 }
189 inline bool Block::canFollowRight(Constraint *c, Variable *last) {
190 return c->right->block==this && c->active && last!=c->right;
191 }
193 // computes the derivative of v and the lagrange multipliers
194 // of v's out constraints (as the recursive sum of those below.
195 // Does not backtrack over u.
196 // also records the constraint with minimum lagrange multiplier
197 // in min_lm
198 double Block::compute_dfdv(Variable *v, Variable *u, Constraint *&min_lm) {
199 double dfdv=v->weight*(v->position() - v->desiredPosition);
200 for(vector<Constraint*>::iterator it=v->out.begin();it!=v->out.end();it++) {
201 Constraint *c=*it;
202 if(canFollowRight(c,u)) {
203 dfdv+=c->lm=compute_dfdv(c->right,v,min_lm);
204 if(min_lm==NULL||c->lm<min_lm->lm) min_lm=c;
205 }
206 }
207 for(vector<Constraint*>::iterator it=v->in.begin();it!=v->in.end();it++) {
208 Constraint *c=*it;
209 if(canFollowLeft(c,u)) {
210 dfdv-=c->lm=-compute_dfdv(c->left,v,min_lm);
211 if(min_lm==NULL||c->lm<min_lm->lm) min_lm=c;
212 }
213 }
214 return dfdv;
215 }
217 // resets LMs for all active constraints to 0 by
218 // traversing active constraint tree starting from v,
219 // not back tracking over u
220 void Block::reset_active_lm(Variable *v, Variable *u) {
221 for(vector<Constraint*>::iterator it=v->out.begin();it!=v->out.end();it++) {
222 Constraint *c=*it;
223 if(canFollowRight(c,u)) {
224 c->lm=0;
225 reset_active_lm(c->right,v);
226 }
227 }
228 for(vector<Constraint*>::iterator it=v->in.begin();it!=v->in.end();it++) {
229 Constraint *c=*it;
230 if(canFollowLeft(c,u)) {
231 c->lm=0;
232 reset_active_lm(c->left,v);
233 }
234 }
235 }
236 /**
237 * finds the constraint with the minimum lagrange multiplier, that is, the constraint
238 * that most wants to split
239 */
240 Constraint *Block::findMinLM() {
241 Constraint *min_lm=NULL;
242 reset_active_lm(vars->front(),NULL);
243 compute_dfdv(vars->front(),NULL,min_lm);
244 return min_lm;
245 }
247 // populates block b by traversing the active constraint tree adding variables as they're
248 // visited. Starts from variable v and does not backtrack over variable u.
249 void Block::populateSplitBlock(Block *b, Variable *v, Variable *u) {
250 b->addVariable(v);
251 for (vector<Constraint*>::iterator c=v->in.begin();c!=v->in.end();c++) {
252 if (canFollowLeft(*c,u))
253 populateSplitBlock(b, (*c)->left, v);
254 }
255 for (vector<Constraint*>::iterator c=v->out.begin();c!=v->out.end();c++) {
256 if (canFollowRight(*c,u))
257 populateSplitBlock(b, (*c)->right, v);
258 }
259 }
260 /**
261 * Creates two new blocks, l and r, and splits this block across constraint c,
262 * placing the left subtree of constraints (and associated variables) into l
263 * and the right into r
264 */
265 void Block::split(Block *&l, Block *&r, Constraint *c) {
266 c->active=false;
267 l=new Block();
268 populateSplitBlock(l,c->left,c->right);
269 r=new Block();
270 populateSplitBlock(r,c->right,c->left);
271 }
273 /**
274 * Computes the cost (squared euclidean distance from desired positions) of the
275 * current positions for variables in this block
276 */
277 double Block::cost() {
278 double c = 0;
279 for (vector<Variable*>::iterator v=vars->begin();v!=vars->end();v++) {
280 double diff = (*v)->position() - (*v)->desiredPosition;
281 c += (*v)->weight * diff * diff;
282 }
283 return c;
284 }
285 ostream& operator <<(ostream &os, const Block &b)
286 {
287 os<<"Block:";
288 for(vector<Variable*>::iterator v=b.vars->begin();v!=b.vars->end();v++) {
289 os<<" "<<**v;
290 }
291 return os;
292 }