1 /**
2 * \brief A block structure defined over the variables
3 *
4 * A block structure defined over the variables such that each block contains
5 * 1 or more variables, with the invariant that all constraints inside a block
6 * are satisfied by keeping the variables fixed relative to one another
7 *
8 * Authors:
9 * Tim Dwyer <tgdwyer@gmail.com>
10 *
11 * Copyright (C) 2005 Authors
12 *
13 * Released under GNU GPL. Read the file 'COPYING' for more information.
14 */
16 #include "blocks.h"
17 #include "block.h"
18 #include "constraint.h"
19 #ifdef RECTANGLE_OVERLAP_LOGGING
20 #include <fstream>
21 using std::ios;
22 using std::ofstream;
23 using std::endl;
24 #endif
25 using std::set;
26 using std::vector;
27 using std::iterator;
28 using std::list;
29 using std::copy;
31 long blockTimeCtr;
33 Blocks::Blocks(Variable *vs[], const int n) : vs(vs),nvs(n) {
34 blockTimeCtr=0;
35 for(int i=0;i<nvs;i++) {
36 insert(new Block(vs[i]));
37 }
38 }
39 Blocks::~Blocks(void)
40 {
41 blockTimeCtr=0;
42 for(set<Block*>::iterator i=begin();i!=end();i++) {
43 delete *i;
44 }
45 clear();
46 }
48 /**
49 * returns a list of variables with total ordering determined by the constraint
50 * DAG
51 */
52 list<Variable*> *Blocks::totalOrder() {
53 list<Variable*> *order = new list<Variable*>;
54 for(int i=0;i<nvs;i++) {
55 vs[i]->visited=false;
56 }
57 for(int i=0;i<nvs;i++) {
58 if(vs[i]->in.size()==0) {
59 dfsVisit(vs[i],order);
60 }
61 }
62 return order;
63 }
64 // Recursive depth first search giving total order by pushing nodes in the DAG
65 // onto the front of the list when we finish searching them
66 void Blocks::dfsVisit(Variable *v, list<Variable*> *order) {
67 v->visited=true;
68 vector<Constraint*>::iterator it=v->out.begin();
69 for(;it!=v->out.end();it++) {
70 Constraint *c=*it;
71 if(!c->right->visited) {
72 dfsVisit(c->right, order);
73 }
74 }
75 #ifdef RECTANGLE_OVERLAP_LOGGING
76 ofstream f(LOGFILE,ios::app);
77 f<<" order="<<*v<<endl;
78 #endif
79 order->push_front(v);
80 }
81 /**
82 * Processes incoming constraints, most violated to least, merging with the
83 * neighbouring (left) block until no more violated constraints are found
84 */
85 void Blocks::mergeLeft(Block *r) {
86 #ifdef RECTANGLE_OVERLAP_LOGGING
87 ofstream f(LOGFILE,ios::app);
88 f<<"mergeLeft called on "<<*r<<endl;
89 #endif
90 r->timeStamp=++blockTimeCtr;
91 r->setUpInConstraints();
92 Constraint *c=r->findMinInConstraint();
93 while (c != NULL && c->slack()<0) {
94 #ifdef RECTANGLE_OVERLAP_LOGGING
95 f<<"mergeLeft on constraint: "<<*c<<endl;
96 #endif
97 r->deleteMinInConstraint();
98 Block *l = c->left->block;
99 if (l->in==NULL) l->setUpInConstraints();
100 double dist = c->right->offset - c->left->offset - c->gap;
101 if (r->vars->size() < l->vars->size()) {
102 dist=-dist;
103 std::swap(l, r);
104 }
105 blockTimeCtr++;
106 r->merge(l, c, dist);
107 r->mergeIn(l);
108 r->timeStamp=blockTimeCtr;
109 removeBlock(l);
110 c=r->findMinInConstraint();
111 }
112 #ifdef RECTANGLE_OVERLAP_LOGGING
113 f<<"merged "<<*r<<endl;
114 #endif
115 }
116 /**
117 * Symmetrical to mergeLeft
118 */
119 void Blocks::mergeRight(Block *l) {
120 #ifdef RECTANGLE_OVERLAP_LOGGING
121 ofstream f(LOGFILE,ios::app);
122 f<<"mergeRight called on "<<*l<<endl;
123 #endif
124 l->setUpOutConstraints();
125 Constraint *c = l->findMinOutConstraint();
126 while (c != NULL && c->slack()<0) {
127 #ifdef RECTANGLE_OVERLAP_LOGGING
128 f<<"mergeRight on constraint: "<<*c<<endl;
129 #endif
130 l->deleteMinOutConstraint();
131 Block *r = c->right->block;
132 r->setUpOutConstraints();
133 double dist = c->left->offset + c->gap - c->right->offset;
134 if (l->vars->size() > r->vars->size()) {
135 dist=-dist;
136 std::swap(l, r);
137 }
138 l->merge(r, c, dist);
139 l->mergeOut(r);
140 removeBlock(r);
141 c=l->findMinOutConstraint();
142 }
143 #ifdef RECTANGLE_OVERLAP_LOGGING
144 f<<"merged "<<*l<<endl;
145 #endif
146 }
147 void Blocks::removeBlock(Block *doomed) {
148 doomed->deleted=true;
149 //erase(doomed);
150 }
151 void Blocks::cleanup() {
152 vector<Block*> bcopy(size());
153 copy(begin(),end(),bcopy.begin());
154 for(vector<Block*>::iterator i=bcopy.begin();i!=bcopy.end();i++) {
155 Block *b=*i;
156 if(b->deleted) {
157 erase(b);
158 delete b;
159 }
160 }
161 }
162 /**
163 * Splits block b across constraint c into two new blocks, l and r (c's left
164 * and right sides respectively)
165 */
166 void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) {
167 b->split(l,r,c);
168 #ifdef RECTANGLE_OVERLAP_LOGGING
169 ofstream f(LOGFILE,ios::app);
170 f<<"Split left: "<<*l<<endl;
171 f<<"Split right: "<<*r<<endl;
172 #endif
173 r->posn = b->posn;
174 r->wposn = r->posn * r->weight;
175 mergeLeft(l);
176 // r may have been merged!
177 r = c->right->block;
178 r->wposn = r->desiredWeightedPosition();
179 r->posn = r->wposn / r->weight;
180 mergeRight(r);
181 removeBlock(b);
183 insert(l);
184 insert(r);
185 }
186 /**
187 * returns the cost total squared distance of variables from their desired
188 * positions
189 */
190 double Blocks::cost() {
191 double c = 0;
192 for(set<Block*>::iterator i=begin();i!=end();i++) {
193 c += (*i)->cost();
194 }
195 return c;
196 }