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> obj_coeff(n_rows, 0.0f);
 501         vector<float> row_coeff(n_rows, 1.0f);
 502         const vector<float> &constants = columns.back().values;
 503         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 504         {
 505                 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)
 506                 {
 507                         bool basic = true;
 508                         for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
 509                                 basic = (i->values[j]==0.0f);
 510                         if(basic)
 511                         {
 512                                 i->basic = i->values.size()-1;
 513                                 row_coeff[i->basic] = 1.0f/i->values.back();
 514                                 obj_coeff[i->basic] = -i->values.front();
 515                                 i->values.clear();
 516                         }
 517                 }
 518         }
 519
 520         // Price out the newly-created basic variables.
 521         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 522                 if(!i->values.empty())
 523                 {
 524                         for(unsigned j=0; j<i->values.size(); ++j)
 525                         {
 526                                 i->values[j] *= row_coeff[j];
 527                                 i->values.front() += obj_coeff[j]*i->values[j];
 528                         }
 529                 }
 530 }
 531
 532 void Layout::LinearProgram::add_artificial_variables()
 533 {
 534         vector<unsigned> artificial_rows(n_rows-1);
 535         for(unsigned i=0; i<artificial_rows.size(); ++i)
 536                 artificial_rows[i] = i+1;
 537
 538         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 539                 if(i->basic)
 540                         artificial_rows[i->basic-1] = 0;
 541         artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
 542
 543         /* Force all non-basic columns fully into existence and relocate objective
 544         row to bottom in preparation of phase 1.  A new objective row is calculated
 545         by pricing out the constraint rows. */
 546         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 547                 if(!i->basic)
 548                 {
 549                         float objective = 0.0f;
 550                         if(!i->values.empty())
 551                         {
 552                                 objective = i->values.front();
 553                                 i->values.front() = 0.0f;
 554                                 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
 555                                         if(*j<i->values.size())
 556                                                 i->values.front() += i->values[*j];
 557                         }
 558                         i->values.resize(n_rows+1, 0.0f);
 559                         i->values.back() = objective;
 560                 }
 561
 562         if(artificial_rows.empty())
 563                 return;
 564
 565         /* Create artificial variables for phase 1.  This ensures that each row has
 566         a basic variable associated with it.  The original objective row already
 567         contains the implicit objective variable, which is basic. */
 568         columns.resize(n_columns+artificial_rows.size());
 569         columns.back() = columns[n_columns-1];
 570         columns[n_columns-1].values.clear();
 571         for(unsigned i=0; i<artificial_rows.size(); ++i)
 572                 columns[n_columns+i-1].basic = artificial_rows[i];
 573 }
 574
 575 void Layout::LinearProgram::remove_artificial_variables()
 576 {
 577         /* See if any artificial variables are still basic.  This could be because
 578         the program is degenerate.  To avoid trouble later on, use pivots to make
 579         some of the original variables basic instead.
 580
 581         I don't fully understand why this is needed, but it appears to work. */
 582         for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
 583                 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
 584                 {
 585                         for(unsigned j=0; j+1<n_columns; ++j)
 586                                 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
 587                                 {
 588                                         make_basic_column(j, columns[i].basic);
 589                                         break;
 590                                 }
 591                 }
 592
 593         /* Get rid of the artificial variables and restore the original objective
 594         row to form the phase 2 problem. */
 595         columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
 596         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 597                 if(!i->basic)
 598                 {
 599                         i->values.front() = i->values.back();
 600                         i->values.pop_back();
 601                 }
 602 }
 603
 604 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 605 {
 606         /* Pick the row with the minimum ratio between the constant column and the
 607         pivot column.  This ensures that when the pivot column is made basic, values
 608         in the constant column stay positive.
 609
 610         The use of n_rows instead of the true size of the column is intentional,
 611         since the relocated objective row must be ignored in phase 1. */
 612         float best = numeric_limits<float>::infinity();
 613         unsigned row = 0;
 614         for(unsigned i=1; i<n_rows; ++i)
 615                 if(columns[c].values[i]>0)
 616                 {
 617                         float ratio = columns.back().values[i]/columns[c].values[i];
 618                         if(ratio<best)
 619                         {
 620                                 best = ratio;
 621                                 row = i;
 622                         }
 623                 }
 624
 625         return row;
 626 }
 627
 628 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 629 {
 630         /* Perform row transfer operations to make the pivot column basic,
 631         containing a 1 on the pivot row. */
 632         for(unsigned i=0; i<columns.size(); ++i)
 633                 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
 634                 {
 635                         if(columns[i].basic)
 636                         {
 637                                 columns[i].values.resize(columns.back().values.size(), 0.0f);
 638                                 columns[i].values[columns[i].basic] = 1.0f;
 639                                 columns[i].basic = 0;
 640                         }
 641
 642                         float scale = columns[i].values[r]/columns[c].values[r];
 643
 644                         columns[i].values[r] = scale;
 645                         for(unsigned j=0; j<columns[i].values.size(); ++j)
 646                                 if(j!=r)
 647                                         columns[i].values[j] -= scale*columns[c].values[j];
 648                 }
 649
 650         columns[c].basic = r;
 651         columns[c].values.clear();
 652 }
 653
 654 bool Layout::LinearProgram::pivot()
 655 {
 656         /* Pick a nonbasic column and make it basic.  Requiring a positive objective
 657         coefficient ensures that the objective function's value will decrease in the
 658         process. */
 659         for(unsigned i=0; i+1<columns.size(); ++i)
 660                 if(!columns[i].basic && columns[i].values.front()>0)
 661                         if(unsigned row = find_minimal_ratio(i))
 662                         {
 663                                 make_basic_column(i, row);
 664                                 return true;
 665                         }
 666
 667         return false;
 668 }
 669
 670
 671 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
 672         linprog(lp),
 673         index(i)
 674 { }
 675
 676 float &Layout::LinearProgram::Row::operator[](unsigned c)
 677 {
 678         if(c>=linprog.n_columns)
 679                 throw out_of_range("Row::operator[]");
 680
 681         Column &column = linprog.columns[c];
 682         if(column.values.size()<=index)
 683                 column.values.resize(index+1);
 684
 685         return column.values[index];
 686 }
 687
 688 float &Layout::LinearProgram::Row::back()
 689 {
 690         return (*this)[linprog.n_columns-1];
 691 }
 692
 693
 694 Layout::LinearProgram::Column::Column():
 695         basic(0)
 696 { }
 697
 698 } // namespace GLtk
 699 } // namespace Msp