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