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,
95 n_slack_constraints[0] = 0;
96 n_slack_constraints[1] = 0;
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++;
222 n_slack_constraints[0] = 0;
223 n_slack_constraints[1] = 0;
224 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
227 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
228 if(j->target.index>(*i)->index && (j->type&SLACK))
229 ++n_slack_constraints[j->type&1];
233 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
235 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
236 if(&(*i)->widget==&wdg)
239 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("&src==&tgt");
252 Slot &src_slot = get_slot_for_widget(src);
253 Slot &tgt_slot = get_slot_for_widget(tgt);
255 for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
256 if(i->type==type && &i->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;
288 void Layout::set_expand(Widget &wdg, bool h, bool v)
290 Slot &slot = get_slot_for_widget(wdg);
292 slot.horiz_pack.expand = h;
293 slot.vert_pack.expand = v;
298 void Layout::set_ghost(Widget &wdg, bool g)
300 Slot &slot = get_slot_for_widget(wdg);
304 if(!wdg.is_visible())
306 update_slot_indices();
311 void Layout::update()
313 solve_constraints(HORIZONTAL, UPDATE);
314 solve_constraints(VERTICAL, UPDATE);
316 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
317 (*i)->widget.set_geometry((*i)->geom);
320 void Layout::autosize(Geometry &geom)
322 solve_constraints(HORIZONTAL, AUTOSIZE);
323 solve_constraints(VERTICAL, AUTOSIZE);
325 geom.w = max(geom.w, autosize_geom.w);
326 geom.h = max(geom.h, autosize_geom.h);
329 void Layout::solve_constraints(int dir, SolveMode mode)
331 Pointers &ptrs = pointers[dir&VERTICAL];
333 const Geometry &geom = container->get_geometry();
334 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
337 /* Set up a linear program to solve the constraints. The program matrix has
338 five columns for each widget, and one constant column. The first and second
339 columns of a widget are its position and dimension, respectively. The
340 remaining three are slack columns; see below for their purposes. */
341 LinearProgram linprog(n_active_slots*5+n_slack_constraints[dir]+1);
342 float weight = slots.size();
343 unsigned k = n_active_slots*5;
344 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
349 LinearProgram::Row objective = linprog.get_objective_row();
352 objective[(*i)->index*5] = -1;
353 objective[(*i)->index*5+1] = -1;
357 objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
358 objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
362 // Prevent the widget from going past the container's low edge.
363 LinearProgram::Row row = linprog.add_row();
364 row[(*i)->index*5] = 1;
365 row[(*i)->index*5+2] = -1;
366 row.back() = margin.*(ptrs.low_margin);
371 // Prevent the widget from going past the container's high edge.
372 LinearProgram::Row row = linprog.add_row();
373 row[(*i)->index*5] = 1;
374 row[(*i)->index*5+1] = 1;
375 row[(*i)->index*5+3] = 1;
376 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
379 if(((*i)->*(ptrs.packing)).gravity==0)
381 /* This forces the widget's distance from the left and right edge of
382 the container to be equal. It's a bit of a hack, but more time and
383 thought is needed for a better solution. */
384 LinearProgram::Row row = linprog.add_row();
385 row[(*i)->index*5+2] = 1;
386 row[(*i)->index*5+3] = -1;
390 /* Don't allow the widget's dimension to get below that determined
392 LinearProgram::Row row = linprog.add_row();
393 row[(*i)->index*5+1] = 1;
394 row[(*i)->index*5+4] = -1;
395 row.back() = (*i)->autosize_geom.*(ptrs.dim);
398 /* Add rows for user-defined constraints. Constraints are always added
399 in pairs, so it's only necessary to create a row for one half. */
400 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
401 if(j->target.index>(*i)->index && (j->type&1)==dir)
403 LinearProgram::Row row = linprog.add_row();
404 float polarity = ((j->type&SELF_DIM) ? -1 : 1);
406 row[(*i)->index*5] = polarity;
408 row[(*i)->index*5+1] = polarity;
409 if(j->type&TARGET_POS)
410 row[j->target.index*5] = -polarity;
411 if(j->type&TARGET_DIM)
412 row[j->target.index*5+1] = -polarity;
414 row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
425 autosize_geom.*(ptrs.dim) = 0;
426 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
429 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
430 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
435 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
438 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
439 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
445 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
452 Layout::Packing::Packing():
458 Layout::Slot::Slot(Layout &l, Widget &w):
464 vert_pack.gravity = 1;
465 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
466 widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
468 autosize_geom = widget.get_geometry();
471 void Layout::Slot::autosize_changed()
474 autosize_geom = widget.get_geometry();
476 if(!widget.is_visible() && !ghost)
479 // If the widget fits in the area it had, just leave it there.
480 if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
481 widget.set_geometry(geom);
484 layout.container->signal_autosize_changed.emit();
489 void Layout::Slot::visibility_changed(bool v)
491 layout.update_slot_indices();
494 layout.container->signal_autosize_changed.emit();
500 Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
501 DataFile::ObjectLoader<Layout>(l),
504 add("column_spacing", &Loader::column_spacing);
505 add("margin", &Loader::margin);
506 add("row_spacing", &Loader::row_spacing);
507 add("spacing", &Loader::spacing);
508 add("widget", &Loader::widget);
511 void Layout::Loader::column_spacing(unsigned s)
513 obj.set_column_spacing(s);
516 void Layout::Loader::margin()
520 obj.set_margin(sides);
523 void Layout::Loader::spacing(unsigned s)
528 void Layout::Loader::row_spacing(unsigned s)
530 obj.set_row_spacing(s);
533 void Layout::Loader::widget(const string &n)
535 Widget &wdg = *get_item(wdg_map, n);
536 WidgetLoader ldr(obj, wdg, wdg_map);
541 Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
546 add("constraint", &WidgetLoader::constraint);
547 add("expand", &WidgetLoader::expand);
548 add("ghost", &WidgetLoader::ghost);
549 add("gravity", &WidgetLoader::gravity);
552 void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
554 Widget &target = *get_item(wdg_map, n);
555 layout.add_constraint(widget, type, target);
558 void Layout::WidgetLoader::expand(bool h, bool v)
560 layout.set_expand(widget, h, v);
563 void Layout::WidgetLoader::ghost(bool g)
565 layout.set_ghost(widget, g);
568 void Layout::WidgetLoader::gravity(int h, int v)
570 layout.set_gravity(widget, h, v);
574 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
576 const string &str = conv.get();
578 ctype = Layout::ABOVE;
579 else if(str=="BELOW")
580 ctype = Layout::BELOW;
581 else if(str=="RIGHT_OF")
582 ctype = Layout::RIGHT_OF;
583 else if(str=="LEFT_OF")
584 ctype = Layout::LEFT_OF;
585 else if(str=="FAR_ABOVE")
586 ctype = Layout::FAR_ABOVE;
587 else if(str=="FAR_BELOW")
588 ctype = Layout::FAR_BELOW;
589 else if(str=="FAR_RIGHT_OF")
590 ctype = Layout::FAR_RIGHT_OF;
591 else if(str=="FAR_LEFT_OF")
592 ctype = Layout::FAR_LEFT_OF;
593 else if(str=="ALIGN_TOP")
594 ctype = Layout::ALIGN_TOP;
595 else if(str=="ALIGN_BOTTOM")
596 ctype = Layout::ALIGN_BOTTOM;
597 else if(str=="ALIGN_RIGHT")
598 ctype = Layout::ALIGN_RIGHT;
599 else if(str=="ALIGN_LEFT")
600 ctype = Layout::ALIGN_LEFT;
601 else if(str=="COPY_WIDTH")
602 ctype = Layout::COPY_WIDTH;
603 else if(str=="COPY_HEIGHT")
604 ctype = Layout::COPY_HEIGHT;
606 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
610 Layout::LinearProgram::LinearProgram(unsigned s):
618 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
620 return Row(*this, n_rows++);
623 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
626 throw out_of_range("LinearProgram::operator[]");
628 return Row(*this, r);
631 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
633 return Row(*this, 0);
636 float Layout::LinearProgram::get_variable(unsigned i)
638 if(!solved || infeasible)
639 throw logic_error("not solved");
641 throw out_of_range("LinearProgram::get_variable");
643 if(unsigned r = columns[i].basic)
644 return columns.back().values[r];
649 bool Layout::LinearProgram::solve()
651 if(solved || infeasible)
654 /* Solve the program using the simplex method. The column representing the
655 objective variable is kept implicit, as it would never change during the
656 execution of the algorithm. */
660 add_artificial_variables();
662 // Solve the phase 1 problem.
665 /* All artificial variables should now be non-basic and thus zero, so the
666 objective function's value should also be zero. If it isn't, the original
667 program can't be solved. */
668 if(columns.back().values.front())
674 remove_artificial_variables();
676 // Solve the phase 2 problem. We already know it to be feasible.
684 void Layout::LinearProgram::prepare_columns()
686 /* See if any variables are already basic. A basic variable must only have
687 a nonzero coefficient on one row, and its product with the constant column
688 must not be negative. Only one variable can be basic for any given row. */
689 vector<float> obj_coeff(n_rows, 0.0f);
690 vector<float> row_coeff(n_rows, 1.0f);
691 const vector<float> &constants = columns.back().values;
692 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
694 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)
697 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
698 basic = (i->values[j]==0.0f);
701 i->basic = i->values.size()-1;
702 row_coeff[i->basic] = 1.0f/i->values.back();
703 obj_coeff[i->basic] = -i->values.front();
709 // Price out the newly-created basic variables.
710 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
711 if(!i->values.empty())
713 for(unsigned j=0; j<i->values.size(); ++j)
715 i->values[j] *= row_coeff[j];
716 i->values.front() += obj_coeff[j]*i->values[j];
721 void Layout::LinearProgram::add_artificial_variables()
723 vector<unsigned> artificial_rows(n_rows-1);
724 for(unsigned i=0; i<artificial_rows.size(); ++i)
725 artificial_rows[i] = i+1;
727 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
729 artificial_rows[i->basic-1] = 0;
730 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
732 /* Force all non-basic columns fully into existence and relocate objective
733 row to bottom in preparation of phase 1. A new objective row is calculated
734 by pricing out the constraint rows. */
735 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
738 float objective = 0.0f;
739 if(!i->values.empty())
741 objective = i->values.front();
742 i->values.front() = 0.0f;
743 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
744 if(*j<i->values.size())
745 i->values.front() += i->values[*j];
747 i->values.resize(n_rows+1, 0.0f);
748 i->values.back() = objective;
751 if(artificial_rows.empty())
754 /* Create artificial variables for phase 1. This ensures that each row has
755 a basic variable associated with it. The original objective row already
756 contains the implicit objective variable, which is basic. */
757 columns.resize(n_columns+artificial_rows.size());
758 columns.back() = columns[n_columns-1];
759 columns[n_columns-1].values.clear();
760 for(unsigned i=0; i<artificial_rows.size(); ++i)
761 columns[n_columns+i-1].basic = artificial_rows[i];
764 void Layout::LinearProgram::remove_artificial_variables()
766 /* See if any artificial variables are still basic. This could be because
767 the program is degenerate. To avoid trouble later on, use pivots to make
768 some of the original variables basic instead.
770 I don't fully understand why this is needed, but it appears to work. */
771 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
772 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
774 for(unsigned j=0; j+1<n_columns; ++j)
775 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
777 make_basic_column(j, columns[i].basic);
782 /* Get rid of the artificial variables and restore the original objective
783 row to form the phase 2 problem. */
784 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
785 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
788 i->values.front() = i->values.back();
789 i->values.pop_back();
793 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
795 /* Pick the row with the minimum ratio between the constant column and the
796 pivot column. This ensures that when the pivot column is made basic, values
797 in the constant column stay positive.
799 The use of n_rows instead of the true size of the column is intentional,
800 since the relocated objective row must be ignored in phase 1. */
801 float best = numeric_limits<float>::infinity();
803 for(unsigned i=1; i<n_rows; ++i)
804 if(columns[c].values[i]>0)
806 float ratio = columns.back().values[i]/columns[c].values[i];
817 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
819 /* Perform row transfer operations to make the pivot column basic,
820 containing a 1 on the pivot row. */
821 for(unsigned i=0; i<columns.size(); ++i)
822 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
826 columns[i].values.resize(columns.back().values.size(), 0.0f);
827 columns[i].values[columns[i].basic] = 1.0f;
828 columns[i].basic = 0;
831 float scale = columns[i].values[r]/columns[c].values[r];
833 columns[i].values[r] = scale;
834 for(unsigned j=0; j<columns[i].values.size(); ++j)
836 columns[i].values[j] -= scale*columns[c].values[j];
839 columns[c].basic = r;
840 columns[c].values.clear();
843 bool Layout::LinearProgram::pivot()
845 /* Pick a nonbasic column and make it basic. Requiring a positive objective
846 coefficient ensures that the objective function's value will decrease in the
848 for(unsigned i=0; i+1<columns.size(); ++i)
849 if(!columns[i].basic && columns[i].values.front()>0)
850 if(unsigned row = find_minimal_ratio(i))
852 make_basic_column(i, row);
860 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
865 float &Layout::LinearProgram::Row::operator[](unsigned c)
867 if(c>=linprog.n_columns)
868 throw out_of_range("Row::operator[]");
870 Column &column = linprog.columns[c];
871 if(column.values.size()<=index)
872 column.values.resize(index+1);
874 return column.values[index];
877 float &Layout::LinearProgram::Row::back()
879 return (*this)[linprog.n_columns-1];
883 Layout::LinearProgram::Column::Column():