source/layout.cpp

   1 #include <algorithm>
   2 #include <limits>
   3 #include <msp/strings/format.h>
   4 #include "arrangement.h"
   5 #include "container.h"
   6 #include "layout.h"
   7 #include "widget.h"
   8
   9 using namespace std;
  10
  11 namespace Msp {
  12 namespace GLtk {
  13
  14 class Layout::LinearProgram
  15 {
  16 public:
  17         class Row
  18         {
  19         private:
  20                 LinearProgram &linprog;
  21                 unsigned index;
  22
  23         public:
  24                 Row(LinearProgram &, unsigned);
  25
  26                 float &operator[](unsigned);
  27                 float &back();
  28         };
  29
  30 private:
  31         struct Column
  32         {
  33                 unsigned basic;
  34                 std::vector<float> values;
  35
  36                 Column();
  37         };
  38
  39         unsigned n_columns;
  40         unsigned n_rows;
  41         std::vector<Column> columns;
  42         bool solved;
  43         bool infeasible;
  44
  45 public:
  46         LinearProgram(unsigned);
  47
  48         Row add_row();
  49         Row operator[](unsigned);
  50         Row get_objective_row();
  51         float get_variable(unsigned);
  52         bool solve();
  53 private:
  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);
  59         bool pivot();
  60 };
  61
  62
  63 struct Layout::Pointers
  64 {
  65         int Geometry::*pos;
  66         unsigned Geometry::*dim;
  67         Packing Slot::*packing;
  68         unsigned Sides::*low_margin;
  69         unsigned Sides::*high_margin;
  70         unsigned Layout::*spacing;
  71 };
  72
  73 Layout::Pointers Layout::pointers[2] =
  74 { {
  75                 &Geometry::x, &Geometry::w,
  76                 &Slot::horiz_pack,
  77                 &Sides::left, &Sides::right,
  78                 &Layout::col_spacing
  79         }, {
  80                 &Geometry::y, &Geometry::h,
  81                 &Slot::vert_pack,
  82                 &Sides::bottom, &Sides::top,
  83                 &Layout::row_spacing
  84 } };
  85
  86
  87 Layout::Layout():
  88         container(0),
  89         n_active_slots(0),
  90         margin(8),
  91         row_spacing(5),
  92         col_spacing(4)
  93 {
  94         n_slack_constraints[0] = 0;
  95         n_slack_constraints[1] = 0;
  96 }
  97
  98 Layout::~Layout()
  99 {
 100         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 101                 delete *i;
 102 }
 103
 104 void Layout::set_container(Container &c)
 105 {
 106         if(container)
 107                 throw logic_error("container!=0");
 108
 109         container = &c;
 110 }
 111
 112 void Layout::set_margin(const Sides &m)
 113 {
 114         margin = m;
 115         if(container)
 116                 update();
 117 }
 118
 119 void Layout::set_spacing(unsigned s)
 120 {
 121         row_spacing = s;
 122         col_spacing = s;
 123         if(container)
 124                 update();
 125 }
 126
 127 void Layout::set_row_spacing(unsigned s)
 128 {
 129         row_spacing = s;
 130         if(container)
 131                 update();
 132 }
 133
 134 void Layout::set_column_spacing(unsigned s)
 135 {
 136         col_spacing = s;
 137         if(container)
 138                 update();
 139 }
 140
 141 void Layout::push_arrangement(Arrangement &arr)
 142 {
 143         arrangement_stack.push_back(&arr);
 144 }
 145
 146 Arrangement *Layout::get_arrangement() const
 147 {
 148         if(arrangement_stack.empty())
 149                 return 0;
 150         else
 151                 return arrangement_stack.back();
 152 }
 153
 154 void Layout::pop_arrangement(Arrangement &arr)
 155 {
 156         list<Arrangement *>::iterator begin = find(arrangement_stack.begin(), arrangement_stack.end(), &arr);
 157         if(begin==arrangement_stack.end())
 158                 return;
 159
 160         while(1)
 161         {
 162                 Arrangement *top = arrangement_stack.back();
 163                 arrangement_stack.pop_back();
 164                 if(!arrangement_stack.empty())
 165                         arrangement_stack.back()->arrange(*top);
 166                 if(top==&arr)
 167                         break;
 168         }
 169 }
 170
 171 void Layout::add_widget(Widget &wdg)
 172 {
 173         if(!container)
 174                 throw logic_error("!container");
 175
 176         slots.push_back(new Slot(*this, wdg));
 177         update_slot_indices();
 178         if(!arrangement_stack.empty())
 179                 arrangement_stack.back()->arrange(wdg);
 180         if(container)
 181                 update();
 182 }
 183
 184 void Layout::remove_widget(Widget &wdg)
 185 {
 186         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 187                 if(&(*i)->widget==&wdg)
 188                 {
 189                         for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
 190                                 if(j!=i)
 191                                 {
 192                                         for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
 193                                         {
 194                                                 if(&k->target==*i)
 195                                                         (*j)->constraints.erase(k++);
 196                                                 else
 197                                                         ++k;
 198                                         }
 199                                 }
 200
 201                         delete *i;
 202                         slots.erase(i);
 203
 204                         update_slot_indices();
 205                         update();
 206                         return;
 207                 }
 208 }
 209
 210 void Layout::update_slot_indices()
 211 {
 212         n_active_slots = 0;
 213         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 214         {
 215                 if((*i)->widget.is_visible())
 216                         (*i)->index = n_active_slots++;
 217                 else
 218                         (*i)->index = -1;
 219         }
 220
 221         n_slack_constraints[0] = 0;
 222         n_slack_constraints[1] = 0;
 223         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 224                 if((*i)->index>=0)
 225                 {
 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];
 229                 }
 230 }
 231
 232 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
 233 {
 234         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 235                 if(&(*i)->widget==&wdg)
 236                         return **i;
 237
 238         throw hierarchy_error("widget not in layout");
 239 }
 240
 241 Layout::ConstraintType Layout::complement(ConstraintType type)
 242 {
 243         return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
 244 }
 245
 246 void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
 247 {
 248         if(&src==&tgt)
 249                 throw invalid_argument("&src==&tgt");
 250
 251         Slot &src_slot = get_slot_for_widget(src);
 252         Slot &tgt_slot = get_slot_for_widget(tgt);
 253
 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)
 256                         return;
 257
 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;
 262
 263         update_slot_indices();
 264         update();
 265 }
 266
 267 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
 268 {
 269         create_constraint(src, type, tgt, -1);
 270 }
 271
 272 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
 273 {
 274         create_constraint(src, type, tgt, spacing);
 275 }
 276
 277 void Layout::set_gravity(Widget &wdg, int h, int v)
 278 {
 279         Slot &slot = get_slot_for_widget(wdg);
 280
 281         slot.horiz_pack.gravity = h;
 282         slot.vert_pack.gravity = v;
 283
 284         update();
 285 }
 286
 287 void Layout::set_expand(Widget &wdg, bool h, bool v)
 288 {
 289         Slot &slot = get_slot_for_widget(wdg);
 290
 291         slot.horiz_pack.expand = h;
 292         slot.vert_pack.expand = v;
 293
 294         update();
 295 }
 296
 297 void Layout::update()
 298 {
 299         solve_constraints(HORIZONTAL, UPDATE);
 300         solve_constraints(VERTICAL, UPDATE);
 301
 302         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 303                 (*i)->widget.set_geometry((*i)->geom);
 304 }
 305
 306 void Layout::autosize()
 307 {
 308         solve_constraints(HORIZONTAL, AUTOSIZE);
 309         solve_constraints(VERTICAL, AUTOSIZE);
 310
 311         container->set_size(autosize_geom.w, autosize_geom.h);
 312 }
 313
 314 void Layout::solve_constraints(int dir, SolveMode mode)
 315 {
 316         Pointers &ptrs = pointers[dir&VERTICAL];
 317
 318         const Geometry &geom = container->get_geometry();
 319         if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
 320                 return;
 321
 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)
 329         {
 330                 if((*i)->index<0)
 331                         continue;
 332
 333                 LinearProgram::Row objective = linprog.get_objective_row();
 334                 if(mode==AUTOSIZE)
 335                 {
 336                         objective[(*i)->index*5] = -1;
 337                         objective[(*i)->index*5+1] = -1;
 338                 }
 339                 else
 340                 {
 341                         objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
 342                         objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
 343                 }
 344
 345                 {
 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);
 351                 }
 352
 353                 if(mode==UPDATE)
 354                 {
 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);
 361                 }
 362
 363                 if(((*i)->*(ptrs.packing)).gravity==0)
 364                 {
 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;
 371                 }
 372
 373                 {
 374                         /* Don't allow the widget's dimension to get below that determined
 375                         by autosizing. */
 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);
 380                 }
 381
 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)
 387                         {
 388                                 LinearProgram::Row row = linprog.add_row();
 389                                 float polarity = ((j->type&SELF_DIM) ? -1 : 1);
 390                                 if(j->type&SELF_POS)
 391                                         row[(*i)->index*5] = polarity;
 392                                 if(j->type&SELF_DIM)
 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;
 398                                 if(j->type&SPACING)
 399                                         row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
 400                                 if(j->type&SLACK)
 401                                         row[k++] = -1;
 402                         }
 403         }
 404
 405         if(!linprog.solve())
 406                 return;
 407
 408         if(mode==AUTOSIZE)
 409         {
 410                 autosize_geom.*(ptrs.dim) = 0;
 411                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 412                         if((*i)->index>=0)
 413                         {
 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));
 416                         }
 417         }
 418         else
 419         {
 420                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 421                         if((*i)->index>=0)
 422                         {
 423                                 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
 424                                 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
 425                         }
 426         }
 427 }
 428
 429
 430 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
 431         type(t),
 432         target(s),
 433         spacing(-1)
 434 { }
 435
 436
 437 Layout::Packing::Packing():
 438         gravity(-1),
 439         expand(false)
 440 { }
 441
 442
 443 Layout::Slot::Slot(Layout &l, Widget &w):
 444         layout(l),
 445         index(0),
 446         widget(w)
 447 {
 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));
 451         widget.autosize();
 452         autosize_geom = widget.get_geometry();
 453 }
 454
 455 void Layout::Slot::autosize_changed()
 456 {
 457         widget.autosize();
 458         autosize_geom = widget.get_geometry();
 459
 460         if(!widget.is_visible())
 461                 return;
 462
 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);
 466         else
 467         {
 468                 layout.container->signal_autosize_changed.emit();
 469                 layout.update();
 470         }
 471 }
 472
 473 void Layout::Slot::visibility_changed(bool v)
 474 {
 475         layout.update_slot_indices();
 476         if(v)
 477         {
 478                 layout.container->signal_autosize_changed.emit();
 479                 layout.update();
 480         }
 481 }
 482
 483
 484 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
 485 {
 486         const string &str = conv.get();
 487         if(str=="ABOVE")
 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;
 515         else
 516                 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
 517 }
 518
 519
 520 Layout::LinearProgram::LinearProgram(unsigned s):
 521         n_columns(s),
 522         n_rows(1),
 523         columns(n_columns),
 524         solved(false),
 525         infeasible(false)
 526 { }
 527
 528 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
 529 {
 530         return Row(*this, n_rows++);
 531 }
 532
 533 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
 534 {
 535         if(r>=n_rows)
 536                 throw out_of_range("LinearProgram::operator[]");
 537
 538         return Row(*this, r);
 539 }
 540
 541 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
 542 {
 543         return Row(*this, 0);
 544 }
 545
 546 float Layout::LinearProgram::get_variable(unsigned i)
 547 {
 548         if(!solved || infeasible)
 549                 throw logic_error("not solved");
 550         if(i+1>=n_columns)
 551                 throw out_of_range("LinearProgram::get_variable");
 552
 553         if(unsigned r = columns[i].basic)
 554                 return columns.back().values[r];
 555         else
 556                 return 0;
 557 }
 558
 559 bool Layout::LinearProgram::solve()
 560 {
 561         if(solved || infeasible)
 562                 return !infeasible;
 563
 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. */
 567
 568         prepare_columns();
 569
 570         add_artificial_variables();
 571
 572         // Solve the phase 1 problem.
 573         while(pivot()) ;
 574
 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())
 579         {
 580                 infeasible = true;
 581                 return false;
 582         }
 583
 584         remove_artificial_variables();
 585
 586         // Solve the phase 2 problem.  We already know it to be feasible.
 587         while(pivot()) ;
 588
 589         solved = true;
 590
 591         return true;
 592 }
 593
 594 void Layout::LinearProgram::prepare_columns()
 595 {
 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)
 603         {
 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)
 605                 {
 606                         bool basic = true;
 607                         for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
 608                                 basic = (i->values[j]==0.0f);
 609                         if(basic)
 610                         {
 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();
 614                                 i->values.clear();
 615                         }
 616                 }
 617         }
 618
 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())
 622                 {
 623                         for(unsigned j=0; j<i->values.size(); ++j)
 624                         {
 625                                 i->values[j] *= row_coeff[j];
 626                                 i->values.front() += obj_coeff[j]*i->values[j];
 627                         }
 628                 }
 629 }
 630
 631 void Layout::LinearProgram::add_artificial_variables()
 632 {
 633         vector<unsigned> artificial_rows(n_rows-1);
 634         for(unsigned i=0; i<artificial_rows.size(); ++i)
 635                 artificial_rows[i] = i+1;
 636
 637         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 638                 if(i->basic)
 639                         artificial_rows[i->basic-1] = 0;
 640         artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
 641
 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)
 646                 if(!i->basic)
 647                 {
 648                         float objective = 0.0f;
 649                         if(!i->values.empty())
 650                         {
 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];
 656                         }
 657                         i->values.resize(n_rows+1, 0.0f);
 658                         i->values.back() = objective;
 659                 }
 660
 661         if(artificial_rows.empty())
 662                 return;
 663
 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];
 672 }
 673
 674 void Layout::LinearProgram::remove_artificial_variables()
 675 {
 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.
 679
 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)
 683                 {
 684                         for(unsigned j=0; j+1<n_columns; ++j)
 685                                 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
 686                                 {
 687                                         make_basic_column(j, columns[i].basic);
 688                                         break;
 689                                 }
 690                 }
 691
 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)
 696                 if(!i->basic)
 697                 {
 698                         i->values.front() = i->values.back();
 699                         i->values.pop_back();
 700                 }
 701 }
 702
 703 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 704 {
 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.
 708
 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();
 712         unsigned row = 0;
 713         for(unsigned i=1; i<n_rows; ++i)
 714                 if(columns[c].values[i]>0)
 715                 {
 716                         float ratio = columns.back().values[i]/columns[c].values[i];
 717                         if(ratio<best)
 718                         {
 719                                 best = ratio;
 720                                 row = i;
 721                         }
 722                 }
 723
 724         return row;
 725 }
 726
 727 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 728 {
 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])))
 733                 {
 734                         if(columns[i].basic)
 735                         {
 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;
 739                         }
 740
 741                         float scale = columns[i].values[r]/columns[c].values[r];
 742
 743                         columns[i].values[r] = scale;
 744                         for(unsigned j=0; j<columns[i].values.size(); ++j)
 745                                 if(j!=r)
 746                                         columns[i].values[j] -= scale*columns[c].values[j];
 747                 }
 748
 749         columns[c].basic = r;
 750         columns[c].values.clear();
 751 }
 752
 753 bool Layout::LinearProgram::pivot()
 754 {
 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
 757         process. */
 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))
 761                         {
 762                                 make_basic_column(i, row);
 763                                 return true;
 764                         }
 765
 766         return false;
 767 }
 768
 769
 770 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
 771         linprog(lp),
 772         index(i)
 773 { }
 774
 775 float &Layout::LinearProgram::Row::operator[](unsigned c)
 776 {
 777         if(c>=linprog.n_columns)
 778                 throw out_of_range("Row::operator[]");
 779
 780         Column &column = linprog.columns[c];
 781         if(column.values.size()<=index)
 782                 column.values.resize(index+1);
 783
 784         return column.values[index];
 785 }
 786
 787 float &Layout::LinearProgram::Row::back()
 788 {
 789         return (*this)[linprog.n_columns-1];
 790 }
 791
 792
 793 Layout::LinearProgram::Column::Column():
 794         basic(0)
 795 { }
 796
 797 } // namespace GLtk
 798 } // namespace Msp