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 &, size_t);
27 float &operator[](size_t);
35 std::vector<float> values;
42 std::vector<Column> columns;
44 bool infeasible = false;
47 LinearProgram(size_t);
50 Row operator[](size_t);
51 Row get_objective_row();
52 float get_variable(size_t);
55 void prepare_columns();
56 void add_artificial_variables();
57 void remove_artificial_variables();
58 size_t find_minimal_ratio(size_t);
59 void make_basic_column(size_t, size_t);
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,
94 void Layout::set_container(Container &c)
97 throw logic_error("container!=0");
102 void Layout::set_margin(const Sides &m)
109 void Layout::set_spacing(unsigned s)
117 void Layout::set_row_spacing(unsigned s)
124 void Layout::set_column_spacing(unsigned s)
131 void Layout::push_arrangement(Arrangement &arr)
133 arrangement_stack.push_back(&arr);
136 Arrangement *Layout::get_arrangement() const
138 if(arrangement_stack.empty())
141 return arrangement_stack.back();
144 void Layout::pop_arrangement(Arrangement &arr)
146 auto begin = find(arrangement_stack, &arr);
147 if(begin==arrangement_stack.end())
152 Arrangement *top = arrangement_stack.back();
153 arrangement_stack.pop_back();
154 if(!arrangement_stack.empty())
155 arrangement_stack.back()->arrange(*top);
161 void Layout::add_widget(Widget &wdg)
164 throw logic_error("!container");
166 slots.push_back(new Slot(*this, wdg));
167 update_slot_indices();
168 if(!arrangement_stack.empty())
169 arrangement_stack.back()->arrange(wdg);
174 void Layout::remove_widget(Widget &wdg)
176 auto i = find_if(slots, [&wdg](Slot *s){ return &s->widget==&wdg; });
183 for(auto k=s->constraints.begin(); k!=s->constraints.end(); )
186 k = s->constraints.erase(k);
195 update_slot_indices();
199 void Layout::update_slot_indices()
202 size_t n_floating = 0;
205 if(s->widget.is_visible() || s->ghost)
207 s->index = n_active_slots++;
215 n_slack_vars[0] = n_floating*2;
216 n_slack_vars[1] = n_floating*2;
217 for(const Slot *s: slots)
222 for(unsigned j=0; j<2; ++j)
223 if((s->*(pointers[j].packing)).gravity==0)
224 n_slack_vars[j] += 2;
227 for(const Constraint &c: s->constraints)
228 if(c.target->index>s->index && (c.type&SLACK))
229 ++n_slack_vars[c.type&1];
233 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
235 auto i = find_if(slots, [&wdg](const Slot *s){ return &s->widget==&wdg; });
237 throw hierarchy_error("widget not in layout");
242 Layout::ConstraintType Layout::complement(ConstraintType type)
244 return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
247 void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
250 throw invalid_argument("Layout::create_constraint");
252 Slot &src_slot = get_slot_for_widget(src);
253 Slot &tgt_slot = get_slot_for_widget(tgt);
255 for(const Constraint &c: src_slot.constraints)
256 if(c.type==type && c.target==&tgt_slot)
259 src_slot.constraints.push_back(Constraint(type, tgt_slot));
260 src_slot.constraints.back().spacing = sp;
261 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
262 tgt_slot.constraints.back().spacing = sp;
264 update_slot_indices();
268 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
270 create_constraint(src, type, tgt, -1);
273 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
275 create_constraint(src, type, tgt, spacing);
278 void Layout::set_gravity(Widget &wdg, int h, int v)
280 Slot &slot = get_slot_for_widget(wdg);
282 slot.horiz_pack.gravity = h;
283 slot.vert_pack.gravity = v;
285 update_slot_indices();
289 void Layout::set_expand(Widget &wdg, bool h, bool v)
291 Slot &slot = get_slot_for_widget(wdg);
293 slot.horiz_pack.expand = h;
294 slot.vert_pack.expand = v;
299 void Layout::set_ghost(Widget &wdg, bool g)
301 Slot &slot = get_slot_for_widget(wdg);
305 if(!wdg.is_visible())
307 update_slot_indices();
312 void Layout::set_floating(Widget &wdg, bool f)
314 Slot &slot = get_slot_for_widget(wdg);
318 update_slot_indices();
322 void Layout::update()
324 solve_constraints(HORIZONTAL, UPDATE);
325 solve_constraints(VERTICAL, UPDATE);
327 for(const Slot *s: slots)
328 s->widget.set_geometry(s->geom);
331 void Layout::autosize(Geometry &geom)
333 solve_constraints(HORIZONTAL, AUTOSIZE);
334 solve_constraints(VERTICAL, AUTOSIZE);
336 geom.w = max(geom.w, autosize_geom.w);
337 geom.h = max(geom.h, autosize_geom.h);
340 void Layout::solve_constraints(int dir, SolveMode mode)
342 Pointers &ptrs = pointers[dir&VERTICAL];
344 const Geometry &geom = container->get_geometry();
345 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
348 /* Set up a linear program to solve the constraints. The program matrix has
349 five columns for each widget, and one constant column. The first and second
350 columns of a widget are its position and dimension, respectively. The
351 remaining three are slack columns; see below for their purposes. */
352 LinearProgram linprog(n_active_slots*5+n_slack_vars[dir]+1);
353 float weight = slots.size()+1;
354 size_t k = n_active_slots*5;
355 for(const Slot *s: slots)
360 LinearProgram::Row objective = linprog.get_objective_row();
363 objective[s->index*5] = -1;
364 objective[s->index*5+1] = -1;
369 objective[s->index*5] = (s->*(ptrs.packing)).gravity/weight;
370 objective[s->index*5+1] = ((s->*(ptrs.packing)).expand ? weight : -1);
374 // Prevent the widget from going past the container's low edge.
375 LinearProgram::Row row = linprog.add_row();
377 row[s->index*5+2] = -1;
378 row.back() = margin.*(ptrs.low_margin);
383 // Prevent the widget from going past the container's high edge.
384 LinearProgram::Row row = linprog.add_row();
386 row[s->index*5+1] = 1;
387 row[s->index*5+3] = 1;
388 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
391 if(s->floating || (s->*(ptrs.packing)).gravity==0)
393 /* Try to keep the widget as close to a target position as possible.
394 Since linear programs can't express absolute values directly, use two
395 opposing slack variables that are optimized for a low value. */
396 float a = (s->*(ptrs.packing)).gravity*0.5+0.5;
397 LinearProgram::Row row = linprog.add_row();
399 row[s->index*5+1] = a;
404 const Geometry &cgeom = s->widget.get_geometry();
405 row.back() = cgeom.*(ptrs.pos)+cgeom.*(ptrs.dim)*a;
408 row.back() = geom.*(ptrs.dim)/2;
415 /* Don't allow the widget's dimension to get below that determined
417 LinearProgram::Row row = linprog.add_row();
418 row[s->index*5+1] = 1;
419 row[s->index*5+4] = -1;
420 row.back() = s->autosize_geom.*(ptrs.dim);
423 /* Add rows for user-defined constraints. Constraints are always added
424 in pairs, so it's only necessary to create a row for one half. */
425 for(const Constraint &c: s->constraints)
426 if(c.target->index>s->index && (c.type&1)==dir)
428 LinearProgram::Row row = linprog.add_row();
429 float polarity = ((c.type&SELF_DIM) ? -1 : 1);
430 float dim_weight = ((c.type&HALF_DIM) ? 0.5f : 1);
432 row[s->index*5] = polarity;
434 row[s->index*5+1] = polarity*dim_weight;
435 if(c.type&TARGET_POS)
436 row[c.target->index*5] = -polarity;
437 if(c.type&TARGET_DIM)
438 row[c.target->index*5+1] = -polarity*dim_weight;
440 row.back() = (c.spacing>=0 ? c.spacing : this->*(ptrs.spacing));
451 autosize_geom.*(ptrs.dim) = 0;
452 for(const Slot *s: slots)
455 int high_edge = linprog.get_variable(s->index*5)+linprog.get_variable(s->index*5+1);
456 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
464 s->geom.*(ptrs.pos) = linprog.get_variable(s->index*5);
465 s->geom.*(ptrs.dim) = linprog.get_variable(s->index*5+1);
471 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
477 Layout::Slot::Slot(Layout &l, Widget &w):
481 vert_pack.gravity = 1;
482 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
483 widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
484 widget.autosize(autosize_geom);
487 void Layout::Slot::autosize_changed()
489 widget.autosize(autosize_geom);
491 if(!widget.is_visible() && !ghost)
494 // Only trigger an update if the widget won't fit in its current area.
495 if(autosize_geom.w>geom.w || autosize_geom.h>geom.h)
497 layout.container->signal_autosize_changed.emit();
502 void Layout::Slot::visibility_changed(bool v)
504 layout.update_slot_indices();
507 layout.container->signal_autosize_changed.emit();
513 Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
514 DataFile::ObjectLoader<Layout>(l),
517 add("column_spacing", &Loader::column_spacing);
518 add("margin", &Loader::margin);
519 add("row_spacing", &Loader::row_spacing);
520 add("spacing", &Loader::spacing);
521 add("widget", &Loader::widget);
524 void Layout::Loader::column_spacing(unsigned s)
526 obj.set_column_spacing(s);
529 void Layout::Loader::margin()
533 obj.set_margin(sides);
536 void Layout::Loader::spacing(unsigned s)
541 void Layout::Loader::row_spacing(unsigned s)
543 obj.set_row_spacing(s);
546 void Layout::Loader::widget(const string &n)
548 Widget &wdg = *get_item(wdg_map, n);
549 WidgetLoader ldr(obj, wdg, wdg_map);
554 Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
559 add("constraint", &WidgetLoader::constraint);
560 add("expand", &WidgetLoader::expand);
561 add("ghost", &WidgetLoader::ghost);
562 add("gravity", &WidgetLoader::gravity);
565 void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
567 Widget &target = *get_item(wdg_map, n);
568 layout.add_constraint(widget, type, target);
571 void Layout::WidgetLoader::expand(bool h, bool v)
573 layout.set_expand(widget, h, v);
576 void Layout::WidgetLoader::ghost(bool g)
578 layout.set_ghost(widget, g);
581 void Layout::WidgetLoader::gravity(int h, int v)
583 layout.set_gravity(widget, h, v);
587 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
589 const string &str = conv.get();
591 ctype = Layout::ABOVE;
592 else if(str=="BELOW")
593 ctype = Layout::BELOW;
594 else if(str=="RIGHT_OF")
595 ctype = Layout::RIGHT_OF;
596 else if(str=="LEFT_OF")
597 ctype = Layout::LEFT_OF;
598 else if(str=="FAR_ABOVE")
599 ctype = Layout::FAR_ABOVE;
600 else if(str=="FAR_BELOW")
601 ctype = Layout::FAR_BELOW;
602 else if(str=="FAR_RIGHT_OF")
603 ctype = Layout::FAR_RIGHT_OF;
604 else if(str=="FAR_LEFT_OF")
605 ctype = Layout::FAR_LEFT_OF;
606 else if(str=="ALIGN_TOP")
607 ctype = Layout::ALIGN_TOP;
608 else if(str=="ALIGN_VCENTER")
609 ctype = Layout::ALIGN_VCENTER;
610 else if(str=="ALIGN_BOTTOM")
611 ctype = Layout::ALIGN_BOTTOM;
612 else if(str=="ALIGN_RIGHT")
613 ctype = Layout::ALIGN_RIGHT;
614 else if(str=="ALIGN_HCENTER")
615 ctype = Layout::ALIGN_HCENTER;
616 else if(str=="ALIGN_LEFT")
617 ctype = Layout::ALIGN_LEFT;
618 else if(str=="COPY_WIDTH")
619 ctype = Layout::COPY_WIDTH;
620 else if(str=="COPY_HEIGHT")
621 ctype = Layout::COPY_HEIGHT;
623 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
627 Layout::LinearProgram::LinearProgram(size_t s):
632 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
634 return Row(*this, n_rows++);
637 Layout::LinearProgram::Row Layout::LinearProgram::operator[](size_t r)
640 throw out_of_range("LinearProgram::operator[]");
642 return Row(*this, r);
645 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
647 return Row(*this, 0);
650 float Layout::LinearProgram::get_variable(size_t i)
652 if(!solved || infeasible)
653 throw logic_error("not solved");
655 throw out_of_range("LinearProgram::get_variable");
657 if(size_t r = columns[i].basic)
658 return columns.back().values[r];
663 bool Layout::LinearProgram::solve()
665 if(solved || infeasible)
668 /* Solve the program using the simplex method. The column representing the
669 objective variable is kept implicit, as it would never change during the
670 execution of the algorithm. */
674 add_artificial_variables();
676 // Solve the phase 1 problem.
679 /* All artificial variables should now be non-basic and thus zero, so the
680 objective function's value should also be zero. If it isn't, the original
681 program can't be solved. */
682 if(columns.back().values.front())
688 remove_artificial_variables();
690 // Solve the phase 2 problem. We already know it to be feasible.
698 void Layout::LinearProgram::prepare_columns()
700 /* See if any variables are already basic. A basic variable must only have
701 a nonzero coefficient on one row, and its product with the constant column
702 must not be negative. Only one variable can be basic for any given row. */
703 vector<float> obj_coeff(n_rows, 0.0f);
704 vector<float> row_coeff(n_rows, 1.0f);
705 const vector<float> &constants = columns.back().values;
706 for(Column &c: columns)
707 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)
710 for(size_t j=1; (basic && j+1<c.values.size()); ++j)
711 basic = (c.values[j]==0.0f);
714 c.basic = c.values.size()-1;
715 row_coeff[c.basic] = 1.0f/c.values.back();
716 obj_coeff[c.basic] = -c.values.front();
721 // Price out the newly-created basic variables.
722 for(Column &c: columns)
723 if(!c.values.empty())
725 for(size_t j=0; j<c.values.size(); ++j)
727 c.values[j] *= row_coeff[j];
728 c.values.front() += obj_coeff[j]*c.values[j];
733 void Layout::LinearProgram::add_artificial_variables()
735 vector<size_t> artificial_rows(n_rows-1);
736 for(size_t i=0; i<artificial_rows.size(); ++i)
737 artificial_rows[i] = i+1;
739 for(const Column &c: columns)
741 artificial_rows[c.basic-1] = 0;
742 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
744 /* Force all non-basic columns fully into existence and relocate objective
745 row to bottom in preparation of phase 1. A new objective row is calculated
746 by pricing out the constraint rows. */
747 for(Column &c: columns)
750 float objective = 0.0f;
751 if(!c.values.empty())
753 objective = c.values.front();
754 c.values.front() = 0.0f;
755 for(size_t r: artificial_rows)
756 if(r<c.values.size())
757 c.values.front() += c.values[r];
759 c.values.resize(n_rows+1, 0.0f);
760 c.values.back() = objective;
763 if(artificial_rows.empty())
766 /* Create artificial variables for phase 1. This ensures that each row has
767 a basic variable associated with it. The original objective row already
768 contains the implicit objective variable, which is basic. */
769 columns.resize(n_columns+artificial_rows.size());
770 columns.back() = columns[n_columns-1];
771 columns[n_columns-1].values.clear();
772 for(size_t i=0; i<artificial_rows.size(); ++i)
773 columns[n_columns+i-1].basic = artificial_rows[i];
776 void Layout::LinearProgram::remove_artificial_variables()
778 /* See if any artificial variables are still basic. This could be because
779 the program is degenerate. To avoid trouble later on, use pivots to make
780 some of the original variables basic instead.
782 I don't fully understand why this is needed, but it appears to work. */
783 for(size_t i=n_columns-1; i+1<columns.size(); ++i)
784 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
786 for(size_t j=0; j+1<n_columns; ++j)
787 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
789 make_basic_column(j, columns[i].basic);
794 /* Get rid of the artificial variables and restore the original objective
795 row to form the phase 2 problem. */
796 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
797 for(Column &c: columns)
800 c.values.front() = c.values.back();
805 size_t Layout::LinearProgram::find_minimal_ratio(size_t c)
807 /* Pick the row with the minimum ratio between the constant column and the
808 pivot column. This ensures that when the pivot column is made basic, values
809 in the constant column stay positive.
811 The use of n_rows instead of the true size of the column is intentional,
812 since the relocated objective row must be ignored in phase 1. */
813 float best = numeric_limits<float>::infinity();
815 for(size_t i=1; i<n_rows; ++i)
816 if(columns[c].values[i]>0)
818 float ratio = columns.back().values[i]/columns[c].values[i];
829 void Layout::LinearProgram::make_basic_column(size_t c, size_t r)
831 /* Perform row transfer operations to make the pivot column basic,
832 containing a 1 on the pivot row. */
833 for(size_t i=0; i<columns.size(); ++i)
834 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
838 columns[i].values.resize(columns.back().values.size(), 0.0f);
839 columns[i].values[columns[i].basic] = 1.0f;
840 columns[i].basic = 0;
843 float scale = columns[i].values[r]/columns[c].values[r];
845 columns[i].values[r] = scale;
846 for(size_t j=0; j<columns[i].values.size(); ++j)
848 columns[i].values[j] -= scale*columns[c].values[j];
851 columns[c].basic = r;
852 columns[c].values.clear();
855 bool Layout::LinearProgram::pivot()
857 /* Pick a nonbasic column and make it basic. Requiring a positive objective
858 coefficient ensures that the objective function's value will decrease in the
860 for(size_t i=0; i+1<columns.size(); ++i)
861 if(!columns[i].basic && columns[i].values.front()>0)
862 if(size_t row = find_minimal_ratio(i))
864 make_basic_column(i, row);
872 Layout::LinearProgram::Row::Row(LinearProgram &lp, size_t i):
877 float &Layout::LinearProgram::Row::operator[](size_t c)
879 if(c>=linprog.n_columns)
880 throw out_of_range("Row::operator[]");
882 Column &column = linprog.columns[c];
883 if(column.values.size()<=index)
884 column.values.resize(index+1);
886 return column.values[index];
889 float &Layout::LinearProgram::Row::back()
891 return (*this)[linprog.n_columns-1];
895 Layout::LinearProgram::Column::Column():