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_BOTTOM")
631 ctype = Layout::ALIGN_BOTTOM;
632 else if(str=="ALIGN_RIGHT")
633 ctype = Layout::ALIGN_RIGHT;
634 else if(str=="ALIGN_LEFT")
635 ctype = Layout::ALIGN_LEFT;
636 else if(str=="COPY_WIDTH")
637 ctype = Layout::COPY_WIDTH;
638 else if(str=="COPY_HEIGHT")
639 ctype = Layout::COPY_HEIGHT;
641 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
645 Layout::LinearProgram::LinearProgram(unsigned s):
653 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
655 return Row(*this, n_rows++);
658 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
661 throw out_of_range("LinearProgram::operator[]");
663 return Row(*this, r);
666 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
668 return Row(*this, 0);
671 float Layout::LinearProgram::get_variable(unsigned i)
673 if(!solved || infeasible)
674 throw logic_error("not solved");
676 throw out_of_range("LinearProgram::get_variable");
678 if(unsigned r = columns[i].basic)
679 return columns.back().values[r];
684 bool Layout::LinearProgram::solve()
686 if(solved || infeasible)
689 /* Solve the program using the simplex method. The column representing the
690 objective variable is kept implicit, as it would never change during the
691 execution of the algorithm. */
695 add_artificial_variables();
697 // Solve the phase 1 problem.
700 /* All artificial variables should now be non-basic and thus zero, so the
701 objective function's value should also be zero. If it isn't, the original
702 program can't be solved. */
703 if(columns.back().values.front())
709 remove_artificial_variables();
711 // Solve the phase 2 problem. We already know it to be feasible.
719 void Layout::LinearProgram::prepare_columns()
721 /* See if any variables are already basic. A basic variable must only have
722 a nonzero coefficient on one row, and its product with the constant column
723 must not be negative. Only one variable can be basic for any given row. */
724 vector<float> obj_coeff(n_rows, 0.0f);
725 vector<float> row_coeff(n_rows, 1.0f);
726 const vector<float> &constants = columns.back().values;
727 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
729 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)
732 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
733 basic = (i->values[j]==0.0f);
736 i->basic = i->values.size()-1;
737 row_coeff[i->basic] = 1.0f/i->values.back();
738 obj_coeff[i->basic] = -i->values.front();
744 // Price out the newly-created basic variables.
745 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
746 if(!i->values.empty())
748 for(unsigned j=0; j<i->values.size(); ++j)
750 i->values[j] *= row_coeff[j];
751 i->values.front() += obj_coeff[j]*i->values[j];
756 void Layout::LinearProgram::add_artificial_variables()
758 vector<unsigned> artificial_rows(n_rows-1);
759 for(unsigned i=0; i<artificial_rows.size(); ++i)
760 artificial_rows[i] = i+1;
762 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
764 artificial_rows[i->basic-1] = 0;
765 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
767 /* Force all non-basic columns fully into existence and relocate objective
768 row to bottom in preparation of phase 1. A new objective row is calculated
769 by pricing out the constraint rows. */
770 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
773 float objective = 0.0f;
774 if(!i->values.empty())
776 objective = i->values.front();
777 i->values.front() = 0.0f;
778 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
779 if(*j<i->values.size())
780 i->values.front() += i->values[*j];
782 i->values.resize(n_rows+1, 0.0f);
783 i->values.back() = objective;
786 if(artificial_rows.empty())
789 /* Create artificial variables for phase 1. This ensures that each row has
790 a basic variable associated with it. The original objective row already
791 contains the implicit objective variable, which is basic. */
792 columns.resize(n_columns+artificial_rows.size());
793 columns.back() = columns[n_columns-1];
794 columns[n_columns-1].values.clear();
795 for(unsigned i=0; i<artificial_rows.size(); ++i)
796 columns[n_columns+i-1].basic = artificial_rows[i];
799 void Layout::LinearProgram::remove_artificial_variables()
801 /* See if any artificial variables are still basic. This could be because
802 the program is degenerate. To avoid trouble later on, use pivots to make
803 some of the original variables basic instead.
805 I don't fully understand why this is needed, but it appears to work. */
806 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
807 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
809 for(unsigned j=0; j+1<n_columns; ++j)
810 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
812 make_basic_column(j, columns[i].basic);
817 /* Get rid of the artificial variables and restore the original objective
818 row to form the phase 2 problem. */
819 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
820 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
823 i->values.front() = i->values.back();
824 i->values.pop_back();
828 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
830 /* Pick the row with the minimum ratio between the constant column and the
831 pivot column. This ensures that when the pivot column is made basic, values
832 in the constant column stay positive.
834 The use of n_rows instead of the true size of the column is intentional,
835 since the relocated objective row must be ignored in phase 1. */
836 float best = numeric_limits<float>::infinity();
838 for(unsigned i=1; i<n_rows; ++i)
839 if(columns[c].values[i]>0)
841 float ratio = columns.back().values[i]/columns[c].values[i];
852 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
854 /* Perform row transfer operations to make the pivot column basic,
855 containing a 1 on the pivot row. */
856 for(unsigned i=0; i<columns.size(); ++i)
857 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
861 columns[i].values.resize(columns.back().values.size(), 0.0f);
862 columns[i].values[columns[i].basic] = 1.0f;
863 columns[i].basic = 0;
866 float scale = columns[i].values[r]/columns[c].values[r];
868 columns[i].values[r] = scale;
869 for(unsigned j=0; j<columns[i].values.size(); ++j)
871 columns[i].values[j] -= scale*columns[c].values[j];
874 columns[c].basic = r;
875 columns[c].values.clear();
878 bool Layout::LinearProgram::pivot()
880 /* Pick a nonbasic column and make it basic. Requiring a positive objective
881 coefficient ensures that the objective function's value will decrease in the
883 for(unsigned i=0; i+1<columns.size(); ++i)
884 if(!columns[i].basic && columns[i].values.front()>0)
885 if(unsigned row = find_minimal_ratio(i))
887 make_basic_column(i, row);
895 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
900 float &Layout::LinearProgram::Row::operator[](unsigned c)
902 if(c>=linprog.n_columns)
903 throw out_of_range("Row::operator[]");
905 Column &column = linprog.columns[c];
906 if(column.values.size()<=index)
907 column.values.resize(index+1);
909 return column.values[index];
912 float &Layout::LinearProgram::Row::back()
914 return (*this)[linprog.n_columns-1];
918 Layout::LinearProgram::Column::Column():