2 #include <msp/core/algorithm.h>
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,
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 auto begin = find(arrangement_stack, &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 auto i = find_if(slots, [&wdg](Slot *s){ return &s->widget==&wdg; });
194 for(auto k=s->constraints.begin(); k!=s->constraints.end(); )
197 s->constraints.erase(k++);
206 update_slot_indices();
210 void Layout::update_slot_indices()
213 unsigned n_floating = 0;
216 if(s->widget.is_visible() || s->ghost)
218 s->index = n_active_slots++;
226 n_slack_vars[0] = n_floating*2;
227 n_slack_vars[1] = n_floating*2;
228 for(const Slot *s: slots)
233 for(unsigned j=0; j<2; ++j)
234 if((s->*(pointers[j].packing)).gravity==0)
235 n_slack_vars[j] += 2;
238 for(const Constraint &c: s->constraints)
239 if(c.target.index>s->index && (c.type&SLACK))
240 ++n_slack_vars[c.type&1];
244 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
246 auto i = find_if(slots, [&wdg](const Slot *s){ return &s->widget==&wdg; });
248 throw hierarchy_error("widget not in layout");
253 Layout::ConstraintType Layout::complement(ConstraintType type)
255 return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
258 void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
261 throw invalid_argument("Layout::create_constraint");
263 Slot &src_slot = get_slot_for_widget(src);
264 Slot &tgt_slot = get_slot_for_widget(tgt);
266 for(const Constraint &c: src_slot.constraints)
267 if(c.type==type && &c.target==&tgt_slot)
270 src_slot.constraints.push_back(Constraint(type, tgt_slot));
271 src_slot.constraints.back().spacing = sp;
272 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
273 tgt_slot.constraints.back().spacing = sp;
275 update_slot_indices();
279 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
281 create_constraint(src, type, tgt, -1);
284 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
286 create_constraint(src, type, tgt, spacing);
289 void Layout::set_gravity(Widget &wdg, int h, int v)
291 Slot &slot = get_slot_for_widget(wdg);
293 slot.horiz_pack.gravity = h;
294 slot.vert_pack.gravity = v;
296 update_slot_indices();
300 void Layout::set_expand(Widget &wdg, bool h, bool v)
302 Slot &slot = get_slot_for_widget(wdg);
304 slot.horiz_pack.expand = h;
305 slot.vert_pack.expand = v;
310 void Layout::set_ghost(Widget &wdg, bool g)
312 Slot &slot = get_slot_for_widget(wdg);
316 if(!wdg.is_visible())
318 update_slot_indices();
323 void Layout::set_floating(Widget &wdg, bool f)
325 Slot &slot = get_slot_for_widget(wdg);
329 update_slot_indices();
333 void Layout::update()
335 solve_constraints(HORIZONTAL, UPDATE);
336 solve_constraints(VERTICAL, UPDATE);
338 for(const Slot *s: slots)
339 s->widget.set_geometry(s->geom);
342 void Layout::autosize(Geometry &geom)
344 solve_constraints(HORIZONTAL, AUTOSIZE);
345 solve_constraints(VERTICAL, AUTOSIZE);
347 geom.w = max(geom.w, autosize_geom.w);
348 geom.h = max(geom.h, autosize_geom.h);
351 void Layout::solve_constraints(int dir, SolveMode mode)
353 Pointers &ptrs = pointers[dir&VERTICAL];
355 const Geometry &geom = container->get_geometry();
356 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
359 /* Set up a linear program to solve the constraints. The program matrix has
360 five columns for each widget, and one constant column. The first and second
361 columns of a widget are its position and dimension, respectively. The
362 remaining three are slack columns; see below for their purposes. */
363 LinearProgram linprog(n_active_slots*5+n_slack_vars[dir]+1);
364 float weight = slots.size()+1;
365 unsigned k = n_active_slots*5;
366 for(const Slot *s: slots)
371 LinearProgram::Row objective = linprog.get_objective_row();
374 objective[s->index*5] = -1;
375 objective[s->index*5+1] = -1;
380 objective[s->index*5] = (s->*(ptrs.packing)).gravity/weight;
381 objective[s->index*5+1] = ((s->*(ptrs.packing)).expand ? weight : -1);
385 // Prevent the widget from going past the container's low edge.
386 LinearProgram::Row row = linprog.add_row();
388 row[s->index*5+2] = -1;
389 row.back() = margin.*(ptrs.low_margin);
394 // Prevent the widget from going past the container's high edge.
395 LinearProgram::Row row = linprog.add_row();
397 row[s->index*5+1] = 1;
398 row[s->index*5+3] = 1;
399 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
402 if(s->floating || (s->*(ptrs.packing)).gravity==0)
404 /* Try to keep the widget as close to a target position as possible.
405 Since linear programs can't express absolute values directly, use two
406 opposing slack variables that are optimized for a low value. */
407 float a = (s->*(ptrs.packing)).gravity*0.5+0.5;
408 LinearProgram::Row row = linprog.add_row();
410 row[s->index*5+1] = a;
415 const Geometry &cgeom = s->widget.get_geometry();
416 row.back() = cgeom.*(ptrs.pos)+cgeom.*(ptrs.dim)*a;
419 row.back() = geom.*(ptrs.dim)/2;
426 /* Don't allow the widget's dimension to get below that determined
428 LinearProgram::Row row = linprog.add_row();
429 row[s->index*5+1] = 1;
430 row[s->index*5+4] = -1;
431 row.back() = s->autosize_geom.*(ptrs.dim);
434 /* Add rows for user-defined constraints. Constraints are always added
435 in pairs, so it's only necessary to create a row for one half. */
436 for(const Constraint &c: s->constraints)
437 if(c.target.index>s->index && (c.type&1)==dir)
439 LinearProgram::Row row = linprog.add_row();
440 float polarity = ((c.type&SELF_DIM) ? -1 : 1);
441 float dim_weight = ((c.type&HALF_DIM) ? 0.5f : 1);
443 row[s->index*5] = polarity;
445 row[s->index*5+1] = polarity*dim_weight;
446 if(c.type&TARGET_POS)
447 row[c.target.index*5] = -polarity;
448 if(c.type&TARGET_DIM)
449 row[c.target.index*5+1] = -polarity*dim_weight;
451 row.back() = (c.spacing>=0 ? c.spacing : this->*(ptrs.spacing));
462 autosize_geom.*(ptrs.dim) = 0;
463 for(const Slot *s: slots)
466 int high_edge = linprog.get_variable(s->index*5)+linprog.get_variable(s->index*5+1);
467 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
475 s->geom.*(ptrs.pos) = linprog.get_variable(s->index*5);
476 s->geom.*(ptrs.dim) = linprog.get_variable(s->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_VCENTER")
630 ctype = Layout::ALIGN_VCENTER;
631 else if(str=="ALIGN_BOTTOM")
632 ctype = Layout::ALIGN_BOTTOM;
633 else if(str=="ALIGN_RIGHT")
634 ctype = Layout::ALIGN_RIGHT;
635 else if(str=="ALIGN_HCENTER")
636 ctype = Layout::ALIGN_HCENTER;
637 else if(str=="ALIGN_LEFT")
638 ctype = Layout::ALIGN_LEFT;
639 else if(str=="COPY_WIDTH")
640 ctype = Layout::COPY_WIDTH;
641 else if(str=="COPY_HEIGHT")
642 ctype = Layout::COPY_HEIGHT;
644 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
648 Layout::LinearProgram::LinearProgram(unsigned s):
656 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
658 return Row(*this, n_rows++);
661 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
664 throw out_of_range("LinearProgram::operator[]");
666 return Row(*this, r);
669 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
671 return Row(*this, 0);
674 float Layout::LinearProgram::get_variable(unsigned i)
676 if(!solved || infeasible)
677 throw logic_error("not solved");
679 throw out_of_range("LinearProgram::get_variable");
681 if(unsigned r = columns[i].basic)
682 return columns.back().values[r];
687 bool Layout::LinearProgram::solve()
689 if(solved || infeasible)
692 /* Solve the program using the simplex method. The column representing the
693 objective variable is kept implicit, as it would never change during the
694 execution of the algorithm. */
698 add_artificial_variables();
700 // Solve the phase 1 problem.
703 /* All artificial variables should now be non-basic and thus zero, so the
704 objective function's value should also be zero. If it isn't, the original
705 program can't be solved. */
706 if(columns.back().values.front())
712 remove_artificial_variables();
714 // Solve the phase 2 problem. We already know it to be feasible.
722 void Layout::LinearProgram::prepare_columns()
724 /* See if any variables are already basic. A basic variable must only have
725 a nonzero coefficient on one row, and its product with the constant column
726 must not be negative. Only one variable can be basic for any given row. */
727 vector<float> obj_coeff(n_rows, 0.0f);
728 vector<float> row_coeff(n_rows, 1.0f);
729 const vector<float> &constants = columns.back().values;
730 for(Column &c: columns)
731 if(c.values.size()>=2 && c.values.back()!=0.0f && (constants.size()<c.values.size() || c.values.back()*constants[c.values.size()-1]>=0.0f) && obj_coeff[c.values.size()-1]==0.0f)
734 for(unsigned j=1; (basic && j+1<c.values.size()); ++j)
735 basic = (c.values[j]==0.0f);
738 c.basic = c.values.size()-1;
739 row_coeff[c.basic] = 1.0f/c.values.back();
740 obj_coeff[c.basic] = -c.values.front();
745 // Price out the newly-created basic variables.
746 for(Column &c: columns)
747 if(!c.values.empty())
749 for(unsigned j=0; j<c.values.size(); ++j)
751 c.values[j] *= row_coeff[j];
752 c.values.front() += obj_coeff[j]*c.values[j];
757 void Layout::LinearProgram::add_artificial_variables()
759 vector<unsigned> artificial_rows(n_rows-1);
760 for(unsigned i=0; i<artificial_rows.size(); ++i)
761 artificial_rows[i] = i+1;
763 for(const Column &c: columns)
765 artificial_rows[c.basic-1] = 0;
766 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
768 /* Force all non-basic columns fully into existence and relocate objective
769 row to bottom in preparation of phase 1. A new objective row is calculated
770 by pricing out the constraint rows. */
771 for(Column &c: columns)
774 float objective = 0.0f;
775 if(!c.values.empty())
777 objective = c.values.front();
778 c.values.front() = 0.0f;
779 for(unsigned r: artificial_rows)
780 if(r<c.values.size())
781 c.values.front() += c.values[r];
783 c.values.resize(n_rows+1, 0.0f);
784 c.values.back() = objective;
787 if(artificial_rows.empty())
790 /* Create artificial variables for phase 1. This ensures that each row has
791 a basic variable associated with it. The original objective row already
792 contains the implicit objective variable, which is basic. */
793 columns.resize(n_columns+artificial_rows.size());
794 columns.back() = columns[n_columns-1];
795 columns[n_columns-1].values.clear();
796 for(unsigned i=0; i<artificial_rows.size(); ++i)
797 columns[n_columns+i-1].basic = artificial_rows[i];
800 void Layout::LinearProgram::remove_artificial_variables()
802 /* See if any artificial variables are still basic. This could be because
803 the program is degenerate. To avoid trouble later on, use pivots to make
804 some of the original variables basic instead.
806 I don't fully understand why this is needed, but it appears to work. */
807 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
808 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
810 for(unsigned j=0; j+1<n_columns; ++j)
811 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
813 make_basic_column(j, columns[i].basic);
818 /* Get rid of the artificial variables and restore the original objective
819 row to form the phase 2 problem. */
820 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
821 for(Column &c: columns)
824 c.values.front() = c.values.back();
829 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
831 /* Pick the row with the minimum ratio between the constant column and the
832 pivot column. This ensures that when the pivot column is made basic, values
833 in the constant column stay positive.
835 The use of n_rows instead of the true size of the column is intentional,
836 since the relocated objective row must be ignored in phase 1. */
837 float best = numeric_limits<float>::infinity();
839 for(unsigned i=1; i<n_rows; ++i)
840 if(columns[c].values[i]>0)
842 float ratio = columns.back().values[i]/columns[c].values[i];
853 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
855 /* Perform row transfer operations to make the pivot column basic,
856 containing a 1 on the pivot row. */
857 for(unsigned i=0; i<columns.size(); ++i)
858 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
862 columns[i].values.resize(columns.back().values.size(), 0.0f);
863 columns[i].values[columns[i].basic] = 1.0f;
864 columns[i].basic = 0;
867 float scale = columns[i].values[r]/columns[c].values[r];
869 columns[i].values[r] = scale;
870 for(unsigned j=0; j<columns[i].values.size(); ++j)
872 columns[i].values[j] -= scale*columns[c].values[j];
875 columns[c].basic = r;
876 columns[c].values.clear();
879 bool Layout::LinearProgram::pivot()
881 /* Pick a nonbasic column and make it basic. Requiring a positive objective
882 coefficient ensures that the objective function's value will decrease in the
884 for(unsigned i=0; i+1<columns.size(); ++i)
885 if(!columns[i].basic && columns[i].values.front()>0)
886 if(unsigned row = find_minimal_ratio(i))
888 make_basic_column(i, row);
896 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
901 float &Layout::LinearProgram::Row::operator[](unsigned c)
903 if(c>=linprog.n_columns)
904 throw out_of_range("Row::operator[]");
906 Column &column = linprog.columns[c];
907 if(column.values.size()<=index)
908 column.values.resize(index+1);
910 return column.values[index];
913 float &Layout::LinearProgram::Row::back()
915 return (*this)[linprog.n_columns-1];
919 Layout::LinearProgram::Column::Column():