source/layout.cpp

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