]> git.tdb.fi Git - libs/gltk.git/blob - source/layout.cpp
5ebb55ccf4f8822de2423427d4c795c8d906ecf8
[libs/gltk.git] / source / layout.cpp
1 #include <algorithm>
2 #include <limits>
3 #include <msp/core/maputils.h>
4 #include <msp/strings/format.h>
5 #include "arrangement.h"
6 #include "container.h"
7 #include "layout.h"
8 #include "widget.h"
9
10 using namespace std;
11
12 namespace Msp {
13 namespace GLtk {
14
15 class Layout::LinearProgram
16 {
17 public:
18         class Row
19         {
20         private:
21                 LinearProgram &linprog;
22                 unsigned index;
23
24         public:
25                 Row(LinearProgram &, unsigned);
26
27                 float &operator[](unsigned);
28                 float &back();
29         };
30
31 private:
32         struct Column
33         {
34                 unsigned basic;
35                 std::vector<float> values;
36
37                 Column();
38         };
39
40         unsigned n_columns;
41         unsigned n_rows;
42         std::vector<Column> columns;
43         bool solved;
44         bool infeasible;
45
46 public:
47         LinearProgram(unsigned);
48
49         Row add_row();
50         Row operator[](unsigned);
51         Row get_objective_row();
52         float get_variable(unsigned);
53         bool solve();
54 private:
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);
60         bool pivot();
61 };
62
63
64 struct Layout::Pointers
65 {
66         int Geometry::*pos;
67         unsigned Geometry::*dim;
68         Packing Slot::*packing;
69         unsigned Sides::*low_margin;
70         unsigned Sides::*high_margin;
71         unsigned Layout::*spacing;
72 };
73
74 Layout::Pointers Layout::pointers[2] =
75 { {
76                 &Geometry::x, &Geometry::w,
77                 &Slot::horiz_pack,
78                 &Sides::left, &Sides::right,
79                 &Layout::col_spacing
80         }, {
81                 &Geometry::y, &Geometry::h,
82                 &Slot::vert_pack,
83                 &Sides::bottom, &Sides::top,
84                 &Layout::row_spacing
85 } };
86
87
88 Layout::Layout():
89         container(0),
90         n_active_slots(0),
91         margin(8),
92         row_spacing(5),
93         col_spacing(4)
94 {
95         n_slack_constraints[0] = 0;
96         n_slack_constraints[1] = 0;
97 }
98
99 Layout::~Layout()
100 {
101         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
102                 delete *i;
103 }
104
105 void Layout::set_container(Container &c)
106 {
107         if(container)
108                 throw logic_error("container!=0");
109
110         container = &c;
111 }
112
113 void Layout::set_margin(const Sides &m)
114 {
115         margin = m;
116         if(container)
117                 update();
118 }
119
120 void Layout::set_spacing(unsigned s)
121 {
122         row_spacing = s;
123         col_spacing = s;
124         if(container)
125                 update();
126 }
127
128 void Layout::set_row_spacing(unsigned s)
129 {
130         row_spacing = s;
131         if(container)
132                 update();
133 }
134
135 void Layout::set_column_spacing(unsigned s)
136 {
137         col_spacing = s;
138         if(container)
139                 update();
140 }
141
142 void Layout::push_arrangement(Arrangement &arr)
143 {
144         arrangement_stack.push_back(&arr);
145 }
146
147 Arrangement *Layout::get_arrangement() const
148 {
149         if(arrangement_stack.empty())
150                 return 0;
151         else
152                 return arrangement_stack.back();
153 }
154
155 void Layout::pop_arrangement(Arrangement &arr)
156 {
157         list<Arrangement *>::iterator begin = find(arrangement_stack.begin(), arrangement_stack.end(), &arr);
158         if(begin==arrangement_stack.end())
159                 return;
160
161         while(1)
162         {
163                 Arrangement *top = arrangement_stack.back();
164                 arrangement_stack.pop_back();
165                 if(!arrangement_stack.empty())
166                         arrangement_stack.back()->arrange(*top);
167                 if(top==&arr)
168                         break;
169         }
170 }
171
172 void Layout::add_widget(Widget &wdg)
173 {
174         if(!container)
175                 throw logic_error("!container");
176
177         slots.push_back(new Slot(*this, wdg));
178         update_slot_indices();
179         if(!arrangement_stack.empty())
180                 arrangement_stack.back()->arrange(wdg);
181         if(container)
182                 update();
183 }
184
185 void Layout::remove_widget(Widget &wdg)
186 {
187         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
188                 if(&(*i)->widget==&wdg)
189                 {
190                         for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
191                                 if(j!=i)
192                                 {
193                                         for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
194                                         {
195                                                 if(&k->target==*i)
196                                                         (*j)->constraints.erase(k++);
197                                                 else
198                                                         ++k;
199                                         }
200                                 }
201
202                         delete *i;
203                         slots.erase(i);
204
205                         update_slot_indices();
206                         update();
207                         return;
208                 }
209 }
210
211 void Layout::update_slot_indices()
212 {
213         n_active_slots = 0;
214         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
215         {
216                 if((*i)->widget.is_visible() || (*i)->ghost)
217                         (*i)->index = n_active_slots++;
218                 else
219                         (*i)->index = -1;
220         }
221
222         n_slack_constraints[0] = 0;
223         n_slack_constraints[1] = 0;
224         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
225                 if((*i)->index>=0)
226                 {
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];
230                 }
231 }
232
233 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
234 {
235         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
236                 if(&(*i)->widget==&wdg)
237                         return **i;
238
239         throw hierarchy_error("widget not in layout");
240 }
241
242 Layout::ConstraintType Layout::complement(ConstraintType type)
243 {
244         return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
245 }
246
247 void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
248 {
249         if(&src==&tgt)
250                 throw invalid_argument("&src==&tgt");
251
252         Slot &src_slot = get_slot_for_widget(src);
253         Slot &tgt_slot = get_slot_for_widget(tgt);
254
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)
257                         return;
258
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;
263
264         update_slot_indices();
265         update();
266 }
267
268 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
269 {
270         create_constraint(src, type, tgt, -1);
271 }
272
273 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
274 {
275         create_constraint(src, type, tgt, spacing);
276 }
277
278 void Layout::set_gravity(Widget &wdg, int h, int v)
279 {
280         Slot &slot = get_slot_for_widget(wdg);
281
282         slot.horiz_pack.gravity = h;
283         slot.vert_pack.gravity = v;
284
285         update();
286 }
287
288 void Layout::set_expand(Widget &wdg, bool h, bool v)
289 {
290         Slot &slot = get_slot_for_widget(wdg);
291
292         slot.horiz_pack.expand = h;
293         slot.vert_pack.expand = v;
294
295         update();
296 }
297
298 void Layout::set_ghost(Widget &wdg, bool g)
299 {
300         Slot &slot = get_slot_for_widget(wdg);
301
302         slot.ghost = g;
303
304         if(!wdg.is_visible())
305         {
306                 update_slot_indices();
307                 update();
308         }
309 }
310
311 void Layout::update()
312 {
313         solve_constraints(HORIZONTAL, UPDATE);
314         solve_constraints(VERTICAL, UPDATE);
315
316         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
317                 (*i)->widget.set_geometry((*i)->geom);
318 }
319
320 void Layout::autosize(Geometry &geom)
321 {
322         solve_constraints(HORIZONTAL, AUTOSIZE);
323         solve_constraints(VERTICAL, AUTOSIZE);
324
325         geom.w = max(geom.w, autosize_geom.w);
326         geom.h = max(geom.h, autosize_geom.h);
327 }
328
329 void Layout::solve_constraints(int dir, SolveMode mode)
330 {
331         Pointers &ptrs = pointers[dir&VERTICAL];
332
333         const Geometry &geom = container->get_geometry();
334         if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
335                 return;
336
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)
345         {
346                 if((*i)->index<0)
347                         continue;
348
349                 LinearProgram::Row objective = linprog.get_objective_row();
350                 if(mode==AUTOSIZE)
351                 {
352                         objective[(*i)->index*5] = -1;
353                         objective[(*i)->index*5+1] = -1;
354                 }
355                 else
356                 {
357                         objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
358                         objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
359                 }
360
361                 {
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);
367                 }
368
369                 if(mode==UPDATE)
370                 {
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);
377                 }
378
379                 if(((*i)->*(ptrs.packing)).gravity==0)
380                 {
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;
387                 }
388
389                 {
390                         /* Don't allow the widget's dimension to get below that determined
391                         by autosizing. */
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);
396                 }
397
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)
402                         {
403                                 LinearProgram::Row row = linprog.add_row();
404                                 float polarity = ((j->type&SELF_DIM) ? -1 : 1);
405                                 if(j->type&SELF_POS)
406                                         row[(*i)->index*5] = polarity;
407                                 if(j->type&SELF_DIM)
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;
413                                 if(j->type&SPACING)
414                                         row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
415                                 if(j->type&SLACK)
416                                         row[k++] = -1;
417                         }
418         }
419
420         if(!linprog.solve())
421                 return;
422
423         if(mode==AUTOSIZE)
424         {
425                 autosize_geom.*(ptrs.dim) = 0;
426                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
427                         if((*i)->index>=0)
428                         {
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));
431                         }
432         }
433         else
434         {
435                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
436                         if((*i)->index>=0)
437                         {
438                                 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
439                                 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
440                         }
441         }
442 }
443
444
445 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
446         type(t),
447         target(s),
448         spacing(-1)
449 { }
450
451
452 Layout::Packing::Packing():
453         gravity(-1),
454         expand(false)
455 { }
456
457
458 Layout::Slot::Slot(Layout &l, Widget &w):
459         layout(l),
460         index(0),
461         widget(w),
462         ghost(false)
463 {
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));
467         widget.autosize();
468         autosize_geom = widget.get_geometry();
469 }
470
471 void Layout::Slot::autosize_changed()
472 {
473         widget.autosize();
474         autosize_geom = widget.get_geometry();
475
476         if(!widget.is_visible() && !ghost)
477                 return;
478
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);
482         else
483         {
484                 layout.container->signal_autosize_changed.emit();
485                 layout.update();
486         }
487 }
488
489 void Layout::Slot::visibility_changed(bool v)
490 {
491         layout.update_slot_indices();
492         if(v || ghost)
493         {
494                 layout.container->signal_autosize_changed.emit();
495                 layout.update();
496         }
497 }
498
499
500 Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
501         DataFile::ObjectLoader<Layout>(l),
502         wdg_map(wm)
503 {
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);
509 }
510
511 void Layout::Loader::column_spacing(unsigned s)
512 {
513         obj.set_column_spacing(s);
514 }
515
516 void Layout::Loader::margin()
517 {
518         Sides sides;
519         load_sub(sides);
520         obj.set_margin(sides);
521 }
522
523 void Layout::Loader::spacing(unsigned s)
524 {
525         obj.set_spacing(s);
526 }
527
528 void Layout::Loader::row_spacing(unsigned s)
529 {
530         obj.set_row_spacing(s);
531 }
532
533 void Layout::Loader::widget(const string &n)
534 {
535         Widget &wdg = *get_item(wdg_map, n);
536         WidgetLoader ldr(obj, wdg, wdg_map);
537         load_sub_with(ldr);
538 }
539
540
541 Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
542         layout(l),
543         widget(w),
544         wdg_map(wm)
545 {
546         add("constraint", &WidgetLoader::constraint);
547         add("expand",     &WidgetLoader::expand);
548         add("ghost",      &WidgetLoader::ghost);
549         add("gravity",    &WidgetLoader::gravity);
550 }
551
552 void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
553 {
554         Widget &target = *get_item(wdg_map, n);
555         layout.add_constraint(widget, type, target);
556 }
557
558 void Layout::WidgetLoader::expand(bool h, bool v)
559 {
560         layout.set_expand(widget, h, v);
561 }
562
563 void Layout::WidgetLoader::ghost(bool g)
564 {
565         layout.set_ghost(widget, g);
566 }
567
568 void Layout::WidgetLoader::gravity(int h, int v)
569 {
570         layout.set_gravity(widget, h, v);
571 }
572
573
574 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
575 {
576         const string &str = conv.get();
577         if(str=="ABOVE")
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;
605         else
606                 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
607 }
608
609
610 Layout::LinearProgram::LinearProgram(unsigned s):
611         n_columns(s),
612         n_rows(1),
613         columns(n_columns),
614         solved(false),
615         infeasible(false)
616 { }
617
618 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
619 {
620         return Row(*this, n_rows++);
621 }
622
623 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
624 {
625         if(r>=n_rows)
626                 throw out_of_range("LinearProgram::operator[]");
627
628         return Row(*this, r);
629 }
630
631 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
632 {
633         return Row(*this, 0);
634 }
635
636 float Layout::LinearProgram::get_variable(unsigned i)
637 {
638         if(!solved || infeasible)
639                 throw logic_error("not solved");
640         if(i+1>=n_columns)
641                 throw out_of_range("LinearProgram::get_variable");
642
643         if(unsigned r = columns[i].basic)
644                 return columns.back().values[r];
645         else
646                 return 0;
647 }
648
649 bool Layout::LinearProgram::solve()
650 {
651         if(solved || infeasible)
652                 return !infeasible;
653
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. */
657
658         prepare_columns();
659
660         add_artificial_variables();
661
662         // Solve the phase 1 problem.
663         while(pivot()) ;
664
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())
669         {
670                 infeasible = true;
671                 return false;
672         }
673
674         remove_artificial_variables();
675
676         // Solve the phase 2 problem.  We already know it to be feasible.
677         while(pivot()) ;
678
679         solved = true;
680
681         return true;
682 }
683
684 void Layout::LinearProgram::prepare_columns()
685 {
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)
693         {
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)
695                 {
696                         bool basic = true;
697                         for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
698                                 basic = (i->values[j]==0.0f);
699                         if(basic)
700                         {
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();
704                                 i->values.clear();
705                         }
706                 }
707         }
708
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())
712                 {
713                         for(unsigned j=0; j<i->values.size(); ++j)
714                         {
715                                 i->values[j] *= row_coeff[j];
716                                 i->values.front() += obj_coeff[j]*i->values[j];
717                         }
718                 }
719 }
720
721 void Layout::LinearProgram::add_artificial_variables()
722 {
723         vector<unsigned> artificial_rows(n_rows-1);
724         for(unsigned i=0; i<artificial_rows.size(); ++i)
725                 artificial_rows[i] = i+1;
726
727         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
728                 if(i->basic)
729                         artificial_rows[i->basic-1] = 0;
730         artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
731
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)
736                 if(!i->basic)
737                 {
738                         float objective = 0.0f;
739                         if(!i->values.empty())
740                         {
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];
746                         }
747                         i->values.resize(n_rows+1, 0.0f);
748                         i->values.back() = objective;
749                 }
750
751         if(artificial_rows.empty())
752                 return;
753
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];
762 }
763
764 void Layout::LinearProgram::remove_artificial_variables()
765 {
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.
769
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)
773                 {
774                         for(unsigned j=0; j+1<n_columns; ++j)
775                                 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
776                                 {
777                                         make_basic_column(j, columns[i].basic);
778                                         break;
779                                 }
780                 }
781
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)
786                 if(!i->basic)
787                 {
788                         i->values.front() = i->values.back();
789                         i->values.pop_back();
790                 }
791 }
792
793 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
794 {
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.
798
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();
802         unsigned row = 0;
803         for(unsigned i=1; i<n_rows; ++i)
804                 if(columns[c].values[i]>0)
805                 {
806                         float ratio = columns.back().values[i]/columns[c].values[i];
807                         if(ratio<best)
808                         {
809                                 best = ratio;
810                                 row = i;
811                         }
812                 }
813
814         return row;
815 }
816
817 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
818 {
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])))
823                 {
824                         if(columns[i].basic)
825                         {
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;
829                         }
830
831                         float scale = columns[i].values[r]/columns[c].values[r];
832
833                         columns[i].values[r] = scale;
834                         for(unsigned j=0; j<columns[i].values.size(); ++j)
835                                 if(j!=r)
836                                         columns[i].values[j] -= scale*columns[c].values[j];
837                 }
838
839         columns[c].basic = r;
840         columns[c].values.clear();
841 }
842
843 bool Layout::LinearProgram::pivot()
844 {
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
847         process. */
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))
851                         {
852                                 make_basic_column(i, row);
853                                 return true;
854                         }
855
856         return false;
857 }
858
859
860 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
861         linprog(lp),
862         index(i)
863 { }
864
865 float &Layout::LinearProgram::Row::operator[](unsigned c)
866 {
867         if(c>=linprog.n_columns)
868                 throw out_of_range("Row::operator[]");
869
870         Column &column = linprog.columns[c];
871         if(column.values.size()<=index)
872                 column.values.resize(index+1);
873
874         return column.values[index];
875 }
876
877 float &Layout::LinearProgram::Row::back()
878 {
879         return (*this)[linprog.n_columns-1];
880 }
881
882
883 Layout::LinearProgram::Column::Column():
884         basic(0)
885 { }
886
887 } // namespace GLtk
888 } // namespace Msp