+#include <algorithm>
#include <limits>
#include "container.h"
#include "layout.h"
Row add_row();
Row operator[](unsigned);
- Row get_object_row();
- bool solve();
+ Row get_objective_row();
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();
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::add_widget(Widget &wdg)
{
if(!container)
return type;
}
-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");
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();
}
+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);
void Layout::update()
{
- for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
- {
- (*i)->widget.autosize();
- (*i)->geom = (*i)->widget.get_geometry();
- }
-
- solve_constraints(HORIZONTAL);
- solve_constraints(VERTICAL);
+ 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::autosize()
+{
+ solve_constraints(HORIZONTAL, AUTOSIZE);
+ solve_constraints(VERTICAL, AUTOSIZE);
+ container->set_size(autosize_geom.w, autosize_geom.h);
}
-void Layout::solve_constraints(int dir)
+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);
float weight = slots.size();
for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
{
- linprog.get_object_row()[(*i)->index*5] = ((*i)->*(ptrs.packing)).gravity/weight;
- linprog.get_object_row()[(*i)->index*5+1] = (((*i)->*(ptrs.packing)).expand ? weight : -1);
+ LinearProgram::Row objective = linprog.get_objective_row();
+ if(mode==AUTOSIZE)
+ {
+ objective[(*i)->index*5] = -1;
+ objective[(*i)->index*5+1] = -1;
+ }
+ else
+ {
+ 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.
LinearProgram::Row row = linprog.add_row();
row[(*i)->index*5] = 1;
row[(*i)->index*5+2] = -1;
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)->*(ptrs.packing)).gravity==0)
+ {
+ /* This forces the widget's distance from the left and right edge of
+ the container to be equal. It's a bit of a hack, but more time and
+ thought is needed for a better solution. */
+ LinearProgram::Row row = linprog.add_row();
+ row[(*i)->index*5+2] = 1;
+ row[(*i)->index*5+3] = -1;
}
{
+ /* Only allow the widget's dimension to increase. The geometry has
+ previously been set to the smallest allowable size. */
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. */
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)
{
LinearProgram::Row row = linprog.add_row();
if(j->type&TARGET_DIM)
row[j->target.index*5+1] = -1;
if(j->type&SPACING)
- row.back() = this->*(ptrs.spacing);
+ row.back() = (j->spacing>=0 ? j->spacing : this->*(ptrs.spacing));
}
- }
}
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)
+ {
+ 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)
+ {
+ (*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)
{ }
{
vert_pack.gravity = 1;
widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
+ widget.autosize();
+ autosize_geom = widget.get_geometry();
}
void Layout::Slot::autosize_changed()
{
- layout.update();
+ widget.autosize();
+ autosize_geom = widget.get_geometry();
+
+ // If the widget fits in the area it had, just leave it there.
+ if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
+ widget.set_geometry(geom);
+ else
+ {
+ layout.container->signal_autosize_changed.emit();
+ layout.update();
+ }
}
return Row(*this, r);
}
-Layout::LinearProgram::Row Layout::LinearProgram::get_object_row()
+Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
{
return Row(*this, 0);
}
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()
if(solved || infeasible)
return !infeasible;
- // Force all columns fully into existence and relocate objective row to bottom
- 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;
- }
+ /* Solve the program using the simplex method. The column representing the
+ objective variable is kept implicit, as it would never change during the
+ execution of the algorithm. */
- // Create artificial variables for phase 1
- 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;
- }
+ prepare_columns();
- // Solve the phase 1 problem
+ add_artificial_variables();
+
+ // Solve the phase 1 problem.
while(pivot()) ;
+ /* All artificial variables should now be non-basic and thus zero, so the
+ objective function's value should also be zero. If it isn't, the original
+ program can't be solved. */
if(columns.back().values.front())
{
infeasible = true;
return false;
}
- // Get rid of artificial columns and restore objective row
- columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
+ 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)
{
- i->values.front() = i->values.back();
- i->values.pop_back();
+ 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;
}
- while(pivot()) ;
+ if(artificial_rows.empty())
+ return;
- solved = true;
+ /* 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];
+}
- return true;
+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);
+ for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
+ if(!i->basic)
+ {
+ i->values.front() = i->values.back();
+ i->values.pop_back();
+ }
}
unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
{
+ /* Pick the row with the minimum ratio between the constant column and the
+ pivot column. This ensures that when the pivot column is made basic, values
+ in the constant column stay positive.
+
+ The use of n_rows instead of the true size of the column is intentional,
+ since the relocated objective row must be ignored in phase 1. */
float best = numeric_limits<float>::infinity();
unsigned row = 0;
- /* Intentionally use n_rows since we need to ignore the relocated original
- objective row in phase 1 */
for(unsigned i=1; i<n_rows; ++i)
if(columns[c].values[i]>0)
{
row = i;
}
}
-
+
return row;
}
void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
{
+ /* Perform row transfer operations to make the pivot column basic,
+ containing a 1 on the pivot row. */
for(unsigned i=0; i<columns.size(); ++i)
if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
{
}
float scale = columns[i].values[r]/columns[c].values[r];
-
+
+ columns[i].values[r] = scale;
for(unsigned j=0; j<columns[i].values.size(); ++j)
- {
- if(j==r)
- columns[i].values[j] = scale;
- else
+ if(j!=r)
columns[i].values[j] -= scale*columns[c].values[j];
- }
}
columns[c].basic = r;
bool Layout::LinearProgram::pivot()
{
+ /* Pick a nonbasic column and make it basic. Requiring a positive objective
+ coefficient ensures that the objective function's value will decrease in the
+ process. */
for(unsigned i=0; i+1<columns.size(); ++i)
if(!columns[i].basic && columns[i].values.front()>0)
if(unsigned row = find_minimal_ratio(i))