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 LGPL. 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 namespace vpsc {
33 long blockTimeCtr;
35 Blocks::Blocks(const int n, Variable* const vs[]) : vs(vs),nvs(n) {
36 blockTimeCtr=0;
37 for(int i=0;i<nvs;i++) {
38 insert(new Block(vs[i]));
39 }
40 }
41 Blocks::~Blocks(void)
42 {
43 blockTimeCtr=0;
44 for(set<Block*>::iterator i=begin();i!=end();++i) {
45 delete *i;
46 }
47 clear();
48 }
50 /**
51 * returns a list of variables with total ordering determined by the constraint
52 * DAG
53 */
54 list<Variable*> *Blocks::totalOrder() {
55 list<Variable*> *order = new list<Variable*>;
56 for(int i=0;i<nvs;i++) {
57 vs[i]->visited=false;
58 }
59 for(int i=0;i<nvs;i++) {
60 if(vs[i]->in.size()==0) {
61 dfsVisit(vs[i],order);
62 }
63 }
64 return order;
65 }
66 // Recursive depth first search giving total order by pushing nodes in the DAG
67 // onto the front of the list when we finish searching them
68 void Blocks::dfsVisit(Variable *v, list<Variable*> *order) {
69 v->visited=true;
70 vector<Constraint*>::iterator it=v->out.begin();
71 for(;it!=v->out.end();++it) {
72 Constraint *c=*it;
73 if(!c->right->visited) {
74 dfsVisit(c->right, order);
75 }
76 }
77 #ifdef RECTANGLE_OVERLAP_LOGGING
78 ofstream f(LOGFILE,ios::app);
79 f<<" order="<<*v<<endl;
80 #endif
81 order->push_front(v);
82 }
83 /**
84 * Processes incoming constraints, most violated to least, merging with the
85 * neighbouring (left) block until no more violated constraints are found
86 */
87 void Blocks::mergeLeft(Block *r) {
88 #ifdef RECTANGLE_OVERLAP_LOGGING
89 ofstream f(LOGFILE,ios::app);
90 f<<"mergeLeft called on "<<*r<<endl;
91 #endif
92 r->timeStamp=++blockTimeCtr;
93 r->setUpInConstraints();
94 Constraint *c=r->findMinInConstraint();
95 while (c != NULL && c->slack()<0) {
96 #ifdef RECTANGLE_OVERLAP_LOGGING
97 f<<"mergeLeft on constraint: "<<*c<<endl;
98 #endif
99 r->deleteMinInConstraint();
100 Block *l = c->left->block;
101 if (l->in==NULL) l->setUpInConstraints();
102 double dist = c->right->offset - c->left->offset - c->gap;
103 if (r->vars->size() < l->vars->size()) {
104 dist=-dist;
105 std::swap(l, r);
106 }
107 blockTimeCtr++;
108 r->merge(l, c, dist);
109 r->mergeIn(l);
110 r->timeStamp=blockTimeCtr;
111 removeBlock(l);
112 c=r->findMinInConstraint();
113 }
114 #ifdef RECTANGLE_OVERLAP_LOGGING
115 f<<"merged "<<*r<<endl;
116 #endif
117 }
118 /**
119 * Symmetrical to mergeLeft
120 */
121 void Blocks::mergeRight(Block *l) {
122 #ifdef RECTANGLE_OVERLAP_LOGGING
123 ofstream f(LOGFILE,ios::app);
124 f<<"mergeRight called on "<<*l<<endl;
125 #endif
126 l->setUpOutConstraints();
127 Constraint *c = l->findMinOutConstraint();
128 while (c != NULL && c->slack()<0) {
129 #ifdef RECTANGLE_OVERLAP_LOGGING
130 f<<"mergeRight on constraint: "<<*c<<endl;
131 #endif
132 l->deleteMinOutConstraint();
133 Block *r = c->right->block;
134 r->setUpOutConstraints();
135 double dist = c->left->offset + c->gap - c->right->offset;
136 if (l->vars->size() > r->vars->size()) {
137 dist=-dist;
138 std::swap(l, r);
139 }
140 l->merge(r, c, dist);
141 l->mergeOut(r);
142 removeBlock(r);
143 c=l->findMinOutConstraint();
144 }
145 #ifdef RECTANGLE_OVERLAP_LOGGING
146 f<<"merged "<<*l<<endl;
147 #endif
148 }
149 void Blocks::removeBlock(Block *doomed) {
150 doomed->deleted=true;
151 //erase(doomed);
152 }
153 void Blocks::cleanup() {
154 vector<Block*> bcopy(begin(),end());
155 for(vector<Block*>::iterator i=bcopy.begin();i!=bcopy.end();++i) {
156 Block *b=*i;
157 if(b->deleted) {
158 erase(b);
159 delete b;
160 }
161 }
162 }
163 /**
164 * Splits block b across constraint c into two new blocks, l and r (c's left
165 * and right sides respectively)
166 */
167 void Blocks::split(Block *b, Block *&l, Block *&r, Constraint *c) {
168 b->split(l,r,c);
169 #ifdef RECTANGLE_OVERLAP_LOGGING
170 ofstream f(LOGFILE,ios::app);
171 f<<"Split left: "<<*l<<endl;
172 f<<"Split right: "<<*r<<endl;
173 #endif
174 r->posn = b->posn;
175 r->wposn = r->posn * r->weight;
176 mergeLeft(l);
177 // r may have been merged!
178 r = c->right->block;
179 r->wposn = r->desiredWeightedPosition();
180 r->posn = r->wposn / r->weight;
181 mergeRight(r);
182 removeBlock(b);
184 insert(l);
185 insert(r);
186 }
187 /**
188 * returns the cost total squared distance of variables from their desired
189 * positions
190 */
191 double Blocks::cost() {
192 double c = 0;
193 for(set<Block*>::iterator i=begin();i!=end();++i) {
194 c += (*i)->cost();
195 }
196 return c;
197 }
199 }