source/layout.cpp

   1 #include <limits>
   2 #include "container.h"
   3 #include "layout.h"
   4 #include "widget.h"
   5
   6 using namespace std;
   7
   8 namespace Msp {
   9 namespace GLtk {
  10
  11 class Layout::LinearProgram
  12 {
  13 public:
  14         class Row
  15         {
  16         private:
  17                 LinearProgram &linprog;
  18                 unsigned index;
  19
  20         public:
  21                 Row(LinearProgram &, unsigned);
  22
  23                 float &operator[](unsigned);
  24                 float &back();
  25         };
  26
  27 private:
  28         struct Column
  29         {
  30                 unsigned basic;
  31                 std::vector<float> values;
  32
  33                 Column();
  34         };
  35
  36         unsigned n_columns;
  37         unsigned n_rows;
  38         std::vector<Column> columns;
  39         bool solved;
  40         bool infeasible;
  41
  42 public:
  43         LinearProgram(unsigned);
  44
  45         Row add_row();
  46         Row operator[](unsigned);
  47         Row get_objective_row();
  48         bool solve();
  49         float get_variable(unsigned);
  50 private:
  51         unsigned find_minimal_ratio(unsigned);
  52         void make_basic_column(unsigned, unsigned);
  53         bool pivot();
  54 };
  55
  56
  57 struct Layout::Pointers
  58 {
  59         int Geometry::*pos;
  60         unsigned Geometry::*dim;
  61         Packing Slot::*packing;
  62         unsigned Sides::*low_margin;
  63         unsigned Sides::*high_margin;
  64         unsigned Layout::*spacing;
  65 };
  66
  67 Layout::Pointers Layout::pointers[2] =
  68 { {
  69                 &Geometry::x, &Geometry::w,
  70                 &Slot::horiz_pack,
  71                 &Sides::left, &Sides::right,
  72                 &Layout::col_spacing
  73         }, {
  74                 &Geometry::y, &Geometry::h,
  75                 &Slot::vert_pack,
  76                 &Sides::bottom, &Sides::top,
  77                 &Layout::row_spacing
  78 } };
  79
  80
  81 Layout::Layout():
  82         container(0),
  83         margin(8),
  84         row_spacing(5),
  85         col_spacing(4)
  86 { }
  87
  88 Layout::~Layout()
  89 {
  90         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
  91                 delete *i;
  92 }
  93
  94 void Layout::set_container(Container &c)
  95 {
  96         if(container)
  97                 throw logic_error("container!=0");
  98
  99         container = &c;
 100 }
 101
 102 void Layout::set_margin(const Sides &m)
 103 {
 104         margin = m;
 105         if(container)
 106                 update();
 107 }
 108
 109 void Layout::add_widget(Widget &wdg)
 110 {
 111         if(!container)
 112                 throw logic_error("!container");
 113
 114         Slot *slot = create_slot(wdg);
 115         for(list<Constraint>::iterator i=slot->constraints.begin(); i!=slot->constraints.end(); ++i)
 116                 i->target.constraints.push_back(Constraint(complement(i->type), *slot));
 117         slot->index = slots.size();
 118         slots.push_back(slot);
 119         if(container)
 120                 update();
 121 }
 122
 123 void Layout::remove_widget(Widget &wdg)
 124 {
 125         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 126                 if(&(*i)->widget==&wdg)
 127                 {
 128                         for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
 129                                 if(j!=i)
 130                                 {
 131                                         for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
 132                                         {
 133                                                 if(&k->target==*i)
 134                                                         (*j)->constraints.erase(k++);
 135                                                 else
 136                                                         ++k;
 137                                         }
 138                                 }
 139
 140                         delete *i;
 141                         slots.erase(i);
 142
 143                         unsigned n = 0;
 144                         for(i=slots.begin(); i!=slots.end(); ++i, ++n)
 145                                 (*i)->index = n;
 146
 147                         update();
 148                         return;
 149                 }
 150 }
 151
 152 Layout::Slot *Layout::create_slot(Widget &wdg)
 153 {
 154         return new Slot(*this, wdg);
 155 }
 156
 157 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
 158 {
 159         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 160                 if(&(*i)->widget==&wdg)
 161                         return **i;
 162
 163         throw hierarchy_error("widget not in layout");
 164 }
 165
 166 Layout::ConstraintType Layout::complement(ConstraintType type)
 167 {
 168         if(type==RIGHT_OF)
 169                 return LEFT_OF;
 170         else if(type==LEFT_OF)
 171                 return RIGHT_OF;
 172         else if(type==ABOVE)
 173                 return BELOW;
 174         else if(type==BELOW)
 175                 return ABOVE;
 176         else
 177                 return type;
 178 }
 179
 180 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
 181 {
 182         if(&src==&tgt)
 183                 throw invalid_argument("&src==&tgt");
 184
 185         Slot &src_slot = get_slot_for_widget(src);
 186         Slot &tgt_slot = get_slot_for_widget(tgt);
 187
 188         for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
 189                 if(i->type==type && &i->target==&tgt_slot)
 190                         return;
 191
 192         src_slot.constraints.push_back(Constraint(type, tgt_slot));
 193         tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
 194
 195         update();
 196 }
 197
 198 void Layout::set_gravity(Widget &wdg, int h, int v)
 199 {
 200         Slot &slot = get_slot_for_widget(wdg);
 201
 202         slot.horiz_pack.gravity = h;
 203         slot.vert_pack.gravity = v;
 204
 205         update();
 206 }
 207
 208 void Layout::set_expand(Widget &wdg, bool h, bool v)
 209 {
 210         Slot &slot = get_slot_for_widget(wdg);
 211
 212         slot.horiz_pack.expand = h;
 213         slot.vert_pack.expand = v;
 214
 215         update();
 216 }
 217
 218 void Layout::update()
 219 {
 220         solve_constraints(HORIZONTAL);
 221         solve_constraints(VERTICAL);
 222
 223         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 224                 (*i)->widget.set_geometry((*i)->geom);
 225 }
 226
 227 void Layout::solve_constraints(int dir)
 228 {
 229         Pointers &ptrs = pointers[dir&VERTICAL];
 230
 231         /* Set up a linear program to solve the constraints.  The program matrix has
 232         five columns for each widget, and one constant column.  The first and second
 233         columns of a widget are its position and dimension, respectively.  The
 234         remaining three are slack columns; see below for their purposes. */
 235         LinearProgram linprog(slots.size()*5+1);
 236         float weight = slots.size();
 237         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 238         {
 239                 linprog.get_objective_row()[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
 240                 linprog.get_objective_row()[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
 241
 242                 {
 243                         // Prevent the widget from going past the container's low edge.
 244                         LinearProgram::Row row = linprog.add_row();
 245                         row[(*i)->index*5] = 1;
 246                         row[(*i)->index*5+2] = -1;
 247                         row.back() = margin.*(ptrs.low_margin);
 248                 }
 249
 250                 {
 251                         // Prevent the widget from going past the container's high edge.
 252                         LinearProgram::Row row = linprog.add_row();
 253                         row[(*i)->index*5] = 1;
 254                         row[(*i)->index*5+1] = 1;
 255                         row[(*i)->index*5+3] = 1;
 256                         row.back() = container->get_geometry().*(ptrs.dim)-margin.*(ptrs.high_margin);
 257                 }
 258
 259                 {
 260                         /* Only allow the widget's dimension to increase.  The geometry has
 261                         previously been set to the smallest allowable size. */
 262                         LinearProgram::Row row = linprog.add_row();
 263                         row[(*i)->index*5+1] = 1;
 264                         row[(*i)->index*5+4] = -1;
 265                         row.back() = (*i)->autosize_geom.*(ptrs.dim);
 266                 }
 267
 268                 /* Add rows for user-defined constraints.  Below/above and left/right of
 269                 constraints are always added in pairs, so it's only necessary to create a
 270                 row for one half. */
 271                 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
 272                         if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
 273                         {
 274                                 LinearProgram::Row row = linprog.add_row();
 275                                 if(j->type&SELF_POS)
 276                                         row[(*i)->index*5] = 1;
 277                                 if(j->type&SELF_DIM)
 278                                         row[(*i)->index*5+1] = 1;
 279                                 if(j->type&TARGET_POS)
 280                                         row[j->target.index*5] = -1;
 281                                 if(j->type&TARGET_DIM)
 282                                         row[j->target.index*5+1] = -1;
 283                                 if(j->type&SPACING)
 284                                         row.back() = this->*(ptrs.spacing);
 285                         }
 286         }
 287
 288         if(!linprog.solve())
 289                 return;
 290
 291         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 292         {
 293                 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
 294                 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
 295         }
 296 }
 297
 298
 299 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
 300         type(t),
 301         target(s)
 302 { }
 303
 304
 305 Layout::Packing::Packing():
 306         gravity(-1),
 307         expand(false)
 308 { }
 309
 310
 311 Layout::Slot::Slot(Layout &l, Widget &w):
 312         layout(l),
 313         index(0),
 314         widget(w)
 315 {
 316         vert_pack.gravity = 1;
 317         widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
 318         widget.autosize();
 319         autosize_geom = widget.get_geometry();
 320 }
 321
 322 void Layout::Slot::autosize_changed()
 323 {
 324         widget.autosize();
 325         autosize_geom = widget.get_geometry();
 326
 327         // If the widget fits in the area it had, just leave it there.
 328         if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
 329                 widget.set_geometry(geom);
 330         else
 331                 layout.update();
 332 }
 333
 334
 335 Layout::LinearProgram::LinearProgram(unsigned s):
 336         n_columns(s),
 337         n_rows(1),
 338         columns(n_columns),
 339         solved(false),
 340         infeasible(false)
 341 { }
 342
 343 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
 344 {
 345         return Row(*this, n_rows++);
 346 }
 347
 348 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
 349 {
 350         if(r>=n_rows)
 351                 throw out_of_range("LinearProgram::operator[]");
 352
 353         return Row(*this, r);
 354 }
 355
 356 Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
 357 {
 358         return Row(*this, 0);
 359 }
 360
 361 float Layout::LinearProgram::get_variable(unsigned i)
 362 {
 363         if(!solved || infeasible)
 364                 throw logic_error("not solved");
 365         if(i+1>=n_columns)
 366                 throw out_of_range("LinearProgram::get_variable");
 367
 368         unsigned r = columns[i].basic;
 369         return columns.back().values[r];
 370 }
 371
 372 bool Layout::LinearProgram::solve()
 373 {
 374         if(solved || infeasible)
 375                 return !infeasible;
 376
 377         /* Solve the program using the simplex method.  The column representing the
 378         objective variable is kept implicit, as it would never change during the
 379         execution of the algorithm. */
 380
 381         /* Force all columns fully into existence and relocate objective row to
 382         bottom in preparation of phase 1.  A new objective row is calculated by
 383         pricing out the constraint rows. */
 384         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 385         {
 386                 float objective = 0.0f;
 387                 if(!i->values.empty())
 388                 {
 389                         objective = i->values.front();
 390                         i->values.front() = 0.0f;
 391                         for(vector<float>::iterator j=i->values.begin(); j!=i->values.end(); ++j)
 392                                 i->values.front() += *j;
 393                 }
 394                 i->values.resize(n_rows+1, 0.0f);
 395                 i->values.back() = objective;
 396         }
 397
 398         /* Create artificial variables for phase 1.  This ensures that each row has
 399         a basic variable associated with it.  The original objective row already
 400         contains the implicit objective variable, which is basic. */
 401         columns.resize(n_columns+n_rows-1);
 402         columns.back() = columns[n_columns-1];
 403         columns[n_columns-1].values.clear();
 404         for(unsigned i=1; i<n_rows; ++i)
 405         {
 406                 Column &column = columns[n_columns+i-2];
 407                 column.basic = i;
 408         }
 409
 410         // Solve the phase 1 problem.
 411         while(pivot()) ;
 412
 413         /* All artificial variables should now be non-basic and thus zero, so the
 414         objective function's value should also be zero.  If it isn't, the original
 415         program can't be solved. */
 416         if(columns.back().values.front())
 417         {
 418                 infeasible = true;
 419                 return false;
 420         }
 421
 422         /* Get rid of the artificial variables and restore the original objective
 423         row to form the phase 2 problem. */
 424         columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
 425         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 426                 if(!i->basic)
 427                 {
 428                         i->values.front() = i->values.back();
 429                         i->values.pop_back();
 430                 }
 431
 432         // Solve the phase 2 problem.  We already know it to be feasible.
 433         while(pivot()) ;
 434
 435         solved = true;
 436
 437         return true;
 438 }
 439
 440 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 441 {
 442         /* Pick the row with the minimum ratio between the constant column and the
 443         pivot column.  This ensures that when the pivot column is made basic, values
 444         in the constant column stay positive.
 445
 446         The use of n_rows instead of the true size of the column is intentional,
 447         since the relocated objective row must be ignored in phase 1. */
 448         float best = numeric_limits<float>::infinity();
 449         unsigned row = 0;
 450         for(unsigned i=1; i<n_rows; ++i)
 451                 if(columns[c].values[i]>0)
 452                 {
 453                         float ratio = columns.back().values[i]/columns[c].values[i];
 454                         if(ratio<best)
 455                         {
 456                                 best = ratio;
 457                                 row = i;
 458                         }
 459                 }
 460
 461         return row;
 462 }
 463
 464 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 465 {
 466         /* Perform row transfer operations to make the pivot column basic,
 467         containing a 1 on the pivot row. */
 468         for(unsigned i=0; i<columns.size(); ++i)
 469                 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
 470                 {
 471                         if(columns[i].basic)
 472                         {
 473                                 columns[i].values.resize(columns.back().values.size(), 0.0f);
 474                                 columns[i].values[columns[i].basic] = 1.0f;
 475                                 columns[i].basic = 0;
 476                         }
 477
 478                         float scale = columns[i].values[r]/columns[c].values[r];
 479
 480                         columns[i].values[r] = scale;
 481                         for(unsigned j=0; j<columns[i].values.size(); ++j)
 482                                 if(j!=r)
 483                                         columns[i].values[j] -= scale*columns[c].values[j];
 484                 }
 485
 486         columns[c].basic = r;
 487         columns[c].values.clear();
 488 }
 489
 490 bool Layout::LinearProgram::pivot()
 491 {
 492         /* Pick a nonbasic column and make it basic.  Requiring a positive objective
 493         coefficient ensures that the objective function's value will decrease in the
 494         process. */
 495         for(unsigned i=0; i+1<columns.size(); ++i)
 496                 if(!columns[i].basic && columns[i].values.front()>0)
 497                         if(unsigned row = find_minimal_ratio(i))
 498                         {
 499                                 make_basic_column(i, row);
 500                                 return true;
 501                         }
 502
 503         return false;
 504 }
 505
 506
 507 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
 508         linprog(lp),
 509         index(i)
 510 { }
 511
 512 float &Layout::LinearProgram::Row::operator[](unsigned c)
 513 {
 514         if(c>=linprog.n_columns)
 515                 throw out_of_range("Row::operator[]");
 516
 517         Column &column = linprog.columns[c];
 518         if(column.values.size()<=index)
 519                 column.values.resize(index+1);
 520
 521         return column.values[index];
 522 }
 523
 524 float &Layout::LinearProgram::Row::back()
 525 {
 526         return (*this)[linprog.n_columns-1];
 527 }
 528
 529
 530 Layout::LinearProgram::Column::Column():
 531         basic(0)
 532 { }
 533
 534 } // namespace GLtk
 535 } // namespace Msp