source/layout.cpp

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