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                 {
 308                         /* Only allow the widget's dimension to increase.  The geometry has
 309                         previously been set to the smallest allowable size. */
 310                         LinearProgram::Row row = linprog.add_row();
 311                         row[(*i)->index*5+1] = 1;
 312                         row[(*i)->index*5+4] = -1;
 313                         row.back() = (*i)->autosize_geom.*(ptrs.dim);
 314                 }
 315
 316                 /* Add rows for user-defined constraints.  Below/above and left/right of
 317                 constraints are always added in pairs, so it's only necessary to create a
 318                 row for one half. */
 319                 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
 320                         if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
 321                         {
 322                                 LinearProgram::Row row = linprog.add_row();
 323                                 if(j->type&SELF_POS)
 324                                         row[(*i)->index*5] = 1;
 325                                 if(j->type&SELF_DIM)
 326                                         row[(*i)->index*5+1] = 1;
 327                                 if(j->type&TARGET_POS)
 328                                         row[j->target.index*5] = -1;
 329                                 if(j->type&TARGET_DIM)
 330                                         row[j->target.index*5+1] = -1;
 331                                 if(j->type&SPACING)
 332                                         row.back() = this->*(ptrs.spacing);
 333                         }
 334         }
 335
 336         if(!linprog.solve())
 337                 return;
 338
 339         if(mode==AUTOSIZE)
 340         {
 341                 autosize_geom.*(ptrs.dim) = 0;
 342                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 343                 {
 344                         int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
 345                         autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
 346                 }
 347         }
 348         else
 349         {
 350                 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 351                 {
 352                         (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
 353                         (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
 354                 }
 355         }
 356 }
 357
 358
 359 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
 360         type(t),
 361         target(s)
 362 { }
 363
 364
 365 Layout::Packing::Packing():
 366         gravity(-1),
 367         expand(false)
 368 { }
 369
 370
 371 Layout::Slot::Slot(Layout &l, Widget &w):
 372         layout(l),
 373         index(0),
 374         widget(w)
 375 {
 376         vert_pack.gravity = 1;
 377         widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
 378         widget.autosize();
 379         autosize_geom = widget.get_geometry();
 380 }
 381
 382 void Layout::Slot::autosize_changed()
 383 {
 384         widget.autosize();
 385         autosize_geom = widget.get_geometry();
 386
 387         // If the widget fits in the area it had, just leave it there.
 388         if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
 389                 widget.set_geometry(geom);
 390         else
 391         {
 392                 layout.container->signal_autosize_changed.emit();
 393                 layout.update();
 394         }
 395 }
 396
 397
 398 Layout::LinearProgram::LinearProgram(unsigned s):
 399         n_columns(s),
 400         n_rows(1),
 401         columns(n_columns),
 402         solved(false),
 403         infeasible(false)
 404 { }
 405
 406 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
 407 {
 408         return Row(*this, n_rows++);
 409 }
 410
 411 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
 412 {
 413         if(r>=n_rows)
 414                 throw out_of_range("LinearProgram::operator[]");
 415
 416         return Row(*this, r);
 417 }
 418
 419 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
 420 {
 421         return Row(*this, 0);
 422 }
 423
 424 float Layout::LinearProgram::get_variable(unsigned i)
 425 {
 426         if(!solved || infeasible)
 427                 throw logic_error("not solved");
 428         if(i+1>=n_columns)
 429                 throw out_of_range("LinearProgram::get_variable");
 430
 431         if(unsigned r = columns[i].basic)
 432                 return columns.back().values[r];
 433         else
 434                 return 0;
 435 }
 436
 437 bool Layout::LinearProgram::solve()
 438 {
 439         if(solved || infeasible)
 440                 return !infeasible;
 441
 442         /* Solve the program using the simplex method.  The column representing the
 443         objective variable is kept implicit, as it would never change during the
 444         execution of the algorithm. */
 445
 446         prepare_columns();
 447
 448         add_artificial_variables();
 449
 450         // Solve the phase 1 problem.
 451         while(pivot()) ;
 452
 453         /* All artificial variables should now be non-basic and thus zero, so the
 454         objective function's value should also be zero.  If it isn't, the original
 455         program can't be solved. */
 456         if(columns.back().values.front())
 457         {
 458                 infeasible = true;
 459                 return false;
 460         }
 461
 462         remove_artificial_variables();
 463
 464         // Solve the phase 2 problem.  We already know it to be feasible.
 465         while(pivot()) ;
 466
 467         solved = true;
 468
 469         return true;
 470 }
 471
 472 void Layout::LinearProgram::prepare_columns()
 473 {
 474         /* See if any variables are already basic.  A basic variable must only have
 475         a nonzero coefficient on one row, and its product with the constant column
 476         must not be negative.  Only one variable can be basic for any given row. */
 477         vector<float> basic_coeff(n_rows, 0.0f);
 478         const vector<float> &constants = columns.back().values;
 479         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 480         {
 481                 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)
 482                 {
 483                         bool basic = true;
 484                         for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
 485                                 basic = (i->values[j]==0.0f);
 486                         if(basic)
 487                         {
 488                                 i->basic = i->values.size()-1;
 489                                 basic_coeff[i->basic] = -i->values.front()/i->values.back();
 490                                 i->values.clear();
 491                         }
 492                 }
 493         }
 494
 495         // Price out the newly-created basic variables.
 496         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 497                 if(!i->values.empty())
 498                 {
 499                         for(unsigned j=0; j<i->values.size(); ++j)
 500                                 i->values.front() += basic_coeff[j]*i->values[j];
 501                 }
 502 }
 503
 504 void Layout::LinearProgram::add_artificial_variables()
 505 {
 506         vector<unsigned> artificial_rows(n_rows-1);
 507         for(unsigned i=0; i<artificial_rows.size(); ++i)
 508                 artificial_rows[i] = i+1;
 509
 510         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 511                 if(i->basic)
 512                         artificial_rows[i->basic-1] = 0;
 513         artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
 514
 515         /* Force all non-basic columns fully into existence and relocate objective
 516         row to bottom in preparation of phase 1.  A new objective row is calculated
 517         by pricing out the constraint rows. */
 518         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 519                 if(!i->basic)
 520                 {
 521                         float objective = 0.0f;
 522                         if(!i->values.empty())
 523                         {
 524                                 objective = i->values.front();
 525                                 i->values.front() = 0.0f;
 526                                 for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
 527                                         if(*j<i->values.size())
 528                                                 i->values.front() += i->values[*j];
 529                         }
 530                         i->values.resize(n_rows+1, 0.0f);
 531                         i->values.back() = objective;
 532                 }
 533
 534         if(artificial_rows.empty())
 535                 return;
 536
 537         /* Create artificial variables for phase 1.  This ensures that each row has
 538         a basic variable associated with it.  The original objective row already
 539         contains the implicit objective variable, which is basic. */
 540         columns.resize(n_columns+artificial_rows.size());
 541         columns.back() = columns[n_columns-1];
 542         columns[n_columns-1].values.clear();
 543         for(unsigned i=0; i<artificial_rows.size(); ++i)
 544                 columns[n_columns+i-1].basic = artificial_rows[i];
 545 }
 546
 547 void Layout::LinearProgram::remove_artificial_variables()
 548 {
 549         /* See if any artificial variables are still basic.  This could be because
 550         the program is degenerate.  To avoid trouble later on, use pivots to make
 551         some of the original variables basic instead.
 552
 553         I don't fully understand why this is needed, but it appears to work. */
 554         for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
 555                 if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
 556                 {
 557                         for(unsigned j=0; j+1<n_columns; ++j)
 558                                 if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
 559                                 {
 560                                         make_basic_column(j, columns[i].basic);
 561                                         break;
 562                                 }
 563                 }
 564
 565         /* Get rid of the artificial variables and restore the original objective
 566         row to form the phase 2 problem. */
 567         columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
 568         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 569                 if(!i->basic)
 570                 {
 571                         i->values.front() = i->values.back();
 572                         i->values.pop_back();
 573                 }
 574 }
 575
 576 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 577 {
 578         /* Pick the row with the minimum ratio between the constant column and the
 579         pivot column.  This ensures that when the pivot column is made basic, values
 580         in the constant column stay positive.
 581
 582         The use of n_rows instead of the true size of the column is intentional,
 583         since the relocated objective row must be ignored in phase 1. */
 584         float best = numeric_limits<float>::infinity();
 585         unsigned row = 0;
 586         for(unsigned i=1; i<n_rows; ++i)
 587                 if(columns[c].values[i]>0)
 588                 {
 589                         float ratio = columns.back().values[i]/columns[c].values[i];
 590                         if(ratio<best)
 591                         {
 592                                 best = ratio;
 593                                 row = i;
 594                         }
 595                 }
 596
 597         return row;
 598 }
 599
 600 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 601 {
 602         /* Perform row transfer operations to make the pivot column basic,
 603         containing a 1 on the pivot row. */
 604         for(unsigned i=0; i<columns.size(); ++i)
 605                 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
 606                 {
 607                         if(columns[i].basic)
 608                         {
 609                                 columns[i].values.resize(columns.back().values.size(), 0.0f);
 610                                 columns[i].values[columns[i].basic] = 1.0f;
 611                                 columns[i].basic = 0;
 612                         }
 613
 614                         float scale = columns[i].values[r]/columns[c].values[r];
 615
 616                         columns[i].values[r] = scale;
 617                         for(unsigned j=0; j<columns[i].values.size(); ++j)
 618                                 if(j!=r)
 619                                         columns[i].values[j] -= scale*columns[c].values[j];
 620                 }
 621
 622         columns[c].basic = r;
 623         columns[c].values.clear();
 624 }
 625
 626 bool Layout::LinearProgram::pivot()
 627 {
 628         /* Pick a nonbasic column and make it basic.  Requiring a positive objective
 629         coefficient ensures that the objective function's value will decrease in the
 630         process. */
 631         for(unsigned i=0; i+1<columns.size(); ++i)
 632                 if(!columns[i].basic && columns[i].values.front()>0)
 633                         if(unsigned row = find_minimal_ratio(i))
 634                         {
 635                                 make_basic_column(i, row);
 636                                 return true;
 637                         }
 638
 639         return false;
 640 }
 641
 642
 643 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
 644         linprog(lp),
 645         index(i)
 646 { }
 647
 648 float &Layout::LinearProgram::Row::operator[](unsigned c)
 649 {
 650         if(c>=linprog.n_columns)
 651                 throw out_of_range("Row::operator[]");
 652
 653         Column &column = linprog.columns[c];
 654         if(column.values.size()<=index)
 655                 column.values.resize(index+1);
 656
 657         return column.values[index];
 658 }
 659
 660 float &Layout::LinearProgram::Row::back()
 661 {
 662         return (*this)[linprog.n_columns-1];
 663 }
 664
 665
 666 Layout::LinearProgram::Column::Column():
 667         basic(0)
 668 { }
 669
 670 } // namespace GLtk
 671 } // namespace Msp