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::set_spacing(unsigned s)
121 void Layout::set_row_spacing(unsigned s)
128 void Layout::set_column_spacing(unsigned s)
135 void Layout::add_widget(Widget &wdg)
138 throw logic_error("!container");
140 Slot *slot = create_slot(wdg);
141 for(list<Constraint>::iterator i=slot->constraints.begin(); i!=slot->constraints.end(); ++i)
142 i->target.constraints.push_back(Constraint(complement(i->type), *slot));
143 slot->index = slots.size();
144 slots.push_back(slot);
149 void Layout::remove_widget(Widget &wdg)
151 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
152 if(&(*i)->widget==&wdg)
154 for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
157 for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
160 (*j)->constraints.erase(k++);
170 for(i=slots.begin(); i!=slots.end(); ++i, ++n)
178 Layout::Slot *Layout::create_slot(Widget &wdg)
180 return new Slot(*this, wdg);
183 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
185 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
186 if(&(*i)->widget==&wdg)
189 throw hierarchy_error("widget not in layout");
192 Layout::ConstraintType Layout::complement(ConstraintType type)
196 else if(type==LEFT_OF)
206 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
209 throw invalid_argument("&src==&tgt");
211 Slot &src_slot = get_slot_for_widget(src);
212 Slot &tgt_slot = get_slot_for_widget(tgt);
214 for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
215 if(i->type==type && &i->target==&tgt_slot)
218 src_slot.constraints.push_back(Constraint(type, tgt_slot));
219 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
224 void Layout::set_gravity(Widget &wdg, int h, int v)
226 Slot &slot = get_slot_for_widget(wdg);
228 slot.horiz_pack.gravity = h;
229 slot.vert_pack.gravity = v;
234 void Layout::set_expand(Widget &wdg, bool h, bool v)
236 Slot &slot = get_slot_for_widget(wdg);
238 slot.horiz_pack.expand = h;
239 slot.vert_pack.expand = v;
244 void Layout::update()
246 solve_constraints(HORIZONTAL, UPDATE);
247 solve_constraints(VERTICAL, UPDATE);
249 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
250 (*i)->widget.set_geometry((*i)->geom);
253 void Layout::autosize()
255 solve_constraints(HORIZONTAL, AUTOSIZE);
256 solve_constraints(VERTICAL, AUTOSIZE);
258 container->set_size(autosize_geom.w, autosize_geom.h);
261 void Layout::solve_constraints(int dir, SolveMode mode)
263 Pointers &ptrs = pointers[dir&VERTICAL];
265 const Geometry &geom = container->get_geometry();
266 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
269 /* Set up a linear program to solve the constraints. The program matrix has
270 five columns for each widget, and one constant column. The first and second
271 columns of a widget are its position and dimension, respectively. The
272 remaining three are slack columns; see below for their purposes. */
273 LinearProgram linprog(slots.size()*5+1);
274 float weight = slots.size();
275 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
277 LinearProgram::Row objective = linprog.get_objective_row();
280 objective[(*i)->index*5] = -1;
281 objective[(*i)->index*5+1] = -1;
285 objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
286 objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
290 // Prevent the widget from going past the container's low edge.
291 LinearProgram::Row row = linprog.add_row();
292 row[(*i)->index*5] = 1;
293 row[(*i)->index*5+2] = -1;
294 row.back() = margin.*(ptrs.low_margin);
299 // Prevent the widget from going past the container's high edge.
300 LinearProgram::Row row = linprog.add_row();
301 row[(*i)->index*5] = 1;
302 row[(*i)->index*5+1] = 1;
303 row[(*i)->index*5+3] = 1;
304 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
308 /* Only allow the widget's dimension to increase. The geometry has
309 previously been set to the smallest allowable size. */
310 LinearProgram::Row row = linprog.add_row();
311 row[(*i)->index*5+1] = 1;
312 row[(*i)->index*5+4] = -1;
313 row.back() = (*i)->autosize_geom.*(ptrs.dim);
316 /* Add rows for user-defined constraints. Below/above and left/right of
317 constraints are always added in pairs, so it's only necessary to create a
319 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
320 if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
322 LinearProgram::Row row = linprog.add_row();
324 row[(*i)->index*5] = 1;
326 row[(*i)->index*5+1] = 1;
327 if(j->type&TARGET_POS)
328 row[j->target.index*5] = -1;
329 if(j->type&TARGET_DIM)
330 row[j->target.index*5+1] = -1;
332 row.back() = this->*(ptrs.spacing);
341 autosize_geom.*(ptrs.dim) = 0;
342 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
344 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
345 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
350 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
352 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
353 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
359 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
365 Layout::Packing::Packing():
371 Layout::Slot::Slot(Layout &l, Widget &w):
376 vert_pack.gravity = 1;
377 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
379 autosize_geom = widget.get_geometry();
382 void Layout::Slot::autosize_changed()
385 autosize_geom = widget.get_geometry();
387 // If the widget fits in the area it had, just leave it there.
388 if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
389 widget.set_geometry(geom);
392 layout.container->signal_autosize_changed.emit();
398 Layout::LinearProgram::LinearProgram(unsigned s):
406 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
408 return Row(*this, n_rows++);
411 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
414 throw out_of_range("LinearProgram::operator[]");
416 return Row(*this, r);
419 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
421 return Row(*this, 0);
424 float Layout::LinearProgram::get_variable(unsigned i)
426 if(!solved || infeasible)
427 throw logic_error("not solved");
429 throw out_of_range("LinearProgram::get_variable");
431 if(unsigned r = columns[i].basic)
432 return columns.back().values[r];
437 bool Layout::LinearProgram::solve()
439 if(solved || infeasible)
442 /* Solve the program using the simplex method. The column representing the
443 objective variable is kept implicit, as it would never change during the
444 execution of the algorithm. */
448 add_artificial_variables();
450 // Solve the phase 1 problem.
453 /* All artificial variables should now be non-basic and thus zero, so the
454 objective function's value should also be zero. If it isn't, the original
455 program can't be solved. */
456 if(columns.back().values.front())
462 remove_artificial_variables();
464 // Solve the phase 2 problem. We already know it to be feasible.
472 void Layout::LinearProgram::prepare_columns()
474 /* See if any variables are already basic. A basic variable must only have
475 a nonzero coefficient on one row, and its product with the constant column
476 must not be negative. Only one variable can be basic for any given row. */
477 vector<float> basic_coeff(n_rows, 0.0f);
478 const vector<float> &constants = columns.back().values;
479 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
481 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)
484 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
485 basic = (i->values[j]==0.0f);
488 i->basic = i->values.size()-1;
489 basic_coeff[i->basic] = -i->values.front()/i->values.back();
495 // Price out the newly-created basic variables.
496 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
497 if(!i->values.empty())
499 for(unsigned j=0; j<i->values.size(); ++j)
500 i->values.front() += basic_coeff[j]*i->values[j];
504 void Layout::LinearProgram::add_artificial_variables()
506 vector<unsigned> artificial_rows(n_rows-1);
507 for(unsigned i=0; i<artificial_rows.size(); ++i)
508 artificial_rows[i] = i+1;
510 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
512 artificial_rows[i->basic-1] = 0;
513 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
515 /* Force all non-basic columns fully into existence and relocate objective
516 row to bottom in preparation of phase 1. A new objective row is calculated
517 by pricing out the constraint rows. */
518 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
521 float objective = 0.0f;
522 if(!i->values.empty())
524 objective = i->values.front();
525 i->values.front() = 0.0f;
526 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
527 if(*j<i->values.size())
528 i->values.front() += i->values[*j];
530 i->values.resize(n_rows+1, 0.0f);
531 i->values.back() = objective;
534 if(artificial_rows.empty())
537 /* Create artificial variables for phase 1. This ensures that each row has
538 a basic variable associated with it. The original objective row already
539 contains the implicit objective variable, which is basic. */
540 columns.resize(n_columns+artificial_rows.size());
541 columns.back() = columns[n_columns-1];
542 columns[n_columns-1].values.clear();
543 for(unsigned i=0; i<artificial_rows.size(); ++i)
544 columns[n_columns+i-1].basic = artificial_rows[i];
547 void Layout::LinearProgram::remove_artificial_variables()
549 /* See if any artificial variables are still basic. This could be because
550 the program is degenerate. To avoid trouble later on, use pivots to make
551 some of the original variables basic instead.
553 I don't fully understand why this is needed, but it appears to work. */
554 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
555 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
557 for(unsigned j=0; j+1<n_columns; ++j)
558 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
560 make_basic_column(j, columns[i].basic);
565 /* Get rid of the artificial variables and restore the original objective
566 row to form the phase 2 problem. */
567 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
568 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
571 i->values.front() = i->values.back();
572 i->values.pop_back();
576 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
578 /* Pick the row with the minimum ratio between the constant column and the
579 pivot column. This ensures that when the pivot column is made basic, values
580 in the constant column stay positive.
582 The use of n_rows instead of the true size of the column is intentional,
583 since the relocated objective row must be ignored in phase 1. */
584 float best = numeric_limits<float>::infinity();
586 for(unsigned i=1; i<n_rows; ++i)
587 if(columns[c].values[i]>0)
589 float ratio = columns.back().values[i]/columns[c].values[i];
600 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
602 /* Perform row transfer operations to make the pivot column basic,
603 containing a 1 on the pivot row. */
604 for(unsigned i=0; i<columns.size(); ++i)
605 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
609 columns[i].values.resize(columns.back().values.size(), 0.0f);
610 columns[i].values[columns[i].basic] = 1.0f;
611 columns[i].basic = 0;
614 float scale = columns[i].values[r]/columns[c].values[r];
616 columns[i].values[r] = scale;
617 for(unsigned j=0; j<columns[i].values.size(); ++j)
619 columns[i].values[j] -= scale*columns[c].values[j];
622 columns[c].basic = r;
623 columns[c].values.clear();
626 bool Layout::LinearProgram::pivot()
628 /* Pick a nonbasic column and make it basic. Requiring a positive objective
629 coefficient ensures that the objective function's value will decrease in the
631 for(unsigned i=0; i+1<columns.size(); ++i)
632 if(!columns[i].basic && columns[i].values.front()>0)
633 if(unsigned row = find_minimal_ratio(i))
635 make_basic_column(i, row);
643 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
648 float &Layout::LinearProgram::Row::operator[](unsigned c)
650 if(c>=linprog.n_columns)
651 throw out_of_range("Row::operator[]");
653 Column &column = linprog.columns[c];
654 if(column.values.size()<=index)
655 column.values.resize(index+1);
657 return column.values[index];
660 float &Layout::LinearProgram::Row::back()
662 return (*this)[linprog.n_columns-1];
666 Layout::LinearProgram::Column::Column():