X-Git-Url: http://git.tdb.fi/?a=blobdiff_plain;f=source%2Flayout.cpp;h=b4c3a0eccd38883ac83beb7b863a62b6d3a52b6b;hb=6549eff66171d53be91ea7ba3f23339812ef6cad;hp=ed7b93617dcd485c54759b7c00df05f90827f626;hpb=411a387be30f4fc25e0ce8924fb115b5863356f1;p=libs%2Fgltk.git diff --git a/source/layout.cpp b/source/layout.cpp index ed7b936..b4c3a0e 100644 --- a/source/layout.cpp +++ b/source/layout.cpp @@ -235,6 +235,10 @@ 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) @@ -243,6 +247,7 @@ void Layout::solve_constraints(int dir) linprog.get_object_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 +255,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,12 +264,17 @@ 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); } + /* 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) @@ -363,7 +374,13 @@ bool Layout::LinearProgram::solve() if(solved || infeasible) return !infeasible; - // Force all columns fully into existence and relocate objective row to bottom + /* 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. */ + + /* 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::iterator i=columns.begin(); i!=columns.end(); ++i) { float objective = i->values.front(); @@ -374,7 +391,9 @@ bool Layout::LinearProgram::solve() i->values.back() = objective; } - // Create artificial variables for phase 1 + /* 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(); @@ -384,16 +403,20 @@ bool Layout::LinearProgram::solve() column.basic = i; } - // Solve the phase 1 problem + // 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 + /* 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::iterator i=columns.begin(); i!=columns.end(); ++i) if(!i->basic) @@ -402,6 +425,7 @@ bool Layout::LinearProgram::solve() i->values.pop_back(); } + // Solve the phase 2 problem. We already know it to be feasible. while(pivot()) ; solved = true; @@ -411,10 +435,14 @@ bool Layout::LinearProgram::solve() 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) { @@ -431,6 +459,8 @@ unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c) 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))