3 #include <msp/core/maputils.h>
4 #include <msp/strings/format.h>
5 #include "arrangement.h"
15 class Layout::LinearProgram
21 LinearProgram &linprog;
25 Row(LinearProgram &, unsigned);
27 float &operator[](unsigned);
35 std::vector<float> values;
42 std::vector<Column> columns;
47 LinearProgram(unsigned);
50 Row operator[](unsigned);
51 Row get_objective_row();
52 float get_variable(unsigned);
55 void prepare_columns();
56 void add_artificial_variables();
57 void remove_artificial_variables();
58 unsigned find_minimal_ratio(unsigned);
59 void make_basic_column(unsigned, unsigned);
64 struct Layout::Pointers
67 unsigned Geometry::*dim;
68 Packing Slot::*packing;
69 unsigned Sides::*low_margin;
70 unsigned Sides::*high_margin;
71 unsigned Layout::*spacing;
74 Layout::Pointers Layout::pointers[2] =
76 &Geometry::x, &Geometry::w,
78 &Sides::left, &Sides::right,
81 &Geometry::y, &Geometry::h,
83 &Sides::bottom, &Sides::top,
101 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
105 void Layout::set_container(Container &c)
108 throw logic_error("container!=0");
113 void Layout::set_margin(const Sides &m)
120 void Layout::set_spacing(unsigned s)
128 void Layout::set_row_spacing(unsigned s)
135 void Layout::set_column_spacing(unsigned s)
142 void Layout::push_arrangement(Arrangement &arr)
144 arrangement_stack.push_back(&arr);
147 Arrangement *Layout::get_arrangement() const
149 if(arrangement_stack.empty())
152 return arrangement_stack.back();
155 void Layout::pop_arrangement(Arrangement &arr)
157 list<Arrangement *>::iterator begin = find(arrangement_stack.begin(), arrangement_stack.end(), &arr);
158 if(begin==arrangement_stack.end())
163 Arrangement *top = arrangement_stack.back();
164 arrangement_stack.pop_back();
165 if(!arrangement_stack.empty())
166 arrangement_stack.back()->arrange(*top);
172 void Layout::add_widget(Widget &wdg)
175 throw logic_error("!container");
177 slots.push_back(new Slot(*this, wdg));
178 update_slot_indices();
179 if(!arrangement_stack.empty())
180 arrangement_stack.back()->arrange(wdg);
185 void Layout::remove_widget(Widget &wdg)
187 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
188 if(&(*i)->widget==&wdg)
190 for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
193 for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
196 (*j)->constraints.erase(k++);
205 update_slot_indices();
211 void Layout::update_slot_indices()
214 unsigned n_floating = 0;
215 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
217 if((*i)->widget.is_visible() || (*i)->ghost)
219 (*i)->index = n_active_slots++;
227 n_slack_vars[0] = n_floating*2;
228 n_slack_vars[1] = n_floating*2;
229 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
234 for(unsigned j=0; j<2; ++j)
235 if(((*i)->*(pointers[j].packing)).gravity==0)
236 n_slack_vars[j] += 2;
239 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
240 if(j->target.index>(*i)->index && (j->type&SLACK))
241 ++n_slack_vars[j->type&1];
245 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
247 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
248 if(&(*i)->widget==&wdg)
251 throw hierarchy_error("widget not in layout");
254 Layout::ConstraintType Layout::complement(ConstraintType type)
256 return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
259 void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
262 throw invalid_argument("Layout::create_constraint");
264 Slot &src_slot = get_slot_for_widget(src);
265 Slot &tgt_slot = get_slot_for_widget(tgt);
267 for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
268 if(i->type==type && &i->target==&tgt_slot)
271 src_slot.constraints.push_back(Constraint(type, tgt_slot));
272 src_slot.constraints.back().spacing = sp;
273 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
274 tgt_slot.constraints.back().spacing = sp;
276 update_slot_indices();
280 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
282 create_constraint(src, type, tgt, -1);
285 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
287 create_constraint(src, type, tgt, spacing);
290 void Layout::set_gravity(Widget &wdg, int h, int v)
292 Slot &slot = get_slot_for_widget(wdg);
294 slot.horiz_pack.gravity = h;
295 slot.vert_pack.gravity = v;
297 update_slot_indices();
301 void Layout::set_expand(Widget &wdg, bool h, bool v)
303 Slot &slot = get_slot_for_widget(wdg);
305 slot.horiz_pack.expand = h;
306 slot.vert_pack.expand = v;
311 void Layout::set_ghost(Widget &wdg, bool g)
313 Slot &slot = get_slot_for_widget(wdg);
317 if(!wdg.is_visible())
319 update_slot_indices();
324 void Layout::set_floating(Widget &wdg, bool f)
326 Slot &slot = get_slot_for_widget(wdg);
330 update_slot_indices();
334 void Layout::update()
336 solve_constraints(HORIZONTAL, UPDATE);
337 solve_constraints(VERTICAL, UPDATE);
339 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
340 (*i)->widget.set_geometry((*i)->geom);
343 void Layout::autosize(Geometry &geom)
345 solve_constraints(HORIZONTAL, AUTOSIZE);
346 solve_constraints(VERTICAL, AUTOSIZE);
348 geom.w = max(geom.w, autosize_geom.w);
349 geom.h = max(geom.h, autosize_geom.h);
352 void Layout::solve_constraints(int dir, SolveMode mode)
354 Pointers &ptrs = pointers[dir&VERTICAL];
356 const Geometry &geom = container->get_geometry();
357 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
360 /* Set up a linear program to solve the constraints. The program matrix has
361 five columns for each widget, and one constant column. The first and second
362 columns of a widget are its position and dimension, respectively. The
363 remaining three are slack columns; see below for their purposes. */
364 LinearProgram linprog(n_active_slots*5+n_slack_vars[dir]+1);
365 float weight = slots.size()+1;
366 unsigned k = n_active_slots*5;
367 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
372 LinearProgram::Row objective = linprog.get_objective_row();
375 objective[(*i)->index*5] = -1;
376 objective[(*i)->index*5+1] = -1;
381 objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
382 objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
386 // Prevent the widget from going past the container's low edge.
387 LinearProgram::Row row = linprog.add_row();
388 row[(*i)->index*5] = 1;
389 row[(*i)->index*5+2] = -1;
390 row.back() = margin.*(ptrs.low_margin);
395 // Prevent the widget from going past the container's high edge.
396 LinearProgram::Row row = linprog.add_row();
397 row[(*i)->index*5] = 1;
398 row[(*i)->index*5+1] = 1;
399 row[(*i)->index*5+3] = 1;
400 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
403 if((*i)->floating || ((*i)->*(ptrs.packing)).gravity==0)
405 /* Try to keep the widget as close to a target position as possible.
406 Since linear programs can't express absolute values directly, use two
407 opposing slack variables that are optimized for a low value. */
408 float a = ((*i)->*(ptrs.packing)).gravity*0.5+0.5;
409 LinearProgram::Row row = linprog.add_row();
410 row[(*i)->index*5] = 1;
411 row[(*i)->index*5+1] = a;
416 const Geometry &cgeom = (*i)->widget.get_geometry();
417 row.back() = cgeom.*(ptrs.pos)+cgeom.*(ptrs.dim)*a;
420 row.back() = geom.*(ptrs.dim)/2;
427 /* Don't allow the widget's dimension to get below that determined
429 LinearProgram::Row row = linprog.add_row();
430 row[(*i)->index*5+1] = 1;
431 row[(*i)->index*5+4] = -1;
432 row.back() = (*i)->autosize_geom.*(ptrs.dim);
435 /* Add rows for user-defined constraints. Constraints are always added
436 in pairs, so it's only necessary to create a row for one half. */
437 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
438 if(j->target.index>(*i)->index && (j->type&1)==dir)
440 LinearProgram::Row row = linprog.add_row();
441 float polarity = ((j->type&SELF_DIM) ? -1 : 1);
443 row[(*i)->index*5] = polarity;
445 row[(*i)->index*5+1] = polarity;
446 if(j->type&TARGET_POS)
447 row[j->target.index*5] = -polarity;
448 if(j->type&TARGET_DIM)
449 row[j->target.index*5+1] = -polarity;
451 row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
462 autosize_geom.*(ptrs.dim) = 0;
463 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
466 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
467 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
472 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
475 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
476 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
482 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
489 Layout::Packing::Packing():
495 Layout::Slot::Slot(Layout &l, Widget &w):
502 vert_pack.gravity = 1;
503 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
504 widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
505 widget.autosize(autosize_geom);
508 void Layout::Slot::autosize_changed()
510 widget.autosize(autosize_geom);
512 if(!widget.is_visible() && !ghost)
515 // Only trigger an update if the widget won't fit in its current area.
516 if(autosize_geom.w>geom.w || autosize_geom.h>geom.h)
518 layout.container->signal_autosize_changed.emit();
523 void Layout::Slot::visibility_changed(bool v)
525 layout.update_slot_indices();
528 layout.container->signal_autosize_changed.emit();
534 Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
535 DataFile::ObjectLoader<Layout>(l),
538 add("column_spacing", &Loader::column_spacing);
539 add("margin", &Loader::margin);
540 add("row_spacing", &Loader::row_spacing);
541 add("spacing", &Loader::spacing);
542 add("widget", &Loader::widget);
545 void Layout::Loader::column_spacing(unsigned s)
547 obj.set_column_spacing(s);
550 void Layout::Loader::margin()
554 obj.set_margin(sides);
557 void Layout::Loader::spacing(unsigned s)
562 void Layout::Loader::row_spacing(unsigned s)
564 obj.set_row_spacing(s);
567 void Layout::Loader::widget(const string &n)
569 Widget &wdg = *get_item(wdg_map, n);
570 WidgetLoader ldr(obj, wdg, wdg_map);
575 Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
580 add("constraint", &WidgetLoader::constraint);
581 add("expand", &WidgetLoader::expand);
582 add("ghost", &WidgetLoader::ghost);
583 add("gravity", &WidgetLoader::gravity);
586 void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
588 Widget &target = *get_item(wdg_map, n);
589 layout.add_constraint(widget, type, target);
592 void Layout::WidgetLoader::expand(bool h, bool v)
594 layout.set_expand(widget, h, v);
597 void Layout::WidgetLoader::ghost(bool g)
599 layout.set_ghost(widget, g);
602 void Layout::WidgetLoader::gravity(int h, int v)
604 layout.set_gravity(widget, h, v);
608 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
610 const string &str = conv.get();
612 ctype = Layout::ABOVE;
613 else if(str=="BELOW")
614 ctype = Layout::BELOW;
615 else if(str=="RIGHT_OF")
616 ctype = Layout::RIGHT_OF;
617 else if(str=="LEFT_OF")
618 ctype = Layout::LEFT_OF;
619 else if(str=="FAR_ABOVE")
620 ctype = Layout::FAR_ABOVE;
621 else if(str=="FAR_BELOW")
622 ctype = Layout::FAR_BELOW;
623 else if(str=="FAR_RIGHT_OF")
624 ctype = Layout::FAR_RIGHT_OF;
625 else if(str=="FAR_LEFT_OF")
626 ctype = Layout::FAR_LEFT_OF;
627 else if(str=="ALIGN_TOP")
628 ctype = Layout::ALIGN_TOP;
629 else if(str=="ALIGN_BOTTOM")
630 ctype = Layout::ALIGN_BOTTOM;
631 else if(str=="ALIGN_RIGHT")
632 ctype = Layout::ALIGN_RIGHT;
633 else if(str=="ALIGN_LEFT")
634 ctype = Layout::ALIGN_LEFT;
635 else if(str=="COPY_WIDTH")
636 ctype = Layout::COPY_WIDTH;
637 else if(str=="COPY_HEIGHT")
638 ctype = Layout::COPY_HEIGHT;
640 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
644 Layout::LinearProgram::LinearProgram(unsigned s):
652 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
654 return Row(*this, n_rows++);
657 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
660 throw out_of_range("LinearProgram::operator[]");
662 return Row(*this, r);
665 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
667 return Row(*this, 0);
670 float Layout::LinearProgram::get_variable(unsigned i)
672 if(!solved || infeasible)
673 throw logic_error("not solved");
675 throw out_of_range("LinearProgram::get_variable");
677 if(unsigned r = columns[i].basic)
678 return columns.back().values[r];
683 bool Layout::LinearProgram::solve()
685 if(solved || infeasible)
688 /* Solve the program using the simplex method. The column representing the
689 objective variable is kept implicit, as it would never change during the
690 execution of the algorithm. */
694 add_artificial_variables();
696 // Solve the phase 1 problem.
699 /* All artificial variables should now be non-basic and thus zero, so the
700 objective function's value should also be zero. If it isn't, the original
701 program can't be solved. */
702 if(columns.back().values.front())
708 remove_artificial_variables();
710 // Solve the phase 2 problem. We already know it to be feasible.
718 void Layout::LinearProgram::prepare_columns()
720 /* See if any variables are already basic. A basic variable must only have
721 a nonzero coefficient on one row, and its product with the constant column
722 must not be negative. Only one variable can be basic for any given row. */
723 vector<float> obj_coeff(n_rows, 0.0f);
724 vector<float> row_coeff(n_rows, 1.0f);
725 const vector<float> &constants = columns.back().values;
726 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
728 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)
731 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
732 basic = (i->values[j]==0.0f);
735 i->basic = i->values.size()-1;
736 row_coeff[i->basic] = 1.0f/i->values.back();
737 obj_coeff[i->basic] = -i->values.front();
743 // Price out the newly-created basic variables.
744 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
745 if(!i->values.empty())
747 for(unsigned j=0; j<i->values.size(); ++j)
749 i->values[j] *= row_coeff[j];
750 i->values.front() += obj_coeff[j]*i->values[j];
755 void Layout::LinearProgram::add_artificial_variables()
757 vector<unsigned> artificial_rows(n_rows-1);
758 for(unsigned i=0; i<artificial_rows.size(); ++i)
759 artificial_rows[i] = i+1;
761 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
763 artificial_rows[i->basic-1] = 0;
764 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
766 /* Force all non-basic columns fully into existence and relocate objective
767 row to bottom in preparation of phase 1. A new objective row is calculated
768 by pricing out the constraint rows. */
769 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
772 float objective = 0.0f;
773 if(!i->values.empty())
775 objective = i->values.front();
776 i->values.front() = 0.0f;
777 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
778 if(*j<i->values.size())
779 i->values.front() += i->values[*j];
781 i->values.resize(n_rows+1, 0.0f);
782 i->values.back() = objective;
785 if(artificial_rows.empty())
788 /* Create artificial variables for phase 1. This ensures that each row has
789 a basic variable associated with it. The original objective row already
790 contains the implicit objective variable, which is basic. */
791 columns.resize(n_columns+artificial_rows.size());
792 columns.back() = columns[n_columns-1];
793 columns[n_columns-1].values.clear();
794 for(unsigned i=0; i<artificial_rows.size(); ++i)
795 columns[n_columns+i-1].basic = artificial_rows[i];
798 void Layout::LinearProgram::remove_artificial_variables()
800 /* See if any artificial variables are still basic. This could be because
801 the program is degenerate. To avoid trouble later on, use pivots to make
802 some of the original variables basic instead.
804 I don't fully understand why this is needed, but it appears to work. */
805 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
806 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
808 for(unsigned j=0; j+1<n_columns; ++j)
809 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
811 make_basic_column(j, columns[i].basic);
816 /* Get rid of the artificial variables and restore the original objective
817 row to form the phase 2 problem. */
818 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
819 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
822 i->values.front() = i->values.back();
823 i->values.pop_back();
827 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
829 /* Pick the row with the minimum ratio between the constant column and the
830 pivot column. This ensures that when the pivot column is made basic, values
831 in the constant column stay positive.
833 The use of n_rows instead of the true size of the column is intentional,
834 since the relocated objective row must be ignored in phase 1. */
835 float best = numeric_limits<float>::infinity();
837 for(unsigned i=1; i<n_rows; ++i)
838 if(columns[c].values[i]>0)
840 float ratio = columns.back().values[i]/columns[c].values[i];
851 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
853 /* Perform row transfer operations to make the pivot column basic,
854 containing a 1 on the pivot row. */
855 for(unsigned i=0; i<columns.size(); ++i)
856 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
860 columns[i].values.resize(columns.back().values.size(), 0.0f);
861 columns[i].values[columns[i].basic] = 1.0f;
862 columns[i].basic = 0;
865 float scale = columns[i].values[r]/columns[c].values[r];
867 columns[i].values[r] = scale;
868 for(unsigned j=0; j<columns[i].values.size(); ++j)
870 columns[i].values[j] -= scale*columns[c].values[j];
873 columns[c].basic = r;
874 columns[c].values.clear();
877 bool Layout::LinearProgram::pivot()
879 /* Pick a nonbasic column and make it basic. Requiring a positive objective
880 coefficient ensures that the objective function's value will decrease in the
882 for(unsigned i=0; i+1<columns.size(); ++i)
883 if(!columns[i].basic && columns[i].values.front()>0)
884 if(unsigned row = find_minimal_ratio(i))
886 make_basic_column(i, row);
894 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
899 float &Layout::LinearProgram::Row::operator[](unsigned c)
901 if(c>=linprog.n_columns)
902 throw out_of_range("Row::operator[]");
904 Column &column = linprog.columns[c];
905 if(column.values.size()<=index)
906 column.values.resize(index+1);
908 return column.values[index];
911 float &Layout::LinearProgram::Row::back()
913 return (*this)[linprog.n_columns-1];
917 Layout::LinearProgram::Column::Column():