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,
95 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
99 void Layout::set_container(Container &c)
102 throw logic_error("container!=0");
107 void Layout::set_margin(const Sides &m)
114 void Layout::set_spacing(unsigned s)
122 void Layout::set_row_spacing(unsigned s)
129 void Layout::set_column_spacing(unsigned s)
136 void Layout::add_widget(Widget &wdg)
139 throw logic_error("!container");
141 Slot *slot = create_slot(wdg);
142 for(list<Constraint>::iterator i=slot->constraints.begin(); i!=slot->constraints.end(); ++i)
143 i->target.constraints.push_back(Constraint(complement(i->type), *slot));
144 slots.push_back(slot);
145 update_slot_indices();
150 void Layout::remove_widget(Widget &wdg)
152 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
153 if(&(*i)->widget==&wdg)
155 for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
158 for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
161 (*j)->constraints.erase(k++);
171 for(i=slots.begin(); i!=slots.end(); ++i, ++n)
179 Layout::Slot *Layout::create_slot(Widget &wdg)
181 return new Slot(*this, wdg);
184 void Layout::update_slot_indices()
187 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
189 if((*i)->widget.is_visible())
190 (*i)->index = n_active_slots++;
196 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
198 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
199 if(&(*i)->widget==&wdg)
202 throw hierarchy_error("widget not in layout");
205 Layout::ConstraintType Layout::complement(ConstraintType type)
209 else if(type==LEFT_OF)
219 void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
222 throw invalid_argument("&src==&tgt");
224 Slot &src_slot = get_slot_for_widget(src);
225 Slot &tgt_slot = get_slot_for_widget(tgt);
227 for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
228 if(i->type==type && &i->target==&tgt_slot)
231 src_slot.constraints.push_back(Constraint(type, tgt_slot));
232 src_slot.constraints.back().spacing = sp;
233 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
234 tgt_slot.constraints.back().spacing = sp;
239 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
241 create_constraint(src, type, tgt, -1);
244 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
246 create_constraint(src, type, tgt, spacing);
249 void Layout::set_gravity(Widget &wdg, int h, int v)
251 Slot &slot = get_slot_for_widget(wdg);
253 slot.horiz_pack.gravity = h;
254 slot.vert_pack.gravity = v;
259 void Layout::set_expand(Widget &wdg, bool h, bool v)
261 Slot &slot = get_slot_for_widget(wdg);
263 slot.horiz_pack.expand = h;
264 slot.vert_pack.expand = v;
269 void Layout::update()
271 solve_constraints(HORIZONTAL, UPDATE);
272 solve_constraints(VERTICAL, UPDATE);
274 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
275 (*i)->widget.set_geometry((*i)->geom);
278 void Layout::autosize()
280 solve_constraints(HORIZONTAL, AUTOSIZE);
281 solve_constraints(VERTICAL, AUTOSIZE);
283 container->set_size(autosize_geom.w, autosize_geom.h);
286 void Layout::solve_constraints(int dir, SolveMode mode)
288 Pointers &ptrs = pointers[dir&VERTICAL];
290 const Geometry &geom = container->get_geometry();
291 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
294 /* Set up a linear program to solve the constraints. The program matrix has
295 five columns for each widget, and one constant column. The first and second
296 columns of a widget are its position and dimension, respectively. The
297 remaining three are slack columns; see below for their purposes. */
298 LinearProgram linprog(n_active_slots*5+1);
299 float weight = slots.size();
300 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
305 LinearProgram::Row objective = linprog.get_objective_row();
308 objective[(*i)->index*5] = -1;
309 objective[(*i)->index*5+1] = -1;
313 objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
314 objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
318 // Prevent the widget from going past the container's low edge.
319 LinearProgram::Row row = linprog.add_row();
320 row[(*i)->index*5] = 1;
321 row[(*i)->index*5+2] = -1;
322 row.back() = margin.*(ptrs.low_margin);
327 // Prevent the widget from going past the container's high edge.
328 LinearProgram::Row row = linprog.add_row();
329 row[(*i)->index*5] = 1;
330 row[(*i)->index*5+1] = 1;
331 row[(*i)->index*5+3] = 1;
332 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
335 if(((*i)->*(ptrs.packing)).gravity==0)
337 /* This forces the widget's distance from the left and right edge of
338 the container to be equal. It's a bit of a hack, but more time and
339 thought is needed for a better solution. */
340 LinearProgram::Row row = linprog.add_row();
341 row[(*i)->index*5+2] = 1;
342 row[(*i)->index*5+3] = -1;
346 /* Only allow the widget's dimension to increase. The geometry has
347 previously been set to the smallest allowable size. */
348 LinearProgram::Row row = linprog.add_row();
349 row[(*i)->index*5+1] = 1;
350 row[(*i)->index*5+4] = -1;
351 row.back() = (*i)->autosize_geom.*(ptrs.dim);
354 /* Add rows for user-defined constraints. Below/above and left/right of
355 constraints are always added in pairs, so it's only necessary to create a
357 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
358 if(j->target.index>=0 && (j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
360 LinearProgram::Row row = linprog.add_row();
362 row[(*i)->index*5] = 1;
364 row[(*i)->index*5+1] = 1;
365 if(j->type&TARGET_POS)
366 row[j->target.index*5] = -1;
367 if(j->type&TARGET_DIM)
368 row[j->target.index*5+1] = -1;
370 row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
379 autosize_geom.*(ptrs.dim) = 0;
380 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
383 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
384 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
389 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
392 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
393 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
399 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
406 Layout::Packing::Packing():
412 Layout::Slot::Slot(Layout &l, Widget &w):
417 vert_pack.gravity = 1;
418 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
419 widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
421 autosize_geom = widget.get_geometry();
424 void Layout::Slot::autosize_changed()
427 autosize_geom = widget.get_geometry();
429 if(!widget.is_visible())
432 // If the widget fits in the area it had, just leave it there.
433 if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
434 widget.set_geometry(geom);
437 layout.container->signal_autosize_changed.emit();
442 void Layout::Slot::visibility_changed(bool v)
444 layout.update_slot_indices();
447 layout.container->signal_autosize_changed.emit();
453 Layout::LinearProgram::LinearProgram(unsigned s):
461 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
463 return Row(*this, n_rows++);
466 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
469 throw out_of_range("LinearProgram::operator[]");
471 return Row(*this, r);
474 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
476 return Row(*this, 0);
479 float Layout::LinearProgram::get_variable(unsigned i)
481 if(!solved || infeasible)
482 throw logic_error("not solved");
484 throw out_of_range("LinearProgram::get_variable");
486 if(unsigned r = columns[i].basic)
487 return columns.back().values[r];
492 bool Layout::LinearProgram::solve()
494 if(solved || infeasible)
497 /* Solve the program using the simplex method. The column representing the
498 objective variable is kept implicit, as it would never change during the
499 execution of the algorithm. */
503 add_artificial_variables();
505 // Solve the phase 1 problem.
508 /* All artificial variables should now be non-basic and thus zero, so the
509 objective function's value should also be zero. If it isn't, the original
510 program can't be solved. */
511 if(columns.back().values.front())
517 remove_artificial_variables();
519 // Solve the phase 2 problem. We already know it to be feasible.
527 void Layout::LinearProgram::prepare_columns()
529 /* See if any variables are already basic. A basic variable must only have
530 a nonzero coefficient on one row, and its product with the constant column
531 must not be negative. Only one variable can be basic for any given row. */
532 vector<float> obj_coeff(n_rows, 0.0f);
533 vector<float> row_coeff(n_rows, 1.0f);
534 const vector<float> &constants = columns.back().values;
535 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
537 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) && obj_coeff[i->values.size()-1]==0.0f)
540 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
541 basic = (i->values[j]==0.0f);
544 i->basic = i->values.size()-1;
545 row_coeff[i->basic] = 1.0f/i->values.back();
546 obj_coeff[i->basic] = -i->values.front();
552 // Price out the newly-created basic variables.
553 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
554 if(!i->values.empty())
556 for(unsigned j=0; j<i->values.size(); ++j)
558 i->values[j] *= row_coeff[j];
559 i->values.front() += obj_coeff[j]*i->values[j];
564 void Layout::LinearProgram::add_artificial_variables()
566 vector<unsigned> artificial_rows(n_rows-1);
567 for(unsigned i=0; i<artificial_rows.size(); ++i)
568 artificial_rows[i] = i+1;
570 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
572 artificial_rows[i->basic-1] = 0;
573 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
575 /* Force all non-basic columns fully into existence and relocate objective
576 row to bottom in preparation of phase 1. A new objective row is calculated
577 by pricing out the constraint rows. */
578 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
581 float objective = 0.0f;
582 if(!i->values.empty())
584 objective = i->values.front();
585 i->values.front() = 0.0f;
586 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
587 if(*j<i->values.size())
588 i->values.front() += i->values[*j];
590 i->values.resize(n_rows+1, 0.0f);
591 i->values.back() = objective;
594 if(artificial_rows.empty())
597 /* Create artificial variables for phase 1. This ensures that each row has
598 a basic variable associated with it. The original objective row already
599 contains the implicit objective variable, which is basic. */
600 columns.resize(n_columns+artificial_rows.size());
601 columns.back() = columns[n_columns-1];
602 columns[n_columns-1].values.clear();
603 for(unsigned i=0; i<artificial_rows.size(); ++i)
604 columns[n_columns+i-1].basic = artificial_rows[i];
607 void Layout::LinearProgram::remove_artificial_variables()
609 /* See if any artificial variables are still basic. This could be because
610 the program is degenerate. To avoid trouble later on, use pivots to make
611 some of the original variables basic instead.
613 I don't fully understand why this is needed, but it appears to work. */
614 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
615 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
617 for(unsigned j=0; j+1<n_columns; ++j)
618 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
620 make_basic_column(j, columns[i].basic);
625 /* Get rid of the artificial variables and restore the original objective
626 row to form the phase 2 problem. */
627 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
628 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
631 i->values.front() = i->values.back();
632 i->values.pop_back();
636 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
638 /* Pick the row with the minimum ratio between the constant column and the
639 pivot column. This ensures that when the pivot column is made basic, values
640 in the constant column stay positive.
642 The use of n_rows instead of the true size of the column is intentional,
643 since the relocated objective row must be ignored in phase 1. */
644 float best = numeric_limits<float>::infinity();
646 for(unsigned i=1; i<n_rows; ++i)
647 if(columns[c].values[i]>0)
649 float ratio = columns.back().values[i]/columns[c].values[i];
660 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
662 /* Perform row transfer operations to make the pivot column basic,
663 containing a 1 on the pivot row. */
664 for(unsigned i=0; i<columns.size(); ++i)
665 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
669 columns[i].values.resize(columns.back().values.size(), 0.0f);
670 columns[i].values[columns[i].basic] = 1.0f;
671 columns[i].basic = 0;
674 float scale = columns[i].values[r]/columns[c].values[r];
676 columns[i].values[r] = scale;
677 for(unsigned j=0; j<columns[i].values.size(); ++j)
679 columns[i].values[j] -= scale*columns[c].values[j];
682 columns[c].basic = r;
683 columns[c].values.clear();
686 bool Layout::LinearProgram::pivot()
688 /* Pick a nonbasic column and make it basic. Requiring a positive objective
689 coefficient ensures that the objective function's value will decrease in the
691 for(unsigned i=0; i+1<columns.size(); ++i)
692 if(!columns[i].basic && columns[i].values.front()>0)
693 if(unsigned row = find_minimal_ratio(i))
695 make_basic_column(i, row);
703 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
708 float &Layout::LinearProgram::Row::operator[](unsigned c)
710 if(c>=linprog.n_columns)
711 throw out_of_range("Row::operator[]");
713 Column &column = linprog.columns[c];
714 if(column.values.size()<=index)
715 column.values.resize(index+1);
717 return column.values[index];
720 float &Layout::LinearProgram::Row::back()
722 return (*this)[linprog.n_columns-1];
726 Layout::LinearProgram::Column::Column():