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);
442 float dim_weight = ((j->type&HALF_DIM) ? 0.5f : 1);
444 row[(*i)->index*5] = polarity;
446 row[(*i)->index*5+1] = polarity*dim_weight;
447 if(j->type&TARGET_POS)
448 row[j->target.index*5] = -polarity;
449 if(j->type&TARGET_DIM)
450 row[j->target.index*5+1] = -polarity*dim_weight;
452 row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
463 autosize_geom.*(ptrs.dim) = 0;
464 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
467 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
468 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
473 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
476 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
477 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
483 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
490 Layout::Packing::Packing():
496 Layout::Slot::Slot(Layout &l, Widget &w):
503 vert_pack.gravity = 1;
504 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
505 widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
506 widget.autosize(autosize_geom);
509 void Layout::Slot::autosize_changed()
511 widget.autosize(autosize_geom);
513 if(!widget.is_visible() && !ghost)
516 // Only trigger an update if the widget won't fit in its current area.
517 if(autosize_geom.w>geom.w || autosize_geom.h>geom.h)
519 layout.container->signal_autosize_changed.emit();
524 void Layout::Slot::visibility_changed(bool v)
526 layout.update_slot_indices();
529 layout.container->signal_autosize_changed.emit();
535 Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
536 DataFile::ObjectLoader<Layout>(l),
539 add("column_spacing", &Loader::column_spacing);
540 add("margin", &Loader::margin);
541 add("row_spacing", &Loader::row_spacing);
542 add("spacing", &Loader::spacing);
543 add("widget", &Loader::widget);
546 void Layout::Loader::column_spacing(unsigned s)
548 obj.set_column_spacing(s);
551 void Layout::Loader::margin()
555 obj.set_margin(sides);
558 void Layout::Loader::spacing(unsigned s)
563 void Layout::Loader::row_spacing(unsigned s)
565 obj.set_row_spacing(s);
568 void Layout::Loader::widget(const string &n)
570 Widget &wdg = *get_item(wdg_map, n);
571 WidgetLoader ldr(obj, wdg, wdg_map);
576 Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
581 add("constraint", &WidgetLoader::constraint);
582 add("expand", &WidgetLoader::expand);
583 add("ghost", &WidgetLoader::ghost);
584 add("gravity", &WidgetLoader::gravity);
587 void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
589 Widget &target = *get_item(wdg_map, n);
590 layout.add_constraint(widget, type, target);
593 void Layout::WidgetLoader::expand(bool h, bool v)
595 layout.set_expand(widget, h, v);
598 void Layout::WidgetLoader::ghost(bool g)
600 layout.set_ghost(widget, g);
603 void Layout::WidgetLoader::gravity(int h, int v)
605 layout.set_gravity(widget, h, v);
609 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
611 const string &str = conv.get();
613 ctype = Layout::ABOVE;
614 else if(str=="BELOW")
615 ctype = Layout::BELOW;
616 else if(str=="RIGHT_OF")
617 ctype = Layout::RIGHT_OF;
618 else if(str=="LEFT_OF")
619 ctype = Layout::LEFT_OF;
620 else if(str=="FAR_ABOVE")
621 ctype = Layout::FAR_ABOVE;
622 else if(str=="FAR_BELOW")
623 ctype = Layout::FAR_BELOW;
624 else if(str=="FAR_RIGHT_OF")
625 ctype = Layout::FAR_RIGHT_OF;
626 else if(str=="FAR_LEFT_OF")
627 ctype = Layout::FAR_LEFT_OF;
628 else if(str=="ALIGN_TOP")
629 ctype = Layout::ALIGN_TOP;
630 else if(str=="ALIGN_VCENTER")
631 ctype = Layout::ALIGN_VCENTER;
632 else if(str=="ALIGN_BOTTOM")
633 ctype = Layout::ALIGN_BOTTOM;
634 else if(str=="ALIGN_RIGHT")
635 ctype = Layout::ALIGN_RIGHT;
636 else if(str=="ALIGN_HCENTER")
637 ctype = Layout::ALIGN_HCENTER;
638 else if(str=="ALIGN_LEFT")
639 ctype = Layout::ALIGN_LEFT;
640 else if(str=="COPY_WIDTH")
641 ctype = Layout::COPY_WIDTH;
642 else if(str=="COPY_HEIGHT")
643 ctype = Layout::COPY_HEIGHT;
645 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
649 Layout::LinearProgram::LinearProgram(unsigned s):
657 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
659 return Row(*this, n_rows++);
662 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
665 throw out_of_range("LinearProgram::operator[]");
667 return Row(*this, r);
670 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
672 return Row(*this, 0);
675 float Layout::LinearProgram::get_variable(unsigned i)
677 if(!solved || infeasible)
678 throw logic_error("not solved");
680 throw out_of_range("LinearProgram::get_variable");
682 if(unsigned r = columns[i].basic)
683 return columns.back().values[r];
688 bool Layout::LinearProgram::solve()
690 if(solved || infeasible)
693 /* Solve the program using the simplex method. The column representing the
694 objective variable is kept implicit, as it would never change during the
695 execution of the algorithm. */
699 add_artificial_variables();
701 // Solve the phase 1 problem.
704 /* All artificial variables should now be non-basic and thus zero, so the
705 objective function's value should also be zero. If it isn't, the original
706 program can't be solved. */
707 if(columns.back().values.front())
713 remove_artificial_variables();
715 // Solve the phase 2 problem. We already know it to be feasible.
723 void Layout::LinearProgram::prepare_columns()
725 /* See if any variables are already basic. A basic variable must only have
726 a nonzero coefficient on one row, and its product with the constant column
727 must not be negative. Only one variable can be basic for any given row. */
728 vector<float> obj_coeff(n_rows, 0.0f);
729 vector<float> row_coeff(n_rows, 1.0f);
730 const vector<float> &constants = columns.back().values;
731 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
733 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)
736 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
737 basic = (i->values[j]==0.0f);
740 i->basic = i->values.size()-1;
741 row_coeff[i->basic] = 1.0f/i->values.back();
742 obj_coeff[i->basic] = -i->values.front();
748 // Price out the newly-created basic variables.
749 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
750 if(!i->values.empty())
752 for(unsigned j=0; j<i->values.size(); ++j)
754 i->values[j] *= row_coeff[j];
755 i->values.front() += obj_coeff[j]*i->values[j];
760 void Layout::LinearProgram::add_artificial_variables()
762 vector<unsigned> artificial_rows(n_rows-1);
763 for(unsigned i=0; i<artificial_rows.size(); ++i)
764 artificial_rows[i] = i+1;
766 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
768 artificial_rows[i->basic-1] = 0;
769 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
771 /* Force all non-basic columns fully into existence and relocate objective
772 row to bottom in preparation of phase 1. A new objective row is calculated
773 by pricing out the constraint rows. */
774 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
777 float objective = 0.0f;
778 if(!i->values.empty())
780 objective = i->values.front();
781 i->values.front() = 0.0f;
782 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
783 if(*j<i->values.size())
784 i->values.front() += i->values[*j];
786 i->values.resize(n_rows+1, 0.0f);
787 i->values.back() = objective;
790 if(artificial_rows.empty())
793 /* Create artificial variables for phase 1. This ensures that each row has
794 a basic variable associated with it. The original objective row already
795 contains the implicit objective variable, which is basic. */
796 columns.resize(n_columns+artificial_rows.size());
797 columns.back() = columns[n_columns-1];
798 columns[n_columns-1].values.clear();
799 for(unsigned i=0; i<artificial_rows.size(); ++i)
800 columns[n_columns+i-1].basic = artificial_rows[i];
803 void Layout::LinearProgram::remove_artificial_variables()
805 /* See if any artificial variables are still basic. This could be because
806 the program is degenerate. To avoid trouble later on, use pivots to make
807 some of the original variables basic instead.
809 I don't fully understand why this is needed, but it appears to work. */
810 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
811 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
813 for(unsigned j=0; j+1<n_columns; ++j)
814 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
816 make_basic_column(j, columns[i].basic);
821 /* Get rid of the artificial variables and restore the original objective
822 row to form the phase 2 problem. */
823 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
824 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
827 i->values.front() = i->values.back();
828 i->values.pop_back();
832 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
834 /* Pick the row with the minimum ratio between the constant column and the
835 pivot column. This ensures that when the pivot column is made basic, values
836 in the constant column stay positive.
838 The use of n_rows instead of the true size of the column is intentional,
839 since the relocated objective row must be ignored in phase 1. */
840 float best = numeric_limits<float>::infinity();
842 for(unsigned i=1; i<n_rows; ++i)
843 if(columns[c].values[i]>0)
845 float ratio = columns.back().values[i]/columns[c].values[i];
856 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
858 /* Perform row transfer operations to make the pivot column basic,
859 containing a 1 on the pivot row. */
860 for(unsigned i=0; i<columns.size(); ++i)
861 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
865 columns[i].values.resize(columns.back().values.size(), 0.0f);
866 columns[i].values[columns[i].basic] = 1.0f;
867 columns[i].basic = 0;
870 float scale = columns[i].values[r]/columns[c].values[r];
872 columns[i].values[r] = scale;
873 for(unsigned j=0; j<columns[i].values.size(); ++j)
875 columns[i].values[j] -= scale*columns[c].values[j];
878 columns[c].basic = r;
879 columns[c].values.clear();
882 bool Layout::LinearProgram::pivot()
884 /* Pick a nonbasic column and make it basic. Requiring a positive objective
885 coefficient ensures that the objective function's value will decrease in the
887 for(unsigned i=0; i+1<columns.size(); ++i)
888 if(!columns[i].basic && columns[i].values.front()>0)
889 if(unsigned row = find_minimal_ratio(i))
891 make_basic_column(i, row);
899 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
904 float &Layout::LinearProgram::Row::operator[](unsigned c)
906 if(c>=linprog.n_columns)
907 throw out_of_range("Row::operator[]");
909 Column &column = linprog.columns[c];
910 if(column.values.size()<=index)
911 column.values.resize(index+1);
913 return column.values[index];
916 float &Layout::LinearProgram::Row::back()
918 return (*this)[linprog.n_columns-1];
922 Layout::LinearProgram::Column::Column():