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         if(unsigned r = columns[i].basic)
 369                 return columns.back().values[r];
 370         else
 371                 return 0;
 372 }
 373
 374 bool Layout::LinearProgram::solve()
 375 {
 376         if(solved || infeasible)
 377                 return !infeasible;
 378
 379         /* Solve the program using the simplex method.  The column representing the
 380         objective variable is kept implicit, as it would never change during the
 381         execution of the algorithm. */
 382
 383         /* Force all columns fully into existence and relocate objective row to
 384         bottom in preparation of phase 1.  A new objective row is calculated by
 385         pricing out the constraint rows. */
 386         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 387         {
 388                 float objective = 0.0f;
 389                 if(!i->values.empty())
 390                 {
 391                         objective = i->values.front();
 392                         i->values.front() = 0.0f;
 393                         for(vector<float>::iterator j=i->values.begin(); j!=i->values.end(); ++j)
 394                                 i->values.front() += *j;
 395                 }
 396                 i->values.resize(n_rows+1, 0.0f);
 397                 i->values.back() = objective;
 398         }
 399
 400         /* Create artificial variables for phase 1.  This ensures that each row has
 401         a basic variable associated with it.  The original objective row already
 402         contains the implicit objective variable, which is basic. */
 403         columns.resize(n_columns+n_rows-1);
 404         columns.back() = columns[n_columns-1];
 405         columns[n_columns-1].values.clear();
 406         for(unsigned i=1; i<n_rows; ++i)
 407         {
 408                 Column &column = columns[n_columns+i-2];
 409                 column.basic = i;
 410         }
 411
 412         // Solve the phase 1 problem.
 413         while(pivot()) ;
 414
 415         /* All artificial variables should now be non-basic and thus zero, so the
 416         objective function's value should also be zero.  If it isn't, the original
 417         program can't be solved. */
 418         if(columns.back().values.front())
 419         {
 420                 infeasible = true;
 421                 return false;
 422         }
 423
 424         /* Get rid of the artificial variables and restore the original objective
 425         row to form the phase 2 problem. */
 426         columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
 427         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 428                 if(!i->basic)
 429                 {
 430                         i->values.front() = i->values.back();
 431                         i->values.pop_back();
 432                 }
 433
 434         // Solve the phase 2 problem.  We already know it to be feasible.
 435         while(pivot()) ;
 436
 437         solved = true;
 438
 439         return true;
 440 }
 441
 442 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 443 {
 444         /* Pick the row with the minimum ratio between the constant column and the
 445         pivot column.  This ensures that when the pivot column is made basic, values
 446         in the constant column stay positive.
 447
 448         The use of n_rows instead of the true size of the column is intentional,
 449         since the relocated objective row must be ignored in phase 1. */
 450         float best = numeric_limits<float>::infinity();
 451         unsigned row = 0;
 452         for(unsigned i=1; i<n_rows; ++i)
 453                 if(columns[c].values[i]>0)
 454                 {
 455                         float ratio = columns.back().values[i]/columns[c].values[i];
 456                         if(ratio<best)
 457                         {
 458                                 best = ratio;
 459                                 row = i;
 460                         }
 461                 }
 462
 463         return row;
 464 }
 465
 466 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 467 {
 468         /* Perform row transfer operations to make the pivot column basic,
 469         containing a 1 on the pivot row. */
 470         for(unsigned i=0; i<columns.size(); ++i)
 471                 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
 472                 {
 473                         if(columns[i].basic)
 474                         {
 475                                 columns[i].values.resize(columns.back().values.size(), 0.0f);
 476                                 columns[i].values[columns[i].basic] = 1.0f;
 477                                 columns[i].basic = 0;
 478                         }
 479
 480                         float scale = columns[i].values[r]/columns[c].values[r];
 481
 482                         columns[i].values[r] = scale;
 483                         for(unsigned j=0; j<columns[i].values.size(); ++j)
 484                                 if(j!=r)
 485                                         columns[i].values[j] -= scale*columns[c].values[j];
 486                 }
 487
 488         columns[c].basic = r;
 489         columns[c].values.clear();
 490 }
 491
 492 bool Layout::LinearProgram::pivot()
 493 {
 494         /* Pick a nonbasic column and make it basic.  Requiring a positive objective
 495         coefficient ensures that the objective function's value will decrease in the
 496         process. */
 497         for(unsigned i=0; i+1<columns.size(); ++i)
 498                 if(!columns[i].basic && columns[i].values.front()>0)
 499                         if(unsigned row = find_minimal_ratio(i))
 500                         {
 501                                 make_basic_column(i, row);
 502                                 return true;
 503                         }
 504
 505         return false;
 506 }
 507
 508
 509 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
 510         linprog(lp),
 511         index(i)
 512 { }
 513
 514 float &Layout::LinearProgram::Row::operator[](unsigned c)
 515 {
 516         if(c>=linprog.n_columns)
 517                 throw out_of_range("Row::operator[]");
 518
 519         Column &column = linprog.columns[c];
 520         if(column.values.size()<=index)
 521                 column.values.resize(index+1);
 522
 523         return column.values[index];
 524 }
 525
 526 float &Layout::LinearProgram::Row::back()
 527 {
 528         return (*this)[linprog.n_columns-1];
 529 }
 530
 531
 532 Layout::LinearProgram::Column::Column():
 533         basic(0)
 534 { }
 535
 536 } // namespace GLtk
 537 } // namespace Msp