12 class Layout::LinearProgram
18 LinearProgram &linprog;
22 Row(LinearProgram &, unsigned);
24 float &operator[](unsigned);
32 std::vector<float> values;
39 std::vector<Column> columns;
44 LinearProgram(unsigned);
47 Row operator[](unsigned);
48 Row get_objective_row();
49 float get_variable(unsigned);
52 void prepare_columns();
53 void add_artificial_variables();
54 void remove_artificial_variables();
55 unsigned find_minimal_ratio(unsigned);
56 void make_basic_column(unsigned, unsigned);
61 struct Layout::Pointers
64 unsigned Geometry::*dim;
65 Packing Slot::*packing;
66 unsigned Sides::*low_margin;
67 unsigned Sides::*high_margin;
68 unsigned Layout::*spacing;
71 Layout::Pointers Layout::pointers[2] =
73 &Geometry::x, &Geometry::w,
75 &Sides::left, &Sides::right,
78 &Geometry::y, &Geometry::h,
80 &Sides::bottom, &Sides::top,
94 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
98 void Layout::set_container(Container &c)
101 throw logic_error("container!=0");
106 void Layout::set_margin(const Sides &m)
113 void Layout::add_widget(Widget &wdg)
116 throw logic_error("!container");
118 Slot *slot = create_slot(wdg);
119 for(list<Constraint>::iterator i=slot->constraints.begin(); i!=slot->constraints.end(); ++i)
120 i->target.constraints.push_back(Constraint(complement(i->type), *slot));
121 slot->index = slots.size();
122 slots.push_back(slot);
127 void Layout::remove_widget(Widget &wdg)
129 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
130 if(&(*i)->widget==&wdg)
132 for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
135 for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
138 (*j)->constraints.erase(k++);
148 for(i=slots.begin(); i!=slots.end(); ++i, ++n)
156 Layout::Slot *Layout::create_slot(Widget &wdg)
158 return new Slot(*this, wdg);
161 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
163 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
164 if(&(*i)->widget==&wdg)
167 throw hierarchy_error("widget not in layout");
170 Layout::ConstraintType Layout::complement(ConstraintType type)
174 else if(type==LEFT_OF)
184 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
187 throw invalid_argument("&src==&tgt");
189 Slot &src_slot = get_slot_for_widget(src);
190 Slot &tgt_slot = get_slot_for_widget(tgt);
192 for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
193 if(i->type==type && &i->target==&tgt_slot)
196 src_slot.constraints.push_back(Constraint(type, tgt_slot));
197 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
202 void Layout::set_gravity(Widget &wdg, int h, int v)
204 Slot &slot = get_slot_for_widget(wdg);
206 slot.horiz_pack.gravity = h;
207 slot.vert_pack.gravity = v;
212 void Layout::set_expand(Widget &wdg, bool h, bool v)
214 Slot &slot = get_slot_for_widget(wdg);
216 slot.horiz_pack.expand = h;
217 slot.vert_pack.expand = v;
222 void Layout::update()
224 solve_constraints(HORIZONTAL, UPDATE);
225 solve_constraints(VERTICAL, UPDATE);
227 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
228 (*i)->widget.set_geometry((*i)->geom);
231 void Layout::autosize()
233 solve_constraints(HORIZONTAL, AUTOSIZE);
234 solve_constraints(VERTICAL, AUTOSIZE);
236 container->set_size(autosize_geom.w, autosize_geom.h);
239 void Layout::solve_constraints(int dir, SolveMode mode)
241 Pointers &ptrs = pointers[dir&VERTICAL];
243 const Geometry &geom = container->get_geometry();
244 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
247 /* Set up a linear program to solve the constraints. The program matrix has
248 five columns for each widget, and one constant column. The first and second
249 columns of a widget are its position and dimension, respectively. The
250 remaining three are slack columns; see below for their purposes. */
251 LinearProgram linprog(slots.size()*5+1);
252 float weight = slots.size();
253 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
255 LinearProgram::Row objective = linprog.get_objective_row();
258 objective[(*i)->index*5] = -1;
259 objective[(*i)->index*5+1] = -1;
263 objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
264 objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
268 // Prevent the widget from going past the container's low edge.
269 LinearProgram::Row row = linprog.add_row();
270 row[(*i)->index*5] = 1;
271 row[(*i)->index*5+2] = -1;
272 row.back() = margin.*(ptrs.low_margin);
277 // Prevent the widget from going past the container's high edge.
278 LinearProgram::Row row = linprog.add_row();
279 row[(*i)->index*5] = 1;
280 row[(*i)->index*5+1] = 1;
281 row[(*i)->index*5+3] = 1;
282 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
286 /* Only allow the widget's dimension to increase. The geometry has
287 previously been set to the smallest allowable size. */
288 LinearProgram::Row row = linprog.add_row();
289 row[(*i)->index*5+1] = 1;
290 row[(*i)->index*5+4] = -1;
291 row.back() = (*i)->autosize_geom.*(ptrs.dim);
294 /* Add rows for user-defined constraints. Below/above and left/right of
295 constraints are always added in pairs, so it's only necessary to create a
297 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
298 if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
300 LinearProgram::Row row = linprog.add_row();
302 row[(*i)->index*5] = 1;
304 row[(*i)->index*5+1] = 1;
305 if(j->type&TARGET_POS)
306 row[j->target.index*5] = -1;
307 if(j->type&TARGET_DIM)
308 row[j->target.index*5+1] = -1;
310 row.back() = this->*(ptrs.spacing);
319 autosize_geom.*(ptrs.dim) = 0;
320 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
322 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
323 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
328 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
330 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
331 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
337 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
343 Layout::Packing::Packing():
349 Layout::Slot::Slot(Layout &l, Widget &w):
354 vert_pack.gravity = 1;
355 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
357 autosize_geom = widget.get_geometry();
360 void Layout::Slot::autosize_changed()
363 autosize_geom = widget.get_geometry();
365 // If the widget fits in the area it had, just leave it there.
366 if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
367 widget.set_geometry(geom);
370 layout.container->signal_autosize_changed.emit();
376 Layout::LinearProgram::LinearProgram(unsigned s):
384 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
386 return Row(*this, n_rows++);
389 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
392 throw out_of_range("LinearProgram::operator[]");
394 return Row(*this, r);
397 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
399 return Row(*this, 0);
402 float Layout::LinearProgram::get_variable(unsigned i)
404 if(!solved || infeasible)
405 throw logic_error("not solved");
407 throw out_of_range("LinearProgram::get_variable");
409 if(unsigned r = columns[i].basic)
410 return columns.back().values[r];
415 bool Layout::LinearProgram::solve()
417 if(solved || infeasible)
420 /* Solve the program using the simplex method. The column representing the
421 objective variable is kept implicit, as it would never change during the
422 execution of the algorithm. */
426 add_artificial_variables();
428 // Solve the phase 1 problem.
431 /* All artificial variables should now be non-basic and thus zero, so the
432 objective function's value should also be zero. If it isn't, the original
433 program can't be solved. */
434 if(columns.back().values.front())
440 remove_artificial_variables();
442 // Solve the phase 2 problem. We already know it to be feasible.
450 void Layout::LinearProgram::prepare_columns()
452 /* See if any variables are already basic. A basic variable must only have
453 a nonzero coefficient on one row, and its product with the constant column
454 must not be negative. Only one variable can be basic for any given row. */
455 vector<float> basic_coeff(n_rows, 0.0f);
456 const vector<float> &constants = columns.back().values;
457 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
459 if(i->values.size()>=2 && i->values.back()!=0.0f && (constants.size()<i->values.size() || i->values.back()*constants[i->values.size()-1]>=0.0f) && basic_coeff[i->values.size()-1]==0.0f)
462 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
463 basic = (i->values[j]==0.0f);
466 i->basic = i->values.size()-1;
467 basic_coeff[i->basic] = -i->values.front()/i->values.back();
473 // Price out the newly-created basic variables.
474 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
475 if(!i->values.empty())
477 for(unsigned j=0; j<i->values.size(); ++j)
478 i->values.front() += basic_coeff[j]*i->values[j];
482 void Layout::LinearProgram::add_artificial_variables()
484 vector<unsigned> artificial_rows(n_rows-1);
485 for(unsigned i=0; i<artificial_rows.size(); ++i)
486 artificial_rows[i] = i+1;
488 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
490 artificial_rows[i->basic-1] = 0;
491 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
493 /* Force all non-basic columns fully into existence and relocate objective
494 row to bottom in preparation of phase 1. A new objective row is calculated
495 by pricing out the constraint rows. */
496 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
499 float objective = 0.0f;
500 if(!i->values.empty())
502 objective = i->values.front();
503 i->values.front() = 0.0f;
504 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
505 if(*j<i->values.size())
506 i->values.front() += i->values[*j];
508 i->values.resize(n_rows+1, 0.0f);
509 i->values.back() = objective;
512 if(artificial_rows.empty())
515 /* Create artificial variables for phase 1. This ensures that each row has
516 a basic variable associated with it. The original objective row already
517 contains the implicit objective variable, which is basic. */
518 columns.resize(n_columns+artificial_rows.size());
519 columns.back() = columns[n_columns-1];
520 columns[n_columns-1].values.clear();
521 for(unsigned i=0; i<artificial_rows.size(); ++i)
522 columns[n_columns+i-1].basic = artificial_rows[i];
525 void Layout::LinearProgram::remove_artificial_variables()
527 /* See if any artificial variables are still basic. This could be because
528 the program is degenerate. To avoid trouble later on, use pivots to make
529 some of the original variables basic instead.
531 I don't fully understand why this is needed, but it appears to work. */
532 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
533 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
535 for(unsigned j=0; j+1<n_columns; ++j)
536 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
538 make_basic_column(j, columns[i].basic);
543 /* Get rid of the artificial variables and restore the original objective
544 row to form the phase 2 problem. */
545 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
546 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
549 i->values.front() = i->values.back();
550 i->values.pop_back();
554 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
556 /* Pick the row with the minimum ratio between the constant column and the
557 pivot column. This ensures that when the pivot column is made basic, values
558 in the constant column stay positive.
560 The use of n_rows instead of the true size of the column is intentional,
561 since the relocated objective row must be ignored in phase 1. */
562 float best = numeric_limits<float>::infinity();
564 for(unsigned i=1; i<n_rows; ++i)
565 if(columns[c].values[i]>0)
567 float ratio = columns.back().values[i]/columns[c].values[i];
578 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
580 /* Perform row transfer operations to make the pivot column basic,
581 containing a 1 on the pivot row. */
582 for(unsigned i=0; i<columns.size(); ++i)
583 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
587 columns[i].values.resize(columns.back().values.size(), 0.0f);
588 columns[i].values[columns[i].basic] = 1.0f;
589 columns[i].basic = 0;
592 float scale = columns[i].values[r]/columns[c].values[r];
594 columns[i].values[r] = scale;
595 for(unsigned j=0; j<columns[i].values.size(); ++j)
597 columns[i].values[j] -= scale*columns[c].values[j];
600 columns[c].basic = r;
601 columns[c].values.clear();
604 bool Layout::LinearProgram::pivot()
606 /* Pick a nonbasic column and make it basic. Requiring a positive objective
607 coefficient ensures that the objective function's value will decrease in the
609 for(unsigned i=0; i+1<columns.size(); ++i)
610 if(!columns[i].basic && columns[i].values.front()>0)
611 if(unsigned row = find_minimal_ratio(i))
613 make_basic_column(i, row);
621 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
626 float &Layout::LinearProgram::Row::operator[](unsigned c)
628 if(c>=linprog.n_columns)
629 throw out_of_range("Row::operator[]");
631 Column &column = linprog.columns[c];
632 if(column.values.size()<=index)
633 column.values.resize(index+1);
635 return column.values[index];
638 float &Layout::LinearProgram::Row::back()
640 return (*this)[linprog.n_columns-1];
644 Layout::LinearProgram::Column::Column():