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         LinearProgram linprog(slots.size()*5+1);
 239         float weight = slots.size();
 240         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 241         {
 242                 linprog.get_object_row()[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
 243                 linprog.get_object_row()[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
 244
 245                 {
 246                         LinearProgram::Row row = linprog.add_row();
 247                         row[(*i)->index*5] = 1;
 248                         row[(*i)->index*5+2] = -1;
 249                         row.back() = margin.*(ptrs.low_margin);
 250                 }
 251
 252                 {
 253                         LinearProgram::Row row = linprog.add_row();
 254                         row[(*i)->index*5] = 1;
 255                         row[(*i)->index*5+1] = 1;
 256                         row[(*i)->index*5+3] = 1;
 257                         row.back() = container->get_geometry().*(ptrs.dim)-margin.*(ptrs.high_margin);
 258                 }
 259
 260                 {
 261                         LinearProgram::Row row = linprog.add_row();
 262                         row[(*i)->index*5+1] = 1;
 263                         row[(*i)->index*5+4] = -1;
 264                         row.back() = (*i)->geom.*(ptrs.dim);
 265                 }
 266
 267                 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
 268                 {
 269                         if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
 270                         {
 271                                 LinearProgram::Row row = linprog.add_row();
 272                                 if(j->type&SELF_POS)
 273                                         row[(*i)->index*5] = 1;
 274                                 if(j->type&SELF_DIM)
 275                                         row[(*i)->index*5+1] = 1;
 276                                 if(j->type&TARGET_POS)
 277                                         row[j->target.index*5] = -1;
 278                                 if(j->type&TARGET_DIM)
 279                                         row[j->target.index*5+1] = -1;
 280                                 if(j->type&SPACING)
 281                                         row.back() = this->*(ptrs.spacing);
 282                         }
 283                 }
 284         }
 285
 286         if(!linprog.solve())
 287                 return;
 288
 289         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 290         {
 291                 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
 292                 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
 293         }
 294 }
 295
 296
 297 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
 298         type(t),
 299         target(s)
 300 { }
 301
 302
 303 Layout::Packing::Packing():
 304         gravity(-1),
 305         expand(false)
 306 { }
 307
 308
 309 Layout::Slot::Slot(Layout &l, Widget &w):
 310         layout(l),
 311         index(0),
 312         widget(w)
 313 {
 314         vert_pack.gravity = 1;
 315         widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
 316 }
 317
 318 void Layout::Slot::autosize_changed()
 319 {
 320         layout.update();
 321 }
 322
 323
 324 Layout::LinearProgram::LinearProgram(unsigned s):
 325         n_columns(s),
 326         n_rows(1),
 327         columns(n_columns),
 328         solved(false),
 329         infeasible(false)
 330 { }
 331
 332 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
 333 {
 334         return Row(*this, n_rows++);
 335 }
 336
 337 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
 338 {
 339         if(r>=n_rows)
 340                 throw out_of_range("LinearProgram::operator[]");
 341
 342         return Row(*this, r);
 343 }
 344
 345 Layout::LinearProgram::Row Layout::LinearProgram::get_object_row()
 346 {
 347         return Row(*this, 0);
 348 }
 349
 350 float Layout::LinearProgram::get_variable(unsigned i)
 351 {
 352         if(!solved || infeasible)
 353                 throw logic_error("not solved");
 354         if(i+1>=n_columns)
 355                 throw out_of_range("LinearProgram::get_variable");
 356
 357         unsigned r = columns[i].basic;
 358         return columns.back().values[r];
 359 }
 360
 361 bool Layout::LinearProgram::solve()
 362 {
 363         if(solved || infeasible)
 364                 return !infeasible;
 365
 366         // Force all columns fully into existence and relocate objective row to bottom
 367         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 368         {
 369                 float objective = i->values.front();
 370                 i->values.front() = 0.0f;
 371                 for(vector<float>::iterator j=i->values.begin(); j!=i->values.end(); ++j)
 372                         i->values.front() += *j;
 373                 i->values.resize(n_rows+1, 0.0f);
 374                 i->values.back() = objective;
 375         }
 376
 377         // Create artificial variables for phase 1
 378         columns.resize(n_columns+n_rows-1);
 379         columns.back() = columns[n_columns-1];
 380         columns[n_columns-1].values.clear();
 381         for(unsigned i=1; i<n_rows; ++i)
 382         {
 383                 Column &column = columns[n_columns+i-2];
 384                 column.basic = i;
 385         }
 386
 387         // Solve the phase 1 problem
 388         while(pivot()) ;
 389
 390         if(columns.back().values.front())
 391         {
 392                 infeasible = true;
 393                 return false;
 394         }
 395
 396         // Get rid of artificial columns and restore objective row
 397         columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
 398         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 399                 if(!i->basic)
 400                 {
 401                         i->values.front() = i->values.back();
 402                         i->values.pop_back();
 403                 }
 404
 405         while(pivot()) ;
 406
 407         solved = true;
 408
 409         return true;
 410 }
 411
 412 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 413 {
 414         float best = numeric_limits<float>::infinity();
 415         unsigned row = 0;
 416         /* Intentionally use n_rows since we need to ignore the relocated original
 417         objective row in phase 1 */
 418         for(unsigned i=1; i<n_rows; ++i)
 419                 if(columns[c].values[i]>0)
 420                 {
 421                         float ratio = columns.back().values[i]/columns[c].values[i];
 422                         if(ratio<best)
 423                         {
 424                                 best = ratio;
 425                                 row = i;
 426                         }
 427                 }
 428
 429         return row;
 430 }
 431
 432 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 433 {
 434         for(unsigned i=0; i<columns.size(); ++i)
 435                 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
 436                 {
 437                         if(columns[i].basic)
 438                         {
 439                                 columns[i].values.resize(columns.back().values.size(), 0.0f);
 440                                 columns[i].values[columns[i].basic] = 1.0f;
 441                                 columns[i].basic = 0;
 442                         }
 443
 444                         float scale = columns[i].values[r]/columns[c].values[r];
 445
 446                         for(unsigned j=0; j<columns[i].values.size(); ++j)
 447                         {
 448                                 if(j==r)
 449                                         columns[i].values[j] = scale;
 450                                 else
 451                                         columns[i].values[j] -= scale*columns[c].values[j];
 452                         }
 453                 }
 454
 455         columns[c].basic = r;
 456         columns[c].values.clear();
 457 }
 458
 459 bool Layout::LinearProgram::pivot()
 460 {
 461         for(unsigned i=0; i+1<columns.size(); ++i)
 462                 if(!columns[i].basic && columns[i].values.front()>0)
 463                         if(unsigned row = find_minimal_ratio(i))
 464                         {
 465                                 make_basic_column(i, row);
 466                                 return true;
 467                         }
 468
 469         return false;
 470 }
 471
 472
 473 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
 474         linprog(lp),
 475         index(i)
 476 { }
 477
 478 float &Layout::LinearProgram::Row::operator[](unsigned c)
 479 {
 480         if(c>=linprog.n_columns)
 481                 throw out_of_range("Row::operator[]");
 482
 483         Column &column = linprog.columns[c];
 484         if(column.values.size()<=index)
 485                 column.values.resize(index+1);
 486
 487         return column.values[index];
 488 }
 489
 490 float &Layout::LinearProgram::Row::back()
 491 {
 492         return (*this)[linprog.n_columns-1];
 493 }
 494
 495
 496 Layout::LinearProgram::Column::Column():
 497         basic(0)
 498 { }
 499
 500 } // namespace GLtk
 501 } // namespace Msp