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