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