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