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_object_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         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 221         {
 222                 (*i)->widget.autosize();
 223                 (*i)->geom = (*i)->widget.get_geometry();
 224         }
 225
 226         solve_constraints(HORIZONTAL);
 227         solve_constraints(VERTICAL);
 228
 229         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 230                 (*i)->widget.set_geometry((*i)->geom);
 231
 232 }
 233
 234 void Layout::solve_constraints(int dir)
 235 {
 236         Pointers &ptrs = pointers[dir&VERTICAL];
 237
 238         /* Set up a linear program to solve the constraints.  The program matrix has
 239         five columns for each widget, and one constant column.  The first and second
 240         columns of a widget are its position and dimension, respectively.  The
 241         remaining three are slack columns; see below for their purposes. */
 242         LinearProgram linprog(slots.size()*5+1);
 243         float weight = slots.size();
 244         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 245         {
 246                 linprog.get_object_row()[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
 247                 linprog.get_object_row()[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
 248
 249                 {
 250                         // Prevent the widget from going past the container's low edge.
 251                         LinearProgram::Row row = linprog.add_row();
 252                         row[(*i)->index*5] = 1;
 253                         row[(*i)->index*5+2] = -1;
 254                         row.back() = margin.*(ptrs.low_margin);
 255                 }
 256
 257                 {
 258                         // Prevent the widget from going past the container's high edge.
 259                         LinearProgram::Row row = linprog.add_row();
 260                         row[(*i)->index*5] = 1;
 261                         row[(*i)->index*5+1] = 1;
 262                         row[(*i)->index*5+3] = 1;
 263                         row.back() = container->get_geometry().*(ptrs.dim)-margin.*(ptrs.high_margin);
 264                 }
 265
 266                 {
 267                         /* Only allow the widget's dimension to increase.  The geometry has
 268                         previously been set to the smallest allowable size. */
 269                         LinearProgram::Row row = linprog.add_row();
 270                         row[(*i)->index*5+1] = 1;
 271                         row[(*i)->index*5+4] = -1;
 272                         row.back() = (*i)->geom.*(ptrs.dim);
 273                 }
 274
 275                 /* Add rows for user-defined constraints.  Below/above and left/right of
 276                 constraints are always added in pairs, so it's only necessary to create a
 277                 row for one half. */
 278                 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
 279                 {
 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
 297         if(!linprog.solve())
 298                 return;
 299
 300         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 301         {
 302                 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
 303                 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
 304         }
 305 }
 306
 307
 308 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
 309         type(t),
 310         target(s)
 311 { }
 312
 313
 314 Layout::Packing::Packing():
 315         gravity(-1),
 316         expand(false)
 317 { }
 318
 319
 320 Layout::Slot::Slot(Layout &l, Widget &w):
 321         layout(l),
 322         index(0),
 323         widget(w)
 324 {
 325         vert_pack.gravity = 1;
 326         widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
 327 }
 328
 329 void Layout::Slot::autosize_changed()
 330 {
 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_object_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 = i->values.front();
 387                 i->values.front() = 0.0f;
 388                 for(vector<float>::iterator j=i->values.begin(); j!=i->values.end(); ++j)
 389                         i->values.front() += *j;
 390                 i->values.resize(n_rows+1, 0.0f);
 391                 i->values.back() = objective;
 392         }
 393
 394         /* Create artificial variables for phase 1.  This ensures that each row has
 395         a basic variable associated with it.  The original objective row already
 396         contains the implicit objective variable, which is basic. */
 397         columns.resize(n_columns+n_rows-1);
 398         columns.back() = columns[n_columns-1];
 399         columns[n_columns-1].values.clear();
 400         for(unsigned i=1; i<n_rows; ++i)
 401         {
 402                 Column &column = columns[n_columns+i-2];
 403                 column.basic = i;
 404         }
 405
 406         // Solve the phase 1 problem.
 407         while(pivot()) ;
 408
 409         /* All artificial variables should now be non-basic and thus zero, so the
 410         objective function's value should also be zero.  If it isn't, the original
 411         program can't be solved. */
 412         if(columns.back().values.front())
 413         {
 414                 infeasible = true;
 415                 return false;
 416         }
 417
 418         /* Get rid of the artificial variables and restore the original objective
 419         row to form the phase 2 problem. */
 420         columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
 421         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 422                 if(!i->basic)
 423                 {
 424                         i->values.front() = i->values.back();
 425                         i->values.pop_back();
 426                 }
 427
 428         // Solve the phase 2 problem.  We already know it to be feasible.
 429         while(pivot()) ;
 430
 431         solved = true;
 432
 433         return true;
 434 }
 435
 436 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 437 {
 438         /* Pick the row with the minimum ratio between the constant column and the
 439         pivot column.  This ensures that when the pivot column is made basic, values
 440         in the constant column stay positive.
 441
 442         The use of n_rows instead of the true size of the column is intentional,
 443         since the relocated objective row must be ignored in phase 1. */
 444         float best = numeric_limits<float>::infinity();
 445         unsigned row = 0;
 446         for(unsigned i=1; i<n_rows; ++i)
 447                 if(columns[c].values[i]>0)
 448                 {
 449                         float ratio = columns.back().values[i]/columns[c].values[i];
 450                         if(ratio<best)
 451                         {
 452                                 best = ratio;
 453                                 row = i;
 454                         }
 455                 }
 456
 457         return row;
 458 }
 459
 460 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 461 {
 462         /* Perform row transfer operations to make the pivot column basic,
 463         containing a 1 on the pivot row. */
 464         for(unsigned i=0; i<columns.size(); ++i)
 465                 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
 466                 {
 467                         if(columns[i].basic)
 468                         {
 469                                 columns[i].values.resize(columns.back().values.size(), 0.0f);
 470                                 columns[i].values[columns[i].basic] = 1.0f;
 471                                 columns[i].basic = 0;
 472                         }
 473
 474                         float scale = columns[i].values[r]/columns[c].values[r];
 475
 476                         for(unsigned j=0; j<columns[i].values.size(); ++j)
 477                         {
 478                                 if(j==r)
 479                                         columns[i].values[j] = scale;
 480                                 else
 481                                         columns[i].values[j] -= scale*columns[c].values[j];
 482                         }
 483                 }
 484
 485         columns[c].basic = r;
 486         columns[c].values.clear();
 487 }
 488
 489 bool Layout::LinearProgram::pivot()
 490 {
 491         /* Pick a nonbasic column and make it basic.  Requiring a positive objective
 492         coefficient ensures that the objective function's value will decrease in the
 493         process. */
 494         for(unsigned i=0; i+1<columns.size(); ++i)
 495                 if(!columns[i].basic && columns[i].values.front()>0)
 496                         if(unsigned row = find_minimal_ratio(i))
 497                         {
 498                                 make_basic_column(i, row);
 499                                 return true;
 500                         }
 501
 502         return false;
 503 }
 504
 505
 506 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
 507         linprog(lp),
 508         index(i)
 509 { }
 510
 511 float &Layout::LinearProgram::Row::operator[](unsigned c)
 512 {
 513         if(c>=linprog.n_columns)
 514                 throw out_of_range("Row::operator[]");
 515
 516         Column &column = linprog.columns[c];
 517         if(column.values.size()<=index)
 518                 column.values.resize(index+1);
 519
 520         return column.values[index];
 521 }
 522
 523 float &Layout::LinearProgram::Row::back()
 524 {
 525         return (*this)[linprog.n_columns-1];
 526 }
 527
 528
 529 Layout::LinearProgram::Column::Column():
 530         basic(0)
 531 { }
 532
 533 } // namespace GLtk
 534 } // namespace Msp