X-Git-Url: http://git.tdb.fi/?a=blobdiff_plain;f=source%2Flayout.cpp;h=34afd7284a35878b409dd95f8b4bc34ebd6c4299;hb=2ea95d42a147747c79cade5c9b7f299d47367be7;hp=6ed46e4d44cecc7e9922ed4920566ada5f609422;hpb=2b70e8801c43875ed3f4135bdd0141265cff0312;p=libs%2Fgltk.git diff --git a/source/layout.cpp b/source/layout.cpp index 6ed46e4..34afd72 100644 --- a/source/layout.cpp +++ b/source/layout.cpp @@ -1,3 +1,4 @@ +#include #include #include "container.h" #include "layout.h" @@ -44,10 +45,13 @@ public: 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(); @@ -94,7 +98,7 @@ Layout::~Layout() void Layout::set_container(Container &c) { if(container) - throw InvalidState("This layout is already assigned to a Container"); + throw logic_error("container!=0"); container = &c; } @@ -109,7 +113,7 @@ void Layout::set_margin(const Sides &m) void Layout::add_widget(Widget &wdg) { if(!container) - throw InvalidState("Can't add Widgets without a Container"); + throw logic_error("!container"); Slot *slot = create_slot(wdg); for(list::iterator i=slot->constraints.begin(); i!=slot->constraints.end(); ++i) @@ -160,7 +164,7 @@ Layout::Slot &Layout::get_slot_for_widget(Widget &wdg) if(&(*i)->widget==&wdg) return **i; - throw InvalidParameterValue("Widget is not in the Layout"); + throw hierarchy_error("widget not in layout"); } Layout::ConstraintType Layout::complement(ConstraintType type) @@ -180,7 +184,7 @@ Layout::ConstraintType Layout::complement(ConstraintType type) void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt) { if(&src==&tgt) - throw InvalidParameterValue("Can't add a self-referencing constraint"); + throw invalid_argument("&src==&tgt"); Slot &src_slot = get_slot_for_widget(src); Slot &tgt_slot = get_slot_for_widget(tgt); @@ -217,32 +221,30 @@ void Layout::set_expand(Widget &wdg, bool h, bool v) void Layout::update() { - for(list::iterator i=slots.begin(); i!=slots.end(); ++i) - { - (*i)->widget.autosize(); - (*i)->geom = (*i)->widget.get_geometry(); - } - solve_constraints(HORIZONTAL); solve_constraints(VERTICAL); for(list::iterator i=slots.begin(); i!=slots.end(); ++i) (*i)->widget.set_geometry((*i)->geom); - } void Layout::solve_constraints(int dir) { Pointers &ptrs = pointers[dir&VERTICAL]; + /* 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::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); + 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); { + // 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; @@ -250,6 +252,7 @@ void Layout::solve_constraints(int dir) } { + // 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; @@ -258,14 +261,18 @@ void Layout::solve_constraints(int dir) } { + /* 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::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(); @@ -280,7 +287,6 @@ void Layout::solve_constraints(int dir) if(j->type&SPACING) row.back() = this->*(ptrs.spacing); } - } } if(!linprog.solve()) @@ -313,11 +319,20 @@ Layout::Slot::Slot(Layout &l, Widget &w): { 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.update(); } @@ -337,12 +352,12 @@ Layout::LinearProgram::Row Layout::LinearProgram::add_row() Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r) { if(r>=n_rows) - throw InvalidParameterValue("Row index out of range"); + throw out_of_range("LinearProgram::operator[]"); return Row(*this, r); } -Layout::LinearProgram::Row Layout::LinearProgram::get_object_row() +Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row() { return Row(*this, 0); } @@ -350,12 +365,14 @@ Layout::LinearProgram::Row Layout::LinearProgram::get_object_row() float Layout::LinearProgram::get_variable(unsigned i) { if(!solved || infeasible) - throw InvalidState("Not solved"); + throw logic_error("not solved"); if(i+1>=n_columns) - throw InvalidParameterValue("Variable index out of range"); + 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() @@ -363,58 +380,150 @@ bool Layout::LinearProgram::solve() if(solved || infeasible) return !infeasible; - // Force all columns fully into existence and relocate objective row to bottom - for(vector::iterator i=columns.begin(); i!=columns.end(); ++i) - { - float objective = i->values.front(); - i->values.front() = 0.0f; - for(vector::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 basic_coeff(n_rows, 0.0f); + const vector &constants = columns.back().values; + for(vector::iterator i=columns.begin(); i!=columns.end(); ++i) + { + if(i->values.size()>=2 && i->values.back()!=0.0f && (constants.size()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+1values.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::iterator i=columns.begin(); i!=columns.end(); ++i) + if(!i->values.empty()) + { + for(unsigned j=0; jvalues.size(); ++j) + i->values.front() += basic_coeff[j]*i->values[j]; + } +} + +void Layout::LinearProgram::add_artificial_variables() +{ + vector artificial_rows(n_rows-1); + for(unsigned i=0; i::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::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::iterator j=artificial_rows.begin(); j!=artificial_rows.end(); ++j) + if(*jvalues.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::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::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; i0) { @@ -425,12 +534,14 @@ unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c) 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; i0) if(unsigned row = find_minimal_ratio(i)) @@ -478,7 +589,7 @@ Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i): float &Layout::LinearProgram::Row::operator[](unsigned c) { if(c>=linprog.n_columns) - throw InvalidParameterValue("Column index out of range"); + throw out_of_range("Row::operator[]"); Column &column = linprog.columns[c]; if(column.values.size()<=index)