source/layout.cpp

   1 /* $Id$
   2
   3 This file is part of libmspgltk
   4 Copyright © 2011  Mikko Rasa, Mikkosoft Productions
   5 Distributed under the LGPL
   6 */
   7
   8 #include <limits>
   9 #include "container.h"
  10 #include "layout.h"
  11 #include "widget.h"
  12
  13 using namespace std;
  14
  15 namespace Msp {
  16 namespace GLtk {
  17
  18 class Layout::LinearProgram
  19 {
  20 public:
  21         class Row
  22         {
  23         private:
  24                 LinearProgram &linprog;
  25                 unsigned index;
  26
  27         public:
  28                 Row(LinearProgram &, unsigned);
  29
  30                 float &operator[](unsigned);
  31                 float &back();
  32         };
  33
  34 private:
  35         struct Column
  36         {
  37                 unsigned basic;
  38                 std::vector<float> values;
  39
  40                 Column();
  41         };
  42
  43         unsigned n_columns;
  44         unsigned n_rows;
  45         std::vector<Column> columns;
  46         bool solved;
  47         bool infeasible;
  48
  49 public:
  50         LinearProgram(unsigned);
  51
  52         Row add_row();
  53         Row operator[](unsigned);
  54         Row get_object_row();
  55         bool solve();
  56         float get_variable(unsigned);
  57 private:
  58         unsigned find_minimal_ratio(unsigned);
  59         void make_basic_column(unsigned, unsigned);
  60         bool pivot();
  61 };
  62
  63
  64 struct Layout::Pointers
  65 {
  66         int Geometry::*pos;
  67         unsigned Geometry::*dim;
  68         Packing Slot::*packing;
  69         unsigned Sides::*low_margin;
  70         unsigned Sides::*high_margin;
  71         unsigned Layout::*spacing;
  72 };
  73
  74 Layout::Pointers Layout::pointers[2] =
  75 { {
  76                 &Geometry::x, &Geometry::w,
  77                 &Slot::horiz_pack,
  78                 &Sides::left, &Sides::right,
  79                 &Layout::col_spacing
  80         }, {
  81                 &Geometry::y, &Geometry::h,
  82                 &Slot::vert_pack,
  83                 &Sides::bottom, &Sides::top,
  84                 &Layout::row_spacing
  85 } };
  86
  87
  88 Layout::Layout():
  89         container(0),
  90         margin(8),
  91         row_spacing(5),
  92         col_spacing(4)
  93 { }
  94
  95 Layout::~Layout()
  96 {
  97         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
  98                 delete *i;
  99 }
 100
 101 void Layout::set_container(Container &c)
 102 {
 103         if(container)
 104                 throw InvalidState("This layout is already assigned to a Container");
 105
 106         container = &c;
 107 }
 108
 109 void Layout::set_margin(const Sides &m)
 110 {
 111         margin = m;
 112         if(container)
 113                 update();
 114 }
 115
 116 void Layout::add_widget(Widget &wdg)
 117 {
 118         if(!container)
 119                 throw InvalidState("Can't add Widgets without a Container");
 120
 121         Slot *slot = create_slot(wdg);
 122         for(list<Constraint>::iterator i=slot->constraints.begin(); i!=slot->constraints.end(); ++i)
 123                 i->target.constraints.push_back(Constraint(complement(i->type), *slot));
 124         slot->index = slots.size();
 125         slots.push_back(slot);
 126         if(container)
 127                 update();
 128 }
 129
 130 void Layout::remove_widget(Widget &wdg)
 131 {
 132         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 133                 if(&(*i)->widget==&wdg)
 134                 {
 135                         for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
 136                                 if(j!=i)
 137                                 {
 138                                         for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
 139                                         {
 140                                                 if(&k->target==*i)
 141                                                         (*j)->constraints.erase(k++);
 142                                                 else
 143                                                         ++k;
 144                                         }
 145                                 }
 146
 147                         delete *i;
 148                         slots.erase(i);
 149
 150                         unsigned n = 0;
 151                         for(i=slots.begin(); i!=slots.end(); ++i, ++n)
 152                                 (*i)->index = n;
 153
 154                         update();
 155                         return;
 156                 }
 157 }
 158
 159 Layout::Slot *Layout::create_slot(Widget &wdg)
 160 {
 161         return new Slot(*this, wdg);
 162 }
 163
 164 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
 165 {
 166         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 167                 if(&(*i)->widget==&wdg)
 168                         return **i;
 169
 170         throw InvalidParameterValue("Widget is not in the Layout");
 171 }
 172
 173 Layout::ConstraintType Layout::complement(ConstraintType type)
 174 {
 175         if(type==RIGHT_OF)
 176                 return LEFT_OF;
 177         else if(type==LEFT_OF)
 178                 return RIGHT_OF;
 179         else if(type==ABOVE)
 180                 return BELOW;
 181         else if(type==BELOW)
 182                 return ABOVE;
 183         else
 184                 return type;
 185 }
 186
 187 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
 188 {
 189         if(&src==&tgt)
 190                 throw InvalidParameterValue("Can't add a self-referencing constraint");
 191
 192         Slot &src_slot = get_slot_for_widget(src);
 193         Slot &tgt_slot = get_slot_for_widget(tgt);
 194
 195         for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
 196                 if(i->type==type && &i->target==&tgt_slot)
 197                         return;
 198
 199         src_slot.constraints.push_back(Constraint(type, tgt_slot));
 200         tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
 201
 202         update();
 203 }
 204
 205 void Layout::set_gravity(Widget &wdg, int h, int v)
 206 {
 207         Slot &slot = get_slot_for_widget(wdg);
 208
 209         slot.horiz_pack.gravity = h;
 210         slot.vert_pack.gravity = v;
 211
 212         update();
 213 }
 214
 215 void Layout::set_expand(Widget &wdg, bool h, bool v)
 216 {
 217         Slot &slot = get_slot_for_widget(wdg);
 218
 219         slot.horiz_pack.expand = h;
 220         slot.vert_pack.expand = v;
 221
 222         update();
 223 }
 224
 225 void Layout::update()
 226 {
 227         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 228         {
 229                 (*i)->widget.autosize();
 230                 (*i)->geom = (*i)->widget.get_geometry();
 231         }
 232
 233         solve_constraints(HORIZONTAL);
 234         solve_constraints(VERTICAL);
 235
 236         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 237                 (*i)->widget.set_geometry((*i)->geom);
 238
 239 }
 240
 241 void Layout::solve_constraints(int dir)
 242 {
 243         Pointers &ptrs = pointers[dir&VERTICAL];
 244
 245         LinearProgram linprog(slots.size()*5+1);
 246         float weight = slots.size();
 247         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 248         {
 249                 linprog.get_object_row()[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
 250                 linprog.get_object_row()[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
 251
 252                 {
 253                         LinearProgram::Row row = linprog.add_row();
 254                         row[(*i)->index*5] = 1;
 255                         row[(*i)->index*5+2] = -1;
 256                         row.back() = margin.*(ptrs.low_margin);
 257                 }
 258
 259                 {
 260                         LinearProgram::Row row = linprog.add_row();
 261                         row[(*i)->index*5] = 1;
 262                         row[(*i)->index*5+1] = 1;
 263                         row[(*i)->index*5+3] = 1;
 264                         row.back() = container->get_geometry().*(ptrs.dim)-margin.*(ptrs.high_margin);
 265                 }
 266
 267                 {
 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                 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
 275                 {
 276                         if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
 277                         {
 278                                 LinearProgram::Row row = linprog.add_row();
 279                                 if(j->type&SELF_POS)
 280                                         row[(*i)->index*5] = 1;
 281                                 if(j->type&SELF_DIM)
 282                                         row[(*i)->index*5+1] = 1;
 283                                 if(j->type&TARGET_POS)
 284                                         row[j->target.index*5] = -1;
 285                                 if(j->type&TARGET_DIM)
 286                                         row[j->target.index*5+1] = -1;
 287                                 if(j->type&SPACING)
 288                                         row.back() = this->*(ptrs.spacing);
 289                         }
 290                 }
 291         }
 292
 293         if(!linprog.solve())
 294                 return;
 295
 296         for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
 297         {
 298                 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
 299                 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
 300         }
 301 }
 302
 303
 304 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
 305         type(t),
 306         target(s)
 307 { }
 308
 309
 310 Layout::Packing::Packing():
 311         gravity(-1),
 312         expand(false)
 313 { }
 314
 315
 316 Layout::Slot::Slot(Layout &l, Widget &w):
 317         layout(l),
 318         index(0),
 319         widget(w)
 320 {
 321         vert_pack.gravity = 1;
 322         widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
 323 }
 324
 325 void Layout::Slot::autosize_changed()
 326 {
 327         layout.update();
 328 }
 329
 330
 331 Layout::LinearProgram::LinearProgram(unsigned s):
 332         n_columns(s),
 333         n_rows(1),
 334         columns(n_columns),
 335         solved(false),
 336         infeasible(false)
 337 { }
 338
 339 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
 340 {
 341         return Row(*this, n_rows++);
 342 }
 343
 344 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
 345 {
 346         if(r>=n_rows)
 347                 throw InvalidParameterValue("Row index out of range");
 348
 349         return Row(*this, r);
 350 }
 351
 352 Layout::LinearProgram::Row Layout::LinearProgram::get_object_row()
 353 {
 354         return Row(*this, 0);
 355 }
 356
 357 float Layout::LinearProgram::get_variable(unsigned i)
 358 {
 359         if(!solved || infeasible)
 360                 throw InvalidState("Not solved");
 361         if(i+1>=n_columns)
 362                 throw InvalidParameterValue("Variable index out of range");
 363
 364         unsigned r = columns[i].basic;
 365         return columns.back().values[r];
 366 }
 367
 368 bool Layout::LinearProgram::solve()
 369 {
 370         if(solved || infeasible)
 371                 return !infeasible;
 372
 373         // Force all columns fully into existence and relocate objective row to bottom
 374         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 375         {
 376                 float objective = i->values.front();
 377                 i->values.front() = 0.0f;
 378                 for(vector<float>::iterator j=i->values.begin(); j!=i->values.end(); ++j)
 379                         i->values.front() += *j;
 380                 i->values.resize(n_rows+1, 0.0f);
 381                 i->values.back() = objective;
 382         }
 383
 384         // Create artificial variables for phase 1
 385         columns.resize(n_columns+n_rows-1);
 386         columns.back() = columns[n_columns-1];
 387         columns[n_columns-1].values.clear();
 388         for(unsigned i=1; i<n_rows; ++i)
 389         {
 390                 Column &column = columns[n_columns+i-2];
 391                 column.basic = i;
 392         }
 393
 394         // Solve the phase 1 problem
 395         while(pivot()) ;
 396
 397         if(columns.back().values.front())
 398         {
 399                 infeasible = true;
 400                 return false;
 401         }
 402
 403         // Get rid of artificial columns and restore objective row
 404         columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
 405         for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
 406                 if(!i->basic)
 407                 {
 408                         i->values.front() = i->values.back();
 409                         i->values.pop_back();
 410                 }
 411
 412         while(pivot()) ;
 413
 414         solved = true;
 415
 416         return true;
 417 }
 418
 419 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 420 {
 421         float best = numeric_limits<float>::infinity();
 422         unsigned row = 0;
 423         /* Intentionally use n_rows since we need to ignore the relocated original
 424         objective row in phase 1 */
 425         for(unsigned i=1; i<n_rows; ++i)
 426                 if(columns[c].values[i]>0)
 427                 {
 428                         float ratio = columns.back().values[i]/columns[c].values[i];
 429                         if(ratio<best)
 430                         {
 431                                 best = ratio;
 432                                 row = i;
 433                         }
 434                 }
 435
 436         return row;
 437 }
 438
 439 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 440 {
 441         for(unsigned i=0; i<columns.size(); ++i)
 442                 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
 443                 {
 444                         if(columns[i].basic)
 445                         {
 446                                 columns[i].values.resize(columns.back().values.size(), 0.0f);
 447                                 columns[i].values[columns[i].basic] = 1.0f;
 448                                 columns[i].basic = 0;
 449                         }
 450
 451                         float scale = columns[i].values[r]/columns[c].values[r];
 452
 453                         for(unsigned j=0; j<columns[i].values.size(); ++j)
 454                         {
 455                                 if(j==r)
 456                                         columns[i].values[j] = scale;
 457                                 else
 458                                         columns[i].values[j] -= scale*columns[c].values[j];
 459                         }
 460                 }
 461
 462         columns[c].basic = r;
 463         columns[c].values.clear();
 464 }
 465
 466 bool Layout::LinearProgram::pivot()
 467 {
 468         for(unsigned i=0; i+1<columns.size(); ++i)
 469                 if(!columns[i].basic && columns[i].values.front()>0)
 470                         if(unsigned row = find_minimal_ratio(i))
 471                         {
 472                                 make_basic_column(i, row);
 473                                 return true;
 474                         }
 475
 476         return false;
 477 }
 478
 479
 480 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
 481         linprog(lp),
 482         index(i)
 483 { }
 484
 485 float &Layout::LinearProgram::Row::operator[](unsigned c)
 486 {
 487         if(c>=linprog.n_columns)
 488                 throw InvalidParameterValue("Column index out of range");
 489
 490         Column &column = linprog.columns[c];
 491         if(column.values.size()<=index)
 492                 column.values.resize(index+1);
 493
 494         return column.values[index];
 495 }
 496
 497 float &Layout::LinearProgram::Row::back()
 498 {
 499         return (*this)[linprog.n_columns-1];
 500 }
 501
 502
 503 Layout::LinearProgram::Column::Column():
 504         basic(0)
 505 { }
 506
 507 } // namespace GLtk
 508 } // namespace Msp