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 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
216 if((*i)->widget.is_visible() || (*i)->ghost)
217 (*i)->index = n_active_slots++;
224 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
227 for(unsigned j=0; j<2; ++j)
228 if(((*i)->*(pointers[j].packing)).gravity==0)
229 n_slack_vars[j] += 2;
230 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
231 if(j->target.index>(*i)->index && (j->type&SLACK))
232 ++n_slack_vars[j->type&1];
236 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
238 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
239 if(&(*i)->widget==&wdg)
242 throw hierarchy_error("widget not in layout");
245 Layout::ConstraintType Layout::complement(ConstraintType type)
247 return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
250 void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
253 throw invalid_argument("&src==&tgt");
255 Slot &src_slot = get_slot_for_widget(src);
256 Slot &tgt_slot = get_slot_for_widget(tgt);
258 for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
259 if(i->type==type && &i->target==&tgt_slot)
262 src_slot.constraints.push_back(Constraint(type, tgt_slot));
263 src_slot.constraints.back().spacing = sp;
264 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
265 tgt_slot.constraints.back().spacing = sp;
267 update_slot_indices();
271 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
273 create_constraint(src, type, tgt, -1);
276 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
278 create_constraint(src, type, tgt, spacing);
281 void Layout::set_gravity(Widget &wdg, int h, int v)
283 Slot &slot = get_slot_for_widget(wdg);
285 slot.horiz_pack.gravity = h;
286 slot.vert_pack.gravity = v;
288 update_slot_indices();
292 void Layout::set_expand(Widget &wdg, bool h, bool v)
294 Slot &slot = get_slot_for_widget(wdg);
296 slot.horiz_pack.expand = h;
297 slot.vert_pack.expand = v;
302 void Layout::set_ghost(Widget &wdg, bool g)
304 Slot &slot = get_slot_for_widget(wdg);
308 if(!wdg.is_visible())
310 update_slot_indices();
315 void Layout::update()
317 solve_constraints(HORIZONTAL, UPDATE);
318 solve_constraints(VERTICAL, UPDATE);
320 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
321 (*i)->widget.set_geometry((*i)->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();
347 unsigned k = n_active_slots*5;
348 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
353 LinearProgram::Row objective = linprog.get_objective_row();
356 objective[(*i)->index*5] = -1;
357 objective[(*i)->index*5+1] = -1;
361 objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
362 objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
366 // Prevent the widget from going past the container's low edge.
367 LinearProgram::Row row = linprog.add_row();
368 row[(*i)->index*5] = 1;
369 row[(*i)->index*5+2] = -1;
370 row.back() = margin.*(ptrs.low_margin);
375 // Prevent the widget from going past the container's high edge.
376 LinearProgram::Row row = linprog.add_row();
377 row[(*i)->index*5] = 1;
378 row[(*i)->index*5+1] = 1;
379 row[(*i)->index*5+3] = 1;
380 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
383 if(((*i)->*(ptrs.packing)).gravity==0)
385 /* Try to keep the widget as close to the center of the container
386 as possible. Since linear programs can't express absolute values
387 directly, use two opposing slack variables that are optimized for
389 LinearProgram::Row row = linprog.add_row();
390 row[(*i)->index*5] = 1;
391 row[(*i)->index*5+1] = 0.5;
394 row.back() = geom.*(ptrs.dim)/2;
401 /* Don't allow the widget's dimension to get below that determined
403 LinearProgram::Row row = linprog.add_row();
404 row[(*i)->index*5+1] = 1;
405 row[(*i)->index*5+4] = -1;
406 row.back() = (*i)->autosize_geom.*(ptrs.dim);
409 /* Add rows for user-defined constraints. Constraints are always added
410 in pairs, so it's only necessary to create a row for one half. */
411 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
412 if(j->target.index>(*i)->index && (j->type&1)==dir)
414 LinearProgram::Row row = linprog.add_row();
415 float polarity = ((j->type&SELF_DIM) ? -1 : 1);
417 row[(*i)->index*5] = polarity;
419 row[(*i)->index*5+1] = polarity;
420 if(j->type&TARGET_POS)
421 row[j->target.index*5] = -polarity;
422 if(j->type&TARGET_DIM)
423 row[j->target.index*5+1] = -polarity;
425 row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
436 autosize_geom.*(ptrs.dim) = 0;
437 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
440 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
441 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
446 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
449 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
450 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
456 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
463 Layout::Packing::Packing():
469 Layout::Slot::Slot(Layout &l, Widget &w):
475 vert_pack.gravity = 1;
476 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
477 widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
479 autosize_geom = widget.get_geometry();
482 void Layout::Slot::autosize_changed()
484 widget.autosize(autosize_geom);
486 if(!widget.is_visible() && !ghost)
489 // Only trigger an update if the widget won't fit in its current area.
490 if(autosize_geom.w>geom.w || autosize_geom.h>geom.h)
492 layout.container->signal_autosize_changed.emit();
497 void Layout::Slot::visibility_changed(bool v)
499 layout.update_slot_indices();
502 layout.container->signal_autosize_changed.emit();
508 Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
509 DataFile::ObjectLoader<Layout>(l),
512 add("column_spacing", &Loader::column_spacing);
513 add("margin", &Loader::margin);
514 add("row_spacing", &Loader::row_spacing);
515 add("spacing", &Loader::spacing);
516 add("widget", &Loader::widget);
519 void Layout::Loader::column_spacing(unsigned s)
521 obj.set_column_spacing(s);
524 void Layout::Loader::margin()
528 obj.set_margin(sides);
531 void Layout::Loader::spacing(unsigned s)
536 void Layout::Loader::row_spacing(unsigned s)
538 obj.set_row_spacing(s);
541 void Layout::Loader::widget(const string &n)
543 Widget &wdg = *get_item(wdg_map, n);
544 WidgetLoader ldr(obj, wdg, wdg_map);
549 Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
554 add("constraint", &WidgetLoader::constraint);
555 add("expand", &WidgetLoader::expand);
556 add("ghost", &WidgetLoader::ghost);
557 add("gravity", &WidgetLoader::gravity);
560 void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
562 Widget &target = *get_item(wdg_map, n);
563 layout.add_constraint(widget, type, target);
566 void Layout::WidgetLoader::expand(bool h, bool v)
568 layout.set_expand(widget, h, v);
571 void Layout::WidgetLoader::ghost(bool g)
573 layout.set_ghost(widget, g);
576 void Layout::WidgetLoader::gravity(int h, int v)
578 layout.set_gravity(widget, h, v);
582 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
584 const string &str = conv.get();
586 ctype = Layout::ABOVE;
587 else if(str=="BELOW")
588 ctype = Layout::BELOW;
589 else if(str=="RIGHT_OF")
590 ctype = Layout::RIGHT_OF;
591 else if(str=="LEFT_OF")
592 ctype = Layout::LEFT_OF;
593 else if(str=="FAR_ABOVE")
594 ctype = Layout::FAR_ABOVE;
595 else if(str=="FAR_BELOW")
596 ctype = Layout::FAR_BELOW;
597 else if(str=="FAR_RIGHT_OF")
598 ctype = Layout::FAR_RIGHT_OF;
599 else if(str=="FAR_LEFT_OF")
600 ctype = Layout::FAR_LEFT_OF;
601 else if(str=="ALIGN_TOP")
602 ctype = Layout::ALIGN_TOP;
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_LEFT")
608 ctype = Layout::ALIGN_LEFT;
609 else if(str=="COPY_WIDTH")
610 ctype = Layout::COPY_WIDTH;
611 else if(str=="COPY_HEIGHT")
612 ctype = Layout::COPY_HEIGHT;
614 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
618 Layout::LinearProgram::LinearProgram(unsigned s):
626 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
628 return Row(*this, n_rows++);
631 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
634 throw out_of_range("LinearProgram::operator[]");
636 return Row(*this, r);
639 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
641 return Row(*this, 0);
644 float Layout::LinearProgram::get_variable(unsigned i)
646 if(!solved || infeasible)
647 throw logic_error("not solved");
649 throw out_of_range("LinearProgram::get_variable");
651 if(unsigned r = columns[i].basic)
652 return columns.back().values[r];
657 bool Layout::LinearProgram::solve()
659 if(solved || infeasible)
662 /* Solve the program using the simplex method. The column representing the
663 objective variable is kept implicit, as it would never change during the
664 execution of the algorithm. */
668 add_artificial_variables();
670 // Solve the phase 1 problem.
673 /* All artificial variables should now be non-basic and thus zero, so the
674 objective function's value should also be zero. If it isn't, the original
675 program can't be solved. */
676 if(columns.back().values.front())
682 remove_artificial_variables();
684 // Solve the phase 2 problem. We already know it to be feasible.
692 void Layout::LinearProgram::prepare_columns()
694 /* See if any variables are already basic. A basic variable must only have
695 a nonzero coefficient on one row, and its product with the constant column
696 must not be negative. Only one variable can be basic for any given row. */
697 vector<float> obj_coeff(n_rows, 0.0f);
698 vector<float> row_coeff(n_rows, 1.0f);
699 const vector<float> &constants = columns.back().values;
700 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
702 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)
705 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
706 basic = (i->values[j]==0.0f);
709 i->basic = i->values.size()-1;
710 row_coeff[i->basic] = 1.0f/i->values.back();
711 obj_coeff[i->basic] = -i->values.front();
717 // Price out the newly-created basic variables.
718 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
719 if(!i->values.empty())
721 for(unsigned j=0; j<i->values.size(); ++j)
723 i->values[j] *= row_coeff[j];
724 i->values.front() += obj_coeff[j]*i->values[j];
729 void Layout::LinearProgram::add_artificial_variables()
731 vector<unsigned> artificial_rows(n_rows-1);
732 for(unsigned i=0; i<artificial_rows.size(); ++i)
733 artificial_rows[i] = i+1;
735 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
737 artificial_rows[i->basic-1] = 0;
738 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
740 /* Force all non-basic columns fully into existence and relocate objective
741 row to bottom in preparation of phase 1. A new objective row is calculated
742 by pricing out the constraint rows. */
743 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
746 float objective = 0.0f;
747 if(!i->values.empty())
749 objective = i->values.front();
750 i->values.front() = 0.0f;
751 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
752 if(*j<i->values.size())
753 i->values.front() += i->values[*j];
755 i->values.resize(n_rows+1, 0.0f);
756 i->values.back() = objective;
759 if(artificial_rows.empty())
762 /* Create artificial variables for phase 1. This ensures that each row has
763 a basic variable associated with it. The original objective row already
764 contains the implicit objective variable, which is basic. */
765 columns.resize(n_columns+artificial_rows.size());
766 columns.back() = columns[n_columns-1];
767 columns[n_columns-1].values.clear();
768 for(unsigned i=0; i<artificial_rows.size(); ++i)
769 columns[n_columns+i-1].basic = artificial_rows[i];
772 void Layout::LinearProgram::remove_artificial_variables()
774 /* See if any artificial variables are still basic. This could be because
775 the program is degenerate. To avoid trouble later on, use pivots to make
776 some of the original variables basic instead.
778 I don't fully understand why this is needed, but it appears to work. */
779 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
780 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
782 for(unsigned j=0; j+1<n_columns; ++j)
783 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
785 make_basic_column(j, columns[i].basic);
790 /* Get rid of the artificial variables and restore the original objective
791 row to form the phase 2 problem. */
792 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
793 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
796 i->values.front() = i->values.back();
797 i->values.pop_back();
801 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
803 /* Pick the row with the minimum ratio between the constant column and the
804 pivot column. This ensures that when the pivot column is made basic, values
805 in the constant column stay positive.
807 The use of n_rows instead of the true size of the column is intentional,
808 since the relocated objective row must be ignored in phase 1. */
809 float best = numeric_limits<float>::infinity();
811 for(unsigned i=1; i<n_rows; ++i)
812 if(columns[c].values[i]>0)
814 float ratio = columns.back().values[i]/columns[c].values[i];
825 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
827 /* Perform row transfer operations to make the pivot column basic,
828 containing a 1 on the pivot row. */
829 for(unsigned i=0; i<columns.size(); ++i)
830 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
834 columns[i].values.resize(columns.back().values.size(), 0.0f);
835 columns[i].values[columns[i].basic] = 1.0f;
836 columns[i].basic = 0;
839 float scale = columns[i].values[r]/columns[c].values[r];
841 columns[i].values[r] = scale;
842 for(unsigned j=0; j<columns[i].values.size(); ++j)
844 columns[i].values[j] -= scale*columns[c].values[j];
847 columns[c].basic = r;
848 columns[c].values.clear();
851 bool Layout::LinearProgram::pivot()
853 /* Pick a nonbasic column and make it basic. Requiring a positive objective
854 coefficient ensures that the objective function's value will decrease in the
856 for(unsigned i=0; i+1<columns.size(); ++i)
857 if(!columns[i].basic && columns[i].values.front()>0)
858 if(unsigned row = find_minimal_ratio(i))
860 make_basic_column(i, row);
868 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
873 float &Layout::LinearProgram::Row::operator[](unsigned c)
875 if(c>=linprog.n_columns)
876 throw out_of_range("Row::operator[]");
878 Column &column = linprog.columns[c];
879 if(column.values.size()<=index)
880 column.values.resize(index+1);
882 return column.values[index];
885 float &Layout::LinearProgram::Row::back()
887 return (*this)[linprog.n_columns-1];
891 Layout::LinearProgram::Column::Column():