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