Improve comments of the Layout class

[libs/gltk.git] / source / layout.cpp

diff --git a/source/layout.cpp b/source/layout.cpp
index ed7b93617dcd485c54759b7c00df05f90827f626..b4c3a0eccd38883ac83beb7b863a62b6d3a52b6b 100644 (file)
--- 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<Slot *>::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<Constraint>::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<Column>::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<Column>::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<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)
                {
@@ -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; i<columns.size(); ++i)
                if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
                {
@@ -458,6 +488,9 @@ void Layout::LinearProgram::make_basic_column(unsigned c, unsigned 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))