11 class Layout::LinearProgram
17 LinearProgram &linprog;
21 Row(LinearProgram &, unsigned);
23 float &operator[](unsigned);
31 std::vector<float> values;
38 std::vector<Column> columns;
43 LinearProgram(unsigned);
46 Row operator[](unsigned);
47 Row get_objective_row();
49 float get_variable(unsigned);
51 unsigned find_minimal_ratio(unsigned);
52 void make_basic_column(unsigned, unsigned);
57 struct Layout::Pointers
60 unsigned Geometry::*dim;
61 Packing Slot::*packing;
62 unsigned Sides::*low_margin;
63 unsigned Sides::*high_margin;
64 unsigned Layout::*spacing;
67 Layout::Pointers Layout::pointers[2] =
69 &Geometry::x, &Geometry::w,
71 &Sides::left, &Sides::right,
74 &Geometry::y, &Geometry::h,
76 &Sides::bottom, &Sides::top,
90 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
94 void Layout::set_container(Container &c)
97 throw logic_error("container!=0");
102 void Layout::set_margin(const Sides &m)
109 void Layout::add_widget(Widget &wdg)
112 throw logic_error("!container");
114 Slot *slot = create_slot(wdg);
115 for(list<Constraint>::iterator i=slot->constraints.begin(); i!=slot->constraints.end(); ++i)
116 i->target.constraints.push_back(Constraint(complement(i->type), *slot));
117 slot->index = slots.size();
118 slots.push_back(slot);
123 void Layout::remove_widget(Widget &wdg)
125 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
126 if(&(*i)->widget==&wdg)
128 for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
131 for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
134 (*j)->constraints.erase(k++);
144 for(i=slots.begin(); i!=slots.end(); ++i, ++n)
152 Layout::Slot *Layout::create_slot(Widget &wdg)
154 return new Slot(*this, wdg);
157 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
159 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
160 if(&(*i)->widget==&wdg)
163 throw hierarchy_error("widget not in layout");
166 Layout::ConstraintType Layout::complement(ConstraintType type)
170 else if(type==LEFT_OF)
180 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
183 throw invalid_argument("&src==&tgt");
185 Slot &src_slot = get_slot_for_widget(src);
186 Slot &tgt_slot = get_slot_for_widget(tgt);
188 for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
189 if(i->type==type && &i->target==&tgt_slot)
192 src_slot.constraints.push_back(Constraint(type, tgt_slot));
193 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
198 void Layout::set_gravity(Widget &wdg, int h, int v)
200 Slot &slot = get_slot_for_widget(wdg);
202 slot.horiz_pack.gravity = h;
203 slot.vert_pack.gravity = v;
208 void Layout::set_expand(Widget &wdg, bool h, bool v)
210 Slot &slot = get_slot_for_widget(wdg);
212 slot.horiz_pack.expand = h;
213 slot.vert_pack.expand = v;
218 void Layout::update()
220 solve_constraints(HORIZONTAL);
221 solve_constraints(VERTICAL);
223 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
224 (*i)->widget.set_geometry((*i)->geom);
227 void Layout::solve_constraints(int dir)
229 Pointers &ptrs = pointers[dir&VERTICAL];
231 /* Set up a linear program to solve the constraints. The program matrix has
232 five columns for each widget, and one constant column. The first and second
233 columns of a widget are its position and dimension, respectively. The
234 remaining three are slack columns; see below for their purposes. */
235 LinearProgram linprog(slots.size()*5+1);
236 float weight = slots.size();
237 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
239 linprog.get_objective_row()[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
240 linprog.get_objective_row()[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
243 // Prevent the widget from going past the container's low edge.
244 LinearProgram::Row row = linprog.add_row();
245 row[(*i)->index*5] = 1;
246 row[(*i)->index*5+2] = -1;
247 row.back() = margin.*(ptrs.low_margin);
251 // Prevent the widget from going past the container's high edge.
252 LinearProgram::Row row = linprog.add_row();
253 row[(*i)->index*5] = 1;
254 row[(*i)->index*5+1] = 1;
255 row[(*i)->index*5+3] = 1;
256 row.back() = container->get_geometry().*(ptrs.dim)-margin.*(ptrs.high_margin);
260 /* Only allow the widget's dimension to increase. The geometry has
261 previously been set to the smallest allowable size. */
262 LinearProgram::Row row = linprog.add_row();
263 row[(*i)->index*5+1] = 1;
264 row[(*i)->index*5+4] = -1;
265 row.back() = (*i)->autosize_geom.*(ptrs.dim);
268 /* Add rows for user-defined constraints. Below/above and left/right of
269 constraints are always added in pairs, so it's only necessary to create a
271 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
272 if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
274 LinearProgram::Row row = linprog.add_row();
276 row[(*i)->index*5] = 1;
278 row[(*i)->index*5+1] = 1;
279 if(j->type&TARGET_POS)
280 row[j->target.index*5] = -1;
281 if(j->type&TARGET_DIM)
282 row[j->target.index*5+1] = -1;
284 row.back() = this->*(ptrs.spacing);
291 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
293 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
294 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
299 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
305 Layout::Packing::Packing():
311 Layout::Slot::Slot(Layout &l, Widget &w):
316 vert_pack.gravity = 1;
317 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
319 autosize_geom = widget.get_geometry();
322 void Layout::Slot::autosize_changed()
325 autosize_geom = widget.get_geometry();
327 // If the widget fits in the area it had, just leave it there.
328 if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
329 widget.set_geometry(geom);
335 Layout::LinearProgram::LinearProgram(unsigned s):
343 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
345 return Row(*this, n_rows++);
348 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
351 throw out_of_range("LinearProgram::operator[]");
353 return Row(*this, r);
356 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
358 return Row(*this, 0);
361 float Layout::LinearProgram::get_variable(unsigned i)
363 if(!solved || infeasible)
364 throw logic_error("not solved");
366 throw out_of_range("LinearProgram::get_variable");
368 if(unsigned r = columns[i].basic)
369 return columns.back().values[r];
374 bool Layout::LinearProgram::solve()
376 if(solved || infeasible)
379 /* Solve the program using the simplex method. The column representing the
380 objective variable is kept implicit, as it would never change during the
381 execution of the algorithm. */
383 /* Force all columns fully into existence and relocate objective row to
384 bottom in preparation of phase 1. A new objective row is calculated by
385 pricing out the constraint rows. */
386 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
388 float objective = 0.0f;
389 if(!i->values.empty())
391 objective = i->values.front();
392 i->values.front() = 0.0f;
393 for(vector<float>::iterator j=i->values.begin(); j!=i->values.end(); ++j)
394 i->values.front() += *j;
396 i->values.resize(n_rows+1, 0.0f);
397 i->values.back() = objective;
400 /* Create artificial variables for phase 1. This ensures that each row has
401 a basic variable associated with it. The original objective row already
402 contains the implicit objective variable, which is basic. */
403 columns.resize(n_columns+n_rows-1);
404 columns.back() = columns[n_columns-1];
405 columns[n_columns-1].values.clear();
406 for(unsigned i=1; i<n_rows; ++i)
408 Column &column = columns[n_columns+i-2];
412 // Solve the phase 1 problem.
415 /* All artificial variables should now be non-basic and thus zero, so the
416 objective function's value should also be zero. If it isn't, the original
417 program can't be solved. */
418 if(columns.back().values.front())
424 /* Get rid of the artificial variables and restore the original objective
425 row to form the phase 2 problem. */
426 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
427 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
430 i->values.front() = i->values.back();
431 i->values.pop_back();
434 // Solve the phase 2 problem. We already know it to be feasible.
442 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
444 /* Pick the row with the minimum ratio between the constant column and the
445 pivot column. This ensures that when the pivot column is made basic, values
446 in the constant column stay positive.
448 The use of n_rows instead of the true size of the column is intentional,
449 since the relocated objective row must be ignored in phase 1. */
450 float best = numeric_limits<float>::infinity();
452 for(unsigned i=1; i<n_rows; ++i)
453 if(columns[c].values[i]>0)
455 float ratio = columns.back().values[i]/columns[c].values[i];
466 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
468 /* Perform row transfer operations to make the pivot column basic,
469 containing a 1 on the pivot row. */
470 for(unsigned i=0; i<columns.size(); ++i)
471 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
475 columns[i].values.resize(columns.back().values.size(), 0.0f);
476 columns[i].values[columns[i].basic] = 1.0f;
477 columns[i].basic = 0;
480 float scale = columns[i].values[r]/columns[c].values[r];
482 columns[i].values[r] = scale;
483 for(unsigned j=0; j<columns[i].values.size(); ++j)
485 columns[i].values[j] -= scale*columns[c].values[j];
488 columns[c].basic = r;
489 columns[c].values.clear();
492 bool Layout::LinearProgram::pivot()
494 /* Pick a nonbasic column and make it basic. Requiring a positive objective
495 coefficient ensures that the objective function's value will decrease in the
497 for(unsigned i=0; i+1<columns.size(); ++i)
498 if(!columns[i].basic && columns[i].values.front()>0)
499 if(unsigned row = find_minimal_ratio(i))
501 make_basic_column(i, row);
509 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
514 float &Layout::LinearProgram::Row::operator[](unsigned c)
516 if(c>=linprog.n_columns)
517 throw out_of_range("Row::operator[]");
519 Column &column = linprog.columns[c];
520 if(column.values.size()<=index)
521 column.values.resize(index+1);
523 return column.values[index];
526 float &Layout::LinearProgram::Row::back()
528 return (*this)[linprog.n_columns-1];
532 Layout::LinearProgram::Column::Column():