From 6549eff66171d53be91ea7ba3f23339812ef6cad Mon Sep 17 00:00:00 2001 From: Mikko Rasa Date: Mon, 26 Nov 2012 20:20:00 +0200 Subject: [PATCH] Improve comments of the Layout class Add some code comments to describe how the constraints are built and how the different parts of the simplex method work. They don't entirely explain the algorithm, but should help understanding the code. Minor fixes to the documentation. --- source/layout.cpp | 45 +++++++++++++++++++++++++++++++++++++++------ source/layout.h | 14 +++++++------- 2 files changed, 46 insertions(+), 13 deletions(-) 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)) diff --git a/source/layout.h b/source/layout.h index 379b468..7d53470 100644 --- a/source/layout.h +++ b/source/layout.h @@ -20,11 +20,11 @@ is then solved to obtain positions and dimensions that fulfill the constraints. There are three kinds of constraints available: ordering, alignment and dimension matching. -Ordering constraints specify that the widgets should be placed next to other -along X or Y axis. These operate on one axis at a time, so a widget could be -"right of" another even if they are separated by hundreds of pixels vertically. -The widgets will be separated by a spacing value, which is settable on a per- -layout basis. +Ordering constraints specify that the widgets should be placed next to each +other along X or Y axis. These operate on one axis at a time, so a widget +could be "right of" another even if they are separated by hundreds of pixels +vertically. The widgets will be separated by a spacing value, which is +settable on a per-layout basis. Alignment constraints make the corresponding edges of two widgets be on the same line. These are incompatible with ordering constraints, so only one or @@ -45,8 +45,8 @@ dependent widgets have the expand flag set, the results are currently undefined. Since specifiyng constraints manually can be quite tedious, there are some -derived Layout classes that implement common positioning patterns. See -MixedRows and Grid. +derived Layout classes that implement common positioning patterns. See Row, +Column, MixedRows and Grid. */ class Layout { -- 2.43.0