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("&src==&tgt");
 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();
 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                                 if(j->type&SELF_POS)
 443                                         row[(*i)->index*5] = polarity;
 444                                 if(j->type&SELF_DIM)
 445                                         row[(*i)->index*5+1] = polarity;
 446                                 if(j->type&TARGET_POS)
 447                                         row[j->target.index*5] = -polarity;
 448                                 if(j->type&TARGET_DIM)
 449                                         row[j->target.index*5+1] = -polarity;
 450                                 if(j->type&SPACING)
 451                                         row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
 452                                 if(j->type&SLACK)
 453                                         row[k++] = -1;
 454                         }
 455         }
 456
 457         if(!linprog.solve())
 458                 return;
 459
 460         if(mode==AUTOSIZE)
 461         {
 462                 autosize_geom.*(ptrs.dim) = 0;
 463                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 464                         if((*i)->index>=0)
 465                         {
 466                                 int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
 467                                 autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
 468                         }
 469         }
 470         else
 471         {
 472                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 473                         if((*i)->index>=0)
 474                         {
 475                                 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
 476                                 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
 477                         }
 478         }
 479 }
 480
 481
 482 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
 483         type(t),
 484         target(s),
 485         spacing(-1)
 486 { }
 487
 488
 489 Layout::Packing::Packing():
 490         gravity(-1),
 491         expand(false)
 492 { }
 493
 494
 495 Layout::Slot::Slot(Layout &l, Widget &w):
 496         layout(l),
 497         index(0),
 498         widget(w),
 499         ghost(false),
 500         floating(false)
 501 {
 502         vert_pack.gravity = 1;
 503         widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
 504         widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
 505         widget.autosize(autosize_geom);
 506 }
 507
 508 void Layout::Slot::autosize_changed()
 509 {
 510         widget.autosize(autosize_geom);
 511
 512         if(!widget.is_visible() && !ghost)
 513                 return;
 514
 515         // Only trigger an update if the widget won't fit in its current area.
 516         if(autosize_geom.w>geom.w || autosize_geom.h>geom.h)
 517         {
 518                 layout.container->signal_autosize_changed.emit();
 519                 layout.update();
 520         }
 521 }
 522
 523 void Layout::Slot::visibility_changed(bool v)
 524 {
 525         layout.update_slot_indices();
 526         if(v || ghost)
 527         {
 528                 layout.container->signal_autosize_changed.emit();
 529                 layout.update();
 530         }
 531 }
 532
 533
 534 Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
 535         DataFile::ObjectLoader<Layout>(l),
 536         wdg_map(wm)
 537 {
 538         add("column_spacing", &Loader::column_spacing);
 539         add("margin",         &Loader::margin);
 540         add("row_spacing",    &Loader::row_spacing);
 541         add("spacing",        &Loader::spacing);
 542         add("widget",         &Loader::widget);
 543 }
 544
 545 void Layout::Loader::column_spacing(unsigned s)
 546 {
 547         obj.set_column_spacing(s);
 548 }
 549
 550 void Layout::Loader::margin()
 551 {
 552         Sides sides;
 553         load_sub(sides);
 554         obj.set_margin(sides);
 555 }
 556
 557 void Layout::Loader::spacing(unsigned s)
 558 {
 559         obj.set_spacing(s);
 560 }
 561
 562 void Layout::Loader::row_spacing(unsigned s)
 563 {
 564         obj.set_row_spacing(s);
 565 }
 566
 567 void Layout::Loader::widget(const string &n)
 568 {
 569         Widget &wdg = *get_item(wdg_map, n);
 570         WidgetLoader ldr(obj, wdg, wdg_map);
 571         load_sub_with(ldr);
 572 }
 573
 574
 575 Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
 576         layout(l),
 577         widget(w),
 578         wdg_map(wm)
 579 {
 580         add("constraint", &WidgetLoader::constraint);
 581         add("expand",     &WidgetLoader::expand);
 582         add("ghost",      &WidgetLoader::ghost);
 583         add("gravity",    &WidgetLoader::gravity);
 584 }
 585
 586 void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
 587 {
 588         Widget &target = *get_item(wdg_map, n);
 589         layout.add_constraint(widget, type, target);
 590 }
 591
 592 void Layout::WidgetLoader::expand(bool h, bool v)
 593 {
 594         layout.set_expand(widget, h, v);
 595 }
 596
 597 void Layout::WidgetLoader::ghost(bool g)
 598 {
 599         layout.set_ghost(widget, g);
 600 }
 601
 602 void Layout::WidgetLoader::gravity(int h, int v)
 603 {
 604         layout.set_gravity(widget, h, v);
 605 }
 606
 607
 608 void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
 609 {
 610         const string &str = conv.get();
 611         if(str=="ABOVE")
 612                 ctype = Layout::ABOVE;
 613         else if(str=="BELOW")
 614                 ctype = Layout::BELOW;
 615         else if(str=="RIGHT_OF")
 616                 ctype = Layout::RIGHT_OF;
 617         else if(str=="LEFT_OF")
 618                 ctype = Layout::LEFT_OF;
 619         else if(str=="FAR_ABOVE")
 620                 ctype = Layout::FAR_ABOVE;
 621         else if(str=="FAR_BELOW")
 622                 ctype = Layout::FAR_BELOW;
 623         else if(str=="FAR_RIGHT_OF")
 624                 ctype = Layout::FAR_RIGHT_OF;
 625         else if(str=="FAR_LEFT_OF")
 626                 ctype = Layout::FAR_LEFT_OF;
 627         else if(str=="ALIGN_TOP")
 628                 ctype = Layout::ALIGN_TOP;
 629         else if(str=="ALIGN_BOTTOM")
 630                 ctype = Layout::ALIGN_BOTTOM;
 631         else if(str=="ALIGN_RIGHT")
 632                 ctype = Layout::ALIGN_RIGHT;
 633         else if(str=="ALIGN_LEFT")
 634                 ctype = Layout::ALIGN_LEFT;
 635         else if(str=="COPY_WIDTH")
 636                 ctype = Layout::COPY_WIDTH;
 637         else if(str=="COPY_HEIGHT")
 638                 ctype = Layout::COPY_HEIGHT;
 639         else
 640                 throw lexical_error(format("conversion of '%s' to ConstraintType", str));
 641 }
 642
 643
 644 Layout::LinearProgram::LinearProgram(unsigned s):
 645         n_columns(s),
 646         n_rows(1),
 647         columns(n_columns),
 648         solved(false),
 649         infeasible(false)
 650 { }
 651
 652 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
 653 {
 654         return Row(*this, n_rows++);
 655 }
 656
 657 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
 658 {
 659         if(r>=n_rows)
 660                 throw out_of_range("LinearProgram::operator[]");
 661
 662         return Row(*this, r);
 663 }
 664
 665 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
 666 {
 667         return Row(*this, 0);
 668 }
 669
 670 float Layout::LinearProgram::get_variable(unsigned i)
 671 {
 672         if(!solved || infeasible)
 673                 throw logic_error("not solved");
 674         if(i+1>=n_columns)
 675                 throw out_of_range("LinearProgram::get_variable");
 676
 677         if(unsigned r = columns[i].basic)
 678                 return columns.back().values[r];
 679         else
 680                 return 0;
 681 }
 682
 683 bool Layout::LinearProgram::solve()
 684 {
 685         if(solved || infeasible)
 686                 return !infeasible;
 687
 688         /* Solve the program using the simplex method.  The column representing the
 689         objective variable is kept implicit, as it would never change during the
 690         execution of the algorithm. */
 691
 692         prepare_columns();
 693
 694         add_artificial_variables();
 695
 696         // Solve the phase 1 problem.
 697         while(pivot()) ;
 698
 699         /* All artificial variables should now be non-basic and thus zero, so the
 700         objective function's value should also be zero.  If it isn't, the original
 701         program can't be solved. */
 702         if(columns.back().values.front())
 703         {
 704                 infeasible = true;
 705                 return false;
 706         }
 707
 708         remove_artificial_variables();
 709
 710         // Solve the phase 2 problem.  We already know it to be feasible.
 711         while(pivot()) ;
 712
 713         solved = true;
 714
 715         return true;
 716 }
 717
 718 void Layout::LinearProgram::prepare_columns()
 719 {
 720         /* See if any variables are already basic.  A basic variable must only have
 721         a nonzero coefficient on one row, and its product with the constant column
 722         must not be negative.  Only one variable can be basic for any given row. */
 723         vector<float> obj_coeff(n_rows, 0.0f);
 724         vector<float> row_coeff(n_rows, 1.0f);
 725         const vector<float> &constants = columns.back().values;
 726         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 727         {
 728                 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)
 729                 {
 730                         bool basic = true;
 731                         for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
 732                                 basic = (i->values[j]==0.0f);
 733                         if(basic)
 734                         {
 735                                 i->basic = i->values.size()-1;
 736                                 row_coeff[i->basic] = 1.0f/i->values.back();
 737                                 obj_coeff[i->basic] = -i->values.front();
 738                                 i->values.clear();
 739                         }
 740                 }
 741         }
 742
 743         // Price out the newly-created basic variables.
 744         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 745                 if(!i->values.empty())
 746                 {
 747                         for(unsigned j=0; j<i->values.size(); ++j)
 748                         {
 749                                 i->values[j] *= row_coeff[j];
 750                                 i->values.front() += obj_coeff[j]*i->values[j];
 751                         }
 752                 }
 753 }
 754
 755 void Layout::LinearProgram::add_artificial_variables()
 756 {
 757         vector<unsigned> artificial_rows(n_rows-1);
 758         for(unsigned i=0; i<artificial_rows.size(); ++i)
 759                 artificial_rows[i] = i+1;
 760
 761         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 762                 if(i->basic)
 763                         artificial_rows[i->basic-1] = 0;
 764         artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
 765
 766         /* Force all non-basic columns fully into existence and relocate objective
 767         row to bottom in preparation of phase 1.  A new objective row is calculated
 768         by pricing out the constraint rows. */
 769         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 770                 if(!i->basic)
 771                 {
 772                         float objective = 0.0f;
 773                         if(!i->values.empty())
 774                         {
 775                                 objective = i->values.front();
 776                                 i->values.front() = 0.0f;
 777                                 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
 778                                         if(*j<i->values.size())
 779                                                 i->values.front() += i->values[*j];
 780                         }
 781                         i->values.resize(n_rows+1, 0.0f);
 782                         i->values.back() = objective;
 783                 }
 784
 785         if(artificial_rows.empty())
 786                 return;
 787
 788         /* Create artificial variables for phase 1.  This ensures that each row has
 789         a basic variable associated with it.  The original objective row already
 790         contains the implicit objective variable, which is basic. */
 791         columns.resize(n_columns+artificial_rows.size());
 792         columns.back() = columns[n_columns-1];
 793         columns[n_columns-1].values.clear();
 794         for(unsigned i=0; i<artificial_rows.size(); ++i)
 795                 columns[n_columns+i-1].basic = artificial_rows[i];
 796 }
 797
 798 void Layout::LinearProgram::remove_artificial_variables()
 799 {
 800         /* See if any artificial variables are still basic.  This could be because
 801         the program is degenerate.  To avoid trouble later on, use pivots to make
 802         some of the original variables basic instead.
 803
 804         I don't fully understand why this is needed, but it appears to work. */
 805         for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
 806                 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
 807                 {
 808                         for(unsigned j=0; j+1<n_columns; ++j)
 809                                 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
 810                                 {
 811                                         make_basic_column(j, columns[i].basic);
 812                                         break;
 813                                 }
 814                 }
 815
 816         /* Get rid of the artificial variables and restore the original objective
 817         row to form the phase 2 problem. */
 818         columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
 819         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 820                 if(!i->basic)
 821                 {
 822                         i->values.front() = i->values.back();
 823                         i->values.pop_back();
 824                 }
 825 }
 826
 827 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 828 {
 829         /* Pick the row with the minimum ratio between the constant column and the
 830         pivot column.  This ensures that when the pivot column is made basic, values
 831         in the constant column stay positive.
 832
 833         The use of n_rows instead of the true size of the column is intentional,
 834         since the relocated objective row must be ignored in phase 1. */
 835         float best = numeric_limits<float>::infinity();
 836         unsigned row = 0;
 837         for(unsigned i=1; i<n_rows; ++i)
 838                 if(columns[c].values[i]>0)
 839                 {
 840                         float ratio = columns.back().values[i]/columns[c].values[i];
 841                         if(ratio<best)
 842                         {
 843                                 best = ratio;
 844                                 row = i;
 845                         }
 846                 }
 847
 848         return row;
 849 }
 850
 851 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 852 {
 853         /* Perform row transfer operations to make the pivot column basic,
 854         containing a 1 on the pivot row. */
 855         for(unsigned i=0; i<columns.size(); ++i)
 856                 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
 857                 {
 858                         if(columns[i].basic)
 859                         {
 860                                 columns[i].values.resize(columns.back().values.size(), 0.0f);
 861                                 columns[i].values[columns[i].basic] = 1.0f;
 862                                 columns[i].basic = 0;
 863                         }
 864
 865                         float scale = columns[i].values[r]/columns[c].values[r];
 866
 867                         columns[i].values[r] = scale;
 868                         for(unsigned j=0; j<columns[i].values.size(); ++j)
 869                                 if(j!=r)
 870                                         columns[i].values[j] -= scale*columns[c].values[j];
 871                 }
 872
 873         columns[c].basic = r;
 874         columns[c].values.clear();
 875 }
 876
 877 bool Layout::LinearProgram::pivot()
 878 {
 879         /* Pick a nonbasic column and make it basic.  Requiring a positive objective
 880         coefficient ensures that the objective function's value will decrease in the
 881         process. */
 882         for(unsigned i=0; i+1<columns.size(); ++i)
 883                 if(!columns[i].basic && columns[i].values.front()>0)
 884                         if(unsigned row = find_minimal_ratio(i))
 885                         {
 886                                 make_basic_column(i, row);
 887                                 return true;
 888                         }
 889
 890         return false;
 891 }
 892
 893
 894 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
 895         linprog(lp),
 896         index(i)
 897 { }
 898
 899 float &Layout::LinearProgram::Row::operator[](unsigned c)
 900 {
 901         if(c>=linprog.n_columns)
 902                 throw out_of_range("Row::operator[]");
 903
 904         Column &column = linprog.columns[c];
 905         if(column.values.size()<=index)
 906                 column.values.resize(index+1);
 907
 908         return column.values[index];
 909 }
 910
 911 float &Layout::LinearProgram::Row::back()
 912 {
 913         return (*this)[linprog.n_columns-1];
 914 }
 915
 916
 917 Layout::LinearProgram::Column::Column():
 918         basic(0)
 919 { }
 920
 921 } // namespace GLtk
 922 } // namespace Msp