+#include <algorithm>
#include <limits>
+#include <msp/core/maputils.h>
+#include <msp/strings/format.h>
+#include "arrangement.h"
#include "container.h"
#include "layout.h"
#include "widget.h"
Row add_row();
Row operator[](unsigned);
Row get_objective_row();
- bool solve();
float get_variable(unsigned);
+ bool solve();
private:
+ void prepare_columns();
+ void add_artificial_variables();
+ void remove_artificial_variables();
unsigned find_minimal_ratio(unsigned);
void make_basic_column(unsigned, unsigned);
bool pivot();
Layout::Layout():
container(0),
+ n_active_slots(0),
margin(8),
row_spacing(5),
col_spacing(4)
-{ }
+{
+ n_slack_vars[0] = 0;
+ n_slack_vars[1] = 0;
+}
Layout::~Layout()
{
update();
}
+void Layout::set_spacing(unsigned s)
+{
+ row_spacing = s;
+ col_spacing = s;
+ if(container)
+ update();
+}
+
+void Layout::set_row_spacing(unsigned s)
+{
+ row_spacing = s;
+ if(container)
+ update();
+}
+
+void Layout::set_column_spacing(unsigned s)
+{
+ col_spacing = s;
+ if(container)
+ update();
+}
+
+void Layout::push_arrangement(Arrangement &arr)
+{
+ arrangement_stack.push_back(&arr);
+}
+
+Arrangement *Layout::get_arrangement() const
+{
+ if(arrangement_stack.empty())
+ return 0;
+ else
+ return arrangement_stack.back();
+}
+
+void Layout::pop_arrangement(Arrangement &arr)
+{
+ list<Arrangement *>::iterator begin = find(arrangement_stack.begin(), arrangement_stack.end(), &arr);
+ if(begin==arrangement_stack.end())
+ return;
+
+ while(1)
+ {
+ Arrangement *top = arrangement_stack.back();
+ arrangement_stack.pop_back();
+ if(!arrangement_stack.empty())
+ arrangement_stack.back()->arrange(*top);
+ if(top==&arr)
+ break;
+ }
+}
+
void Layout::add_widget(Widget &wdg)
{
if(!container)
throw logic_error("!container");
- Slot *slot = create_slot(wdg);
- for(list<Constraint>::iterator i=slot->constraints.begin(); i!=slot->constraints.end(); ++i)
- i->target.constraints.push_back(Constraint(complement(i->type), *slot));
- slot->index = slots.size();
- slots.push_back(slot);
+ slots.push_back(new Slot(*this, wdg));
+ update_slot_indices();
+ if(!arrangement_stack.empty())
+ arrangement_stack.back()->arrange(wdg);
if(container)
update();
}
delete *i;
slots.erase(i);
- unsigned n = 0;
- for(i=slots.begin(); i!=slots.end(); ++i, ++n)
- (*i)->index = n;
-
+ update_slot_indices();
update();
return;
}
}
-Layout::Slot *Layout::create_slot(Widget &wdg)
+void Layout::update_slot_indices()
{
- return new Slot(*this, wdg);
+ n_active_slots = 0;
+ unsigned n_floating = 0;
+ for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
+ {
+ if((*i)->widget.is_visible() || (*i)->ghost)
+ {
+ (*i)->index = n_active_slots++;
+ if((*i)->floating)
+ ++n_floating;
+ }
+ else
+ (*i)->index = -1;
+ }
+
+ n_slack_vars[0] = n_floating*2;
+ n_slack_vars[1] = n_floating*2;
+ for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
+ if((*i)->index>=0)
+ {
+ if(!(*i)->floating)
+ {
+ for(unsigned j=0; j<2; ++j)
+ if(((*i)->*(pointers[j].packing)).gravity==0)
+ n_slack_vars[j] += 2;
+ }
+
+ for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
+ if(j->target.index>(*i)->index && (j->type&SLACK))
+ ++n_slack_vars[j->type&1];
+ }
}
Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
Layout::ConstraintType Layout::complement(ConstraintType type)
{
- if(type==RIGHT_OF)
- return LEFT_OF;
- else if(type==LEFT_OF)
- return RIGHT_OF;
- else if(type==ABOVE)
- return BELOW;
- else if(type==BELOW)
- return ABOVE;
- else
- return type;
+ return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
}
-void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
+void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
{
if(&src==&tgt)
- throw invalid_argument("&src==&tgt");
+ throw invalid_argument("Layout::create_constraint");
Slot &src_slot = get_slot_for_widget(src);
Slot &tgt_slot = get_slot_for_widget(tgt);
return;
src_slot.constraints.push_back(Constraint(type, tgt_slot));
+ src_slot.constraints.back().spacing = sp;
tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
+ tgt_slot.constraints.back().spacing = sp;
+ update_slot_indices();
update();
}
+void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
+{
+ create_constraint(src, type, tgt, -1);
+}
+
+void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
+{
+ create_constraint(src, type, tgt, spacing);
+}
+
void Layout::set_gravity(Widget &wdg, int h, int v)
{
Slot &slot = get_slot_for_widget(wdg);
slot.horiz_pack.gravity = h;
slot.vert_pack.gravity = v;
+ update_slot_indices();
update();
}
update();
}
-void Layout::update()
+void Layout::set_ghost(Widget &wdg, bool g)
{
- for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
+ Slot &slot = get_slot_for_widget(wdg);
+
+ slot.ghost = g;
+
+ if(!wdg.is_visible())
{
- (*i)->widget.autosize();
- (*i)->geom = (*i)->widget.get_geometry();
+ update_slot_indices();
+ update();
}
+}
+
+void Layout::set_floating(Widget &wdg, bool f)
+{
+ Slot &slot = get_slot_for_widget(wdg);
+
+ slot.floating = f;
+
+ update_slot_indices();
+ update();
+}
- solve_constraints(HORIZONTAL);
- solve_constraints(VERTICAL);
+void Layout::update()
+{
+ solve_constraints(HORIZONTAL, UPDATE);
+ solve_constraints(VERTICAL, UPDATE);
for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
(*i)->widget.set_geometry((*i)->geom);
}
-void Layout::solve_constraints(int dir)
+void Layout::autosize(Geometry &geom)
+{
+ solve_constraints(HORIZONTAL, AUTOSIZE);
+ solve_constraints(VERTICAL, AUTOSIZE);
+
+ geom.w = max(geom.w, autosize_geom.w);
+ geom.h = max(geom.h, autosize_geom.h);
+}
+
+void Layout::solve_constraints(int dir, SolveMode mode)
{
Pointers &ptrs = pointers[dir&VERTICAL];
+ const Geometry &geom = container->get_geometry();
+ if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
+ return;
+
/* Set up a linear program to solve the constraints. The program matrix has
five columns for each widget, and one constant column. The first and second
columns of a widget are its position and dimension, respectively. The
remaining three are slack columns; see below for their purposes. */
- LinearProgram linprog(slots.size()*5+1);
+ LinearProgram linprog(n_active_slots*5+n_slack_vars[dir]+1);
float weight = slots.size();
+ unsigned k = n_active_slots*5;
for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
{
- linprog.get_objective_row()[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
- linprog.get_objective_row()[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
+ if((*i)->index<0)
+ continue;
+
+ LinearProgram::Row objective = linprog.get_objective_row();
+ if(mode==AUTOSIZE)
+ {
+ objective[(*i)->index*5] = -1;
+ objective[(*i)->index*5+1] = -1;
+ }
+ else
+ {
+ if(!(*i)->floating)
+ objective[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
+ objective[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
+ }
{
// Prevent the widget from going past the container's low edge.
row.back() = margin.*(ptrs.low_margin);
}
+ if(mode==UPDATE)
{
// Prevent the widget from going past the container's high edge.
LinearProgram::Row row = linprog.add_row();
row[(*i)->index*5] = 1;
row[(*i)->index*5+1] = 1;
row[(*i)->index*5+3] = 1;
- row.back() = container->get_geometry().*(ptrs.dim)-margin.*(ptrs.high_margin);
+ row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
}
+ if((*i)->floating || ((*i)->*(ptrs.packing)).gravity==0)
{
- /* Only allow the widget's dimension to increase. The geometry has
- previously been set to the smallest allowable size. */
+ /* Try to keep the widget as close to a target position as possible.
+ Since linear programs can't express absolute values directly, use two
+ opposing slack variables that are optimized for a low value. */
+ float a = ((*i)->*(ptrs.packing)).gravity*0.5+0.5;
+ LinearProgram::Row row = linprog.add_row();
+ row[(*i)->index*5] = 1;
+ row[(*i)->index*5+1] = a;
+ row[k] = 1;
+ row[k+1] = -1;
+ if((*i)->floating)
+ {
+ const Geometry &cgeom = (*i)->widget.get_geometry();
+ row.back() = cgeom.*(ptrs.pos)+cgeom.*(ptrs.dim)*a;
+ }
+ else
+ row.back() = geom.*(ptrs.dim)/2;
+ objective[k] = -1;
+ objective[k+1] = -1;
+ k += 2;
+ }
+
+ {
+ /* Don't allow the widget's dimension to get below that determined
+ by autosizing. */
LinearProgram::Row row = linprog.add_row();
row[(*i)->index*5+1] = 1;
row[(*i)->index*5+4] = -1;
- row.back() = (*i)->geom.*(ptrs.dim);
+ row.back() = (*i)->autosize_geom.*(ptrs.dim);
}
- /* Add rows for user-defined constraints. Below/above and left/right of
- constraints are always added in pairs, so it's only necessary to create a
- row for one half. */
+ /* Add rows for user-defined constraints. Constraints are always added
+ in pairs, so it's only necessary to create a row for one half. */
for(list<Constraint>::iterator j=(*i)->constraints.begin(); j!=(*i)->constraints.end(); ++j)
- if((j->type&1)==dir && j->type!=BELOW && j->type!=LEFT_OF)
+ if(j->target.index>(*i)->index && (j->type&1)==dir)
{
LinearProgram::Row row = linprog.add_row();
+ float polarity = ((j->type&SELF_DIM) ? -1 : 1);
if(j->type&SELF_POS)
- row[(*i)->index*5] = 1;
+ row[(*i)->index*5] = polarity;
if(j->type&SELF_DIM)
- row[(*i)->index*5+1] = 1;
+ row[(*i)->index*5+1] = polarity;
if(j->type&TARGET_POS)
- row[j->target.index*5] = -1;
+ row[j->target.index*5] = -polarity;
if(j->type&TARGET_DIM)
- row[j->target.index*5+1] = -1;
+ row[j->target.index*5+1] = -polarity;
if(j->type&SPACING)
- row.back() = this->*(ptrs.spacing);
+ row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
+ if(j->type&SLACK)
+ row[k++] = -1;
}
}
if(!linprog.solve())
return;
- for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
+ if(mode==AUTOSIZE)
{
- (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
- (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
+ autosize_geom.*(ptrs.dim) = 0;
+ for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
+ if((*i)->index>=0)
+ {
+ int high_edge = linprog.get_variable((*i)->index*5)+linprog.get_variable((*i)->index*5+1);
+ autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
+ }
+ }
+ else
+ {
+ for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
+ if((*i)->index>=0)
+ {
+ (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
+ (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
+ }
}
}
Layout::Constraint::Constraint(ConstraintType t, Slot &s):
type(t),
- target(s)
+ target(s),
+ spacing(-1)
{ }
Layout::Slot::Slot(Layout &l, Widget &w):
layout(l),
index(0),
- widget(w)
+ widget(w),
+ ghost(false),
+ floating(false)
{
vert_pack.gravity = 1;
widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
+ widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
+ widget.autosize(autosize_geom);
}
void Layout::Slot::autosize_changed()
{
- layout.update();
+ widget.autosize(autosize_geom);
+
+ if(!widget.is_visible() && !ghost)
+ return;
+
+ // Only trigger an update if the widget won't fit in its current area.
+ if(autosize_geom.w>geom.w || autosize_geom.h>geom.h)
+ {
+ layout.container->signal_autosize_changed.emit();
+ layout.update();
+ }
+}
+
+void Layout::Slot::visibility_changed(bool v)
+{
+ layout.update_slot_indices();
+ if(v || ghost)
+ {
+ layout.container->signal_autosize_changed.emit();
+ layout.update();
+ }
+}
+
+
+Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
+ DataFile::ObjectLoader<Layout>(l),
+ wdg_map(wm)
+{
+ add("column_spacing", &Loader::column_spacing);
+ add("margin", &Loader::margin);
+ add("row_spacing", &Loader::row_spacing);
+ add("spacing", &Loader::spacing);
+ add("widget", &Loader::widget);
+}
+
+void Layout::Loader::column_spacing(unsigned s)
+{
+ obj.set_column_spacing(s);
+}
+
+void Layout::Loader::margin()
+{
+ Sides sides;
+ load_sub(sides);
+ obj.set_margin(sides);
+}
+
+void Layout::Loader::spacing(unsigned s)
+{
+ obj.set_spacing(s);
+}
+
+void Layout::Loader::row_spacing(unsigned s)
+{
+ obj.set_row_spacing(s);
+}
+
+void Layout::Loader::widget(const string &n)
+{
+ Widget &wdg = *get_item(wdg_map, n);
+ WidgetLoader ldr(obj, wdg, wdg_map);
+ load_sub_with(ldr);
+}
+
+
+Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
+ layout(l),
+ widget(w),
+ wdg_map(wm)
+{
+ add("constraint", &WidgetLoader::constraint);
+ add("expand", &WidgetLoader::expand);
+ add("ghost", &WidgetLoader::ghost);
+ add("gravity", &WidgetLoader::gravity);
+}
+
+void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
+{
+ Widget &target = *get_item(wdg_map, n);
+ layout.add_constraint(widget, type, target);
+}
+
+void Layout::WidgetLoader::expand(bool h, bool v)
+{
+ layout.set_expand(widget, h, v);
+}
+
+void Layout::WidgetLoader::ghost(bool g)
+{
+ layout.set_ghost(widget, g);
+}
+
+void Layout::WidgetLoader::gravity(int h, int v)
+{
+ layout.set_gravity(widget, h, v);
+}
+
+
+void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
+{
+ const string &str = conv.get();
+ if(str=="ABOVE")
+ ctype = Layout::ABOVE;
+ else if(str=="BELOW")
+ ctype = Layout::BELOW;
+ else if(str=="RIGHT_OF")
+ ctype = Layout::RIGHT_OF;
+ else if(str=="LEFT_OF")
+ ctype = Layout::LEFT_OF;
+ else if(str=="FAR_ABOVE")
+ ctype = Layout::FAR_ABOVE;
+ else if(str=="FAR_BELOW")
+ ctype = Layout::FAR_BELOW;
+ else if(str=="FAR_RIGHT_OF")
+ ctype = Layout::FAR_RIGHT_OF;
+ else if(str=="FAR_LEFT_OF")
+ ctype = Layout::FAR_LEFT_OF;
+ else if(str=="ALIGN_TOP")
+ ctype = Layout::ALIGN_TOP;
+ else if(str=="ALIGN_BOTTOM")
+ ctype = Layout::ALIGN_BOTTOM;
+ else if(str=="ALIGN_RIGHT")
+ ctype = Layout::ALIGN_RIGHT;
+ else if(str=="ALIGN_LEFT")
+ ctype = Layout::ALIGN_LEFT;
+ else if(str=="COPY_WIDTH")
+ ctype = Layout::COPY_WIDTH;
+ else if(str=="COPY_HEIGHT")
+ ctype = Layout::COPY_HEIGHT;
+ else
+ throw lexical_error(format("conversion of '%s' to ConstraintType", str));
}
if(i+1>=n_columns)
throw out_of_range("LinearProgram::get_variable");
- unsigned r = columns[i].basic;
- return columns.back().values[r];
+ if(unsigned r = columns[i].basic)
+ return columns.back().values[r];
+ else
+ return 0;
}
bool Layout::LinearProgram::solve()
objective variable is kept implicit, as it would never change during the
execution of the algorithm. */
- /* Force all columns fully into existence and relocate objective row to
- bottom in preparation of phase 1. A new objective row is calculated by
- pricing out the constraint rows. */
- for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
- {
- float objective = i->values.front();
- i->values.front() = 0.0f;
- for(vector<float>::iterator j=i->values.begin(); j!=i->values.end(); ++j)
- i->values.front() += *j;
- i->values.resize(n_rows+1, 0.0f);
- i->values.back() = objective;
- }
+ prepare_columns();
- /* Create artificial variables for phase 1. This ensures that each row has
- a basic variable associated with it. The original objective row already
- contains the implicit objective variable, which is basic. */
- columns.resize(n_columns+n_rows-1);
- columns.back() = columns[n_columns-1];
- columns[n_columns-1].values.clear();
- for(unsigned i=1; i<n_rows; ++i)
- {
- Column &column = columns[n_columns+i-2];
- column.basic = i;
- }
+ add_artificial_variables();
// Solve the phase 1 problem.
while(pivot()) ;
return false;
}
+ remove_artificial_variables();
+
+ // Solve the phase 2 problem. We already know it to be feasible.
+ while(pivot()) ;
+
+ solved = true;
+
+ return true;
+}
+
+void Layout::LinearProgram::prepare_columns()
+{
+ /* See if any variables are already basic. A basic variable must only have
+ a nonzero coefficient on one row, and its product with the constant column
+ must not be negative. Only one variable can be basic for any given row. */
+ vector<float> obj_coeff(n_rows, 0.0f);
+ vector<float> row_coeff(n_rows, 1.0f);
+ const vector<float> &constants = columns.back().values;
+ for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
+ {
+ if(i->values.size()>=2 && i->values.back()!=0.0f && (constants.size()<i->values.size() || i->values.back()*constants[i->values.size()-1]>=0.0f) && obj_coeff[i->values.size()-1]==0.0f)
+ {
+ bool basic = true;
+ for(unsigned j=1; (basic && j+1<i->values.size()); ++j)
+ basic = (i->values[j]==0.0f);
+ if(basic)
+ {
+ i->basic = i->values.size()-1;
+ row_coeff[i->basic] = 1.0f/i->values.back();
+ obj_coeff[i->basic] = -i->values.front();
+ i->values.clear();
+ }
+ }
+ }
+
+ // Price out the newly-created basic variables.
+ for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
+ if(!i->values.empty())
+ {
+ for(unsigned j=0; j<i->values.size(); ++j)
+ {
+ i->values[j] *= row_coeff[j];
+ i->values.front() += obj_coeff[j]*i->values[j];
+ }
+ }
+}
+
+void Layout::LinearProgram::add_artificial_variables()
+{
+ vector<unsigned> artificial_rows(n_rows-1);
+ for(unsigned i=0; i<artificial_rows.size(); ++i)
+ artificial_rows[i] = i+1;
+
+ for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
+ if(i->basic)
+ artificial_rows[i->basic-1] = 0;
+ artificial_rows.erase(std::remove(artificial_rows.begin(), artificial_rows.end(), 0), artificial_rows.end());
+
+ /* Force all non-basic columns fully into existence and relocate objective
+ row to bottom in preparation of phase 1. A new objective row is calculated
+ by pricing out the constraint rows. */
+ for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
+ if(!i->basic)
+ {
+ float objective = 0.0f;
+ if(!i->values.empty())
+ {
+ objective = i->values.front();
+ i->values.front() = 0.0f;
+ for(vector<unsigned>::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j)
+ if(*j<i->values.size())
+ i->values.front() += i->values[*j];
+ }
+ i->values.resize(n_rows+1, 0.0f);
+ i->values.back() = objective;
+ }
+
+ if(artificial_rows.empty())
+ return;
+
+ /* Create artificial variables for phase 1. This ensures that each row has
+ a basic variable associated with it. The original objective row already
+ contains the implicit objective variable, which is basic. */
+ columns.resize(n_columns+artificial_rows.size());
+ columns.back() = columns[n_columns-1];
+ columns[n_columns-1].values.clear();
+ for(unsigned i=0; i<artificial_rows.size(); ++i)
+ columns[n_columns+i-1].basic = artificial_rows[i];
+}
+
+void Layout::LinearProgram::remove_artificial_variables()
+{
+ /* See if any artificial variables are still basic. This could be because
+ the program is degenerate. To avoid trouble later on, use pivots to make
+ some of the original variables basic instead.
+
+ I don't fully understand why this is needed, but it appears to work. */
+ for(unsigned i=n_columns-1; i+1<columns.size(); ++i)
+ if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
+ {
+ for(unsigned j=0; j+1<n_columns; ++j)
+ if(!columns[j].basic && columns[j].values[columns[i].basic]!=0.0f)
+ {
+ make_basic_column(j, columns[i].basic);
+ break;
+ }
+ }
+
/* Get rid of the artificial variables and restore the original objective
row to form the phase 2 problem. */
columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
i->values.front() = i->values.back();
i->values.pop_back();
}
-
- // Solve the phase 2 problem. We already know it to be feasible.
- while(pivot()) ;
-
- solved = true;
-
- return true;
}
unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
projects / libs / gltk.git / blobdiff