3 This file is part of libmspgltk
4 Copyright © 2011 Mikko Rasa, Mikkosoft Productions
5 Distributed under the LGPL
18 class Layout::LinearProgram
24 LinearProgram &linprog;
28 Row(LinearProgram &, unsigned);
30 float &operator[](unsigned);
38 std::vector<float> values;
45 std::vector<Column> columns;
50 LinearProgram(unsigned);
53 Row operator[](unsigned);
56 float get_variable(unsigned);
58 unsigned find_minimal_ratio(unsigned);
59 void make_basic_column(unsigned, unsigned);
64 struct Layout::Pointers
67 unsigned Geometry::*dim;
68 Packing Slot::*packing;
69 unsigned Sides::*low_margin;
70 unsigned Sides::*high_margin;
71 unsigned Layout::*spacing;
74 Layout::Pointers Layout::pointers[2] =
76 &Geometry::x, &Geometry::w,
78 &Sides::left, &Sides::right,
81 &Geometry::y, &Geometry::h,
83 &Sides::bottom, &Sides::top,
97 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
101 void Layout::set_container(Container &c)
104 throw InvalidState("This layout is already assigned to a Container");
109 void Layout::set_margin(const Sides &m)
116 void Layout::add_widget(Widget &wdg)
119 throw InvalidState("Can't add Widgets without a Container");
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);
130 void Layout::remove_widget(Widget &wdg)
132 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
133 if(&(*i)->widget==&wdg)
135 for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
138 for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
141 (*j)->constraints.erase(k++);
151 for(i=slots.begin(); i!=slots.end(); ++i, ++n)
159 Layout::Slot *Layout::create_slot(Widget &wdg)
161 return new Slot(*this, wdg);
164 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
166 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
167 if(&(*i)->widget==&wdg)
170 throw InvalidParameterValue("Widget is not in the Layout");
173 Layout::ConstraintType Layout::complement(ConstraintType type)
177 else if(type==LEFT_OF)
187 void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
190 throw InvalidParameterValue("Can't add a self-referencing constraint");
192 Slot &src_slot = get_slot_for_widget(src);
193 Slot &tgt_slot = get_slot_for_widget(tgt);
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)
199 src_slot.constraints.push_back(Constraint(type, tgt_slot));
200 tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
205 void Layout::set_gravity(Widget &wdg, int h, int v)
207 Slot &slot = get_slot_for_widget(wdg);
209 slot.horiz_pack.gravity = h;
210 slot.vert_pack.gravity = v;
215 void Layout::set_expand(Widget &wdg, bool h, bool v)
217 Slot &slot = get_slot_for_widget(wdg);
219 slot.horiz_pack.expand = h;
220 slot.vert_pack.expand = v;
225 void Layout::update()
227 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
229 (*i)->widget.autosize();
230 (*i)->geom = (*i)->widget.get_geometry();
233 solve_constraints(HORIZONTAL);
234 solve_constraints(VERTICAL);
236 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
237 (*i)->widget.set_geometry((*i)->geom);
241 void Layout::solve_constraints(int dir)
243 Pointers &ptrs = pointers[dir&VERTICAL];
245 LinearProgram linprog(slots.size()*5+1);
246 float weight = slots.size();
247 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
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);
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);
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);
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);
274 for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
276 if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
278 LinearProgram::Row row = linprog.add_row();
280 row[(*i)->index*5] = 1;
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;
288 row.back() = this->*(ptrs.spacing);
296 for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
298 (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
299 (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
304 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
310 Layout::Packing::Packing():
316 Layout::Slot::Slot(Layout &l, Widget &w):
321 vert_pack.gravity = 1;
322 widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
325 void Layout::Slot::autosize_changed()
331 Layout::LinearProgram::LinearProgram(unsigned s):
339 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
341 return Row(*this, n_rows++);
344 Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
347 throw InvalidParameterValue("Row index out of range");
349 return Row(*this, r);
352 Layout::LinearProgram::Row Layout::LinearProgram::get_object_row()
354 return Row(*this, 0);
357 float Layout::LinearProgram::get_variable(unsigned i)
359 if(!solved || infeasible)
360 throw InvalidState("Not solved");
362 throw InvalidParameterValue("Variable index out of range");
364 unsigned r = columns[i].basic;
365 return columns.back().values[r];
368 bool Layout::LinearProgram::solve()
370 if(solved || infeasible)
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)
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;
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)
390 Column &column = columns[n_columns+i-2];
394 // Solve the phase 1 problem
397 if(columns.back().values.front())
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)
408 i->values.front() = i->values.back();
409 i->values.pop_back();
419 unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
421 float best = numeric_limits<float>::infinity();
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)
428 float ratio = columns.back().values[i]/columns[c].values[i];
439 void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
441 for(unsigned i=0; i<columns.size(); ++i)
442 if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
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;
451 float scale = columns[i].values[r]/columns[c].values[r];
453 for(unsigned j=0; j<columns[i].values.size(); ++j)
456 columns[i].values[j] = scale;
458 columns[i].values[j] -= scale*columns[c].values[j];
462 columns[c].basic = r;
463 columns[c].values.clear();
466 bool Layout::LinearProgram::pivot()
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))
472 make_basic_column(i, row);
480 Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
485 float &Layout::LinearProgram::Row::operator[](unsigned c)
487 if(c>=linprog.n_columns)
488 throw InvalidParameterValue("Column index out of range");
490 Column &column = linprog.columns[c];
491 if(column.values.size()<=index)
492 column.values.resize(index+1);
494 return column.values[index];
497 float &Layout::LinearProgram::Row::back()
499 return (*this)[linprog.n_columns-1];
503 Layout::LinearProgram::Column::Column():