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,
88 void Layout::set_container(Container &c)
91 throw logic_error("container!=0");
96 void Layout::set_margin(const Sides &m)
103 void Layout::set_spacing(unsigned s)
111 void Layout::set_row_spacing(unsigned s)
118 void Layout::set_column_spacing(unsigned s)
125 void Layout::push_arrangement(Arrangement &arr)
127 arrangement_stack.push_back(&arr);
130 Arrangement *Layout::get_arrangement() const
132 if(arrangement_stack.empty())
135 return arrangement_stack.back();
138 void Layout::pop_arrangement(Arrangement &arr)
140 auto begin = find(arrangement_stack, &arr);
141 if(begin==arrangement_stack.end())
146 Arrangement *top = arrangement_stack.back();
147 arrangement_stack.pop_back();
148 if(!arrangement_stack.empty())
149 arrangement_stack.back()->arrange(*top);
155 void Layout::add_widget(Widget &wdg)
158 throw logic_error("!container");
160 slots.emplace_back(make_unique<Slot>(*this, wdg));
161 update_slot_indices();
162 if(!arrangement_stack.empty())
163 arrangement_stack.back()->arrange(wdg);
168 void Layout::remove_widget(Widget &wdg)
170 auto i = find_if(slots, [&wdg](const unique_ptr<Slot> &s){ return &s->widget==&wdg; });
174 for(const unique_ptr<Slot> &s: slots)
177 for(auto k=s->constraints.begin(); k!=s->constraints.end(); )
179 if(k->target==i->get())
180 k = s->constraints.erase(k);
188 update_slot_indices();
192 void Layout::update_slot_indices()
195 size_t n_floating = 0;
196 for(const unique_ptr<Slot> &s: slots)
198 if(s->widget.is_visible() || s->ghost)
200 s->index = n_active_slots++;
208 n_slack_vars[0] = n_floating*2;
209 n_slack_vars[1] = n_floating*2;
210 for(const unique_ptr<Slot> &s: slots)
215 for(unsigned j=0; j<2; ++j)
216 if((s.get()->*(pointers[j].packing)).gravity==0)
217 n_slack_vars[j] += 2;
220 for(const Constraint &c: s->constraints)
221 if(c.target->index>s->index && (c.type&SLACK))
222 ++n_slack_vars[c.type&1];
226 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
228 auto i = find_if(slots, [&wdg](const unique_ptr<Slot> &s){ return &s->widget==&wdg; });
230 throw hierarchy_error("widget not in layout");
235 Layout::ConstraintType Layout::complement(ConstraintType type)
237 return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
240 void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
243 throw invalid_argument("Layout::create_constraint");
245 Slot &src_slot = get_slot_for_widget(src);
246 Slot &tgt_slot = get_slot_for_widget(tgt);
248 for(const Constraint &c: src_slot.constraints)
249 if(c.type==type && c.target==&tgt_slot)
252 src_slot.constraints.push_back(Constraint(type, tgt_slot));
253 src_slot.constraints.back().spacing = sp;
254 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
255 tgt_slot.constraints.back().spacing = sp;
257 update_slot_indices();
261 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
263 create_constraint(src, type, tgt, -1);
266 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
268 create_constraint(src, type, tgt, spacing);
271 void Layout::set_gravity(Widget &wdg, int h, int v)
273 Slot &slot = get_slot_for_widget(wdg);
275 slot.horiz_pack.gravity = h;
276 slot.vert_pack.gravity = v;
278 update_slot_indices();
282 void Layout::set_expand(Widget &wdg, bool h, bool v)
284 Slot &slot = get_slot_for_widget(wdg);
286 slot.horiz_pack.expand = h;
287 slot.vert_pack.expand = v;
292 void Layout::set_ghost(Widget &wdg, bool g)
294 Slot &slot = get_slot_for_widget(wdg);
298 if(!wdg.is_visible())
300 update_slot_indices();
305 void Layout::set_floating(Widget &wdg, bool f)
307 Slot &slot = get_slot_for_widget(wdg);
311 update_slot_indices();
315 void Layout::update()
317 solve_constraints(HORIZONTAL, UPDATE);
318 solve_constraints(VERTICAL, UPDATE);
320 for(const unique_ptr<Slot> &s: slots)
321 s->widget.set_geometry(s->geom);
324 void Layout::autosize(Geometry &geom)
326 solve_constraints(HORIZONTAL, AUTOSIZE);
327 solve_constraints(VERTICAL, AUTOSIZE);
329 geom.w = max(geom.w, autosize_geom.w);
330 geom.h = max(geom.h, autosize_geom.h);
333 void Layout::solve_constraints(int dir, SolveMode mode)
335 Pointers &ptrs = pointers[dir&VERTICAL];
337 const Geometry &geom = container->get_geometry();
338 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
341 /* Set up a linear program to solve the constraints. The program matrix has
342 five columns for each widget, and one constant column. The first and second
343 columns of a widget are its position and dimension, respectively. The
344 remaining three are slack columns; see below for their purposes. */
345 LinearProgram linprog(n_active_slots*5+n_slack_vars[dir]+1);
346 float weight = slots.size()+1;
347 size_t k = n_active_slots*5;
348 for(const unique_ptr<Slot> &s: slots)
353 LinearProgram::Row objective = linprog.get_objective_row();
356 objective[s->index*5] = -1;
357 objective[s->index*5+1] = -1;
362 objective[s->index*5] = (s.get()->*(ptrs.packing)).gravity/weight;
363 objective[s->index*5+1] = ((s.get()->*(ptrs.packing)).expand ? weight : -1);
367 // Prevent the widget from going past the container's low edge.
368 LinearProgram::Row row = linprog.add_row();
370 row[s->index*5+2] = -1;
371 row.back() = margin.*(ptrs.low_margin);
376 // Prevent the widget from going past the container's high edge.
377 LinearProgram::Row row = linprog.add_row();
379 row[s->index*5+1] = 1;
380 row[s->index*5+3] = 1;
381 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
384 if(s->floating || (s.get()->*(ptrs.packing)).gravity==0)
386 /* Try to keep the widget as close to a target position as possible.
387 Since linear programs can't express absolute values directly, use two
388 opposing slack variables that are optimized for a low value. */
389 float a = (s.get()->*(ptrs.packing)).gravity*0.5+0.5;
390 LinearProgram::Row row = linprog.add_row();
392 row[s->index*5+1] = a;
397 const Geometry &cgeom = s->widget.get_geometry();
398 row.back() = cgeom.*(ptrs.pos)+cgeom.*(ptrs.dim)*a;
401 row.back() = geom.*(ptrs.dim)/2;
408 /* Don't allow the widget's dimension to get below that determined
410 LinearProgram::Row row = linprog.add_row();
411 row[s->index*5+1] = 1;
412 row[s->index*5+4] = -1;
413 row.back() = s->autosize_geom.*(ptrs.dim);
416 /* Add rows for user-defined constraints. Constraints are always added
417 in pairs, so it's only necessary to create a row for one half. */
418 for(const Constraint &c: s->constraints)
419 if(c.target->index>s->index && (c.type&1)==dir)
421 LinearProgram::Row row = linprog.add_row();
422 float polarity = ((c.type&SELF_DIM) ? -1 : 1);
423 float dim_weight = ((c.type&HALF_DIM) ? 0.5f : 1);
425 row[s->index*5] = polarity;
427 row[s->index*5+1] = polarity*dim_weight;
428 if(c.type&TARGET_POS)
429 row[c.target->index*5] = -polarity;
430 if(c.type&TARGET_DIM)
431 row[c.target->index*5+1] = -polarity*dim_weight;
433 row.back() = (c.spacing>=0 ? c.spacing : this->*(ptrs.spacing));
444 autosize_geom.*(ptrs.dim) = 0;
445 for(const unique_ptr<Slot> &s: slots)
448 int high_edge = linprog.get_variable(s->index*5)+linprog.get_variable(s->index*5+1);
449 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
454 for(const unique_ptr<Slot> &s: slots)
457 s->geom.*(ptrs.pos) = linprog.get_variable(s->index*5);
458 s->geom.*(ptrs.dim) = linprog.get_variable(s->index*5+1);
464 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
470 Layout::Slot::Slot(Layout &l, Widget &w):
474 vert_pack.gravity = 1;
475 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
476 widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
477 widget.autosize(autosize_geom);
480 void Layout::Slot::autosize_changed()
482 widget.autosize(autosize_geom);
484 if(!widget.is_visible() && !ghost)
487 // Only trigger an update if the widget won't fit in its current area.
488 if(autosize_geom.w>geom.w || autosize_geom.h>geom.h)
490 layout.container->signal_autosize_changed.emit();
495 void Layout::Slot::visibility_changed(bool v)
497 layout.update_slot_indices();
500 layout.container->signal_autosize_changed.emit();
506 Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
507 DataFile::ObjectLoader<Layout>(l),
510 add("column_spacing", &Loader::column_spacing);
511 add("margin", &Loader::margin);
512 add("row_spacing", &Loader::row_spacing);
513 add("spacing", &Loader::spacing);
514 add("widget", &Loader::widget);
517 void Layout::Loader::column_spacing(unsigned s)
519 obj.set_column_spacing(s);
522 void Layout::Loader::margin()
526 obj.set_margin(sides);
529 void Layout::Loader::spacing(unsigned s)
534 void Layout::Loader::row_spacing(unsigned s)
536 obj.set_row_spacing(s);
539 void Layout::Loader::widget(const string &n)
541 Widget &wdg = *get_item(wdg_map, n);
542 WidgetLoader ldr(obj, wdg, wdg_map);
547 Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
552 add("constraint", &WidgetLoader::constraint);
553 add("expand", &WidgetLoader::expand);
554 add("ghost", &WidgetLoader::ghost);
555 add("gravity", &WidgetLoader::gravity);
558 void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
560 Widget &target = *get_item(wdg_map, n);
561 layout.add_constraint(widget, type, target);
564 void Layout::WidgetLoader::expand(bool h, bool v)
566 layout.set_expand(widget, h, v);
569 void Layout::WidgetLoader::ghost(bool g)
571 layout.set_ghost(widget, g);
574 void Layout::WidgetLoader::gravity(int h, int v)
576 layout.set_gravity(widget, h, v);
580 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
582 const string &str = conv.get();
584 ctype = Layout::ABOVE;
585 else if(str=="BELOW")
586 ctype = Layout::BELOW;
587 else if(str=="RIGHT_OF")
588 ctype = Layout::RIGHT_OF;
589 else if(str=="LEFT_OF")
590 ctype = Layout::LEFT_OF;
591 else if(str=="FAR_ABOVE")
592 ctype = Layout::FAR_ABOVE;
593 else if(str=="FAR_BELOW")
594 ctype = Layout::FAR_BELOW;
595 else if(str=="FAR_RIGHT_OF")
596 ctype = Layout::FAR_RIGHT_OF;
597 else if(str=="FAR_LEFT_OF")
598 ctype = Layout::FAR_LEFT_OF;
599 else if(str=="ALIGN_TOP")
600 ctype = Layout::ALIGN_TOP;
601 else if(str=="ALIGN_VCENTER")
602 ctype = Layout::ALIGN_VCENTER;
603 else if(str=="ALIGN_BOTTOM")
604 ctype = Layout::ALIGN_BOTTOM;
605 else if(str=="ALIGN_RIGHT")
606 ctype = Layout::ALIGN_RIGHT;
607 else if(str=="ALIGN_HCENTER")
608 ctype = Layout::ALIGN_HCENTER;
609 else if(str=="ALIGN_LEFT")
610 ctype = Layout::ALIGN_LEFT;
611 else if(str=="COPY_WIDTH")
612 ctype = Layout::COPY_WIDTH;
613 else if(str=="COPY_HEIGHT")
614 ctype = Layout::COPY_HEIGHT;
616 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
620 Layout::LinearProgram::LinearProgram(size_t s):
625 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
627 return Row(*this, n_rows++);
630 Layout::LinearProgram::Row Layout::LinearProgram::operator[](size_t r)
633 throw out_of_range("LinearProgram::operator[]");
635 return Row(*this, r);
638 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
640 return Row(*this, 0);
643 float Layout::LinearProgram::get_variable(size_t i)
645 if(!solved || infeasible)
646 throw logic_error("not solved");
648 throw out_of_range("LinearProgram::get_variable");
650 if(size_t r = columns[i].basic)
651 return columns.back().values[r];
656 bool Layout::LinearProgram::solve()
658 if(solved || infeasible)
661 /* Solve the program using the simplex method. The column representing the
662 objective variable is kept implicit, as it would never change during the
663 execution of the algorithm. */
667 add_artificial_variables();
669 // Solve the phase 1 problem.
672 /* All artificial variables should now be non-basic and thus zero, so the
673 objective function's value should also be zero. If it isn't, the original
674 program can't be solved. */
675 if(columns.back().values.front())
681 remove_artificial_variables();
683 // Solve the phase 2 problem. We already know it to be feasible.
691 void Layout::LinearProgram::prepare_columns()
693 /* See if any variables are already basic. A basic variable must only have
694 a nonzero coefficient on one row, and its product with the constant column
695 must not be negative. Only one variable can be basic for any given row. */
696 vector<float> obj_coeff(n_rows, 0.0f);
697 vector<float> row_coeff(n_rows, 1.0f);
698 const vector<float> &constants = columns.back().values;
699 for(Column &c: columns)
700 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)
703 for(size_t j=1; (basic && j+1<c.values.size()); ++j)
704 basic = (c.values[j]==0.0f);
707 c.basic = c.values.size()-1;
708 row_coeff[c.basic] = 1.0f/c.values.back();
709 obj_coeff[c.basic] = -c.values.front();
714 // Price out the newly-created basic variables.
715 for(Column &c: columns)
716 if(!c.values.empty())
718 for(size_t j=0; j<c.values.size(); ++j)
720 c.values[j] *= row_coeff[j];
721 c.values.front() += obj_coeff[j]*c.values[j];
726 void Layout::LinearProgram::add_artificial_variables()
728 vector<size_t> artificial_rows(n_rows-1);
729 for(size_t i=0; i<artificial_rows.size(); ++i)
730 artificial_rows[i] = i+1;
732 for(const Column &c: columns)
734 artificial_rows[c.basic-1] = 0;
735 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
737 /* Force all non-basic columns fully into existence and relocate objective
738 row to bottom in preparation of phase 1. A new objective row is calculated
739 by pricing out the constraint rows. */
740 for(Column &c: columns)
743 float objective = 0.0f;
744 if(!c.values.empty())
746 objective = c.values.front();
747 c.values.front() = 0.0f;
748 for(size_t r: artificial_rows)
749 if(r<c.values.size())
750 c.values.front() += c.values[r];
752 c.values.resize(n_rows+1, 0.0f);
753 c.values.back() = objective;
756 if(artificial_rows.empty())
759 /* Create artificial variables for phase 1. This ensures that each row has
760 a basic variable associated with it. The original objective row already
761 contains the implicit objective variable, which is basic. */
762 columns.resize(n_columns+artificial_rows.size());
763 columns.back() = columns[n_columns-1];
764 columns[n_columns-1].values.clear();
765 for(size_t i=0; i<artificial_rows.size(); ++i)
766 columns[n_columns+i-1].basic = artificial_rows[i];
769 void Layout::LinearProgram::remove_artificial_variables()
771 /* See if any artificial variables are still basic. This could be because
772 the program is degenerate. To avoid trouble later on, use pivots to make
773 some of the original variables basic instead.
775 I don't fully understand why this is needed, but it appears to work. */
776 for(size_t i=n_columns-1; i+1<columns.size(); ++i)
777 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
779 for(size_t j=0; j+1<n_columns; ++j)
780 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
782 make_basic_column(j, columns[i].basic);
787 /* Get rid of the artificial variables and restore the original objective
788 row to form the phase 2 problem. */
789 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
790 for(Column &c: columns)
793 c.values.front() = c.values.back();
798 size_t Layout::LinearProgram::find_minimal_ratio(size_t c)
800 /* Pick the row with the minimum ratio between the constant column and the
801 pivot column. This ensures that when the pivot column is made basic, values
802 in the constant column stay positive.
804 The use of n_rows instead of the true size of the column is intentional,
805 since the relocated objective row must be ignored in phase 1. */
806 float best = numeric_limits<float>::infinity();
808 for(size_t i=1; i<n_rows; ++i)
809 if(columns[c].values[i]>0)
811 float ratio = columns.back().values[i]/columns[c].values[i];
822 void Layout::LinearProgram::make_basic_column(size_t c, size_t r)
824 /* Perform row transfer operations to make the pivot column basic,
825 containing a 1 on the pivot row. */
826 for(size_t i=0; i<columns.size(); ++i)
827 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
831 columns[i].values.resize(columns.back().values.size(), 0.0f);
832 columns[i].values[columns[i].basic] = 1.0f;
833 columns[i].basic = 0;
836 float scale = columns[i].values[r]/columns[c].values[r];
838 columns[i].values[r] = scale;
839 for(size_t j=0; j<columns[i].values.size(); ++j)
841 columns[i].values[j] -= scale*columns[c].values[j];
844 columns[c].basic = r;
845 columns[c].values.clear();
848 bool Layout::LinearProgram::pivot()
850 /* Pick a nonbasic column and make it basic. Requiring a positive objective
851 coefficient ensures that the objective function's value will decrease in the
853 for(size_t i=0; i+1<columns.size(); ++i)
854 if(!columns[i].basic && columns[i].values.front()>0)
855 if(size_t row = find_minimal_ratio(i))
857 make_basic_column(i, row);
865 Layout::LinearProgram::Row::Row(LinearProgram &lp, size_t i):
870 float &Layout::LinearProgram::Row::operator[](size_t c)
872 if(c>=linprog.n_columns)
873 throw out_of_range("Row::operator[]");
875 Column &column = linprog.columns[c];
876 if(column.values.size()<=index)
877 column.values.resize(index+1);
879 return column.values[index];
882 float &Layout::LinearProgram::Row::back()
884 return (*this)[linprog.n_columns-1];
888 Layout::LinearProgram::Column::Column():