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