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