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_vars[0] = 0;
  96         n_slack_vars[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_vars[0] = 0;
 223         n_slack_vars[1] = 0;
 224         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 225                 if((*i)->index>=0)
 226                 {
 227                         for(unsigned j=0; j<2; ++j)
 228                                 if(((*i)->*(pointers[j].packing)).gravity==0)
 229                                         n_slack_vars[j] += 2;
 230                         for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
 231                                 if(j->target.index>(*i)->index && (j->type&SLACK))
 232                                         ++n_slack_vars[j->type&1];
 233                 }
 234 }
 235
 236 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
 237 {
 238         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 239                 if(&(*i)->widget==&wdg)
 240                         return **i;
 241
 242         throw hierarchy_error("widget not in layout");
 243 }
 244
 245 Layout::ConstraintType Layout::complement(ConstraintType type)
 246 {
 247         return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
 248 }
 249
 250 void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
 251 {
 252         if(&src==&tgt)
 253                 throw invalid_argument("&src==&tgt");
 254
 255         Slot &src_slot = get_slot_for_widget(src);
 256         Slot &tgt_slot = get_slot_for_widget(tgt);
 257
 258         for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
 259                 if(i->type==type && &i->target==&tgt_slot)
 260                         return;
 261
 262         src_slot.constraints.push_back(Constraint(type, tgt_slot));
 263         src_slot.constraints.back().spacing = sp;
 264         tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
 265         tgt_slot.constraints.back().spacing = sp;
 266
 267         update_slot_indices();
 268         update();
 269 }
 270
 271 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
 272 {
 273         create_constraint(src, type, tgt, -1);
 274 }
 275
 276 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
 277 {
 278         create_constraint(src, type, tgt, spacing);
 279 }
 280
 281 void Layout::set_gravity(Widget &wdg, int h, int v)
 282 {
 283         Slot &slot = get_slot_for_widget(wdg);
 284
 285         slot.horiz_pack.gravity = h;
 286         slot.vert_pack.gravity = v;
 287
 288         update_slot_indices();
 289         update();
 290 }
 291
 292 void Layout::set_expand(Widget &wdg, bool h, bool v)
 293 {
 294         Slot &slot = get_slot_for_widget(wdg);
 295
 296         slot.horiz_pack.expand = h;
 297         slot.vert_pack.expand = v;
 298
 299         update();
 300 }
 301
 302 void Layout::set_ghost(Widget &wdg, bool g)
 303 {
 304         Slot &slot = get_slot_for_widget(wdg);
 305
 306         slot.ghost = g;
 307
 308         if(!wdg.is_visible())
 309         {
 310                 update_slot_indices();
 311                 update();
 312         }
 313 }
 314
 315 void Layout::update()
 316 {
 317         solve_constraints(HORIZONTAL, UPDATE);
 318         solve_constraints(VERTICAL, UPDATE);
 319
 320         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 321                 (*i)->widget.set_geometry((*i)->geom);
 322 }
 323
 324 void Layout::autosize(Geometry &geom)
 325 {
 326         solve_constraints(HORIZONTAL, AUTOSIZE);
 327         solve_constraints(VERTICAL, AUTOSIZE);
 328
 329         geom.w = max(geom.w, autosize_geom.w);
 330         geom.h = max(geom.h, autosize_geom.h);
 331 }
 332
 333 void Layout::solve_constraints(int dir, SolveMode mode)
 334 {
 335         Pointers &ptrs = pointers[dir&VERTICAL];
 336
 337         const Geometry &geom = container->get_geometry();
 338         if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
 339                 return;
 340
 341         /* Set up a linear program to solve the constraints.  The program matrix has
 342         five columns for each widget, and one constant column.  The first and second
 343         columns of a widget are its position and dimension, respectively.  The
 344         remaining three are slack columns; see below for their purposes. */
 345         LinearProgram linprog(n_active_slots*5+n_slack_vars[dir]+1);
 346         float weight = slots.size();
 347         unsigned k = n_active_slots*5;
 348         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 349         {
 350                 if((*i)->index<0)
 351                         continue;
 352
 353                 LinearProgram::Row objective = linprog.get_objective_row();
 354                 if(mode==AUTOSIZE)
 355                 {
 356                         objective[(*i)->index*5] = -1;
 357                         objective[(*i)->index*5+1] = -1;
 358                 }
 359                 else
 360                 {
 361                         objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
 362                         objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
 363                 }
 364
 365                 {
 366                         // Prevent the widget from going past the container's low edge.
 367                         LinearProgram::Row row = linprog.add_row();
 368                         row[(*i)->index*5] = 1;
 369                         row[(*i)->index*5+2] = -1;
 370                         row.back() = margin.*(ptrs.low_margin);
 371                 }
 372
 373                 if(mode==UPDATE)
 374                 {
 375                         // Prevent the widget from going past the container's high edge.
 376                         LinearProgram::Row row = linprog.add_row();
 377                         row[(*i)->index*5] = 1;
 378                         row[(*i)->index*5+1] = 1;
 379                         row[(*i)->index*5+3] = 1;
 380                         row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
 381                 }
 382
 383                 if(((*i)->*(ptrs.packing)).gravity==0)
 384                 {
 385                         /* Try to keep the widget as close to the center of the container
 386                         as possible.  Since linear programs can't express absolute values
 387                         directly, use two opposing slack variables that are optimized for
 388                         a low value. */
 389                         LinearProgram::Row row = linprog.add_row();
 390                         row[(*i)->index*5] = 1;
 391                         row[(*i)->index*5+1] = 0.5;
 392                         row[k] = 1;
 393                         row[k+1] = -1;
 394                         row.back() = geom.*(ptrs.dim)/2;
 395                         objective[k] = -1;
 396                         objective[k+1] = -1;
 397                         k += 2;
 398                 }
 399
 400                 {
 401                         /* Don't allow the widget's dimension to get below that determined
 402                         by autosizing. */
 403                         LinearProgram::Row row = linprog.add_row();
 404                         row[(*i)->index*5+1] = 1;
 405                         row[(*i)->index*5+4] = -1;
 406                         row.back() = (*i)->autosize_geom.*(ptrs.dim);
 407                 }
 408
 409                 /* Add rows for user-defined constraints.  Constraints are always added
 410                 in pairs, so it's only necessary to create a row for one half. */
 411                 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
 412                         if(j->target.index>(*i)->index && (j->type&1)==dir)
 413                         {
 414                                 LinearProgram::Row row = linprog.add_row();
 415                                 float polarity = ((j->type&SELF_DIM) ? -1 : 1);
 416                                 if(j->type&SELF_POS)
 417                                         row[(*i)->index*5] = polarity;
 418                                 if(j->type&SELF_DIM)
 419                                         row[(*i)->index*5+1] = polarity;
 420                                 if(j->type&TARGET_POS)
 421                                         row[j->target.index*5] = -polarity;
 422                                 if(j->type&TARGET_DIM)
 423                                         row[j->target.index*5+1] = -polarity;
 424                                 if(j->type&SPACING)
 425                                         row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
 426                                 if(j->type&SLACK)
 427                                         row[k++] = -1;
 428                         }
 429         }
 430
 431         if(!linprog.solve())
 432                 return;
 433
 434         if(mode==AUTOSIZE)
 435         {
 436                 autosize_geom.*(ptrs.dim) = 0;
 437                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 438                         if((*i)->index>=0)
 439                         {
 440                                 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
 441                                 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
 442                         }
 443         }
 444         else
 445         {
 446                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 447                         if((*i)->index>=0)
 448                         {
 449                                 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
 450                                 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
 451                         }
 452         }
 453 }
 454
 455
 456 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
 457         type(t),
 458         target(s),
 459         spacing(-1)
 460 { }
 461
 462
 463 Layout::Packing::Packing():
 464         gravity(-1),
 465         expand(false)
 466 { }
 467
 468
 469 Layout::Slot::Slot(Layout &l, Widget &w):
 470         layout(l),
 471         index(0),
 472         widget(w),
 473         ghost(false)
 474 {
 475         vert_pack.gravity = 1;
 476         widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
 477         widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
 478         widget.autosize(autosize_geom);
 479 }
 480
 481 void Layout::Slot::autosize_changed()
 482 {
 483         widget.autosize(autosize_geom);
 484
 485         if(!widget.is_visible() && !ghost)
 486                 return;
 487
 488         // Only trigger an update if the widget won't fit in its current area.
 489         if(autosize_geom.w>geom.w || autosize_geom.h>geom.h)
 490         {
 491                 layout.container->signal_autosize_changed.emit();
 492                 layout.update();
 493         }
 494 }
 495
 496 void Layout::Slot::visibility_changed(bool v)
 497 {
 498         layout.update_slot_indices();
 499         if(v || ghost)
 500         {
 501                 layout.container->signal_autosize_changed.emit();
 502                 layout.update();
 503         }
 504 }
 505
 506
 507 Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
 508         DataFile::ObjectLoader<Layout>(l),
 509         wdg_map(wm)
 510 {
 511         add("column_spacing", &Loader::column_spacing);
 512         add("margin",         &Loader::margin);
 513         add("row_spacing",    &Loader::row_spacing);
 514         add("spacing",        &Loader::spacing);
 515         add("widget",         &Loader::widget);
 516 }
 517
 518 void Layout::Loader::column_spacing(unsigned s)
 519 {
 520         obj.set_column_spacing(s);
 521 }
 522
 523 void Layout::Loader::margin()
 524 {
 525         Sides sides;
 526         load_sub(sides);
 527         obj.set_margin(sides);
 528 }
 529
 530 void Layout::Loader::spacing(unsigned s)
 531 {
 532         obj.set_spacing(s);
 533 }
 534
 535 void Layout::Loader::row_spacing(unsigned s)
 536 {
 537         obj.set_row_spacing(s);
 538 }
 539
 540 void Layout::Loader::widget(const string &n)
 541 {
 542         Widget &wdg = *get_item(wdg_map, n);
 543         WidgetLoader ldr(obj, wdg, wdg_map);
 544         load_sub_with(ldr);
 545 }
 546
 547
 548 Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
 549         layout(l),
 550         widget(w),
 551         wdg_map(wm)
 552 {
 553         add("constraint", &WidgetLoader::constraint);
 554         add("expand",     &WidgetLoader::expand);
 555         add("ghost",      &WidgetLoader::ghost);
 556         add("gravity",    &WidgetLoader::gravity);
 557 }
 558
 559 void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
 560 {
 561         Widget &target = *get_item(wdg_map, n);
 562         layout.add_constraint(widget, type, target);
 563 }
 564
 565 void Layout::WidgetLoader::expand(bool h, bool v)
 566 {
 567         layout.set_expand(widget, h, v);
 568 }
 569
 570 void Layout::WidgetLoader::ghost(bool g)
 571 {
 572         layout.set_ghost(widget, g);
 573 }
 574
 575 void Layout::WidgetLoader::gravity(int h, int v)
 576 {
 577         layout.set_gravity(widget, h, v);
 578 }
 579
 580
 581 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
 582 {
 583         const string &str = conv.get();
 584         if(str=="ABOVE")
 585                 ctype = Layout::ABOVE;
 586         else if(str=="BELOW")
 587                 ctype = Layout::BELOW;
 588         else if(str=="RIGHT_OF")
 589                 ctype = Layout::RIGHT_OF;
 590         else if(str=="LEFT_OF")
 591                 ctype = Layout::LEFT_OF;
 592         else if(str=="FAR_ABOVE")
 593                 ctype = Layout::FAR_ABOVE;
 594         else if(str=="FAR_BELOW")
 595                 ctype = Layout::FAR_BELOW;
 596         else if(str=="FAR_RIGHT_OF")
 597                 ctype = Layout::FAR_RIGHT_OF;
 598         else if(str=="FAR_LEFT_OF")
 599                 ctype = Layout::FAR_LEFT_OF;
 600         else if(str=="ALIGN_TOP")
 601                 ctype = Layout::ALIGN_TOP;
 602         else if(str=="ALIGN_BOTTOM")
 603                 ctype = Layout::ALIGN_BOTTOM;
 604         else if(str=="ALIGN_RIGHT")
 605                 ctype = Layout::ALIGN_RIGHT;
 606         else if(str=="ALIGN_LEFT")
 607                 ctype = Layout::ALIGN_LEFT;
 608         else if(str=="COPY_WIDTH")
 609                 ctype = Layout::COPY_WIDTH;
 610         else if(str=="COPY_HEIGHT")
 611                 ctype = Layout::COPY_HEIGHT;
 612         else
 613                 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
 614 }
 615
 616
 617 Layout::LinearProgram::LinearProgram(unsigned s):
 618         n_columns(s),
 619         n_rows(1),
 620         columns(n_columns),
 621         solved(false),
 622         infeasible(false)
 623 { }
 624
 625 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
 626 {
 627         return Row(*this, n_rows++);
 628 }
 629
 630 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
 631 {
 632         if(r>=n_rows)
 633                 throw out_of_range("LinearProgram::operator[]");
 634
 635         return Row(*this, r);
 636 }
 637
 638 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
 639 {
 640         return Row(*this, 0);
 641 }
 642
 643 float Layout::LinearProgram::get_variable(unsigned i)
 644 {
 645         if(!solved || infeasible)
 646                 throw logic_error("not solved");
 647         if(i+1>=n_columns)
 648                 throw out_of_range("LinearProgram::get_variable");
 649
 650         if(unsigned r = columns[i].basic)
 651                 return columns.back().values[r];
 652         else
 653                 return 0;
 654 }
 655
 656 bool Layout::LinearProgram::solve()
 657 {
 658         if(solved || infeasible)
 659                 return !infeasible;
 660
 661         /* Solve the program using the simplex method.  The column representing the
 662         objective variable is kept implicit, as it would never change during the
 663         execution of the algorithm. */
 664
 665         prepare_columns();
 666
 667         add_artificial_variables();
 668
 669         // Solve the phase 1 problem.
 670         while(pivot()) ;
 671
 672         /* All artificial variables should now be non-basic and thus zero, so the
 673         objective function's value should also be zero.  If it isn't, the original
 674         program can't be solved. */
 675         if(columns.back().values.front())
 676         {
 677                 infeasible = true;
 678                 return false;
 679         }
 680
 681         remove_artificial_variables();
 682
 683         // Solve the phase 2 problem.  We already know it to be feasible.
 684         while(pivot()) ;
 685
 686         solved = true;
 687
 688         return true;
 689 }
 690
 691 void Layout::LinearProgram::prepare_columns()
 692 {
 693         /* See if any variables are already basic.  A basic variable must only have
 694         a nonzero coefficient on one row, and its product with the constant column
 695         must not be negative.  Only one variable can be basic for any given row. */
 696         vector<float> obj_coeff(n_rows, 0.0f);
 697         vector<float> row_coeff(n_rows, 1.0f);
 698         const vector<float> &constants = columns.back().values;
 699         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 700         {
 701                 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)
 702                 {
 703                         bool basic = true;
 704                         for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
 705                                 basic = (i->values[j]==0.0f);
 706                         if(basic)
 707                         {
 708                                 i->basic = i->values.size()-1;
 709                                 row_coeff[i->basic] = 1.0f/i->values.back();
 710                                 obj_coeff[i->basic] = -i->values.front();
 711                                 i->values.clear();
 712                         }
 713                 }
 714         }
 715
 716         // Price out the newly-created basic variables.
 717         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 718                 if(!i->values.empty())
 719                 {
 720                         for(unsigned j=0; j<i->values.size(); ++j)
 721                         {
 722                                 i->values[j] *= row_coeff[j];
 723                                 i->values.front() += obj_coeff[j]*i->values[j];
 724                         }
 725                 }
 726 }
 727
 728 void Layout::LinearProgram::add_artificial_variables()
 729 {
 730         vector<unsigned> artificial_rows(n_rows-1);
 731         for(unsigned i=0; i<artificial_rows.size(); ++i)
 732                 artificial_rows[i] = i+1;
 733
 734         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 735                 if(i->basic)
 736                         artificial_rows[i->basic-1] = 0;
 737         artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
 738
 739         /* Force all non-basic columns fully into existence and relocate objective
 740         row to bottom in preparation of phase 1.  A new objective row is calculated
 741         by pricing out the constraint rows. */
 742         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 743                 if(!i->basic)
 744                 {
 745                         float objective = 0.0f;
 746                         if(!i->values.empty())
 747                         {
 748                                 objective = i->values.front();
 749                                 i->values.front() = 0.0f;
 750                                 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
 751                                         if(*j<i->values.size())
 752                                                 i->values.front() += i->values[*j];
 753                         }
 754                         i->values.resize(n_rows+1, 0.0f);
 755                         i->values.back() = objective;
 756                 }
 757
 758         if(artificial_rows.empty())
 759                 return;
 760
 761         /* Create artificial variables for phase 1.  This ensures that each row has
 762         a basic variable associated with it.  The original objective row already
 763         contains the implicit objective variable, which is basic. */
 764         columns.resize(n_columns+artificial_rows.size());
 765         columns.back() = columns[n_columns-1];
 766         columns[n_columns-1].values.clear();
 767         for(unsigned i=0; i<artificial_rows.size(); ++i)
 768                 columns[n_columns+i-1].basic = artificial_rows[i];
 769 }
 770
 771 void Layout::LinearProgram::remove_artificial_variables()
 772 {
 773         /* See if any artificial variables are still basic.  This could be because
 774         the program is degenerate.  To avoid trouble later on, use pivots to make
 775         some of the original variables basic instead.
 776
 777         I don't fully understand why this is needed, but it appears to work. */
 778         for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
 779                 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
 780                 {
 781                         for(unsigned j=0; j+1<n_columns; ++j)
 782                                 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
 783                                 {
 784                                         make_basic_column(j, columns[i].basic);
 785                                         break;
 786                                 }
 787                 }
 788
 789         /* Get rid of the artificial variables and restore the original objective
 790         row to form the phase 2 problem. */
 791         columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
 792         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 793                 if(!i->basic)
 794                 {
 795                         i->values.front() = i->values.back();
 796                         i->values.pop_back();
 797                 }
 798 }
 799
 800 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 801 {
 802         /* Pick the row with the minimum ratio between the constant column and the
 803         pivot column.  This ensures that when the pivot column is made basic, values
 804         in the constant column stay positive.
 805
 806         The use of n_rows instead of the true size of the column is intentional,
 807         since the relocated objective row must be ignored in phase 1. */
 808         float best = numeric_limits<float>::infinity();
 809         unsigned row = 0;
 810         for(unsigned i=1; i<n_rows; ++i)
 811                 if(columns[c].values[i]>0)
 812                 {
 813                         float ratio = columns.back().values[i]/columns[c].values[i];
 814                         if(ratio<best)
 815                         {
 816                                 best = ratio;
 817                                 row = i;
 818                         }
 819                 }
 820
 821         return row;
 822 }
 823
 824 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 825 {
 826         /* Perform row transfer operations to make the pivot column basic,
 827         containing a 1 on the pivot row. */
 828         for(unsigned i=0; i<columns.size(); ++i)
 829                 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
 830                 {
 831                         if(columns[i].basic)
 832                         {
 833                                 columns[i].values.resize(columns.back().values.size(), 0.0f);
 834                                 columns[i].values[columns[i].basic] = 1.0f;
 835                                 columns[i].basic = 0;
 836                         }
 837
 838                         float scale = columns[i].values[r]/columns[c].values[r];
 839
 840                         columns[i].values[r] = scale;
 841                         for(unsigned j=0; j<columns[i].values.size(); ++j)
 842                                 if(j!=r)
 843                                         columns[i].values[j] -= scale*columns[c].values[j];
 844                 }
 845
 846         columns[c].basic = r;
 847         columns[c].values.clear();
 848 }
 849
 850 bool Layout::LinearProgram::pivot()
 851 {
 852         /* Pick a nonbasic column and make it basic.  Requiring a positive objective
 853         coefficient ensures that the objective function's value will decrease in the
 854         process. */
 855         for(unsigned i=0; i+1<columns.size(); ++i)
 856                 if(!columns[i].basic && columns[i].values.front()>0)
 857                         if(unsigned row = find_minimal_ratio(i))
 858                         {
 859                                 make_basic_column(i, row);
 860                                 return true;
 861                         }
 862
 863         return false;
 864 }
 865
 866
 867 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
 868         linprog(lp),
 869         index(i)
 870 { }
 871
 872 float &Layout::LinearProgram::Row::operator[](unsigned c)
 873 {
 874         if(c>=linprog.n_columns)
 875                 throw out_of_range("Row::operator[]");
 876
 877         Column &column = linprog.columns[c];
 878         if(column.values.size()<=index)
 879                 column.values.resize(index+1);
 880
 881         return column.values[index];
 882 }
 883
 884 float &Layout::LinearProgram::Row::back()
 885 {
 886         return (*this)[linprog.n_columns-1];
 887 }
 888
 889
 890 Layout::LinearProgram::Column::Column():
 891         basic(0)
 892 { }
 893
 894 } // namespace GLtk
 895 } // namespace Msp