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