source/layout.cpp

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