source/layout.cpp

   1 #include <algorithm>
   2 #include <limits>
   3 #include "container.h"
   4 #include "layout.h"
   5 #include "widget.h"
   6
   7 using namespace std;
   8
   9 namespace Msp {
  10 namespace GLtk {
  11
  12 class Layout::LinearProgram
  13 {
  14 public:
  15         class Row
  16         {
  17         private:
  18                 LinearProgram &linprog;
  19                 unsigned index;
  20
  21         public:
  22                 Row(LinearProgram &, unsigned);
  23
  24                 float &operator[](unsigned);
  25                 float &back();
  26         };
  27
  28 private:
  29         struct Column
  30         {
  31                 unsigned basic;
  32                 std::vector<float> values;
  33
  34                 Column();
  35         };
  36
  37         unsigned n_columns;
  38         unsigned n_rows;
  39         std::vector<Column> columns;
  40         bool solved;
  41         bool infeasible;
  42
  43 public:
  44         LinearProgram(unsigned);
  45
  46         Row add_row();
  47         Row operator[](unsigned);
  48         Row get_objective_row();
  49         float get_variable(unsigned);
  50         bool solve();
  51 private:
  52         void prepare_columns();
  53         void add_artificial_variables();
  54         void remove_artificial_variables();
  55         unsigned find_minimal_ratio(unsigned);
  56         void make_basic_column(unsigned, unsigned);
  57         bool pivot();
  58 };
  59
  60
  61 struct Layout::Pointers
  62 {
  63         int Geometry::*pos;
  64         unsigned Geometry::*dim;
  65         Packing Slot::*packing;
  66         unsigned Sides::*low_margin;
  67         unsigned Sides::*high_margin;
  68         unsigned Layout::*spacing;
  69 };
  70
  71 Layout::Pointers Layout::pointers[2] =
  72 { {
  73                 &Geometry::x, &Geometry::w,
  74                 &Slot::horiz_pack,
  75                 &Sides::left, &Sides::right,
  76                 &Layout::col_spacing
  77         }, {
  78                 &Geometry::y, &Geometry::h,
  79                 &Slot::vert_pack,
  80                 &Sides::bottom, &Sides::top,
  81                 &Layout::row_spacing
  82 } };
  83
  84
  85 Layout::Layout():
  86         container(0),
  87         margin(8),
  88         row_spacing(5),
  89         col_spacing(4)
  90 { }
  91
  92 Layout::~Layout()
  93 {
  94         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
  95                 delete *i;
  96 }
  97
  98 void Layout::set_container(Container &c)
  99 {
 100         if(container)
 101                 throw logic_error("container!=0");
 102
 103         container = &c;
 104 }
 105
 106 void Layout::set_margin(const Sides &m)
 107 {
 108         margin = m;
 109         if(container)
 110                 update();
 111 }
 112
 113 void Layout::set_spacing(unsigned s)
 114 {
 115         row_spacing = s;
 116         col_spacing = s;
 117         if(container)
 118                 update();
 119 }
 120
 121 void Layout::set_row_spacing(unsigned s)
 122 {
 123         row_spacing = s;
 124         if(container)
 125                 update();
 126 }
 127
 128 void Layout::set_column_spacing(unsigned s)
 129 {
 130         col_spacing = s;
 131         if(container)
 132                 update();
 133 }
 134
 135 void Layout::add_widget(Widget &wdg)
 136 {
 137         if(!container)
 138                 throw logic_error("!container");
 139
 140         Slot *slot = create_slot(wdg);
 141         for(list<Constraint>::iterator i=slot->constraints.begin(); i!=slot->constraints.end(); ++i)
 142                 i->target.constraints.push_back(Constraint(complement(i->type), *slot));
 143         slot->index = slots.size();
 144         slots.push_back(slot);
 145         if(container)
 146                 update();
 147 }
 148
 149 void Layout::remove_widget(Widget &wdg)
 150 {
 151         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 152                 if(&(*i)->widget==&wdg)
 153                 {
 154                         for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
 155                                 if(j!=i)
 156                                 {
 157                                         for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
 158                                         {
 159                                                 if(&k->target==*i)
 160                                                         (*j)->constraints.erase(k++);
 161                                                 else
 162                                                         ++k;
 163                                         }
 164                                 }
 165
 166                         delete *i;
 167                         slots.erase(i);
 168
 169                         unsigned n = 0;
 170                         for(i=slots.begin(); i!=slots.end(); ++i, ++n)
 171                                 (*i)->index = n;
 172
 173                         update();
 174                         return;
 175                 }
 176 }
 177
 178 Layout::Slot *Layout::create_slot(Widget &wdg)
 179 {
 180         return new Slot(*this, wdg);
 181 }
 182
 183 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
 184 {
 185         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 186                 if(&(*i)->widget==&wdg)
 187                         return **i;
 188
 189         throw hierarchy_error("widget not in layout");
 190 }
 191
 192 Layout::ConstraintType Layout::complement(ConstraintType type)
 193 {
 194         if(type==RIGHT_OF)
 195                 return LEFT_OF;
 196         else if(type==LEFT_OF)
 197                 return RIGHT_OF;
 198         else if(type==ABOVE)
 199                 return BELOW;
 200         else if(type==BELOW)
 201                 return ABOVE;
 202         else
 203                 return type;
 204 }
 205
 206 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
 207 {
 208         if(&src==&tgt)
 209                 throw invalid_argument("&src==&tgt");
 210
 211         Slot &src_slot = get_slot_for_widget(src);
 212         Slot &tgt_slot = get_slot_for_widget(tgt);
 213
 214         for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
 215                 if(i->type==type && &i->target==&tgt_slot)
 216                         return;
 217
 218         src_slot.constraints.push_back(Constraint(type, tgt_slot));
 219         tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
 220
 221         update();
 222 }
 223
 224 void Layout::set_gravity(Widget &wdg, int h, int v)
 225 {
 226         Slot &slot = get_slot_for_widget(wdg);
 227
 228         slot.horiz_pack.gravity = h;
 229         slot.vert_pack.gravity = v;
 230
 231         update();
 232 }
 233
 234 void Layout::set_expand(Widget &wdg, bool h, bool v)
 235 {
 236         Slot &slot = get_slot_for_widget(wdg);
 237
 238         slot.horiz_pack.expand = h;
 239         slot.vert_pack.expand = v;
 240
 241         update();
 242 }
 243
 244 void Layout::update()
 245 {
 246         solve_constraints(HORIZONTAL, UPDATE);
 247         solve_constraints(VERTICAL, UPDATE);
 248
 249         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 250                 (*i)->widget.set_geometry((*i)->geom);
 251 }
 252
 253 void Layout::autosize()
 254 {
 255         solve_constraints(HORIZONTAL, AUTOSIZE);
 256         solve_constraints(VERTICAL, AUTOSIZE);
 257
 258         container->set_size(autosize_geom.w, autosize_geom.h);
 259 }
 260
 261 void Layout::solve_constraints(int dir, SolveMode mode)
 262 {
 263         Pointers &ptrs = pointers[dir&VERTICAL];
 264
 265         const Geometry &geom = container->get_geometry();
 266         if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
 267                 return;
 268
 269         /* Set up a linear program to solve the constraints.  The program matrix has
 270         five columns for each widget, and one constant column.  The first and second
 271         columns of a widget are its position and dimension, respectively.  The
 272         remaining three are slack columns; see below for their purposes. */
 273         LinearProgram linprog(slots.size()*5+1);
 274         float weight = slots.size();
 275         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 276         {
 277                 LinearProgram::Row objective = linprog.get_objective_row();
 278                 if(mode==AUTOSIZE)
 279                 {
 280                         objective[(*i)->index*5] = -1;
 281                         objective[(*i)->index*5+1] = -1;
 282                 }
 283                 else
 284                 {
 285                         objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
 286                         objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
 287                 }
 288
 289                 {
 290                         // Prevent the widget from going past the container's low edge.
 291                         LinearProgram::Row row = linprog.add_row();
 292                         row[(*i)->index*5] = 1;
 293                         row[(*i)->index*5+2] = -1;
 294                         row.back() = margin.*(ptrs.low_margin);
 295                 }
 296
 297                 if(mode==UPDATE)
 298                 {
 299                         // Prevent the widget from going past the container's high edge.
 300                         LinearProgram::Row row = linprog.add_row();
 301                         row[(*i)->index*5] = 1;
 302                         row[(*i)->index*5+1] = 1;
 303                         row[(*i)->index*5+3] = 1;
 304                         row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
 305                 }
 306
 307                 if(((*i)->*(ptrs.packing)).gravity==0)
 308                 {
 309                         /* This forces the widget's distance from the left and right edge of
 310                         the container to be equal.  It's a bit of a hack, but more time and
 311                         thought is needed for a better solution. */
 312                         LinearProgram::Row row = linprog.add_row();
 313                         row[(*i)->index*5+2] = 1;
 314                         row[(*i)->index*5+3] = -1;
 315                 }
 316
 317                 {
 318                         /* Only allow the widget's dimension to increase.  The geometry has
 319                         previously been set to the smallest allowable size. */
 320                         LinearProgram::Row row = linprog.add_row();
 321                         row[(*i)->index*5+1] = 1;
 322                         row[(*i)->index*5+4] = -1;
 323                         row.back() = (*i)->autosize_geom.*(ptrs.dim);
 324                 }
 325
 326                 /* Add rows for user-defined constraints.  Below/above and left/right of
 327                 constraints are always added in pairs, so it's only necessary to create a
 328                 row for one half. */
 329                 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
 330                         if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
 331                         {
 332                                 LinearProgram::Row row = linprog.add_row();
 333                                 if(j->type&SELF_POS)
 334                                         row[(*i)->index*5] = 1;
 335                                 if(j->type&SELF_DIM)
 336                                         row[(*i)->index*5+1] = 1;
 337                                 if(j->type&TARGET_POS)
 338                                         row[j->target.index*5] = -1;
 339                                 if(j->type&TARGET_DIM)
 340                                         row[j->target.index*5+1] = -1;
 341                                 if(j->type&SPACING)
 342                                         row.back() = this->*(ptrs.spacing);
 343                         }
 344         }
 345
 346         if(!linprog.solve())
 347                 return;
 348
 349         if(mode==AUTOSIZE)
 350         {
 351                 autosize_geom.*(ptrs.dim) = 0;
 352                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 353                 {
 354                         int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
 355                         autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
 356                 }
 357         }
 358         else
 359         {
 360                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 361                 {
 362                         (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
 363                         (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
 364                 }
 365         }
 366 }
 367
 368
 369 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
 370         type(t),
 371         target(s)
 372 { }
 373
 374
 375 Layout::Packing::Packing():
 376         gravity(-1),
 377         expand(false)
 378 { }
 379
 380
 381 Layout::Slot::Slot(Layout &l, Widget &w):
 382         layout(l),
 383         index(0),
 384         widget(w)
 385 {
 386         vert_pack.gravity = 1;
 387         widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
 388         widget.autosize();
 389         autosize_geom = widget.get_geometry();
 390 }
 391
 392 void Layout::Slot::autosize_changed()
 393 {
 394         widget.autosize();
 395         autosize_geom = widget.get_geometry();
 396
 397         // If the widget fits in the area it had, just leave it there.
 398         if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
 399                 widget.set_geometry(geom);
 400         else
 401         {
 402                 layout.container->signal_autosize_changed.emit();
 403                 layout.update();
 404         }
 405 }
 406
 407
 408 Layout::LinearProgram::LinearProgram(unsigned s):
 409         n_columns(s),
 410         n_rows(1),
 411         columns(n_columns),
 412         solved(false),
 413         infeasible(false)
 414 { }
 415
 416 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
 417 {
 418         return Row(*this, n_rows++);
 419 }
 420
 421 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
 422 {
 423         if(r>=n_rows)
 424                 throw out_of_range("LinearProgram::operator[]");
 425
 426         return Row(*this, r);
 427 }
 428
 429 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
 430 {
 431         return Row(*this, 0);
 432 }
 433
 434 float Layout::LinearProgram::get_variable(unsigned i)
 435 {
 436         if(!solved || infeasible)
 437                 throw logic_error("not solved");
 438         if(i+1>=n_columns)
 439                 throw out_of_range("LinearProgram::get_variable");
 440
 441         if(unsigned r = columns[i].basic)
 442                 return columns.back().values[r];
 443         else
 444                 return 0;
 445 }
 446
 447 bool Layout::LinearProgram::solve()
 448 {
 449         if(solved || infeasible)
 450                 return !infeasible;
 451
 452         /* Solve the program using the simplex method.  The column representing the
 453         objective variable is kept implicit, as it would never change during the
 454         execution of the algorithm. */
 455
 456         prepare_columns();
 457
 458         add_artificial_variables();
 459
 460         // Solve the phase 1 problem.
 461         while(pivot()) ;
 462
 463         /* All artificial variables should now be non-basic and thus zero, so the
 464         objective function's value should also be zero.  If it isn't, the original
 465         program can't be solved. */
 466         if(columns.back().values.front())
 467         {
 468                 infeasible = true;
 469                 return false;
 470         }
 471
 472         remove_artificial_variables();
 473
 474         // Solve the phase 2 problem.  We already know it to be feasible.
 475         while(pivot()) ;
 476
 477         solved = true;
 478
 479         return true;
 480 }
 481
 482 void Layout::LinearProgram::prepare_columns()
 483 {
 484         /* See if any variables are already basic.  A basic variable must only have
 485         a nonzero coefficient on one row, and its product with the constant column
 486         must not be negative.  Only one variable can be basic for any given row. */
 487         vector<float> basic_coeff(n_rows, 0.0f);
 488         const vector<float> &constants = columns.back().values;
 489         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 490         {
 491                 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) && basic_coeff[i->values.size()-1]==0.0f)
 492                 {
 493                         bool basic = true;
 494                         for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
 495                                 basic = (i->values[j]==0.0f);
 496                         if(basic)
 497                         {
 498                                 i->basic = i->values.size()-1;
 499                                 basic_coeff[i->basic] = -i->values.front()/i->values.back();
 500                                 i->values.clear();
 501                         }
 502                 }
 503         }
 504
 505         // Price out the newly-created basic variables.
 506         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 507                 if(!i->values.empty())
 508                 {
 509                         for(unsigned j=0; j<i->values.size(); ++j)
 510                                 i->values.front() += basic_coeff[j]*i->values[j];
 511                 }
 512 }
 513
 514 void Layout::LinearProgram::add_artificial_variables()
 515 {
 516         vector<unsigned> artificial_rows(n_rows-1);
 517         for(unsigned i=0; i<artificial_rows.size(); ++i)
 518                 artificial_rows[i] = i+1;
 519
 520         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 521                 if(i->basic)
 522                         artificial_rows[i->basic-1] = 0;
 523         artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
 524
 525         /* Force all non-basic columns fully into existence and relocate objective
 526         row to bottom in preparation of phase 1.  A new objective row is calculated
 527         by pricing out the constraint rows. */
 528         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 529                 if(!i->basic)
 530                 {
 531                         float objective = 0.0f;
 532                         if(!i->values.empty())
 533                         {
 534                                 objective = i->values.front();
 535                                 i->values.front() = 0.0f;
 536                                 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
 537                                         if(*j<i->values.size())
 538                                                 i->values.front() += i->values[*j];
 539                         }
 540                         i->values.resize(n_rows+1, 0.0f);
 541                         i->values.back() = objective;
 542                 }
 543
 544         if(artificial_rows.empty())
 545                 return;
 546
 547         /* Create artificial variables for phase 1.  This ensures that each row has
 548         a basic variable associated with it.  The original objective row already
 549         contains the implicit objective variable, which is basic. */
 550         columns.resize(n_columns+artificial_rows.size());
 551         columns.back() = columns[n_columns-1];
 552         columns[n_columns-1].values.clear();
 553         for(unsigned i=0; i<artificial_rows.size(); ++i)
 554                 columns[n_columns+i-1].basic = artificial_rows[i];
 555 }
 556
 557 void Layout::LinearProgram::remove_artificial_variables()
 558 {
 559         /* See if any artificial variables are still basic.  This could be because
 560         the program is degenerate.  To avoid trouble later on, use pivots to make
 561         some of the original variables basic instead.
 562
 563         I don't fully understand why this is needed, but it appears to work. */
 564         for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
 565                 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
 566                 {
 567                         for(unsigned j=0; j+1<n_columns; ++j)
 568                                 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
 569                                 {
 570                                         make_basic_column(j, columns[i].basic);
 571                                         break;
 572                                 }
 573                 }
 574
 575         /* Get rid of the artificial variables and restore the original objective
 576         row to form the phase 2 problem. */
 577         columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
 578         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 579                 if(!i->basic)
 580                 {
 581                         i->values.front() = i->values.back();
 582                         i->values.pop_back();
 583                 }
 584 }
 585
 586 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 587 {
 588         /* Pick the row with the minimum ratio between the constant column and the
 589         pivot column.  This ensures that when the pivot column is made basic, values
 590         in the constant column stay positive.
 591
 592         The use of n_rows instead of the true size of the column is intentional,
 593         since the relocated objective row must be ignored in phase 1. */
 594         float best = numeric_limits<float>::infinity();
 595         unsigned row = 0;
 596         for(unsigned i=1; i<n_rows; ++i)
 597                 if(columns[c].values[i]>0)
 598                 {
 599                         float ratio = columns.back().values[i]/columns[c].values[i];
 600                         if(ratio<best)
 601                         {
 602                                 best = ratio;
 603                                 row = i;
 604                         }
 605                 }
 606
 607         return row;
 608 }
 609
 610 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 611 {
 612         /* Perform row transfer operations to make the pivot column basic,
 613         containing a 1 on the pivot row. */
 614         for(unsigned i=0; i<columns.size(); ++i)
 615                 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
 616                 {
 617                         if(columns[i].basic)
 618                         {
 619                                 columns[i].values.resize(columns.back().values.size(), 0.0f);
 620                                 columns[i].values[columns[i].basic] = 1.0f;
 621                                 columns[i].basic = 0;
 622                         }
 623
 624                         float scale = columns[i].values[r]/columns[c].values[r];
 625
 626                         columns[i].values[r] = scale;
 627                         for(unsigned j=0; j<columns[i].values.size(); ++j)
 628                                 if(j!=r)
 629                                         columns[i].values[j] -= scale*columns[c].values[j];
 630                 }
 631
 632         columns[c].basic = r;
 633         columns[c].values.clear();
 634 }
 635
 636 bool Layout::LinearProgram::pivot()
 637 {
 638         /* Pick a nonbasic column and make it basic.  Requiring a positive objective
 639         coefficient ensures that the objective function's value will decrease in the
 640         process. */
 641         for(unsigned i=0; i+1<columns.size(); ++i)
 642                 if(!columns[i].basic && columns[i].values.front()>0)
 643                         if(unsigned row = find_minimal_ratio(i))
 644                         {
 645                                 make_basic_column(i, row);
 646                                 return true;
 647                         }
 648
 649         return false;
 650 }
 651
 652
 653 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
 654         linprog(lp),
 655         index(i)
 656 { }
 657
 658 float &Layout::LinearProgram::Row::operator[](unsigned c)
 659 {
 660         if(c>=linprog.n_columns)
 661                 throw out_of_range("Row::operator[]");
 662
 663         Column &column = linprog.columns[c];
 664         if(column.values.size()<=index)
 665                 column.values.resize(index+1);
 666
 667         return column.values[index];
 668 }
 669
 670 float &Layout::LinearProgram::Row::back()
 671 {
 672         return (*this)[linprog.n_columns-1];
 673 }
 674
 675
 676 Layout::LinearProgram::Column::Column():
 677         basic(0)
 678 { }
 679
 680 } // namespace GLtk
 681 } // namespace Msp