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