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::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
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 src_slot.constraints.back().spacing = sp;
220 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
221 tgt_slot.constraints.back().spacing = sp;
226 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
228 create_constraint(src, type, tgt, -1);
231 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
233 create_constraint(src, type, tgt, spacing);
236 void Layout::set_gravity(Widget &wdg, int h, int v)
238 Slot &slot = get_slot_for_widget(wdg);
240 slot.horiz_pack.gravity = h;
241 slot.vert_pack.gravity = v;
246 void Layout::set_expand(Widget &wdg, bool h, bool v)
248 Slot &slot = get_slot_for_widget(wdg);
250 slot.horiz_pack.expand = h;
251 slot.vert_pack.expand = v;
256 void Layout::update()
258 solve_constraints(HORIZONTAL, UPDATE);
259 solve_constraints(VERTICAL, UPDATE);
261 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
262 (*i)->widget.set_geometry((*i)->geom);
265 void Layout::autosize()
267 solve_constraints(HORIZONTAL, AUTOSIZE);
268 solve_constraints(VERTICAL, AUTOSIZE);
270 container->set_size(autosize_geom.w, autosize_geom.h);
273 void Layout::solve_constraints(int dir, SolveMode mode)
275 Pointers &ptrs = pointers[dir&VERTICAL];
277 const Geometry &geom = container->get_geometry();
278 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
281 /* Set up a linear program to solve the constraints. The program matrix has
282 five columns for each widget, and one constant column. The first and second
283 columns of a widget are its position and dimension, respectively. The
284 remaining three are slack columns; see below for their purposes. */
285 LinearProgram linprog(slots.size()*5+1);
286 float weight = slots.size();
287 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
289 LinearProgram::Row objective = linprog.get_objective_row();
292 objective[(*i)->index*5] = -1;
293 objective[(*i)->index*5+1] = -1;
297 objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
298 objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
302 // Prevent the widget from going past the container's low edge.
303 LinearProgram::Row row = linprog.add_row();
304 row[(*i)->index*5] = 1;
305 row[(*i)->index*5+2] = -1;
306 row.back() = margin.*(ptrs.low_margin);
311 // Prevent the widget from going past the container's high edge.
312 LinearProgram::Row row = linprog.add_row();
313 row[(*i)->index*5] = 1;
314 row[(*i)->index*5+1] = 1;
315 row[(*i)->index*5+3] = 1;
316 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
319 if(((*i)->*(ptrs.packing)).gravity==0)
321 /* This forces the widget's distance from the left and right edge of
322 the container to be equal. It's a bit of a hack, but more time and
323 thought is needed for a better solution. */
324 LinearProgram::Row row = linprog.add_row();
325 row[(*i)->index*5+2] = 1;
326 row[(*i)->index*5+3] = -1;
330 /* Only allow the widget's dimension to increase. The geometry has
331 previously been set to the smallest allowable size. */
332 LinearProgram::Row row = linprog.add_row();
333 row[(*i)->index*5+1] = 1;
334 row[(*i)->index*5+4] = -1;
335 row.back() = (*i)->autosize_geom.*(ptrs.dim);
338 /* Add rows for user-defined constraints. Below/above and left/right of
339 constraints are always added in pairs, so it's only necessary to create a
341 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
342 if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
344 LinearProgram::Row row = linprog.add_row();
346 row[(*i)->index*5] = 1;
348 row[(*i)->index*5+1] = 1;
349 if(j->type&TARGET_POS)
350 row[j->target.index*5] = -1;
351 if(j->type&TARGET_DIM)
352 row[j->target.index*5+1] = -1;
354 row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
363 autosize_geom.*(ptrs.dim) = 0;
364 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
366 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
367 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
372 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
374 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
375 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
381 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
388 Layout::Packing::Packing():
394 Layout::Slot::Slot(Layout &l, Widget &w):
399 vert_pack.gravity = 1;
400 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
402 autosize_geom = widget.get_geometry();
405 void Layout::Slot::autosize_changed()
408 autosize_geom = widget.get_geometry();
410 // If the widget fits in the area it had, just leave it there.
411 if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
412 widget.set_geometry(geom);
415 layout.container->signal_autosize_changed.emit();
421 Layout::LinearProgram::LinearProgram(unsigned s):
429 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
431 return Row(*this, n_rows++);
434 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
437 throw out_of_range("LinearProgram::operator[]");
439 return Row(*this, r);
442 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
444 return Row(*this, 0);
447 float Layout::LinearProgram::get_variable(unsigned i)
449 if(!solved || infeasible)
450 throw logic_error("not solved");
452 throw out_of_range("LinearProgram::get_variable");
454 if(unsigned r = columns[i].basic)
455 return columns.back().values[r];
460 bool Layout::LinearProgram::solve()
462 if(solved || infeasible)
465 /* Solve the program using the simplex method. The column representing the
466 objective variable is kept implicit, as it would never change during the
467 execution of the algorithm. */
471 add_artificial_variables();
473 // Solve the phase 1 problem.
476 /* All artificial variables should now be non-basic and thus zero, so the
477 objective function's value should also be zero. If it isn't, the original
478 program can't be solved. */
479 if(columns.back().values.front())
485 remove_artificial_variables();
487 // Solve the phase 2 problem. We already know it to be feasible.
495 void Layout::LinearProgram::prepare_columns()
497 /* See if any variables are already basic. A basic variable must only have
498 a nonzero coefficient on one row, and its product with the constant column
499 must not be negative. Only one variable can be basic for any given row. */
500 vector<float> basic_coeff(n_rows, 0.0f);
501 const vector<float> &constants = columns.back().values;
502 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
504 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)
507 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
508 basic = (i->values[j]==0.0f);
511 i->basic = i->values.size()-1;
512 basic_coeff[i->basic] = -i->values.front()/i->values.back();
518 // Price out the newly-created basic variables.
519 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
520 if(!i->values.empty())
522 for(unsigned j=0; j<i->values.size(); ++j)
523 i->values.front() += basic_coeff[j]*i->values[j];
527 void Layout::LinearProgram::add_artificial_variables()
529 vector<unsigned> artificial_rows(n_rows-1);
530 for(unsigned i=0; i<artificial_rows.size(); ++i)
531 artificial_rows[i] = i+1;
533 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
535 artificial_rows[i->basic-1] = 0;
536 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
538 /* Force all non-basic columns fully into existence and relocate objective
539 row to bottom in preparation of phase 1. A new objective row is calculated
540 by pricing out the constraint rows. */
541 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
544 float objective = 0.0f;
545 if(!i->values.empty())
547 objective = i->values.front();
548 i->values.front() = 0.0f;
549 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
550 if(*j<i->values.size())
551 i->values.front() += i->values[*j];
553 i->values.resize(n_rows+1, 0.0f);
554 i->values.back() = objective;
557 if(artificial_rows.empty())
560 /* Create artificial variables for phase 1. This ensures that each row has
561 a basic variable associated with it. The original objective row already
562 contains the implicit objective variable, which is basic. */
563 columns.resize(n_columns+artificial_rows.size());
564 columns.back() = columns[n_columns-1];
565 columns[n_columns-1].values.clear();
566 for(unsigned i=0; i<artificial_rows.size(); ++i)
567 columns[n_columns+i-1].basic = artificial_rows[i];
570 void Layout::LinearProgram::remove_artificial_variables()
572 /* See if any artificial variables are still basic. This could be because
573 the program is degenerate. To avoid trouble later on, use pivots to make
574 some of the original variables basic instead.
576 I don't fully understand why this is needed, but it appears to work. */
577 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
578 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
580 for(unsigned j=0; j+1<n_columns; ++j)
581 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
583 make_basic_column(j, columns[i].basic);
588 /* Get rid of the artificial variables and restore the original objective
589 row to form the phase 2 problem. */
590 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
591 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
594 i->values.front() = i->values.back();
595 i->values.pop_back();
599 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
601 /* Pick the row with the minimum ratio between the constant column and the
602 pivot column. This ensures that when the pivot column is made basic, values
603 in the constant column stay positive.
605 The use of n_rows instead of the true size of the column is intentional,
606 since the relocated objective row must be ignored in phase 1. */
607 float best = numeric_limits<float>::infinity();
609 for(unsigned i=1; i<n_rows; ++i)
610 if(columns[c].values[i]>0)
612 float ratio = columns.back().values[i]/columns[c].values[i];
623 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
625 /* Perform row transfer operations to make the pivot column basic,
626 containing a 1 on the pivot row. */
627 for(unsigned i=0; i<columns.size(); ++i)
628 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
632 columns[i].values.resize(columns.back().values.size(), 0.0f);
633 columns[i].values[columns[i].basic] = 1.0f;
634 columns[i].basic = 0;
637 float scale = columns[i].values[r]/columns[c].values[r];
639 columns[i].values[r] = scale;
640 for(unsigned j=0; j<columns[i].values.size(); ++j)
642 columns[i].values[j] -= scale*columns[c].values[j];
645 columns[c].basic = r;
646 columns[c].values.clear();
649 bool Layout::LinearProgram::pivot()
651 /* Pick a nonbasic column and make it basic. Requiring a positive objective
652 coefficient ensures that the objective function's value will decrease in the
654 for(unsigned i=0; i+1<columns.size(); ++i)
655 if(!columns[i].basic && columns[i].values.front()>0)
656 if(unsigned row = find_minimal_ratio(i))
658 make_basic_column(i, row);
666 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
671 float &Layout::LinearProgram::Row::operator[](unsigned c)
673 if(c>=linprog.n_columns)
674 throw out_of_range("Row::operator[]");
676 Column &column = linprog.columns[c];
677 if(column.values.size()<=index)
678 column.values.resize(index+1);
680 return column.values[index];
683 float &Layout::LinearProgram::Row::back()
685 return (*this)[linprog.n_columns-1];
689 Layout::LinearProgram::Column::Column():