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