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::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
 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         src_slot.constraints.back().spacing = sp;
 220         tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
 221         tgt_slot.constraints.back().spacing = sp;
 222
 223         update();
 224 }
 225
 226 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
 227 {
 228         create_constraint(src, type, tgt, -1);
 229 }
 230
 231 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
 232 {
 233         create_constraint(src, type, tgt, spacing);
 234 }
 235
 236 void Layout::set_gravity(Widget &wdg, int h, int v)
 237 {
 238         Slot &slot = get_slot_for_widget(wdg);
 239
 240         slot.horiz_pack.gravity = h;
 241         slot.vert_pack.gravity = v;
 242
 243         update();
 244 }
 245
 246 void Layout::set_expand(Widget &wdg, bool h, bool v)
 247 {
 248         Slot &slot = get_slot_for_widget(wdg);
 249
 250         slot.horiz_pack.expand = h;
 251         slot.vert_pack.expand = v;
 252
 253         update();
 254 }
 255
 256 void Layout::update()
 257 {
 258         solve_constraints(HORIZONTAL, UPDATE);
 259         solve_constraints(VERTICAL, UPDATE);
 260
 261         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 262                 (*i)->widget.set_geometry((*i)->geom);
 263 }
 264
 265 void Layout::autosize()
 266 {
 267         solve_constraints(HORIZONTAL, AUTOSIZE);
 268         solve_constraints(VERTICAL, AUTOSIZE);
 269
 270         container->set_size(autosize_geom.w, autosize_geom.h);
 271 }
 272
 273 void Layout::solve_constraints(int dir, SolveMode mode)
 274 {
 275         Pointers &ptrs = pointers[dir&VERTICAL];
 276
 277         const Geometry &geom = container->get_geometry();
 278         if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
 279                 return;
 280
 281         /* Set up a linear program to solve the constraints.  The program matrix has
 282         five columns for each widget, and one constant column.  The first and second
 283         columns of a widget are its position and dimension, respectively.  The
 284         remaining three are slack columns; see below for their purposes. */
 285         LinearProgram linprog(slots.size()*5+1);
 286         float weight = slots.size();
 287         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 288         {
 289                 LinearProgram::Row objective = linprog.get_objective_row();
 290                 if(mode==AUTOSIZE)
 291                 {
 292                         objective[(*i)->index*5] = -1;
 293                         objective[(*i)->index*5+1] = -1;
 294                 }
 295                 else
 296                 {
 297                         objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
 298                         objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
 299                 }
 300
 301                 {
 302                         // Prevent the widget from going past the container's low edge.
 303                         LinearProgram::Row row = linprog.add_row();
 304                         row[(*i)->index*5] = 1;
 305                         row[(*i)->index*5+2] = -1;
 306                         row.back() = margin.*(ptrs.low_margin);
 307                 }
 308
 309                 if(mode==UPDATE)
 310                 {
 311                         // Prevent the widget from going past the container's high edge.
 312                         LinearProgram::Row row = linprog.add_row();
 313                         row[(*i)->index*5] = 1;
 314                         row[(*i)->index*5+1] = 1;
 315                         row[(*i)->index*5+3] = 1;
 316                         row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
 317                 }
 318
 319                 if(((*i)->*(ptrs.packing)).gravity==0)
 320                 {
 321                         /* This forces the widget's distance from the left and right edge of
 322                         the container to be equal.  It's a bit of a hack, but more time and
 323                         thought is needed for a better solution. */
 324                         LinearProgram::Row row = linprog.add_row();
 325                         row[(*i)->index*5+2] = 1;
 326                         row[(*i)->index*5+3] = -1;
 327                 }
 328
 329                 {
 330                         /* Only allow the widget's dimension to increase.  The geometry has
 331                         previously been set to the smallest allowable size. */
 332                         LinearProgram::Row row = linprog.add_row();
 333                         row[(*i)->index*5+1] = 1;
 334                         row[(*i)->index*5+4] = -1;
 335                         row.back() = (*i)->autosize_geom.*(ptrs.dim);
 336                 }
 337
 338                 /* Add rows for user-defined constraints.  Below/above and left/right of
 339                 constraints are always added in pairs, so it's only necessary to create a
 340                 row for one half. */
 341                 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
 342                         if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
 343                         {
 344                                 LinearProgram::Row row = linprog.add_row();
 345                                 if(j->type&SELF_POS)
 346                                         row[(*i)->index*5] = 1;
 347                                 if(j->type&SELF_DIM)
 348                                         row[(*i)->index*5+1] = 1;
 349                                 if(j->type&TARGET_POS)
 350                                         row[j->target.index*5] = -1;
 351                                 if(j->type&TARGET_DIM)
 352                                         row[j->target.index*5+1] = -1;
 353                                 if(j->type&SPACING)
 354                                         row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
 355                         }
 356         }
 357
 358         if(!linprog.solve())
 359                 return;
 360
 361         if(mode==AUTOSIZE)
 362         {
 363                 autosize_geom.*(ptrs.dim) = 0;
 364                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 365                 {
 366                         int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
 367                         autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
 368                 }
 369         }
 370         else
 371         {
 372                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 373                 {
 374                         (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
 375                         (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
 376                 }
 377         }
 378 }
 379
 380
 381 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
 382         type(t),
 383         target(s),
 384         spacing(-1)
 385 { }
 386
 387
 388 Layout::Packing::Packing():
 389         gravity(-1),
 390         expand(false)
 391 { }
 392
 393
 394 Layout::Slot::Slot(Layout &l, Widget &w):
 395         layout(l),
 396         index(0),
 397         widget(w)
 398 {
 399         vert_pack.gravity = 1;
 400         widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
 401         widget.autosize();
 402         autosize_geom = widget.get_geometry();
 403 }
 404
 405 void Layout::Slot::autosize_changed()
 406 {
 407         widget.autosize();
 408         autosize_geom = widget.get_geometry();
 409
 410         // If the widget fits in the area it had, just leave it there.
 411         if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
 412                 widget.set_geometry(geom);
 413         else
 414         {
 415                 layout.container->signal_autosize_changed.emit();
 416                 layout.update();
 417         }
 418 }
 419
 420
 421 Layout::LinearProgram::LinearProgram(unsigned s):
 422         n_columns(s),
 423         n_rows(1),
 424         columns(n_columns),
 425         solved(false),
 426         infeasible(false)
 427 { }
 428
 429 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
 430 {
 431         return Row(*this, n_rows++);
 432 }
 433
 434 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
 435 {
 436         if(r>=n_rows)
 437                 throw out_of_range("LinearProgram::operator[]");
 438
 439         return Row(*this, r);
 440 }
 441
 442 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
 443 {
 444         return Row(*this, 0);
 445 }
 446
 447 float Layout::LinearProgram::get_variable(unsigned i)
 448 {
 449         if(!solved || infeasible)
 450                 throw logic_error("not solved");
 451         if(i+1>=n_columns)
 452                 throw out_of_range("LinearProgram::get_variable");
 453
 454         if(unsigned r = columns[i].basic)
 455                 return columns.back().values[r];
 456         else
 457                 return 0;
 458 }
 459
 460 bool Layout::LinearProgram::solve()
 461 {
 462         if(solved || infeasible)
 463                 return !infeasible;
 464
 465         /* Solve the program using the simplex method.  The column representing the
 466         objective variable is kept implicit, as it would never change during the
 467         execution of the algorithm. */
 468
 469         prepare_columns();
 470
 471         add_artificial_variables();
 472
 473         // Solve the phase 1 problem.
 474         while(pivot()) ;
 475
 476         /* All artificial variables should now be non-basic and thus zero, so the
 477         objective function's value should also be zero.  If it isn't, the original
 478         program can't be solved. */
 479         if(columns.back().values.front())
 480         {
 481                 infeasible = true;
 482                 return false;
 483         }
 484
 485         remove_artificial_variables();
 486
 487         // Solve the phase 2 problem.  We already know it to be feasible.
 488         while(pivot()) ;
 489
 490         solved = true;
 491
 492         return true;
 493 }
 494
 495 void Layout::LinearProgram::prepare_columns()
 496 {
 497         /* See if any variables are already basic.  A basic variable must only have
 498         a nonzero coefficient on one row, and its product with the constant column
 499         must not be negative.  Only one variable can be basic for any given row. */
 500         vector<float> basic_coeff(n_rows, 0.0f);
 501         const vector<float> &constants = columns.back().values;
 502         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 503         {
 504                 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)
 505                 {
 506                         bool basic = true;
 507                         for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
 508                                 basic = (i->values[j]==0.0f);
 509                         if(basic)
 510                         {
 511                                 i->basic = i->values.size()-1;
 512                                 basic_coeff[i->basic] = -i->values.front()/i->values.back();
 513                                 i->values.clear();
 514                         }
 515                 }
 516         }
 517
 518         // Price out the newly-created basic variables.
 519         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 520                 if(!i->values.empty())
 521                 {
 522                         for(unsigned j=0; j<i->values.size(); ++j)
 523                                 i->values.front() += basic_coeff[j]*i->values[j];
 524                 }
 525 }
 526
 527 void Layout::LinearProgram::add_artificial_variables()
 528 {
 529         vector<unsigned> artificial_rows(n_rows-1);
 530         for(unsigned i=0; i<artificial_rows.size(); ++i)
 531                 artificial_rows[i] = i+1;
 532
 533         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 534                 if(i->basic)
 535                         artificial_rows[i->basic-1] = 0;
 536         artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
 537
 538         /* Force all non-basic columns fully into existence and relocate objective
 539         row to bottom in preparation of phase 1.  A new objective row is calculated
 540         by pricing out the constraint rows. */
 541         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 542                 if(!i->basic)
 543                 {
 544                         float objective = 0.0f;
 545                         if(!i->values.empty())
 546                         {
 547                                 objective = i->values.front();
 548                                 i->values.front() = 0.0f;
 549                                 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
 550                                         if(*j<i->values.size())
 551                                                 i->values.front() += i->values[*j];
 552                         }
 553                         i->values.resize(n_rows+1, 0.0f);
 554                         i->values.back() = objective;
 555                 }
 556
 557         if(artificial_rows.empty())
 558                 return;
 559
 560         /* Create artificial variables for phase 1.  This ensures that each row has
 561         a basic variable associated with it.  The original objective row already
 562         contains the implicit objective variable, which is basic. */
 563         columns.resize(n_columns+artificial_rows.size());
 564         columns.back() = columns[n_columns-1];
 565         columns[n_columns-1].values.clear();
 566         for(unsigned i=0; i<artificial_rows.size(); ++i)
 567                 columns[n_columns+i-1].basic = artificial_rows[i];
 568 }
 569
 570 void Layout::LinearProgram::remove_artificial_variables()
 571 {
 572         /* See if any artificial variables are still basic.  This could be because
 573         the program is degenerate.  To avoid trouble later on, use pivots to make
 574         some of the original variables basic instead.
 575
 576         I don't fully understand why this is needed, but it appears to work. */
 577         for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
 578                 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
 579                 {
 580                         for(unsigned j=0; j+1<n_columns; ++j)
 581                                 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
 582                                 {
 583                                         make_basic_column(j, columns[i].basic);
 584                                         break;
 585                                 }
 586                 }
 587
 588         /* Get rid of the artificial variables and restore the original objective
 589         row to form the phase 2 problem. */
 590         columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
 591         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 592                 if(!i->basic)
 593                 {
 594                         i->values.front() = i->values.back();
 595                         i->values.pop_back();
 596                 }
 597 }
 598
 599 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 600 {
 601         /* Pick the row with the minimum ratio between the constant column and the
 602         pivot column.  This ensures that when the pivot column is made basic, values
 603         in the constant column stay positive.
 604
 605         The use of n_rows instead of the true size of the column is intentional,
 606         since the relocated objective row must be ignored in phase 1. */
 607         float best = numeric_limits<float>::infinity();
 608         unsigned row = 0;
 609         for(unsigned i=1; i<n_rows; ++i)
 610                 if(columns[c].values[i]>0)
 611                 {
 612                         float ratio = columns.back().values[i]/columns[c].values[i];
 613                         if(ratio<best)
 614                         {
 615                                 best = ratio;
 616                                 row = i;
 617                         }
 618                 }
 619
 620         return row;
 621 }
 622
 623 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 624 {
 625         /* Perform row transfer operations to make the pivot column basic,
 626         containing a 1 on the pivot row. */
 627         for(unsigned i=0; i<columns.size(); ++i)
 628                 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
 629                 {
 630                         if(columns[i].basic)
 631                         {
 632                                 columns[i].values.resize(columns.back().values.size(), 0.0f);
 633                                 columns[i].values[columns[i].basic] = 1.0f;
 634                                 columns[i].basic = 0;
 635                         }
 636
 637                         float scale = columns[i].values[r]/columns[c].values[r];
 638
 639                         columns[i].values[r] = scale;
 640                         for(unsigned j=0; j<columns[i].values.size(); ++j)
 641                                 if(j!=r)
 642                                         columns[i].values[j] -= scale*columns[c].values[j];
 643                 }
 644
 645         columns[c].basic = r;
 646         columns[c].values.clear();
 647 }
 648
 649 bool Layout::LinearProgram::pivot()
 650 {
 651         /* Pick a nonbasic column and make it basic.  Requiring a positive objective
 652         coefficient ensures that the objective function's value will decrease in the
 653         process. */
 654         for(unsigned i=0; i+1<columns.size(); ++i)
 655                 if(!columns[i].basic && columns[i].values.front()>0)
 656                         if(unsigned row = find_minimal_ratio(i))
 657                         {
 658                                 make_basic_column(i, row);
 659                                 return true;
 660                         }
 661
 662         return false;
 663 }
 664
 665
 666 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
 667         linprog(lp),
 668         index(i)
 669 { }
 670
 671 float &Layout::LinearProgram::Row::operator[](unsigned c)
 672 {
 673         if(c>=linprog.n_columns)
 674                 throw out_of_range("Row::operator[]");
 675
 676         Column &column = linprog.columns[c];
 677         if(column.values.size()<=index)
 678                 column.values.resize(index+1);
 679
 680         return column.values[index];
 681 }
 682
 683 float &Layout::LinearProgram::Row::back()
 684 {
 685         return (*this)[linprog.n_columns-1];
 686 }
 687
 688
 689 Layout::LinearProgram::Column::Column():
 690         basic(0)
 691 { }
 692
 693 } // namespace GLtk
 694 } // namespace Msp