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,
92 n_slack_constraints[0] = 0;
93 n_slack_constraints[1] = 0;
98 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
102 void Layout::set_container(Container &c)
105 throw logic_error("container!=0");
110 void Layout::set_margin(const Sides &m)
117 void Layout::set_spacing(unsigned s)
125 void Layout::set_row_spacing(unsigned s)
132 void Layout::set_column_spacing(unsigned s)
139 void Layout::add_widget(Widget &wdg)
142 throw logic_error("!container");
144 Slot *slot = create_slot(wdg);
145 for(list<Constraint>::iterator i=slot->constraints.begin(); i!=slot->constraints.end(); ++i)
146 i->target.constraints.push_back(Constraint(complement(i->type), *slot));
147 slots.push_back(slot);
148 update_slot_indices();
153 void Layout::remove_widget(Widget &wdg)
155 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
156 if(&(*i)->widget==&wdg)
158 for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
161 for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
164 (*j)->constraints.erase(k++);
173 update_slot_indices();
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++;
195 n_slack_constraints[0] = 0;
196 n_slack_constraints[1] = 0;
197 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
200 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
201 if(j->target.index>(*i)->index && (j->type&SLACK))
202 ++n_slack_constraints[j->type&1];
206 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
208 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
209 if(&(*i)->widget==&wdg)
212 throw hierarchy_error("widget not in layout");
215 Layout::ConstraintType Layout::complement(ConstraintType type)
217 return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
220 void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
223 throw invalid_argument("&src==&tgt");
225 Slot &src_slot = get_slot_for_widget(src);
226 Slot &tgt_slot = get_slot_for_widget(tgt);
228 for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
229 if(i->type==type && &i->target==&tgt_slot)
232 src_slot.constraints.push_back(Constraint(type, tgt_slot));
233 src_slot.constraints.back().spacing = sp;
234 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
235 tgt_slot.constraints.back().spacing = sp;
237 update_slot_indices();
241 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
243 create_constraint(src, type, tgt, -1);
246 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
248 create_constraint(src, type, tgt, spacing);
251 void Layout::set_gravity(Widget &wdg, int h, int v)
253 Slot &slot = get_slot_for_widget(wdg);
255 slot.horiz_pack.gravity = h;
256 slot.vert_pack.gravity = v;
261 void Layout::set_expand(Widget &wdg, bool h, bool v)
263 Slot &slot = get_slot_for_widget(wdg);
265 slot.horiz_pack.expand = h;
266 slot.vert_pack.expand = v;
271 void Layout::update()
273 solve_constraints(HORIZONTAL, UPDATE);
274 solve_constraints(VERTICAL, UPDATE);
276 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
277 (*i)->widget.set_geometry((*i)->geom);
280 void Layout::autosize()
282 solve_constraints(HORIZONTAL, AUTOSIZE);
283 solve_constraints(VERTICAL, AUTOSIZE);
285 container->set_size(autosize_geom.w, autosize_geom.h);
288 void Layout::solve_constraints(int dir, SolveMode mode)
290 Pointers &ptrs = pointers[dir&VERTICAL];
292 const Geometry &geom = container->get_geometry();
293 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
296 /* Set up a linear program to solve the constraints. The program matrix has
297 five columns for each widget, and one constant column. The first and second
298 columns of a widget are its position and dimension, respectively. The
299 remaining three are slack columns; see below for their purposes. */
300 LinearProgram linprog(n_active_slots*5+n_slack_constraints[dir]+1);
301 float weight = slots.size();
302 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
307 LinearProgram::Row objective = linprog.get_objective_row();
310 objective[(*i)->index*5] = -1;
311 objective[(*i)->index*5+1] = -1;
315 objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
316 objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
320 // Prevent the widget from going past the container's low edge.
321 LinearProgram::Row row = linprog.add_row();
322 row[(*i)->index*5] = 1;
323 row[(*i)->index*5+2] = -1;
324 row.back() = margin.*(ptrs.low_margin);
329 // Prevent the widget from going past the container's high edge.
330 LinearProgram::Row row = linprog.add_row();
331 row[(*i)->index*5] = 1;
332 row[(*i)->index*5+1] = 1;
333 row[(*i)->index*5+3] = 1;
334 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
337 if(((*i)->*(ptrs.packing)).gravity==0)
339 /* This forces the widget's distance from the left and right edge of
340 the container to be equal. It's a bit of a hack, but more time and
341 thought is needed for a better solution. */
342 LinearProgram::Row row = linprog.add_row();
343 row[(*i)->index*5+2] = 1;
344 row[(*i)->index*5+3] = -1;
348 /* Don't allow the widget's dimension to get below that determined
350 LinearProgram::Row row = linprog.add_row();
351 row[(*i)->index*5+1] = 1;
352 row[(*i)->index*5+4] = -1;
353 row.back() = (*i)->autosize_geom.*(ptrs.dim);
356 /* Add rows for user-defined constraints. Constraints are always added
357 in pairs, so it's only necessary to create a row for one half. */
358 unsigned k = n_active_slots*5;
359 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
360 if(j->target.index>(*i)->index && (j->type&1)==dir)
362 LinearProgram::Row row = linprog.add_row();
363 float polarity = ((j->type&SELF_DIM) ? -1 : 1);
365 row[(*i)->index*5] = polarity;
367 row[(*i)->index*5+1] = polarity;
368 if(j->type&TARGET_POS)
369 row[j->target.index*5] = -polarity;
370 if(j->type&TARGET_DIM)
371 row[j->target.index*5+1] = -polarity;
373 row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
384 autosize_geom.*(ptrs.dim) = 0;
385 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
388 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
389 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
394 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
397 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
398 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
404 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
411 Layout::Packing::Packing():
417 Layout::Slot::Slot(Layout &l, Widget &w):
422 vert_pack.gravity = 1;
423 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
424 widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
426 autosize_geom = widget.get_geometry();
429 void Layout::Slot::autosize_changed()
432 autosize_geom = widget.get_geometry();
434 if(!widget.is_visible())
437 // If the widget fits in the area it had, just leave it there.
438 if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
439 widget.set_geometry(geom);
442 layout.container->signal_autosize_changed.emit();
447 void Layout::Slot::visibility_changed(bool v)
449 layout.update_slot_indices();
452 layout.container->signal_autosize_changed.emit();
458 Layout::LinearProgram::LinearProgram(unsigned s):
466 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
468 return Row(*this, n_rows++);
471 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
474 throw out_of_range("LinearProgram::operator[]");
476 return Row(*this, r);
479 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
481 return Row(*this, 0);
484 float Layout::LinearProgram::get_variable(unsigned i)
486 if(!solved || infeasible)
487 throw logic_error("not solved");
489 throw out_of_range("LinearProgram::get_variable");
491 if(unsigned r = columns[i].basic)
492 return columns.back().values[r];
497 bool Layout::LinearProgram::solve()
499 if(solved || infeasible)
502 /* Solve the program using the simplex method. The column representing the
503 objective variable is kept implicit, as it would never change during the
504 execution of the algorithm. */
508 add_artificial_variables();
510 // Solve the phase 1 problem.
513 /* All artificial variables should now be non-basic and thus zero, so the
514 objective function's value should also be zero. If it isn't, the original
515 program can't be solved. */
516 if(columns.back().values.front())
522 remove_artificial_variables();
524 // Solve the phase 2 problem. We already know it to be feasible.
532 void Layout::LinearProgram::prepare_columns()
534 /* See if any variables are already basic. A basic variable must only have
535 a nonzero coefficient on one row, and its product with the constant column
536 must not be negative. Only one variable can be basic for any given row. */
537 vector<float> obj_coeff(n_rows, 0.0f);
538 vector<float> row_coeff(n_rows, 1.0f);
539 const vector<float> &constants = columns.back().values;
540 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
542 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)
545 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
546 basic = (i->values[j]==0.0f);
549 i->basic = i->values.size()-1;
550 row_coeff[i->basic] = 1.0f/i->values.back();
551 obj_coeff[i->basic] = -i->values.front();
557 // Price out the newly-created basic variables.
558 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
559 if(!i->values.empty())
561 for(unsigned j=0; j<i->values.size(); ++j)
563 i->values[j] *= row_coeff[j];
564 i->values.front() += obj_coeff[j]*i->values[j];
569 void Layout::LinearProgram::add_artificial_variables()
571 vector<unsigned> artificial_rows(n_rows-1);
572 for(unsigned i=0; i<artificial_rows.size(); ++i)
573 artificial_rows[i] = i+1;
575 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
577 artificial_rows[i->basic-1] = 0;
578 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
580 /* Force all non-basic columns fully into existence and relocate objective
581 row to bottom in preparation of phase 1. A new objective row is calculated
582 by pricing out the constraint rows. */
583 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
586 float objective = 0.0f;
587 if(!i->values.empty())
589 objective = i->values.front();
590 i->values.front() = 0.0f;
591 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
592 if(*j<i->values.size())
593 i->values.front() += i->values[*j];
595 i->values.resize(n_rows+1, 0.0f);
596 i->values.back() = objective;
599 if(artificial_rows.empty())
602 /* Create artificial variables for phase 1. This ensures that each row has
603 a basic variable associated with it. The original objective row already
604 contains the implicit objective variable, which is basic. */
605 columns.resize(n_columns+artificial_rows.size());
606 columns.back() = columns[n_columns-1];
607 columns[n_columns-1].values.clear();
608 for(unsigned i=0; i<artificial_rows.size(); ++i)
609 columns[n_columns+i-1].basic = artificial_rows[i];
612 void Layout::LinearProgram::remove_artificial_variables()
614 /* See if any artificial variables are still basic. This could be because
615 the program is degenerate. To avoid trouble later on, use pivots to make
616 some of the original variables basic instead.
618 I don't fully understand why this is needed, but it appears to work. */
619 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
620 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
622 for(unsigned j=0; j+1<n_columns; ++j)
623 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
625 make_basic_column(j, columns[i].basic);
630 /* Get rid of the artificial variables and restore the original objective
631 row to form the phase 2 problem. */
632 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
633 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
636 i->values.front() = i->values.back();
637 i->values.pop_back();
641 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
643 /* Pick the row with the minimum ratio between the constant column and the
644 pivot column. This ensures that when the pivot column is made basic, values
645 in the constant column stay positive.
647 The use of n_rows instead of the true size of the column is intentional,
648 since the relocated objective row must be ignored in phase 1. */
649 float best = numeric_limits<float>::infinity();
651 for(unsigned i=1; i<n_rows; ++i)
652 if(columns[c].values[i]>0)
654 float ratio = columns.back().values[i]/columns[c].values[i];
665 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
667 /* Perform row transfer operations to make the pivot column basic,
668 containing a 1 on the pivot row. */
669 for(unsigned i=0; i<columns.size(); ++i)
670 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
674 columns[i].values.resize(columns.back().values.size(), 0.0f);
675 columns[i].values[columns[i].basic] = 1.0f;
676 columns[i].basic = 0;
679 float scale = columns[i].values[r]/columns[c].values[r];
681 columns[i].values[r] = scale;
682 for(unsigned j=0; j<columns[i].values.size(); ++j)
684 columns[i].values[j] -= scale*columns[c].values[j];
687 columns[c].basic = r;
688 columns[c].values.clear();
691 bool Layout::LinearProgram::pivot()
693 /* Pick a nonbasic column and make it basic. Requiring a positive objective
694 coefficient ensures that the objective function's value will decrease in the
696 for(unsigned i=0; i+1<columns.size(); ++i)
697 if(!columns[i].basic && columns[i].values.front()>0)
698 if(unsigned row = find_minimal_ratio(i))
700 make_basic_column(i, row);
708 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
713 float &Layout::LinearProgram::Row::operator[](unsigned c)
715 if(c>=linprog.n_columns)
716 throw out_of_range("Row::operator[]");
718 Column &column = linprog.columns[c];
719 if(column.values.size()<=index)
720 column.values.resize(index+1);
722 return column.values[index];
725 float &Layout::LinearProgram::Row::back()
727 return (*this)[linprog.n_columns-1];
731 Layout::LinearProgram::Column::Column():