X-Git-Url: http://git.tdb.fi/?a=blobdiff_plain;f=source%2Flayout.cpp;h=34afd7284a35878b409dd95f8b4bc34ebd6c4299;hb=2ea95d42a147747c79cade5c9b7f299d47367be7;hp=6cf7b348a4dc5c753f0d5bd7574cc39c477ed365;hpb=39cf4c8d917dc60c087fb4af6885bfa78f6fba34;p=libs%2Fgltk.git

diff --git a/source/layout.cpp b/source/layout.cpp
index 6cf7b34..34afd72 100644
--- a/source/layout.cpp
+++ b/source/layout.cpp
@@ -1,3 +1,4 @@
+#include <algorithm>
 #include <limits>
 #include "container.h"
 #include "layout.h"
@@ -45,9 +46,12 @@ public:
 	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();
@@ -217,12 +221,6 @@ void Layout::set_expand(Widget &wdg, bool h, bool v)
 
 void Layout::update()
 {
-	for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
-	{
-		(*i)->widget.autosize();
-		(*i)->geom = (*i)->widget.get_geometry();
-	}
-
 	solve_constraints(HORIZONTAL);
 	solve_constraints(VERTICAL);
 
@@ -268,7 +266,7 @@ void Layout::solve_constraints(int dir)
 			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
@@ -321,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();
 }
 
 
@@ -362,8 +369,10 @@ float Layout::LinearProgram::get_variable(unsigned i)
 	if(i+1>=n_columns)
 		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()
@@ -375,30 +384,9 @@ bool Layout::LinearProgram::solve()
 	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();
-		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()) ;
@@ -412,6 +400,109 @@ bool Layout::LinearProgram::solve()
 		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);
@@ -421,13 +512,6 @@ bool Layout::LinearProgram::solve()
 			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)