source/layout.cpp

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