]> git.tdb.fi Git - libs/gltk.git/blob - source/layout.cpp
ccd02830924b0622eb12dcf86ba4a0aa9b5a2b74
[libs/gltk.git] / source / layout.cpp
1 #include <algorithm>
2 #include <limits>
3 #include "container.h"
4 #include "layout.h"
5 #include "widget.h"
6
7 using namespace std;
8
9 namespace Msp {
10 namespace GLtk {
11
12 class Layout::LinearProgram
13 {
14 public:
15         class Row
16         {
17         private:
18                 LinearProgram &linprog;
19                 unsigned index;
20
21         public:
22                 Row(LinearProgram &, unsigned);
23
24                 float &operator[](unsigned);
25                 float &back();
26         };
27
28 private:
29         struct Column
30         {
31                 unsigned basic;
32                 std::vector<float> values;
33
34                 Column();
35         };
36
37         unsigned n_columns;
38         unsigned n_rows;
39         std::vector<Column> columns;
40         bool solved;
41         bool infeasible;
42
43 public:
44         LinearProgram(unsigned);
45
46         Row add_row();
47         Row operator[](unsigned);
48         Row get_objective_row();
49         float get_variable(unsigned);
50         bool solve();
51 private:
52         void prepare_columns();
53         void add_artificial_variables();
54         void remove_artificial_variables();
55         unsigned find_minimal_ratio(unsigned);
56         void make_basic_column(unsigned, unsigned);
57         bool pivot();
58 };
59
60
61 struct Layout::Pointers
62 {
63         int Geometry::*pos;
64         unsigned Geometry::*dim;
65         Packing Slot::*packing;
66         unsigned Sides::*low_margin;
67         unsigned Sides::*high_margin;
68         unsigned Layout::*spacing;
69 };
70
71 Layout::Pointers Layout::pointers[2] =
72 { {
73                 &Geometry::x, &Geometry::w,
74                 &Slot::horiz_pack,
75                 &Sides::left, &Sides::right,
76                 &Layout::col_spacing
77         }, {
78                 &Geometry::y, &Geometry::h,
79                 &Slot::vert_pack,
80                 &Sides::bottom, &Sides::top,
81                 &Layout::row_spacing
82 } };
83
84
85 Layout::Layout():
86         container(0),
87         margin(8),
88         row_spacing(5),
89         col_spacing(4)
90 { }
91
92 Layout::~Layout()
93 {
94         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
95                 delete *i;
96 }
97
98 void Layout::set_container(Container &c)
99 {
100         if(container)
101                 throw logic_error("container!=0");
102
103         container = &c;
104 }
105
106 void Layout::set_margin(const Sides &m)
107 {
108         margin = m;
109         if(container)
110                 update();
111 }
112
113 void Layout::add_widget(Widget &wdg)
114 {
115         if(!container)
116                 throw logic_error("!container");
117
118         Slot *slot = create_slot(wdg);
119         for(list<Constraint>::iterator i=slot->constraints.begin(); i!=slot->constraints.end(); ++i)
120                 i->target.constraints.push_back(Constraint(complement(i->type), *slot));
121         slot->index = slots.size();
122         slots.push_back(slot);
123         if(container)
124                 update();
125 }
126
127 void Layout::remove_widget(Widget &wdg)
128 {
129         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
130                 if(&(*i)->widget==&wdg)
131                 {
132                         for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
133                                 if(j!=i)
134                                 {
135                                         for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
136                                         {
137                                                 if(&k->target==*i)
138                                                         (*j)->constraints.erase(k++);
139                                                 else
140                                                         ++k;
141                                         }
142                                 }
143
144                         delete *i;
145                         slots.erase(i);
146
147                         unsigned n = 0;
148                         for(i=slots.begin(); i!=slots.end(); ++i, ++n)
149                                 (*i)->index = n;
150
151                         update();
152                         return;
153                 }
154 }
155
156 Layout::Slot *Layout::create_slot(Widget &wdg)
157 {
158         return new Slot(*this, wdg);
159 }
160
161 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
162 {
163         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
164                 if(&(*i)->widget==&wdg)
165                         return **i;
166
167         throw hierarchy_error("widget not in layout");
168 }
169
170 Layout::ConstraintType Layout::complement(ConstraintType type)
171 {
172         if(type==RIGHT_OF)
173                 return LEFT_OF;
174         else if(type==LEFT_OF)
175                 return RIGHT_OF;
176         else if(type==ABOVE)
177                 return BELOW;
178         else if(type==BELOW)
179                 return ABOVE;
180         else
181                 return type;
182 }
183
184 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
185 {
186         if(&src==&tgt)
187                 throw invalid_argument("&src==&tgt");
188
189         Slot &src_slot = get_slot_for_widget(src);
190         Slot &tgt_slot = get_slot_for_widget(tgt);
191
192         for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
193                 if(i->type==type && &i->target==&tgt_slot)
194                         return;
195
196         src_slot.constraints.push_back(Constraint(type, tgt_slot));
197         tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
198
199         update();
200 }
201
202 void Layout::set_gravity(Widget &wdg, int h, int v)
203 {
204         Slot &slot = get_slot_for_widget(wdg);
205
206         slot.horiz_pack.gravity = h;
207         slot.vert_pack.gravity = v;
208
209         update();
210 }
211
212 void Layout::set_expand(Widget &wdg, bool h, bool v)
213 {
214         Slot &slot = get_slot_for_widget(wdg);
215
216         slot.horiz_pack.expand = h;
217         slot.vert_pack.expand = v;
218
219         update();
220 }
221
222 void Layout::update()
223 {
224         solve_constraints(HORIZONTAL, UPDATE);
225         solve_constraints(VERTICAL, UPDATE);
226
227         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
228                 (*i)->widget.set_geometry((*i)->geom);
229 }
230
231 void Layout::autosize()
232 {
233         solve_constraints(HORIZONTAL, AUTOSIZE);
234         solve_constraints(VERTICAL, AUTOSIZE);
235
236         container->set_size(autosize_geom.w, autosize_geom.h);
237 }
238
239 void Layout::solve_constraints(int dir, SolveMode mode)
240 {
241         Pointers &ptrs = pointers[dir&VERTICAL];
242
243         const Geometry &geom = container->get_geometry();
244         if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
245                 return;
246
247         /* Set up a linear program to solve the constraints.  The program matrix has
248         five columns for each widget, and one constant column.  The first and second
249         columns of a widget are its position and dimension, respectively.  The
250         remaining three are slack columns; see below for their purposes. */
251         LinearProgram linprog(slots.size()*5+1);
252         float weight = slots.size();
253         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
254         {
255                 LinearProgram::Row objective = linprog.get_objective_row();
256                 if(mode==AUTOSIZE)
257                 {
258                         objective[(*i)->index*5] = -1;
259                         objective[(*i)->index*5+1] = -1;
260                 }
261                 else
262                 {
263                         objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
264                         objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
265                 }
266
267                 {
268                         // Prevent the widget from going past the container's low edge.
269                         LinearProgram::Row row = linprog.add_row();
270                         row[(*i)->index*5] = 1;
271                         row[(*i)->index*5+2] = -1;
272                         row.back() = margin.*(ptrs.low_margin);
273                 }
274
275                 if(mode==UPDATE)
276                 {
277                         // Prevent the widget from going past the container's high edge.
278                         LinearProgram::Row row = linprog.add_row();
279                         row[(*i)->index*5] = 1;
280                         row[(*i)->index*5+1] = 1;
281                         row[(*i)->index*5+3] = 1;
282                         row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
283                 }
284
285                 {
286                         /* Only allow the widget's dimension to increase.  The geometry has
287                         previously been set to the smallest allowable size. */
288                         LinearProgram::Row row = linprog.add_row();
289                         row[(*i)->index*5+1] = 1;
290                         row[(*i)->index*5+4] = -1;
291                         row.back() = (*i)->autosize_geom.*(ptrs.dim);
292                 }
293
294                 /* Add rows for user-defined constraints.  Below/above and left/right of
295                 constraints are always added in pairs, so it's only necessary to create a
296                 row for one half. */
297                 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
298                         if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
299                         {
300                                 LinearProgram::Row row = linprog.add_row();
301                                 if(j->type&SELF_POS)
302                                         row[(*i)->index*5] = 1;
303                                 if(j->type&SELF_DIM)
304                                         row[(*i)->index*5+1] = 1;
305                                 if(j->type&TARGET_POS)
306                                         row[j->target.index*5] = -1;
307                                 if(j->type&TARGET_DIM)
308                                         row[j->target.index*5+1] = -1;
309                                 if(j->type&SPACING)
310                                         row.back() = this->*(ptrs.spacing);
311                         }
312         }
313
314         if(!linprog.solve())
315                 return;
316
317         if(mode==AUTOSIZE)
318         {
319                 autosize_geom.*(ptrs.dim) = 0;
320                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
321                 {
322                         int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
323                         autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
324                 }
325         }
326         else
327         {
328                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
329                 {
330                         (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
331                         (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
332                 }
333         }
334 }
335
336
337 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
338         type(t),
339         target(s)
340 { }
341
342
343 Layout::Packing::Packing():
344         gravity(-1),
345         expand(false)
346 { }
347
348
349 Layout::Slot::Slot(Layout &l, Widget &w):
350         layout(l),
351         index(0),
352         widget(w)
353 {
354         vert_pack.gravity = 1;
355         widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
356         widget.autosize();
357         autosize_geom = widget.get_geometry();
358 }
359
360 void Layout::Slot::autosize_changed()
361 {
362         widget.autosize();
363         autosize_geom = widget.get_geometry();
364
365         // If the widget fits in the area it had, just leave it there.
366         if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
367                 widget.set_geometry(geom);
368         else
369         {
370                 layout.container->signal_autosize_changed.emit();
371                 layout.update();
372         }
373 }
374
375
376 Layout::LinearProgram::LinearProgram(unsigned s):
377         n_columns(s),
378         n_rows(1),
379         columns(n_columns),
380         solved(false),
381         infeasible(false)
382 { }
383
384 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
385 {
386         return Row(*this, n_rows++);
387 }
388
389 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
390 {
391         if(r>=n_rows)
392                 throw out_of_range("LinearProgram::operator[]");
393
394         return Row(*this, r);
395 }
396
397 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
398 {
399         return Row(*this, 0);
400 }
401
402 float Layout::LinearProgram::get_variable(unsigned i)
403 {
404         if(!solved || infeasible)
405                 throw logic_error("not solved");
406         if(i+1>=n_columns)
407                 throw out_of_range("LinearProgram::get_variable");
408
409         if(unsigned r = columns[i].basic)
410                 return columns.back().values[r];
411         else
412                 return 0;
413 }
414
415 bool Layout::LinearProgram::solve()
416 {
417         if(solved || infeasible)
418                 return !infeasible;
419
420         /* Solve the program using the simplex method.  The column representing the
421         objective variable is kept implicit, as it would never change during the
422         execution of the algorithm. */
423
424         prepare_columns();
425
426         add_artificial_variables();
427
428         // Solve the phase 1 problem.
429         while(pivot()) ;
430
431         /* All artificial variables should now be non-basic and thus zero, so the
432         objective function's value should also be zero.  If it isn't, the original
433         program can't be solved. */
434         if(columns.back().values.front())
435         {
436                 infeasible = true;
437                 return false;
438         }
439
440         remove_artificial_variables();
441
442         // Solve the phase 2 problem.  We already know it to be feasible.
443         while(pivot()) ;
444
445         solved = true;
446
447         return true;
448 }
449
450 void Layout::LinearProgram::prepare_columns()
451 {
452         /* See if any variables are already basic.  A basic variable must only have
453         a nonzero coefficient on one row, and its product with the constant column
454         must not be negative.  Only one variable can be basic for any given row. */
455         vector<float> basic_coeff(n_rows, 0.0f);
456         const vector<float> &constants = columns.back().values;
457         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
458         {
459                 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) && basic_coeff[i->values.size()-1]==0.0f)
460                 {
461                         bool basic = true;
462                         for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
463                                 basic = (i->values[j]==0.0f);
464                         if(basic)
465                         {
466                                 i->basic = i->values.size()-1;
467                                 basic_coeff[i->basic] = -i->values.front()/i->values.back();
468                                 i->values.clear();
469                         }
470                 }
471         }
472
473         // Price out the newly-created basic variables.
474         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
475                 if(!i->values.empty())
476                 {
477                         for(unsigned j=0; j<i->values.size(); ++j)
478                                 i->values.front() += basic_coeff[j]*i->values[j];
479                 }
480 }
481
482 void Layout::LinearProgram::add_artificial_variables()
483 {
484         vector<unsigned> artificial_rows(n_rows-1);
485         for(unsigned i=0; i<artificial_rows.size(); ++i)
486                 artificial_rows[i] = i+1;
487
488         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
489                 if(i->basic)
490                         artificial_rows[i->basic-1] = 0;
491         artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
492
493         /* Force all non-basic columns fully into existence and relocate objective
494         row to bottom in preparation of phase 1.  A new objective row is calculated
495         by pricing out the constraint rows. */
496         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
497                 if(!i->basic)
498                 {
499                         float objective = 0.0f;
500                         if(!i->values.empty())
501                         {
502                                 objective = i->values.front();
503                                 i->values.front() = 0.0f;
504                                 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
505                                         if(*j<i->values.size())
506                                                 i->values.front() += i->values[*j];
507                         }
508                         i->values.resize(n_rows+1, 0.0f);
509                         i->values.back() = objective;
510                 }
511
512         if(artificial_rows.empty())
513                 return;
514
515         /* Create artificial variables for phase 1.  This ensures that each row has
516         a basic variable associated with it.  The original objective row already
517         contains the implicit objective variable, which is basic. */
518         columns.resize(n_columns+artificial_rows.size());
519         columns.back() = columns[n_columns-1];
520         columns[n_columns-1].values.clear();
521         for(unsigned i=0; i<artificial_rows.size(); ++i)
522                 columns[n_columns+i-1].basic = artificial_rows[i];
523 }
524
525 void Layout::LinearProgram::remove_artificial_variables()
526 {
527         /* See if any artificial variables are still basic.  This could be because
528         the program is degenerate.  To avoid trouble later on, use pivots to make
529         some of the original variables basic instead.
530
531         I don't fully understand why this is needed, but it appears to work. */
532         for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
533                 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
534                 {
535                         for(unsigned j=0; j+1<n_columns; ++j)
536                                 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
537                                 {
538                                         make_basic_column(j, columns[i].basic);
539                                         break;
540                                 }
541                 }
542
543         /* Get rid of the artificial variables and restore the original objective
544         row to form the phase 2 problem. */
545         columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
546         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
547                 if(!i->basic)
548                 {
549                         i->values.front() = i->values.back();
550                         i->values.pop_back();
551                 }
552 }
553
554 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
555 {
556         /* Pick the row with the minimum ratio between the constant column and the
557         pivot column.  This ensures that when the pivot column is made basic, values
558         in the constant column stay positive.
559
560         The use of n_rows instead of the true size of the column is intentional,
561         since the relocated objective row must be ignored in phase 1. */
562         float best = numeric_limits<float>::infinity();
563         unsigned row = 0;
564         for(unsigned i=1; i<n_rows; ++i)
565                 if(columns[c].values[i]>0)
566                 {
567                         float ratio = columns.back().values[i]/columns[c].values[i];
568                         if(ratio<best)
569                         {
570                                 best = ratio;
571                                 row = i;
572                         }
573                 }
574
575         return row;
576 }
577
578 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
579 {
580         /* Perform row transfer operations to make the pivot column basic,
581         containing a 1 on the pivot row. */
582         for(unsigned i=0; i<columns.size(); ++i)
583                 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
584                 {
585                         if(columns[i].basic)
586                         {
587                                 columns[i].values.resize(columns.back().values.size(), 0.0f);
588                                 columns[i].values[columns[i].basic] = 1.0f;
589                                 columns[i].basic = 0;
590                         }
591
592                         float scale = columns[i].values[r]/columns[c].values[r];
593
594                         columns[i].values[r] = scale;
595                         for(unsigned j=0; j<columns[i].values.size(); ++j)
596                                 if(j!=r)
597                                         columns[i].values[j] -= scale*columns[c].values[j];
598                 }
599
600         columns[c].basic = r;
601         columns[c].values.clear();
602 }
603
604 bool Layout::LinearProgram::pivot()
605 {
606         /* Pick a nonbasic column and make it basic.  Requiring a positive objective
607         coefficient ensures that the objective function's value will decrease in the
608         process. */
609         for(unsigned i=0; i+1<columns.size(); ++i)
610                 if(!columns[i].basic && columns[i].values.front()>0)
611                         if(unsigned row = find_minimal_ratio(i))
612                         {
613                                 make_basic_column(i, row);
614                                 return true;
615                         }
616
617         return false;
618 }
619
620
621 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
622         linprog(lp),
623         index(i)
624 { }
625
626 float &Layout::LinearProgram::Row::operator[](unsigned c)
627 {
628         if(c>=linprog.n_columns)
629                 throw out_of_range("Row::operator[]");
630
631         Column &column = linprog.columns[c];
632         if(column.values.size()<=index)
633                 column.values.resize(index+1);
634
635         return column.values[index];
636 }
637
638 float &Layout::LinearProgram::Row::back()
639 {
640         return (*this)[linprog.n_columns-1];
641 }
642
643
644 Layout::LinearProgram::Column::Column():
645         basic(0)
646 { }
647
648 } // namespace GLtk
649 } // namespace Msp