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