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));
478 widget.autosize(autosize_geom);
481 void Layout::Slot::autosize_changed()
483 widget.autosize(autosize_geom);
485 if(!widget.is_visible() && !ghost)
488 // Only trigger an update if the widget won't fit in its current area.
489 if(autosize_geom.w>geom.w || autosize_geom.h>geom.h)
491 layout.container->signal_autosize_changed.emit();
496 void Layout::Slot::visibility_changed(bool v)
498 layout.update_slot_indices();
501 layout.container->signal_autosize_changed.emit();
507 Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
508 DataFile::ObjectLoader<Layout>(l),
511 add("column_spacing", &Loader::column_spacing);
512 add("margin", &Loader::margin);
513 add("row_spacing", &Loader::row_spacing);
514 add("spacing", &Loader::spacing);
515 add("widget", &Loader::widget);
518 void Layout::Loader::column_spacing(unsigned s)
520 obj.set_column_spacing(s);
523 void Layout::Loader::margin()
527 obj.set_margin(sides);
530 void Layout::Loader::spacing(unsigned s)
535 void Layout::Loader::row_spacing(unsigned s)
537 obj.set_row_spacing(s);
540 void Layout::Loader::widget(const string &n)
542 Widget &wdg = *get_item(wdg_map, n);
543 WidgetLoader ldr(obj, wdg, wdg_map);
548 Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
553 add("constraint", &WidgetLoader::constraint);
554 add("expand", &WidgetLoader::expand);
555 add("ghost", &WidgetLoader::ghost);
556 add("gravity", &WidgetLoader::gravity);
559 void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
561 Widget &target = *get_item(wdg_map, n);
562 layout.add_constraint(widget, type, target);
565 void Layout::WidgetLoader::expand(bool h, bool v)
567 layout.set_expand(widget, h, v);
570 void Layout::WidgetLoader::ghost(bool g)
572 layout.set_ghost(widget, g);
575 void Layout::WidgetLoader::gravity(int h, int v)
577 layout.set_gravity(widget, h, v);
581 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
583 const string &str = conv.get();
585 ctype = Layout::ABOVE;
586 else if(str=="BELOW")
587 ctype = Layout::BELOW;
588 else if(str=="RIGHT_OF")
589 ctype = Layout::RIGHT_OF;
590 else if(str=="LEFT_OF")
591 ctype = Layout::LEFT_OF;
592 else if(str=="FAR_ABOVE")
593 ctype = Layout::FAR_ABOVE;
594 else if(str=="FAR_BELOW")
595 ctype = Layout::FAR_BELOW;
596 else if(str=="FAR_RIGHT_OF")
597 ctype = Layout::FAR_RIGHT_OF;
598 else if(str=="FAR_LEFT_OF")
599 ctype = Layout::FAR_LEFT_OF;
600 else if(str=="ALIGN_TOP")
601 ctype = Layout::ALIGN_TOP;
602 else if(str=="ALIGN_BOTTOM")
603 ctype = Layout::ALIGN_BOTTOM;
604 else if(str=="ALIGN_RIGHT")
605 ctype = Layout::ALIGN_RIGHT;
606 else if(str=="ALIGN_LEFT")
607 ctype = Layout::ALIGN_LEFT;
608 else if(str=="COPY_WIDTH")
609 ctype = Layout::COPY_WIDTH;
610 else if(str=="COPY_HEIGHT")
611 ctype = Layout::COPY_HEIGHT;
613 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
617 Layout::LinearProgram::LinearProgram(unsigned s):
625 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
627 return Row(*this, n_rows++);
630 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned 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(unsigned i)
645 if(!solved || infeasible)
646 throw logic_error("not solved");
648 throw out_of_range("LinearProgram::get_variable");
650 if(unsigned 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(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
701 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)
704 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
705 basic = (i->values[j]==0.0f);
708 i->basic = i->values.size()-1;
709 row_coeff[i->basic] = 1.0f/i->values.back();
710 obj_coeff[i->basic] = -i->values.front();
716 // Price out the newly-created basic variables.
717 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
718 if(!i->values.empty())
720 for(unsigned j=0; j<i->values.size(); ++j)
722 i->values[j] *= row_coeff[j];
723 i->values.front() += obj_coeff[j]*i->values[j];
728 void Layout::LinearProgram::add_artificial_variables()
730 vector<unsigned> artificial_rows(n_rows-1);
731 for(unsigned i=0; i<artificial_rows.size(); ++i)
732 artificial_rows[i] = i+1;
734 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
736 artificial_rows[i->basic-1] = 0;
737 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
739 /* Force all non-basic columns fully into existence and relocate objective
740 row to bottom in preparation of phase 1. A new objective row is calculated
741 by pricing out the constraint rows. */
742 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
745 float objective = 0.0f;
746 if(!i->values.empty())
748 objective = i->values.front();
749 i->values.front() = 0.0f;
750 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
751 if(*j<i->values.size())
752 i->values.front() += i->values[*j];
754 i->values.resize(n_rows+1, 0.0f);
755 i->values.back() = objective;
758 if(artificial_rows.empty())
761 /* Create artificial variables for phase 1. This ensures that each row has
762 a basic variable associated with it. The original objective row already
763 contains the implicit objective variable, which is basic. */
764 columns.resize(n_columns+artificial_rows.size());
765 columns.back() = columns[n_columns-1];
766 columns[n_columns-1].values.clear();
767 for(unsigned i=0; i<artificial_rows.size(); ++i)
768 columns[n_columns+i-1].basic = artificial_rows[i];
771 void Layout::LinearProgram::remove_artificial_variables()
773 /* See if any artificial variables are still basic. This could be because
774 the program is degenerate. To avoid trouble later on, use pivots to make
775 some of the original variables basic instead.
777 I don't fully understand why this is needed, but it appears to work. */
778 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
779 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
781 for(unsigned j=0; j+1<n_columns; ++j)
782 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
784 make_basic_column(j, columns[i].basic);
789 /* Get rid of the artificial variables and restore the original objective
790 row to form the phase 2 problem. */
791 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
792 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
795 i->values.front() = i->values.back();
796 i->values.pop_back();
800 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
802 /* Pick the row with the minimum ratio between the constant column and the
803 pivot column. This ensures that when the pivot column is made basic, values
804 in the constant column stay positive.
806 The use of n_rows instead of the true size of the column is intentional,
807 since the relocated objective row must be ignored in phase 1. */
808 float best = numeric_limits<float>::infinity();
810 for(unsigned i=1; i<n_rows; ++i)
811 if(columns[c].values[i]>0)
813 float ratio = columns.back().values[i]/columns[c].values[i];
824 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
826 /* Perform row transfer operations to make the pivot column basic,
827 containing a 1 on the pivot row. */
828 for(unsigned i=0; i<columns.size(); ++i)
829 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
833 columns[i].values.resize(columns.back().values.size(), 0.0f);
834 columns[i].values[columns[i].basic] = 1.0f;
835 columns[i].basic = 0;
838 float scale = columns[i].values[r]/columns[c].values[r];
840 columns[i].values[r] = scale;
841 for(unsigned j=0; j<columns[i].values.size(); ++j)
843 columns[i].values[j] -= scale*columns[c].values[j];
846 columns[c].basic = r;
847 columns[c].values.clear();
850 bool Layout::LinearProgram::pivot()
852 /* Pick a nonbasic column and make it basic. Requiring a positive objective
853 coefficient ensures that the objective function's value will decrease in the
855 for(unsigned i=0; i+1<columns.size(); ++i)
856 if(!columns[i].basic && columns[i].values.front()>0)
857 if(unsigned row = find_minimal_ratio(i))
859 make_basic_column(i, row);
867 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
872 float &Layout::LinearProgram::Row::operator[](unsigned c)
874 if(c>=linprog.n_columns)
875 throw out_of_range("Row::operator[]");
877 Column &column = linprog.columns[c];
878 if(column.values.size()<=index)
879 column.values.resize(index+1);
881 return column.values[index];
884 float &Layout::LinearProgram::Row::back()
886 return (*this)[linprog.n_columns-1];
890 Layout::LinearProgram::Column::Column():