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)
207 return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
210 void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
213 throw invalid_argument("&src==&tgt");
215 Slot &src_slot = get_slot_for_widget(src);
216 Slot &tgt_slot = get_slot_for_widget(tgt);
218 for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
219 if(i->type==type && &i->target==&tgt_slot)
222 src_slot.constraints.push_back(Constraint(type, tgt_slot));
223 src_slot.constraints.back().spacing = sp;
224 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
225 tgt_slot.constraints.back().spacing = sp;
230 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
232 create_constraint(src, type, tgt, -1);
235 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
237 create_constraint(src, type, tgt, spacing);
240 void Layout::set_gravity(Widget &wdg, int h, int v)
242 Slot &slot = get_slot_for_widget(wdg);
244 slot.horiz_pack.gravity = h;
245 slot.vert_pack.gravity = v;
250 void Layout::set_expand(Widget &wdg, bool h, bool v)
252 Slot &slot = get_slot_for_widget(wdg);
254 slot.horiz_pack.expand = h;
255 slot.vert_pack.expand = v;
260 void Layout::update()
262 solve_constraints(HORIZONTAL, UPDATE);
263 solve_constraints(VERTICAL, UPDATE);
265 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
266 (*i)->widget.set_geometry((*i)->geom);
269 void Layout::autosize()
271 solve_constraints(HORIZONTAL, AUTOSIZE);
272 solve_constraints(VERTICAL, AUTOSIZE);
274 container->set_size(autosize_geom.w, autosize_geom.h);
277 void Layout::solve_constraints(int dir, SolveMode mode)
279 Pointers &ptrs = pointers[dir&VERTICAL];
281 const Geometry &geom = container->get_geometry();
282 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
285 /* Set up a linear program to solve the constraints. The program matrix has
286 five columns for each widget, and one constant column. The first and second
287 columns of a widget are its position and dimension, respectively. The
288 remaining three are slack columns; see below for their purposes. */
289 LinearProgram linprog(n_active_slots*5+1);
290 float weight = slots.size();
291 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
296 LinearProgram::Row objective = linprog.get_objective_row();
299 objective[(*i)->index*5] = -1;
300 objective[(*i)->index*5+1] = -1;
304 objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
305 objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
309 // Prevent the widget from going past the container's low edge.
310 LinearProgram::Row row = linprog.add_row();
311 row[(*i)->index*5] = 1;
312 row[(*i)->index*5+2] = -1;
313 row.back() = margin.*(ptrs.low_margin);
318 // Prevent the widget from going past the container's high edge.
319 LinearProgram::Row row = linprog.add_row();
320 row[(*i)->index*5] = 1;
321 row[(*i)->index*5+1] = 1;
322 row[(*i)->index*5+3] = 1;
323 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
326 if(((*i)->*(ptrs.packing)).gravity==0)
328 /* This forces the widget's distance from the left and right edge of
329 the container to be equal. It's a bit of a hack, but more time and
330 thought is needed for a better solution. */
331 LinearProgram::Row row = linprog.add_row();
332 row[(*i)->index*5+2] = 1;
333 row[(*i)->index*5+3] = -1;
337 /* Don't allow the widget's dimension to get below that determined
339 LinearProgram::Row row = linprog.add_row();
340 row[(*i)->index*5+1] = 1;
341 row[(*i)->index*5+4] = -1;
342 row.back() = (*i)->autosize_geom.*(ptrs.dim);
345 /* Add rows for user-defined constraints. Constraints are always added
346 in pairs, so it's only necessary to create a row for one half. */
347 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
348 if(j->target.index>(*i)->index && (j->type&1)==dir)
350 LinearProgram::Row row = linprog.add_row();
351 float polarity = ((j->type&SELF_DIM) ? -1 : 1);
353 row[(*i)->index*5] = polarity;
355 row[(*i)->index*5+1] = polarity;
356 if(j->type&TARGET_POS)
357 row[j->target.index*5] = -polarity;
358 if(j->type&TARGET_DIM)
359 row[j->target.index*5+1] = -polarity;
361 row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
370 autosize_geom.*(ptrs.dim) = 0;
371 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
374 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
375 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
380 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
383 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
384 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
390 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
397 Layout::Packing::Packing():
403 Layout::Slot::Slot(Layout &l, Widget &w):
408 vert_pack.gravity = 1;
409 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
410 widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
412 autosize_geom = widget.get_geometry();
415 void Layout::Slot::autosize_changed()
418 autosize_geom = widget.get_geometry();
420 if(!widget.is_visible())
423 // If the widget fits in the area it had, just leave it there.
424 if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
425 widget.set_geometry(geom);
428 layout.container->signal_autosize_changed.emit();
433 void Layout::Slot::visibility_changed(bool v)
435 layout.update_slot_indices();
438 layout.container->signal_autosize_changed.emit();
444 Layout::LinearProgram::LinearProgram(unsigned s):
452 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
454 return Row(*this, n_rows++);
457 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
460 throw out_of_range("LinearProgram::operator[]");
462 return Row(*this, r);
465 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
467 return Row(*this, 0);
470 float Layout::LinearProgram::get_variable(unsigned i)
472 if(!solved || infeasible)
473 throw logic_error("not solved");
475 throw out_of_range("LinearProgram::get_variable");
477 if(unsigned r = columns[i].basic)
478 return columns.back().values[r];
483 bool Layout::LinearProgram::solve()
485 if(solved || infeasible)
488 /* Solve the program using the simplex method. The column representing the
489 objective variable is kept implicit, as it would never change during the
490 execution of the algorithm. */
494 add_artificial_variables();
496 // Solve the phase 1 problem.
499 /* All artificial variables should now be non-basic and thus zero, so the
500 objective function's value should also be zero. If it isn't, the original
501 program can't be solved. */
502 if(columns.back().values.front())
508 remove_artificial_variables();
510 // Solve the phase 2 problem. We already know it to be feasible.
518 void Layout::LinearProgram::prepare_columns()
520 /* See if any variables are already basic. A basic variable must only have
521 a nonzero coefficient on one row, and its product with the constant column
522 must not be negative. Only one variable can be basic for any given row. */
523 vector<float> obj_coeff(n_rows, 0.0f);
524 vector<float> row_coeff(n_rows, 1.0f);
525 const vector<float> &constants = columns.back().values;
526 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
528 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)
531 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
532 basic = (i->values[j]==0.0f);
535 i->basic = i->values.size()-1;
536 row_coeff[i->basic] = 1.0f/i->values.back();
537 obj_coeff[i->basic] = -i->values.front();
543 // Price out the newly-created basic variables.
544 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
545 if(!i->values.empty())
547 for(unsigned j=0; j<i->values.size(); ++j)
549 i->values[j] *= row_coeff[j];
550 i->values.front() += obj_coeff[j]*i->values[j];
555 void Layout::LinearProgram::add_artificial_variables()
557 vector<unsigned> artificial_rows(n_rows-1);
558 for(unsigned i=0; i<artificial_rows.size(); ++i)
559 artificial_rows[i] = i+1;
561 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
563 artificial_rows[i->basic-1] = 0;
564 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
566 /* Force all non-basic columns fully into existence and relocate objective
567 row to bottom in preparation of phase 1. A new objective row is calculated
568 by pricing out the constraint rows. */
569 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
572 float objective = 0.0f;
573 if(!i->values.empty())
575 objective = i->values.front();
576 i->values.front() = 0.0f;
577 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
578 if(*j<i->values.size())
579 i->values.front() += i->values[*j];
581 i->values.resize(n_rows+1, 0.0f);
582 i->values.back() = objective;
585 if(artificial_rows.empty())
588 /* Create artificial variables for phase 1. This ensures that each row has
589 a basic variable associated with it. The original objective row already
590 contains the implicit objective variable, which is basic. */
591 columns.resize(n_columns+artificial_rows.size());
592 columns.back() = columns[n_columns-1];
593 columns[n_columns-1].values.clear();
594 for(unsigned i=0; i<artificial_rows.size(); ++i)
595 columns[n_columns+i-1].basic = artificial_rows[i];
598 void Layout::LinearProgram::remove_artificial_variables()
600 /* See if any artificial variables are still basic. This could be because
601 the program is degenerate. To avoid trouble later on, use pivots to make
602 some of the original variables basic instead.
604 I don't fully understand why this is needed, but it appears to work. */
605 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
606 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
608 for(unsigned j=0; j+1<n_columns; ++j)
609 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
611 make_basic_column(j, columns[i].basic);
616 /* Get rid of the artificial variables and restore the original objective
617 row to form the phase 2 problem. */
618 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
619 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
622 i->values.front() = i->values.back();
623 i->values.pop_back();
627 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
629 /* Pick the row with the minimum ratio between the constant column and the
630 pivot column. This ensures that when the pivot column is made basic, values
631 in the constant column stay positive.
633 The use of n_rows instead of the true size of the column is intentional,
634 since the relocated objective row must be ignored in phase 1. */
635 float best = numeric_limits<float>::infinity();
637 for(unsigned i=1; i<n_rows; ++i)
638 if(columns[c].values[i]>0)
640 float ratio = columns.back().values[i]/columns[c].values[i];
651 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
653 /* Perform row transfer operations to make the pivot column basic,
654 containing a 1 on the pivot row. */
655 for(unsigned i=0; i<columns.size(); ++i)
656 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
660 columns[i].values.resize(columns.back().values.size(), 0.0f);
661 columns[i].values[columns[i].basic] = 1.0f;
662 columns[i].basic = 0;
665 float scale = columns[i].values[r]/columns[c].values[r];
667 columns[i].values[r] = scale;
668 for(unsigned j=0; j<columns[i].values.size(); ++j)
670 columns[i].values[j] -= scale*columns[c].values[j];
673 columns[c].basic = r;
674 columns[c].values.clear();
677 bool Layout::LinearProgram::pivot()
679 /* Pick a nonbasic column and make it basic. Requiring a positive objective
680 coefficient ensures that the objective function's value will decrease in the
682 for(unsigned i=0; i+1<columns.size(); ++i)
683 if(!columns[i].basic && columns[i].values.front()>0)
684 if(unsigned row = find_minimal_ratio(i))
686 make_basic_column(i, row);
694 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
699 float &Layout::LinearProgram::Row::operator[](unsigned c)
701 if(c>=linprog.n_columns)
702 throw out_of_range("Row::operator[]");
704 Column &column = linprog.columns[c];
705 if(column.values.size()<=index)
706 column.values.resize(index+1);
708 return column.values[index];
711 float &Layout::LinearProgram::Row::back()
713 return (*this)[linprog.n_columns-1];
717 Layout::LinearProgram::Column::Column():