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 unsigned r = columns[i].basic;
369 return columns.back().values[r];
372 bool Layout::LinearProgram::solve()
374 if(solved || infeasible)
377 /* Solve the program using the simplex method. The column representing the
378 objective variable is kept implicit, as it would never change during the
379 execution of the algorithm. */
381 /* Force all columns fully into existence and relocate objective row to
382 bottom in preparation of phase 1. A new objective row is calculated by
383 pricing out the constraint rows. */
384 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
386 float objective = i->values.front();
387 i->values.front() = 0.0f;
388 for(vector<float>::iterator j=i->values.begin(); j!=i->values.end(); ++j)
389 i->values.front() += *j;
390 i->values.resize(n_rows+1, 0.0f);
391 i->values.back() = objective;
394 /* Create artificial variables for phase 1. This ensures that each row has
395 a basic variable associated with it. The original objective row already
396 contains the implicit objective variable, which is basic. */
397 columns.resize(n_columns+n_rows-1);
398 columns.back() = columns[n_columns-1];
399 columns[n_columns-1].values.clear();
400 for(unsigned i=1; i<n_rows; ++i)
402 Column &column = columns[n_columns+i-2];
406 // Solve the phase 1 problem.
409 /* All artificial variables should now be non-basic and thus zero, so the
410 objective function's value should also be zero. If it isn't, the original
411 program can't be solved. */
412 if(columns.back().values.front())
418 /* Get rid of the artificial variables and restore the original objective
419 row to form the phase 2 problem. */
420 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
421 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
424 i->values.front() = i->values.back();
425 i->values.pop_back();
428 // Solve the phase 2 problem. We already know it to be feasible.
436 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
438 /* Pick the row with the minimum ratio between the constant column and the
439 pivot column. This ensures that when the pivot column is made basic, values
440 in the constant column stay positive.
442 The use of n_rows instead of the true size of the column is intentional,
443 since the relocated objective row must be ignored in phase 1. */
444 float best = numeric_limits<float>::infinity();
446 for(unsigned i=1; i<n_rows; ++i)
447 if(columns[c].values[i]>0)
449 float ratio = columns.back().values[i]/columns[c].values[i];
460 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
462 /* Perform row transfer operations to make the pivot column basic,
463 containing a 1 on the pivot row. */
464 for(unsigned i=0; i<columns.size(); ++i)
465 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
469 columns[i].values.resize(columns.back().values.size(), 0.0f);
470 columns[i].values[columns[i].basic] = 1.0f;
471 columns[i].basic = 0;
474 float scale = columns[i].values[r]/columns[c].values[r];
476 columns[i].values[r] = scale;
477 for(unsigned j=0; j<columns[i].values.size(); ++j)
479 columns[i].values[j] -= scale*columns[c].values[j];
482 columns[c].basic = r;
483 columns[c].values.clear();
486 bool Layout::LinearProgram::pivot()
488 /* Pick a nonbasic column and make it basic. Requiring a positive objective
489 coefficient ensures that the objective function's value will decrease in the
491 for(unsigned i=0; i+1<columns.size(); ++i)
492 if(!columns[i].basic && columns[i].values.front()>0)
493 if(unsigned row = find_minimal_ratio(i))
495 make_basic_column(i, row);
503 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
508 float &Layout::LinearProgram::Row::operator[](unsigned c)
510 if(c>=linprog.n_columns)
511 throw out_of_range("Row::operator[]");
513 Column &column = linprog.columns[c];
514 if(column.values.size()<=index)
515 column.values.resize(index+1);
517 return column.values[index];
520 float &Layout::LinearProgram::Row::back()
522 return (*this)[linprog.n_columns-1];
526 Layout::LinearProgram::Column::Column():