+#include <algorithm>
#include <limits>
#include "container.h"
#include "layout.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();
void Layout::update()
{
- 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::solve_constraints(int dir)
+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, 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
float weight = slots.size();
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);
+ 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.
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(!linprog.solve())
return;
- for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
+ if(mode==AUTOSIZE)
+ {
+ 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
{
- (*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
- (*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
+ 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);
+ }
}
}
if(autosize_geom.w<=geom.w && autosize_geom.h<=geom.h)
widget.set_geometry(geom);
else
+ {
+ layout.container->signal_autosize_changed.emit();
layout.update();
+ }
}
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 = 0.0f;
- if(!i->values.empty())
- {
- 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> basic_coeff(n_rows, 0.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) && basic_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;
+ basic_coeff[i->basic] = -i->values.front()/i->values.back();
+ 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.front() += basic_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