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);
225 solve_constraints(VERTICAL);
227 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
228 (*i)->widget.set_geometry((*i)->geom);
231 void Layout::solve_constraints(int dir)
233 Pointers &ptrs = pointers[dir&VERTICAL];
235 const Geometry &geom = container->get_geometry();
236 if(geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
239 /* Set up a linear program to solve the constraints. The program matrix has
240 five columns for each widget, and one constant column. The first and second
241 columns of a widget are its position and dimension, respectively. The
242 remaining three are slack columns; see below for their purposes. */
243 LinearProgram linprog(slots.size()*5+1);
244 float weight = slots.size();
245 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
247 linprog.get_objective_row()[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
248 linprog.get_objective_row()[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
251 // Prevent the widget from going past the container's low edge.
252 LinearProgram::Row row = linprog.add_row();
253 row[(*i)->index*5] = 1;
254 row[(*i)->index*5+2] = -1;
255 row.back() = margin.*(ptrs.low_margin);
259 // Prevent the widget from going past the container's high edge.
260 LinearProgram::Row row = linprog.add_row();
261 row[(*i)->index*5] = 1;
262 row[(*i)->index*5+1] = 1;
263 row[(*i)->index*5+3] = 1;
264 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
268 /* Only allow the widget's dimension to increase. The geometry has
269 previously been set to the smallest allowable size. */
270 LinearProgram::Row row = linprog.add_row();
271 row[(*i)->index*5+1] = 1;
272 row[(*i)->index*5+4] = -1;
273 row.back() = (*i)->autosize_geom.*(ptrs.dim);
276 /* Add rows for user-defined constraints. Below/above and left/right of
277 constraints are always added in pairs, so it's only necessary to create a
279 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
280 if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
282 LinearProgram::Row row = linprog.add_row();
284 row[(*i)->index*5] = 1;
286 row[(*i)->index*5+1] = 1;
287 if(j->type&TARGET_POS)
288 row[j->target.index*5] = -1;
289 if(j->type&TARGET_DIM)
290 row[j->target.index*5+1] = -1;
292 row.back() = this->*(ptrs.spacing);
299 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
301 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
302 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
307 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
313 Layout::Packing::Packing():
319 Layout::Slot::Slot(Layout &l, Widget &w):
324 vert_pack.gravity = 1;
325 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
327 autosize_geom = widget.get_geometry();
330 void Layout::Slot::autosize_changed()
333 autosize_geom = widget.get_geometry();
335 // If the widget fits in the area it had, just leave it there.
336 if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
337 widget.set_geometry(geom);
343 Layout::LinearProgram::LinearProgram(unsigned s):
351 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
353 return Row(*this, n_rows++);
356 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
359 throw out_of_range("LinearProgram::operator[]");
361 return Row(*this, r);
364 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
366 return Row(*this, 0);
369 float Layout::LinearProgram::get_variable(unsigned i)
371 if(!solved || infeasible)
372 throw logic_error("not solved");
374 throw out_of_range("LinearProgram::get_variable");
376 if(unsigned r = columns[i].basic)
377 return columns.back().values[r];
382 bool Layout::LinearProgram::solve()
384 if(solved || infeasible)
387 /* Solve the program using the simplex method. The column representing the
388 objective variable is kept implicit, as it would never change during the
389 execution of the algorithm. */
393 add_artificial_variables();
395 // Solve the phase 1 problem.
398 /* All artificial variables should now be non-basic and thus zero, so the
399 objective function's value should also be zero. If it isn't, the original
400 program can't be solved. */
401 if(columns.back().values.front())
407 remove_artificial_variables();
409 // Solve the phase 2 problem. We already know it to be feasible.
417 void Layout::LinearProgram::prepare_columns()
419 /* See if any variables are already basic. A basic variable must only have
420 a nonzero coefficient on one row, and its product with the constant column
421 must not be negative. Only one variable can be basic for any given row. */
422 vector<float> basic_coeff(n_rows, 0.0f);
423 const vector<float> &constants = columns.back().values;
424 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
426 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)
429 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
430 basic = (i->values[j]==0.0f);
433 i->basic = i->values.size()-1;
434 basic_coeff[i->basic] = -i->values.front()/i->values.back();
440 // Price out the newly-created basic variables.
441 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
442 if(!i->values.empty())
444 for(unsigned j=0; j<i->values.size(); ++j)
445 i->values.front() += basic_coeff[j]*i->values[j];
449 void Layout::LinearProgram::add_artificial_variables()
451 vector<unsigned> artificial_rows(n_rows-1);
452 for(unsigned i=0; i<artificial_rows.size(); ++i)
453 artificial_rows[i] = i+1;
455 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
457 artificial_rows[i->basic-1] = 0;
458 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
460 /* Force all non-basic columns fully into existence and relocate objective
461 row to bottom in preparation of phase 1. A new objective row is calculated
462 by pricing out the constraint rows. */
463 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
466 float objective = 0.0f;
467 if(!i->values.empty())
469 objective = i->values.front();
470 i->values.front() = 0.0f;
471 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
472 if(*j<i->values.size())
473 i->values.front() += i->values[*j];
475 i->values.resize(n_rows+1, 0.0f);
476 i->values.back() = objective;
479 if(artificial_rows.empty())
482 /* Create artificial variables for phase 1. This ensures that each row has
483 a basic variable associated with it. The original objective row already
484 contains the implicit objective variable, which is basic. */
485 columns.resize(n_columns+artificial_rows.size());
486 columns.back() = columns[n_columns-1];
487 columns[n_columns-1].values.clear();
488 for(unsigned i=0; i<artificial_rows.size(); ++i)
489 columns[n_columns+i-1].basic = artificial_rows[i];
492 void Layout::LinearProgram::remove_artificial_variables()
494 /* See if any artificial variables are still basic. This could be because
495 the program is degenerate. To avoid trouble later on, use pivots to make
496 some of the original variables basic instead.
498 I don't fully understand why this is needed, but it appears to work. */
499 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
500 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
502 for(unsigned j=0; j+1<n_columns; ++j)
503 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
505 make_basic_column(j, columns[i].basic);
510 /* Get rid of the artificial variables and restore the original objective
511 row to form the phase 2 problem. */
512 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
513 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
516 i->values.front() = i->values.back();
517 i->values.pop_back();
521 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
523 /* Pick the row with the minimum ratio between the constant column and the
524 pivot column. This ensures that when the pivot column is made basic, values
525 in the constant column stay positive.
527 The use of n_rows instead of the true size of the column is intentional,
528 since the relocated objective row must be ignored in phase 1. */
529 float best = numeric_limits<float>::infinity();
531 for(unsigned i=1; i<n_rows; ++i)
532 if(columns[c].values[i]>0)
534 float ratio = columns.back().values[i]/columns[c].values[i];
545 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
547 /* Perform row transfer operations to make the pivot column basic,
548 containing a 1 on the pivot row. */
549 for(unsigned i=0; i<columns.size(); ++i)
550 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
554 columns[i].values.resize(columns.back().values.size(), 0.0f);
555 columns[i].values[columns[i].basic] = 1.0f;
556 columns[i].basic = 0;
559 float scale = columns[i].values[r]/columns[c].values[r];
561 columns[i].values[r] = scale;
562 for(unsigned j=0; j<columns[i].values.size(); ++j)
564 columns[i].values[j] -= scale*columns[c].values[j];
567 columns[c].basic = r;
568 columns[c].values.clear();
571 bool Layout::LinearProgram::pivot()
573 /* Pick a nonbasic column and make it basic. Requiring a positive objective
574 coefficient ensures that the objective function's value will decrease in the
576 for(unsigned i=0; i+1<columns.size(); ++i)
577 if(!columns[i].basic && columns[i].values.front()>0)
578 if(unsigned row = find_minimal_ratio(i))
580 make_basic_column(i, row);
588 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
593 float &Layout::LinearProgram::Row::operator[](unsigned c)
595 if(c>=linprog.n_columns)
596 throw out_of_range("Row::operator[]");
598 Column &column = linprog.columns[c];
599 if(column.values.size()<=index)
600 column.values.resize(index+1);
602 return column.values[index];
605 float &Layout::LinearProgram::Row::back()
607 return (*this)[linprog.n_columns-1];
611 Layout::LinearProgram::Column::Column():