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()
322 solve_constraints(HORIZONTAL, AUTOSIZE);
323 solve_constraints(VERTICAL, AUTOSIZE);
325 container->set_size(autosize_geom.w, autosize_geom.h);
328 void Layout::solve_constraints(int dir, SolveMode mode)
330 Pointers &ptrs = pointers[dir&VERTICAL];
332 const Geometry &geom = container->get_geometry();
333 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
336 /* Set up a linear program to solve the constraints. The program matrix has
337 five columns for each widget, and one constant column. The first and second
338 columns of a widget are its position and dimension, respectively. The
339 remaining three are slack columns; see below for their purposes. */
340 LinearProgram linprog(n_active_slots*5+n_slack_constraints[dir]+1);
341 float weight = slots.size();
342 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
347 LinearProgram::Row objective = linprog.get_objective_row();
350 objective[(*i)->index*5] = -1;
351 objective[(*i)->index*5+1] = -1;
355 objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
356 objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
360 // Prevent the widget from going past the container's low edge.
361 LinearProgram::Row row = linprog.add_row();
362 row[(*i)->index*5] = 1;
363 row[(*i)->index*5+2] = -1;
364 row.back() = margin.*(ptrs.low_margin);
369 // Prevent the widget from going past the container's high edge.
370 LinearProgram::Row row = linprog.add_row();
371 row[(*i)->index*5] = 1;
372 row[(*i)->index*5+1] = 1;
373 row[(*i)->index*5+3] = 1;
374 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
377 if(((*i)->*(ptrs.packing)).gravity==0)
379 /* This forces the widget's distance from the left and right edge of
380 the container to be equal. It's a bit of a hack, but more time and
381 thought is needed for a better solution. */
382 LinearProgram::Row row = linprog.add_row();
383 row[(*i)->index*5+2] = 1;
384 row[(*i)->index*5+3] = -1;
388 /* Don't allow the widget's dimension to get below that determined
390 LinearProgram::Row row = linprog.add_row();
391 row[(*i)->index*5+1] = 1;
392 row[(*i)->index*5+4] = -1;
393 row.back() = (*i)->autosize_geom.*(ptrs.dim);
396 /* Add rows for user-defined constraints. Constraints are always added
397 in pairs, so it's only necessary to create a row for one half. */
398 unsigned k = n_active_slots*5;
399 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
400 if(j->target.index>(*i)->index && (j->type&1)==dir)
402 LinearProgram::Row row = linprog.add_row();
403 float polarity = ((j->type&SELF_DIM) ? -1 : 1);
405 row[(*i)->index*5] = polarity;
407 row[(*i)->index*5+1] = polarity;
408 if(j->type&TARGET_POS)
409 row[j->target.index*5] = -polarity;
410 if(j->type&TARGET_DIM)
411 row[j->target.index*5+1] = -polarity;
413 row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
424 autosize_geom.*(ptrs.dim) = 0;
425 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
428 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
429 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
434 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
437 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
438 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
444 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
451 Layout::Packing::Packing():
457 Layout::Slot::Slot(Layout &l, Widget &w):
463 vert_pack.gravity = 1;
464 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
465 widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
467 autosize_geom = widget.get_geometry();
470 void Layout::Slot::autosize_changed()
473 autosize_geom = widget.get_geometry();
475 if(!widget.is_visible() && !ghost)
478 // If the widget fits in the area it had, just leave it there.
479 if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
480 widget.set_geometry(geom);
483 layout.container->signal_autosize_changed.emit();
488 void Layout::Slot::visibility_changed(bool v)
490 layout.update_slot_indices();
493 layout.container->signal_autosize_changed.emit();
499 Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
500 DataFile::ObjectLoader<Layout>(l),
503 add("column_spacing", &Loader::column_spacing);
504 add("margin", &Loader::margin);
505 add("row_spacing", &Loader::row_spacing);
506 add("spacing", &Loader::spacing);
507 add("widget", &Loader::widget);
510 void Layout::Loader::column_spacing(unsigned s)
512 obj.set_column_spacing(s);
515 void Layout::Loader::margin()
519 obj.set_margin(sides);
522 void Layout::Loader::spacing(unsigned s)
527 void Layout::Loader::row_spacing(unsigned s)
529 obj.set_row_spacing(s);
532 void Layout::Loader::widget(const string &n)
534 Widget &wdg = *get_item(wdg_map, n);
535 WidgetLoader ldr(obj, wdg, wdg_map);
540 Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
545 add("constraint", &WidgetLoader::constraint);
546 add("expand", &WidgetLoader::expand);
547 add("ghost", &WidgetLoader::ghost);
548 add("gravity", &WidgetLoader::gravity);
551 void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
553 Widget &target = *get_item(wdg_map, n);
554 layout.add_constraint(widget, type, target);
557 void Layout::WidgetLoader::expand(bool h, bool v)
559 layout.set_expand(widget, h, v);
562 void Layout::WidgetLoader::ghost(bool g)
564 layout.set_ghost(widget, g);
567 void Layout::WidgetLoader::gravity(int h, int v)
569 layout.set_gravity(widget, h, v);
573 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
575 const string &str = conv.get();
577 ctype = Layout::ABOVE;
578 else if(str=="BELOW")
579 ctype = Layout::BELOW;
580 else if(str=="RIGHT_OF")
581 ctype = Layout::RIGHT_OF;
582 else if(str=="LEFT_OF")
583 ctype = Layout::LEFT_OF;
584 else if(str=="FAR_ABOVE")
585 ctype = Layout::FAR_ABOVE;
586 else if(str=="FAR_BELOW")
587 ctype = Layout::FAR_BELOW;
588 else if(str=="FAR_RIGHT_OF")
589 ctype = Layout::FAR_RIGHT_OF;
590 else if(str=="FAR_LEFT_OF")
591 ctype = Layout::FAR_LEFT_OF;
592 else if(str=="ALIGN_TOP")
593 ctype = Layout::ALIGN_TOP;
594 else if(str=="ALIGN_BOTTOM")
595 ctype = Layout::ALIGN_BOTTOM;
596 else if(str=="ALIGN_RIGHT")
597 ctype = Layout::ALIGN_RIGHT;
598 else if(str=="ALIGN_LEFT")
599 ctype = Layout::ALIGN_LEFT;
600 else if(str=="COPY_WIDTH")
601 ctype = Layout::COPY_WIDTH;
602 else if(str=="COPY_HEIGHT")
603 ctype = Layout::COPY_HEIGHT;
605 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
609 Layout::LinearProgram::LinearProgram(unsigned s):
617 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
619 return Row(*this, n_rows++);
622 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
625 throw out_of_range("LinearProgram::operator[]");
627 return Row(*this, r);
630 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
632 return Row(*this, 0);
635 float Layout::LinearProgram::get_variable(unsigned i)
637 if(!solved || infeasible)
638 throw logic_error("not solved");
640 throw out_of_range("LinearProgram::get_variable");
642 if(unsigned r = columns[i].basic)
643 return columns.back().values[r];
648 bool Layout::LinearProgram::solve()
650 if(solved || infeasible)
653 /* Solve the program using the simplex method. The column representing the
654 objective variable is kept implicit, as it would never change during the
655 execution of the algorithm. */
659 add_artificial_variables();
661 // Solve the phase 1 problem.
664 /* All artificial variables should now be non-basic and thus zero, so the
665 objective function's value should also be zero. If it isn't, the original
666 program can't be solved. */
667 if(columns.back().values.front())
673 remove_artificial_variables();
675 // Solve the phase 2 problem. We already know it to be feasible.
683 void Layout::LinearProgram::prepare_columns()
685 /* See if any variables are already basic. A basic variable must only have
686 a nonzero coefficient on one row, and its product with the constant column
687 must not be negative. Only one variable can be basic for any given row. */
688 vector<float> obj_coeff(n_rows, 0.0f);
689 vector<float> row_coeff(n_rows, 1.0f);
690 const vector<float> &constants = columns.back().values;
691 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
693 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)
696 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
697 basic = (i->values[j]==0.0f);
700 i->basic = i->values.size()-1;
701 row_coeff[i->basic] = 1.0f/i->values.back();
702 obj_coeff[i->basic] = -i->values.front();
708 // Price out the newly-created basic variables.
709 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
710 if(!i->values.empty())
712 for(unsigned j=0; j<i->values.size(); ++j)
714 i->values[j] *= row_coeff[j];
715 i->values.front() += obj_coeff[j]*i->values[j];
720 void Layout::LinearProgram::add_artificial_variables()
722 vector<unsigned> artificial_rows(n_rows-1);
723 for(unsigned i=0; i<artificial_rows.size(); ++i)
724 artificial_rows[i] = i+1;
726 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
728 artificial_rows[i->basic-1] = 0;
729 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
731 /* Force all non-basic columns fully into existence and relocate objective
732 row to bottom in preparation of phase 1. A new objective row is calculated
733 by pricing out the constraint rows. */
734 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
737 float objective = 0.0f;
738 if(!i->values.empty())
740 objective = i->values.front();
741 i->values.front() = 0.0f;
742 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
743 if(*j<i->values.size())
744 i->values.front() += i->values[*j];
746 i->values.resize(n_rows+1, 0.0f);
747 i->values.back() = objective;
750 if(artificial_rows.empty())
753 /* Create artificial variables for phase 1. This ensures that each row has
754 a basic variable associated with it. The original objective row already
755 contains the implicit objective variable, which is basic. */
756 columns.resize(n_columns+artificial_rows.size());
757 columns.back() = columns[n_columns-1];
758 columns[n_columns-1].values.clear();
759 for(unsigned i=0; i<artificial_rows.size(); ++i)
760 columns[n_columns+i-1].basic = artificial_rows[i];
763 void Layout::LinearProgram::remove_artificial_variables()
765 /* See if any artificial variables are still basic. This could be because
766 the program is degenerate. To avoid trouble later on, use pivots to make
767 some of the original variables basic instead.
769 I don't fully understand why this is needed, but it appears to work. */
770 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
771 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
773 for(unsigned j=0; j+1<n_columns; ++j)
774 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
776 make_basic_column(j, columns[i].basic);
781 /* Get rid of the artificial variables and restore the original objective
782 row to form the phase 2 problem. */
783 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
784 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
787 i->values.front() = i->values.back();
788 i->values.pop_back();
792 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
794 /* Pick the row with the minimum ratio between the constant column and the
795 pivot column. This ensures that when the pivot column is made basic, values
796 in the constant column stay positive.
798 The use of n_rows instead of the true size of the column is intentional,
799 since the relocated objective row must be ignored in phase 1. */
800 float best = numeric_limits<float>::infinity();
802 for(unsigned i=1; i<n_rows; ++i)
803 if(columns[c].values[i]>0)
805 float ratio = columns.back().values[i]/columns[c].values[i];
816 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
818 /* Perform row transfer operations to make the pivot column basic,
819 containing a 1 on the pivot row. */
820 for(unsigned i=0; i<columns.size(); ++i)
821 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
825 columns[i].values.resize(columns.back().values.size(), 0.0f);
826 columns[i].values[columns[i].basic] = 1.0f;
827 columns[i].basic = 0;
830 float scale = columns[i].values[r]/columns[c].values[r];
832 columns[i].values[r] = scale;
833 for(unsigned j=0; j<columns[i].values.size(); ++j)
835 columns[i].values[j] -= scale*columns[c].values[j];
838 columns[c].basic = r;
839 columns[c].values.clear();
842 bool Layout::LinearProgram::pivot()
844 /* Pick a nonbasic column and make it basic. Requiring a positive objective
845 coefficient ensures that the objective function's value will decrease in the
847 for(unsigned i=0; i+1<columns.size(); ++i)
848 if(!columns[i].basic && columns[i].values.front()>0)
849 if(unsigned row = find_minimal_ratio(i))
851 make_basic_column(i, row);
859 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
864 float &Layout::LinearProgram::Row::operator[](unsigned c)
866 if(c>=linprog.n_columns)
867 throw out_of_range("Row::operator[]");
869 Column &column = linprog.columns[c];
870 if(column.values.size()<=index)
871 column.values.resize(index+1);
873 return column.values[index];
876 float &Layout::LinearProgram::Row::back()
878 return (*this)[linprog.n_columns-1];
882 Layout::LinearProgram::Column::Column():