3 #include <msp/strings/format.h>
4 #include "arrangement.h"
14 class Layout::LinearProgram
20 LinearProgram &linprog;
24 Row(LinearProgram &, unsigned);
26 float &operator[](unsigned);
34 std::vector<float> values;
41 std::vector<Column> columns;
46 LinearProgram(unsigned);
49 Row operator[](unsigned);
50 Row get_objective_row();
51 float get_variable(unsigned);
54 void prepare_columns();
55 void add_artificial_variables();
56 void remove_artificial_variables();
57 unsigned find_minimal_ratio(unsigned);
58 void make_basic_column(unsigned, unsigned);
63 struct Layout::Pointers
66 unsigned Geometry::*dim;
67 Packing Slot::*packing;
68 unsigned Sides::*low_margin;
69 unsigned Sides::*high_margin;
70 unsigned Layout::*spacing;
73 Layout::Pointers Layout::pointers[2] =
75 &Geometry::x, &Geometry::w,
77 &Sides::left, &Sides::right,
80 &Geometry::y, &Geometry::h,
82 &Sides::bottom, &Sides::top,
94 n_slack_constraints[0] = 0;
95 n_slack_constraints[1] = 0;
100 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
104 void Layout::set_container(Container &c)
107 throw logic_error("container!=0");
112 void Layout::set_margin(const Sides &m)
119 void Layout::set_spacing(unsigned s)
127 void Layout::set_row_spacing(unsigned s)
134 void Layout::set_column_spacing(unsigned s)
141 void Layout::push_arrangement(Arrangement &arr)
143 arrangement_stack.push_back(&arr);
146 Arrangement *Layout::get_arrangement() const
148 if(arrangement_stack.empty())
151 return arrangement_stack.back();
154 void Layout::pop_arrangement(Arrangement &arr)
156 list<Arrangement *>::iterator begin = find(arrangement_stack.begin(), arrangement_stack.end(), &arr);
157 if(begin==arrangement_stack.end())
162 Arrangement *top = arrangement_stack.back();
163 arrangement_stack.pop_back();
164 if(!arrangement_stack.empty())
165 arrangement_stack.back()->arrange(*top);
171 void Layout::add_widget(Widget &wdg)
174 throw logic_error("!container");
176 slots.push_back(new Slot(*this, wdg));
177 update_slot_indices();
178 if(!arrangement_stack.empty())
179 arrangement_stack.back()->arrange(wdg);
184 void Layout::remove_widget(Widget &wdg)
186 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
187 if(&(*i)->widget==&wdg)
189 for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
192 for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
195 (*j)->constraints.erase(k++);
204 update_slot_indices();
210 void Layout::update_slot_indices()
213 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
215 if((*i)->widget.is_visible())
216 (*i)->index = n_active_slots++;
221 n_slack_constraints[0] = 0;
222 n_slack_constraints[1] = 0;
223 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
226 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
227 if(j->target.index>(*i)->index && (j->type&SLACK))
228 ++n_slack_constraints[j->type&1];
232 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
234 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
235 if(&(*i)->widget==&wdg)
238 throw hierarchy_error("widget not in layout");
241 Layout::ConstraintType Layout::complement(ConstraintType type)
243 return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
246 void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
249 throw invalid_argument("&src==&tgt");
251 Slot &src_slot = get_slot_for_widget(src);
252 Slot &tgt_slot = get_slot_for_widget(tgt);
254 for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
255 if(i->type==type && &i->target==&tgt_slot)
258 src_slot.constraints.push_back(Constraint(type, tgt_slot));
259 src_slot.constraints.back().spacing = sp;
260 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
261 tgt_slot.constraints.back().spacing = sp;
263 update_slot_indices();
267 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
269 create_constraint(src, type, tgt, -1);
272 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
274 create_constraint(src, type, tgt, spacing);
277 void Layout::set_gravity(Widget &wdg, int h, int v)
279 Slot &slot = get_slot_for_widget(wdg);
281 slot.horiz_pack.gravity = h;
282 slot.vert_pack.gravity = v;
287 void Layout::set_expand(Widget &wdg, bool h, bool v)
289 Slot &slot = get_slot_for_widget(wdg);
291 slot.horiz_pack.expand = h;
292 slot.vert_pack.expand = v;
297 void Layout::update()
299 solve_constraints(HORIZONTAL, UPDATE);
300 solve_constraints(VERTICAL, UPDATE);
302 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
303 (*i)->widget.set_geometry((*i)->geom);
306 void Layout::autosize()
308 solve_constraints(HORIZONTAL, AUTOSIZE);
309 solve_constraints(VERTICAL, AUTOSIZE);
311 container->set_size(autosize_geom.w, autosize_geom.h);
314 void Layout::solve_constraints(int dir, SolveMode mode)
316 Pointers &ptrs = pointers[dir&VERTICAL];
318 const Geometry &geom = container->get_geometry();
319 if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
322 /* Set up a linear program to solve the constraints. The program matrix has
323 five columns for each widget, and one constant column. The first and second
324 columns of a widget are its position and dimension, respectively. The
325 remaining three are slack columns; see below for their purposes. */
326 LinearProgram linprog(n_active_slots*5+n_slack_constraints[dir]+1);
327 float weight = slots.size();
328 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
333 LinearProgram::Row objective = linprog.get_objective_row();
336 objective[(*i)->index*5] = -1;
337 objective[(*i)->index*5+1] = -1;
341 objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
342 objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
346 // Prevent the widget from going past the container's low edge.
347 LinearProgram::Row row = linprog.add_row();
348 row[(*i)->index*5] = 1;
349 row[(*i)->index*5+2] = -1;
350 row.back() = margin.*(ptrs.low_margin);
355 // Prevent the widget from going past the container's high edge.
356 LinearProgram::Row row = linprog.add_row();
357 row[(*i)->index*5] = 1;
358 row[(*i)->index*5+1] = 1;
359 row[(*i)->index*5+3] = 1;
360 row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
363 if(((*i)->*(ptrs.packing)).gravity==0)
365 /* This forces the widget's distance from the left and right edge of
366 the container to be equal. It's a bit of a hack, but more time and
367 thought is needed for a better solution. */
368 LinearProgram::Row row = linprog.add_row();
369 row[(*i)->index*5+2] = 1;
370 row[(*i)->index*5+3] = -1;
374 /* Don't allow the widget's dimension to get below that determined
376 LinearProgram::Row row = linprog.add_row();
377 row[(*i)->index*5+1] = 1;
378 row[(*i)->index*5+4] = -1;
379 row.back() = (*i)->autosize_geom.*(ptrs.dim);
382 /* Add rows for user-defined constraints. Constraints are always added
383 in pairs, so it's only necessary to create a row for one half. */
384 unsigned k = n_active_slots*5;
385 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
386 if(j->target.index>(*i)->index && (j->type&1)==dir)
388 LinearProgram::Row row = linprog.add_row();
389 float polarity = ((j->type&SELF_DIM) ? -1 : 1);
391 row[(*i)->index*5] = polarity;
393 row[(*i)->index*5+1] = polarity;
394 if(j->type&TARGET_POS)
395 row[j->target.index*5] = -polarity;
396 if(j->type&TARGET_DIM)
397 row[j->target.index*5+1] = -polarity;
399 row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
410 autosize_geom.*(ptrs.dim) = 0;
411 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
414 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
415 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
420 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
423 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
424 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
430 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
437 Layout::Packing::Packing():
443 Layout::Slot::Slot(Layout &l, Widget &w):
448 vert_pack.gravity = 1;
449 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
450 widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
452 autosize_geom = widget.get_geometry();
455 void Layout::Slot::autosize_changed()
458 autosize_geom = widget.get_geometry();
460 if(!widget.is_visible())
463 // If the widget fits in the area it had, just leave it there.
464 if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
465 widget.set_geometry(geom);
468 layout.container->signal_autosize_changed.emit();
473 void Layout::Slot::visibility_changed(bool v)
475 layout.update_slot_indices();
478 layout.container->signal_autosize_changed.emit();
484 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
486 const string &str = conv.get();
488 ctype = Layout::ABOVE;
489 else if(str=="BELOW")
490 ctype = Layout::BELOW;
491 else if(str=="RIGHT_OF")
492 ctype = Layout::RIGHT_OF;
493 else if(str=="LEFT_OF")
494 ctype = Layout::LEFT_OF;
495 else if(str=="FAR_ABOVE")
496 ctype = Layout::FAR_ABOVE;
497 else if(str=="FAR_BELOW")
498 ctype = Layout::FAR_BELOW;
499 else if(str=="FAR_RIGHT_OF")
500 ctype = Layout::FAR_RIGHT_OF;
501 else if(str=="FAR_LEFT_OF")
502 ctype = Layout::FAR_LEFT_OF;
503 else if(str=="ALIGN_TOP")
504 ctype = Layout::ALIGN_TOP;
505 else if(str=="ALIGN_BOTTOM")
506 ctype = Layout::ALIGN_BOTTOM;
507 else if(str=="ALIGN_RIGHT")
508 ctype = Layout::ALIGN_RIGHT;
509 else if(str=="ALIGN_LEFT")
510 ctype = Layout::ALIGN_LEFT;
511 else if(str=="COPY_WIDTH")
512 ctype = Layout::COPY_WIDTH;
513 else if(str=="COPY_HEIGHT")
514 ctype = Layout::COPY_HEIGHT;
516 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
520 Layout::LinearProgram::LinearProgram(unsigned s):
528 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
530 return Row(*this, n_rows++);
533 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
536 throw out_of_range("LinearProgram::operator[]");
538 return Row(*this, r);
541 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
543 return Row(*this, 0);
546 float Layout::LinearProgram::get_variable(unsigned i)
548 if(!solved || infeasible)
549 throw logic_error("not solved");
551 throw out_of_range("LinearProgram::get_variable");
553 if(unsigned r = columns[i].basic)
554 return columns.back().values[r];
559 bool Layout::LinearProgram::solve()
561 if(solved || infeasible)
564 /* Solve the program using the simplex method. The column representing the
565 objective variable is kept implicit, as it would never change during the
566 execution of the algorithm. */
570 add_artificial_variables();
572 // Solve the phase 1 problem.
575 /* All artificial variables should now be non-basic and thus zero, so the
576 objective function's value should also be zero. If it isn't, the original
577 program can't be solved. */
578 if(columns.back().values.front())
584 remove_artificial_variables();
586 // Solve the phase 2 problem. We already know it to be feasible.
594 void Layout::LinearProgram::prepare_columns()
596 /* See if any variables are already basic. A basic variable must only have
597 a nonzero coefficient on one row, and its product with the constant column
598 must not be negative. Only one variable can be basic for any given row. */
599 vector<float> obj_coeff(n_rows, 0.0f);
600 vector<float> row_coeff(n_rows, 1.0f);
601 const vector<float> &constants = columns.back().values;
602 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
604 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)
607 for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
608 basic = (i->values[j]==0.0f);
611 i->basic = i->values.size()-1;
612 row_coeff[i->basic] = 1.0f/i->values.back();
613 obj_coeff[i->basic] = -i->values.front();
619 // Price out the newly-created basic variables.
620 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
621 if(!i->values.empty())
623 for(unsigned j=0; j<i->values.size(); ++j)
625 i->values[j] *= row_coeff[j];
626 i->values.front() += obj_coeff[j]*i->values[j];
631 void Layout::LinearProgram::add_artificial_variables()
633 vector<unsigned> artificial_rows(n_rows-1);
634 for(unsigned i=0; i<artificial_rows.size(); ++i)
635 artificial_rows[i] = i+1;
637 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
639 artificial_rows[i->basic-1] = 0;
640 artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
642 /* Force all non-basic columns fully into existence and relocate objective
643 row to bottom in preparation of phase 1. A new objective row is calculated
644 by pricing out the constraint rows. */
645 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
648 float objective = 0.0f;
649 if(!i->values.empty())
651 objective = i->values.front();
652 i->values.front() = 0.0f;
653 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
654 if(*j<i->values.size())
655 i->values.front() += i->values[*j];
657 i->values.resize(n_rows+1, 0.0f);
658 i->values.back() = objective;
661 if(artificial_rows.empty())
664 /* Create artificial variables for phase 1. This ensures that each row has
665 a basic variable associated with it. The original objective row already
666 contains the implicit objective variable, which is basic. */
667 columns.resize(n_columns+artificial_rows.size());
668 columns.back() = columns[n_columns-1];
669 columns[n_columns-1].values.clear();
670 for(unsigned i=0; i<artificial_rows.size(); ++i)
671 columns[n_columns+i-1].basic = artificial_rows[i];
674 void Layout::LinearProgram::remove_artificial_variables()
676 /* See if any artificial variables are still basic. This could be because
677 the program is degenerate. To avoid trouble later on, use pivots to make
678 some of the original variables basic instead.
680 I don't fully understand why this is needed, but it appears to work. */
681 for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
682 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
684 for(unsigned j=0; j+1<n_columns; ++j)
685 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
687 make_basic_column(j, columns[i].basic);
692 /* Get rid of the artificial variables and restore the original objective
693 row to form the phase 2 problem. */
694 columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
695 for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
698 i->values.front() = i->values.back();
699 i->values.pop_back();
703 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
705 /* Pick the row with the minimum ratio between the constant column and the
706 pivot column. This ensures that when the pivot column is made basic, values
707 in the constant column stay positive.
709 The use of n_rows instead of the true size of the column is intentional,
710 since the relocated objective row must be ignored in phase 1. */
711 float best = numeric_limits<float>::infinity();
713 for(unsigned i=1; i<n_rows; ++i)
714 if(columns[c].values[i]>0)
716 float ratio = columns.back().values[i]/columns[c].values[i];
727 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
729 /* Perform row transfer operations to make the pivot column basic,
730 containing a 1 on the pivot row. */
731 for(unsigned i=0; i<columns.size(); ++i)
732 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
736 columns[i].values.resize(columns.back().values.size(), 0.0f);
737 columns[i].values[columns[i].basic] = 1.0f;
738 columns[i].basic = 0;
741 float scale = columns[i].values[r]/columns[c].values[r];
743 columns[i].values[r] = scale;
744 for(unsigned j=0; j<columns[i].values.size(); ++j)
746 columns[i].values[j] -= scale*columns[c].values[j];
749 columns[c].basic = r;
750 columns[c].values.clear();
753 bool Layout::LinearProgram::pivot()
755 /* Pick a nonbasic column and make it basic. Requiring a positive objective
756 coefficient ensures that the objective function's value will decrease in the
758 for(unsigned i=0; i+1<columns.size(); ++i)
759 if(!columns[i].basic && columns[i].values.front()>0)
760 if(unsigned row = find_minimal_ratio(i))
762 make_basic_column(i, row);
770 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
775 float &Layout::LinearProgram::Row::operator[](unsigned c)
777 if(c>=linprog.n_columns)
778 throw out_of_range("Row::operator[]");
780 Column &column = linprog.columns[c];
781 if(column.values.size()<=index)
782 column.values.resize(index+1);
784 return column.values[index];
787 float &Layout::LinearProgram::Row::back()
789 return (*this)[linprog.n_columns-1];
793 Layout::LinearProgram::Column::Column():