X-Git-Url: http://git.tdb.fi/?a=blobdiff_plain;f=source%2Flayout.cpp;h=1cf35c722a3a95476532ec1d35898aa7a0e5b903;hb=HEAD;hp=ed7b93617dcd485c54759b7c00df05f90827f626;hpb=c1faa54a3218b53757b8b55de0ff8aa64412253b;p=libs%2Fgltk.git

diff --git a/source/layout.cpp b/source/layout.cpp
index ed7b936..495d626 100644
--- a/source/layout.cpp
+++ b/source/layout.cpp
@@ -1,4 +1,8 @@
 #include <limits>
+#include <msp/core/algorithm.h>
+#include <msp/core/maputils.h>
+#include <msp/strings/format.h>
+#include "arrangement.h"
 #include "container.h"
 #include "layout.h"
 #include "widget.h"
@@ -15,41 +19,44 @@ public:
 	{
 	private:
 		LinearProgram &linprog;
-		unsigned index;
+		size_t index;
 
 	public:
-		Row(LinearProgram &, unsigned);
+		Row(LinearProgram &, size_t);
 
-		float &operator[](unsigned);
+		float &operator[](size_t);
 		float &back();
 	};
 
 private:
 	struct Column
 	{
-		unsigned basic;
+		size_t basic;
 		std::vector<float> values;
 
 		Column();
 	};
 
-	unsigned n_columns;
-	unsigned n_rows;
+	size_t n_columns = 1;
+	size_t n_rows = 1;
 	std::vector<Column> columns;
-	bool solved;
-	bool infeasible;
+	bool solved = false;
+	bool infeasible = false;
 
 public:
-	LinearProgram(unsigned);
+	LinearProgram(size_t);
 
 	Row add_row();
-	Row operator[](unsigned);
-	Row get_object_row();
+	Row operator[](size_t);
+	Row get_objective_row();
+	float get_variable(size_t);
 	bool solve();
-	float get_variable(unsigned);
 private:
-	unsigned find_minimal_ratio(unsigned);
-	void make_basic_column(unsigned, unsigned);
+	void prepare_columns();
+	void add_artificial_variables();
+	void remove_artificial_variables();
+	size_t find_minimal_ratio(size_t);
+	void make_basic_column(size_t, size_t);
 	bool pivot();
 };
 
@@ -78,19 +85,6 @@ Layout::Pointers Layout::pointers[2] =
 } };
 
 
-Layout::Layout():
-	container(0),
-	margin(8),
-	row_spacing(5),
-	col_spacing(4)
-{ }
-
-Layout::~Layout()
-{
-	for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
-		delete *i;
-}
-
 void Layout::set_container(Container &c)
 {
 	if(container)
@@ -106,95 +100,174 @@ void Layout::set_margin(const Sides &m)
 		update();
 }
 
+void Layout::set_spacing(unsigned s)
+{
+	row_spacing = s;
+	col_spacing = s;
+	if(container)
+		update();
+}
+
+void Layout::set_row_spacing(unsigned s)
+{
+	row_spacing = s;
+	if(container)
+		update();
+}
+
+void Layout::set_column_spacing(unsigned s)
+{
+	col_spacing = s;
+	if(container)
+		update();
+}
+
+void Layout::push_arrangement(Arrangement &arr)
+{
+	arrangement_stack.push_back(&arr);
+}
+
+Arrangement *Layout::get_arrangement() const
+{
+	if(arrangement_stack.empty())
+		return nullptr;
+	else
+		return arrangement_stack.back();
+}
+
+void Layout::pop_arrangement(Arrangement &arr)
+{
+	auto begin = find(arrangement_stack, &arr);
+	if(begin==arrangement_stack.end())
+		return;
+
+	while(1)
+	{
+		Arrangement *top = arrangement_stack.back();
+		arrangement_stack.pop_back();
+		if(!arrangement_stack.empty())
+			arrangement_stack.back()->arrange(*top);
+		if(top==&arr)
+			break;
+	}
+}
+
 void Layout::add_widget(Widget &wdg)
 {
 	if(!container)
 		throw logic_error("!container");
 
-	Slot *slot = create_slot(wdg);
-	for(list<Constraint>::iterator i=slot->constraints.begin(); i!=slot->constraints.end(); ++i)
-		i->target.constraints.push_back(Constraint(complement(i->type), *slot));
-	slot->index = slots.size();
-	slots.push_back(slot);
+	slots.emplace_back(make_unique<Slot>(*this, wdg));
+	update_slot_indices();
+	if(!arrangement_stack.empty())
+		arrangement_stack.back()->arrange(wdg);
 	if(container)
 		update();
 }
 
 void Layout::remove_widget(Widget &wdg)
 {
-	for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
-		if(&(*i)->widget==&wdg)
-		{
-			for(list<Slot *>::iterator j=slots.begin(); j!=slots.end(); ++j)
-				if(j!=i)
-				{
-					for(list<Constraint>::iterator k=(*j)->constraints.begin(); k!=(*j)->constraints.end(); )
-					{
-						if(&k->target==*i)
-							(*j)->constraints.erase(k++);
-						else
-							++k;
-					}
-				}
+	auto i = find_if(slots, [&wdg](const unique_ptr<Slot> &s){ return &s->widget==&wdg; });
+	if(i==slots.end())
+		return;
 
-			delete *i;
-			slots.erase(i);
+	for(const unique_ptr<Slot> &s: slots)
+		if(s!=*i)
+		{
+			for(auto k=s->constraints.begin(); k!=s->constraints.end(); )
+			{
+				if(k->target==i->get())
+					k = s->constraints.erase(k);
+				else
+					++k;
+			}
+		}
 
-			unsigned n = 0;
-			for(i=slots.begin(); i!=slots.end(); ++i, ++n)
-				(*i)->index = n;
+	slots.erase(i);
 
-			update();
-			return;
-		}
+	update_slot_indices();
+	update();
 }
 
-Layout::Slot *Layout::create_slot(Widget &wdg)
+void Layout::update_slot_indices()
 {
-	return new Slot(*this, wdg);
+	n_active_slots = 0;
+	size_t n_floating = 0;
+	for(const unique_ptr<Slot> &s: slots)
+	{
+		if(s->widget.is_visible() || s->ghost)
+		{
+			s->index = n_active_slots++;
+			if(s->floating)
+				++n_floating;
+		}
+		else
+			s->index = -1;
+	}
+
+	n_slack_vars[0] = n_floating*2;
+	n_slack_vars[1] = n_floating*2;
+	for(const unique_ptr<Slot> &s: slots)
+		if(s->index>=0)
+		{
+			if(!s->floating)
+			{
+				for(unsigned j=0; j<2; ++j)
+					if((s.get()->*(pointers[j].packing)).gravity==0)
+						n_slack_vars[j] += 2;
+			}
+
+			for(const Constraint &c: s->constraints)
+				if(c.target->index>s->index && (c.type&SLACK))
+					++n_slack_vars[c.type&1];
+		}
 }
 
 Layout::Slot &Layout::get_slot_for_widget(Widget &wdg)
 {
-	for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
-		if(&(*i)->widget==&wdg)
-			return **i;
+	auto i = find_if(slots, [&wdg](const unique_ptr<Slot> &s){ return &s->widget==&wdg; });
+	if(i==slots.end())
+		throw hierarchy_error("widget not in layout");
 
-	throw hierarchy_error("widget not in layout");
+	return **i;
 }
 
 Layout::ConstraintType Layout::complement(ConstraintType type)
 {
-	if(type==RIGHT_OF)
-		return LEFT_OF;
-	else if(type==LEFT_OF)
-		return RIGHT_OF;
-	else if(type==ABOVE)
-		return BELOW;
-	else if(type==BELOW)
-		return ABOVE;
-	else
-		return type;
+	return static_cast<ConstraintType>((type&~(SELF_MASK|TARGET_MASK)) | ((type&SELF_MASK)<<2) | ((type&TARGET_MASK)>>2));
 }
 
-void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
+void Layout::create_constraint(Widget &src, ConstraintType type, Widget &tgt, int sp)
 {
 	if(&src==&tgt)
-		throw invalid_argument("&src==&tgt");
+		throw invalid_argument("Layout::create_constraint");
 
 	Slot &src_slot = get_slot_for_widget(src);
 	Slot &tgt_slot = get_slot_for_widget(tgt);
 
-	for(list<Constraint>::iterator i=src_slot.constraints.begin(); i!=src_slot.constraints.end(); ++i)
-		if(i->type==type && &i->target==&tgt_slot)
+	for(const Constraint &c: src_slot.constraints)
+		if(c.type==type && c.target==&tgt_slot)
 			return;
 
 	src_slot.constraints.push_back(Constraint(type, tgt_slot));
+	src_slot.constraints.back().spacing = sp;
 	tgt_slot.constraints.push_back(Constraint(complement(type), src_slot));
+	tgt_slot.constraints.back().spacing = sp;
 
+	update_slot_indices();
 	update();
 }
 
+void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt)
+{
+	create_constraint(src, type, tgt, -1);
+}
+
+void Layout::add_constraint(Widget &src, ConstraintType type, Widget &tgt, unsigned spacing)
+{
+	create_constraint(src, type, tgt, spacing);
+}
+
 void Layout::set_gravity(Widget &wdg, int h, int v)
 {
 	Slot &slot = get_slot_for_widget(wdg);
@@ -202,6 +275,7 @@ void Layout::set_gravity(Widget &wdg, int h, int v)
 	slot.horiz_pack.gravity = h;
 	slot.vert_pack.gravity = v;
 
+	update_slot_indices();
 	update();
 }
 
@@ -215,118 +289,337 @@ void Layout::set_expand(Widget &wdg, bool h, bool v)
 	update();
 }
 
-void Layout::update()
+void Layout::set_ghost(Widget &wdg, bool g)
 {
-	for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
+	Slot &slot = get_slot_for_widget(wdg);
+
+	slot.ghost = g;
+
+	if(!wdg.is_visible())
 	{
-		(*i)->widget.autosize();
-		(*i)->geom = (*i)->widget.get_geometry();
+		update_slot_indices();
+		update();
 	}
+}
+
+void Layout::set_floating(Widget &wdg, bool f)
+{
+	Slot &slot = get_slot_for_widget(wdg);
+
+	slot.floating = f;
+
+	update_slot_indices();
+	update();
+}
+
+void Layout::update()
+{
+	solve_constraints(HORIZONTAL, UPDATE);
+	solve_constraints(VERTICAL, UPDATE);
 
-	solve_constraints(HORIZONTAL);
-	solve_constraints(VERTICAL);
+	for(const unique_ptr<Slot> &s: slots)
+		s->widget.set_geometry(s->geom);
+}
 
-	for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
-		(*i)->widget.set_geometry((*i)->geom);
+void Layout::autosize(Geometry &geom)
+{
+	solve_constraints(HORIZONTAL, AUTOSIZE);
+	solve_constraints(VERTICAL, AUTOSIZE);
 
+	geom.w = max(geom.w, autosize_geom.w);
+	geom.h = max(geom.h, autosize_geom.h);
 }
 
-void Layout::solve_constraints(int dir)
+void Layout::solve_constraints(int dir, SolveMode mode)
 {
 	Pointers &ptrs = pointers[dir&VERTICAL];
 
-	LinearProgram linprog(slots.size()*5+1);
-	float weight = slots.size();
-	for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
+	const Geometry &geom = container->get_geometry();
+	if(mode==UPDATE && geom.*(ptrs.dim)<margin.*(ptrs.low_margin)+margin.*(ptrs.high_margin))
+		return;
+
+	/* 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(n_active_slots*5+n_slack_vars[dir]+1);
+	float weight = slots.size()+1;
+	size_t k = n_active_slots*5;
+	for(const unique_ptr<Slot> &s: slots)
 	{
-		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);
+		if(s->index<0)
+			continue;
 
+		LinearProgram::Row objective = linprog.get_objective_row();
+		if(mode==AUTOSIZE)
 		{
+			objective[s->index*5] = -1;
+			objective[s->index*5+1] = -1;
+		}
+		else
+		{
+			if(!s->floating)
+				objective[s->index*5] = (s.get()->*(ptrs.packing)).gravity/weight;
+			objective[s->index*5+1] = ((s.get()->*(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;
+			row[s->index*5] = 1;
+			row[s->index*5+2] = -1;
 			row.back() = margin.*(ptrs.low_margin);
 		}
 
+		if(mode==UPDATE)
 		{
+			// 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;
-			row[(*i)->index*5+3] = 1;
-			row.back() = container->get_geometry().*(ptrs.dim)-margin.*(ptrs.high_margin);
+			row[s->index*5] = 1;
+			row[s->index*5+1] = 1;
+			row[s->index*5+3] = 1;
+			row.back() = geom.*(ptrs.dim)-margin.*(ptrs.high_margin);
 		}
 
+		if(s->floating || (s.get()->*(ptrs.packing)).gravity==0)
 		{
+			/* Try to keep the widget as close to a target position as possible.
+			Since linear programs can't express absolute values directly, use two
+			opposing slack variables that are optimized for a low value. */
+			float a = (s.get()->*(ptrs.packing)).gravity*0.5+0.5;
 			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[s->index*5] = 1;
+			row[s->index*5+1] = a;
+			row[k] = 1;
+			row[k+1] = -1;
+			if(s->floating)
+			{
+				const Geometry &cgeom = s->widget.get_geometry();
+				row.back() = cgeom.*(ptrs.pos)+cgeom.*(ptrs.dim)*a;
+			}
+			else
+				row.back() = geom.*(ptrs.dim)/2;
+			objective[k] = -1;
+			objective[k+1] = -1;
+			k += 2;
 		}
 
-		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)
+			/* Don't allow the widget's dimension to get below that determined
+			by autosizing. */
+			LinearProgram::Row row = linprog.add_row();
+			row[s->index*5+1] = 1;
+			row[s->index*5+4] = -1;
+			row.back() = s->autosize_geom.*(ptrs.dim);
+		}
+
+		/* Add rows for user-defined constraints.  Constraints are always added
+		in pairs, so it's only necessary to create a row for one half. */
+		for(const Constraint &c: s->constraints)
+			if(c.target->index>s->index && (c.type&1)==dir)
 			{
 				LinearProgram::Row row = linprog.add_row();
-				if(j->type&SELF_POS)
-					row[(*i)->index*5] = 1;
-				if(j->type&SELF_DIM)
-					row[(*i)->index*5+1] = 1;
-				if(j->type&TARGET_POS)
-					row[j->target.index*5] = -1;
-				if(j->type&TARGET_DIM)
-					row[j->target.index*5+1] = -1;
-				if(j->type&SPACING)
-					row.back() = this->*(ptrs.spacing);
+				float polarity = ((c.type&SELF_DIM) ? -1 : 1);
+				float dim_weight = ((c.type&HALF_DIM) ? 0.5f : 1);
+				if(c.type&SELF_POS)
+					row[s->index*5] = polarity;
+				if(c.type&SELF_DIM)
+					row[s->index*5+1] = polarity*dim_weight;
+				if(c.type&TARGET_POS)
+					row[c.target->index*5] = -polarity;
+				if(c.type&TARGET_DIM)
+					row[c.target->index*5+1] = -polarity*dim_weight;
+				if(c.type&SPACING)
+					row.back() = (c.spacing>=0 ? c.spacing : this->*(ptrs.spacing));
+				if(c.type&SLACK)
+					row[k++] = -1;
 			}
-		}
 	}
 
 	if(!linprog.solve())
 		return;
 
-	for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
+	if(mode==AUTOSIZE)
 	{
-		(*i)->geom.*(ptrs.pos) = linprog.get_variable((*i)->index*5);
-		(*i)->geom.*(ptrs.dim) = linprog.get_variable((*i)->index*5+1);
+		autosize_geom.*(ptrs.dim) = 0;
+		for(const unique_ptr<Slot> &s: slots)
+			if(s->index>=0)
+			{
+				int high_edge = linprog.get_variable(s->index*5)+linprog.get_variable(s->index*5+1);
+				autosize_geom.*(ptrs.dim) = max(autosize_geom.*(ptrs.dim), high_edge+margin.*(ptrs.high_margin));
+			}
+	}
+	else
+	{
+		for(const unique_ptr<Slot> &s: slots)
+			if(s->index>=0)
+			{
+				s->geom.*(ptrs.pos) = linprog.get_variable(s->index*5);
+				s->geom.*(ptrs.dim) = linprog.get_variable(s->index*5+1);
+			}
 	}
 }
 
 
 Layout::Constraint::Constraint(ConstraintType t, Slot &s):
 	type(t),
-	target(s)
-{ }
-
-
-Layout::Packing::Packing():
-	gravity(-1),
-	expand(false)
+	target(&s)
 { }
 
 
 Layout::Slot::Slot(Layout &l, Widget &w):
 	layout(l),
-	index(0),
 	widget(w)
 {
 	vert_pack.gravity = 1;
 	widget.signal_autosize_changed.connect(sigc::mem_fun(this, &Slot::autosize_changed));
+	widget.signal_visibility_changed.connect(sigc::mem_fun(this, &Slot::visibility_changed));
+	widget.autosize(autosize_geom);
 }
 
 void Layout::Slot::autosize_changed()
 {
-	layout.update();
+	widget.autosize(autosize_geom);
+
+	if(!widget.is_visible() && !ghost)
+		return;
+
+	// Only trigger an update if the widget won't fit in its current area.
+	if(autosize_geom.w>geom.w || autosize_geom.h>geom.h)
+	{
+		layout.container->signal_autosize_changed.emit();
+		layout.update();
+	}
+}
+
+void Layout::Slot::visibility_changed(bool v)
+{
+	layout.update_slot_indices();
+	if(v || ghost)
+	{
+		layout.container->signal_autosize_changed.emit();
+		layout.update();
+	}
 }
 
 
-Layout::LinearProgram::LinearProgram(unsigned s):
+Layout::Loader::Loader(Layout &l, const WidgetMap &wm):
+	DataFile::ObjectLoader<Layout>(l),
+	wdg_map(wm)
+{
+	add("column_spacing", &Loader::column_spacing);
+	add("margin",         &Loader::margin);
+	add("row_spacing",    &Loader::row_spacing);
+	add("spacing",        &Loader::spacing);
+	add("widget",         &Loader::widget);
+}
+
+void Layout::Loader::column_spacing(unsigned s)
+{
+	obj.set_column_spacing(s);
+}
+
+void Layout::Loader::margin()
+{
+	Sides sides;
+	load_sub(sides);
+	obj.set_margin(sides);
+}
+
+void Layout::Loader::spacing(unsigned s)
+{
+	obj.set_spacing(s);
+}
+
+void Layout::Loader::row_spacing(unsigned s)
+{
+	obj.set_row_spacing(s);
+}
+
+void Layout::Loader::widget(const string &n)
+{
+	Widget &wdg = *get_item(wdg_map, n);
+	WidgetLoader ldr(obj, wdg, wdg_map);
+	load_sub_with(ldr);
+}
+
+
+Layout::WidgetLoader::WidgetLoader(Layout &l, Widget &w, const Layout::Loader::WidgetMap &wm):
+	layout(l),
+	widget(w),
+	wdg_map(wm)
+{
+	add("constraint", &WidgetLoader::constraint);
+	add("expand",     &WidgetLoader::expand);
+	add("ghost",      &WidgetLoader::ghost);
+	add("gravity",    &WidgetLoader::gravity);
+}
+
+void Layout::WidgetLoader::constraint(ConstraintType type, const string &n)
+{
+	Widget &target = *get_item(wdg_map, n);
+	layout.add_constraint(widget, type, target);
+}
+
+void Layout::WidgetLoader::expand(bool h, bool v)
+{
+	layout.set_expand(widget, h, v);
+}
+
+void Layout::WidgetLoader::ghost(bool g)
+{
+	layout.set_ghost(widget, g);
+}
+
+void Layout::WidgetLoader::gravity(int h, int v)
+{
+	layout.set_gravity(widget, h, v);
+}
+
+
+void operator>>(const LexicalConverter &conv, Layout::ConstraintType &ctype)
+{
+	const string &str = conv.get();
+	if(str=="ABOVE")
+		ctype = Layout::ABOVE;
+	else if(str=="BELOW")
+		ctype = Layout::BELOW;
+	else if(str=="RIGHT_OF")
+		ctype = Layout::RIGHT_OF;
+	else if(str=="LEFT_OF")
+		ctype = Layout::LEFT_OF;
+	else if(str=="FAR_ABOVE")
+		ctype = Layout::FAR_ABOVE;
+	else if(str=="FAR_BELOW")
+		ctype = Layout::FAR_BELOW;
+	else if(str=="FAR_RIGHT_OF")
+		ctype = Layout::FAR_RIGHT_OF;
+	else if(str=="FAR_LEFT_OF")
+		ctype = Layout::FAR_LEFT_OF;
+	else if(str=="ALIGN_TOP")
+		ctype = Layout::ALIGN_TOP;
+	else if(str=="ALIGN_VCENTER")
+		ctype = Layout::ALIGN_VCENTER;
+	else if(str=="ALIGN_BOTTOM")
+		ctype = Layout::ALIGN_BOTTOM;
+	else if(str=="ALIGN_RIGHT")
+		ctype = Layout::ALIGN_RIGHT;
+	else if(str=="ALIGN_HCENTER")
+		ctype = Layout::ALIGN_HCENTER;
+	else if(str=="ALIGN_LEFT")
+		ctype = Layout::ALIGN_LEFT;
+	else if(str=="COPY_WIDTH")
+		ctype = Layout::COPY_WIDTH;
+	else if(str=="COPY_HEIGHT")
+		ctype = Layout::COPY_HEIGHT;
+	else
+		throw lexical_error(format("conversion of '%s' to ConstraintType", str));
+}
+
+
+Layout::LinearProgram::LinearProgram(size_t s):
 	n_columns(s),
-	n_rows(1),
-	columns(n_columns),
-	solved(false),
-	infeasible(false)
+	columns(n_columns)
 { }
 
 Layout::LinearProgram::Row Layout::LinearProgram::add_row()
@@ -334,7 +627,7 @@ Layout::LinearProgram::Row Layout::LinearProgram::add_row()
 	return Row(*this, n_rows++);
 }
 
-Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
+Layout::LinearProgram::Row Layout::LinearProgram::operator[](size_t r)
 {
 	if(r>=n_rows)
 		throw out_of_range("LinearProgram::operator[]");
@@ -342,20 +635,22 @@ Layout::LinearProgram::Row Layout::LinearProgram::operator[](unsigned r)
 	return Row(*this, r);
 }
 
-Layout::LinearProgram::Row Layout::LinearProgram::get_object_row()
+Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
 {
 	return Row(*this, 0);
 }
 
-float Layout::LinearProgram::get_variable(unsigned i)
+float Layout::LinearProgram::get_variable(size_t i)
 {
 	if(!solved || infeasible)
 		throw logic_error("not solved");
 	if(i+1>=n_columns)
 		throw out_of_range("LinearProgram::get_variable");
 
-	unsigned r = columns[i].basic;
-	return columns.back().values[r];
+	if(size_t r = columns[i].basic)
+		return columns.back().values[r];
+	else
+		return 0;
 }
 
 bool Layout::LinearProgram::solve()
@@ -363,45 +658,29 @@ bool Layout::LinearProgram::solve()
 	if(solved || infeasible)
 		return !infeasible;
 
-	// Force all columns fully into existence and relocate objective row to bottom
-	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;
-	}
+	/* 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<n_rows; ++i)
-	{
-		Column &column = columns[n_columns+i-2];
-		column.basic = i;
-	}
+	prepare_columns();
+
+	add_artificial_variables();
 
-	// 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
-	columns.erase(columns.begin()+(n_columns-1), columns.end()-1);
-	for(vector<Column>::iterator i=columns.begin(); i!=columns.end(); ++i)
-		if(!i->basic)
-		{
-			i->values.front() = i->values.back();
-			i->values.pop_back();
-		}
+	remove_artificial_variables();
 
+	// Solve the phase 2 problem.  We already know it to be feasible.
 	while(pivot()) ;
 
 	solved = true;
@@ -409,13 +688,124 @@ bool Layout::LinearProgram::solve()
 	return true;
 }
 
-unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
+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> obj_coeff(n_rows, 0.0f);
+	vector<float> row_coeff(n_rows, 1.0f);
+	const vector<float> &constants = columns.back().values;
+	for(Column &c: columns)
+		if(c.values.size()>=2 && c.values.back()!=0.0f && (constants.size()<c.values.size() || c.values.back()*constants[c.values.size()-1]>=0.0f) && obj_coeff[c.values.size()-1]==0.0f)
+		{
+			bool basic = true;
+			for(size_t j=1; (basic && j+1<c.values.size()); ++j)
+				basic = (c.values[j]==0.0f);
+			if(basic)
+			{
+				c.basic = c.values.size()-1;
+				row_coeff[c.basic] = 1.0f/c.values.back();
+				obj_coeff[c.basic] = -c.values.front();
+				c.values.clear();
+			}
+		}
+
+	// Price out the newly-created basic variables.
+	for(Column &c: columns)
+		if(!c.values.empty())
+		{
+			for(size_t j=0; j<c.values.size(); ++j)
+			{
+				c.values[j] *= row_coeff[j];
+				c.values.front() += obj_coeff[j]*c.values[j];
+			}
+		}
+}
+
+void Layout::LinearProgram::add_artificial_variables()
+{
+	vector<size_t> artificial_rows(n_rows-1);
+	for(size_t i=0; i<artificial_rows.size(); ++i)
+		artificial_rows[i] = i+1;
+
+	for(const Column &c: columns)
+		if(c.basic)
+			artificial_rows[c.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(Column &c: columns)
+		if(!c.basic)
+		{
+			float objective = 0.0f;
+			if(!c.values.empty())
+			{
+				objective = c.values.front();
+				c.values.front() = 0.0f;
+				for(size_t r: artificial_rows)
+					if(r<c.values.size())
+						c.values.front() += c.values[r];
+			}
+			c.values.resize(n_rows+1, 0.0f);
+			c.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(size_t 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(size_t i=n_columns-1; i+1<columns.size(); ++i)
+		if(columns[i].basic && columns.back().values[columns[i].basic]==0.0f)
+		{
+			for(size_t 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);
+	for(Column &c: columns)
+		if(!c.basic)
+		{
+			c.values.front() = c.values.back();
+			c.values.pop_back();
+		}
+}
+
+size_t Layout::LinearProgram::find_minimal_ratio(size_t 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)
+	size_t row = 0;
+	for(size_t i=1; i<n_rows; ++i)
 		if(columns[c].values[i]>0)
 		{
 			float ratio = columns.back().values[i]/columns[c].values[i];
@@ -425,13 +815,15 @@ unsigned Layout::LinearProgram::find_minimal_ratio(unsigned c)
 				row = i;
 			}
 		}
-	
+
 	return row;
 }
 
-void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
+void Layout::LinearProgram::make_basic_column(size_t c, size_t r)
 {
-	for(unsigned i=0; i<columns.size(); ++i)
+	/* Perform row transfer operations to make the pivot column basic,
+	containing a 1 on the pivot row. */
+	for(size_t i=0; i<columns.size(); ++i)
 		if(i!=c && (columns[i].basic==r || (!columns[i].basic && columns[i].values[r])))
 		{
 			if(columns[i].basic)
@@ -442,14 +834,11 @@ void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 			}
 
 			float scale = columns[i].values[r]/columns[c].values[r];
-			
-			for(unsigned j=0; j<columns[i].values.size(); ++j)
-			{
-				if(j==r)
-					columns[i].values[j] = scale;
-				else
+
+			columns[i].values[r] = scale;
+			for(size_t j=0; j<columns[i].values.size(); ++j)
+				if(j!=r)
 					columns[i].values[j] -= scale*columns[c].values[j];
-			}
 		}
 
 	columns[c].basic = r;
@@ -458,9 +847,12 @@ void Layout::LinearProgram::make_basic_column(unsigned c, unsigned r)
 
 bool Layout::LinearProgram::pivot()
 {
-	for(unsigned i=0; i+1<columns.size(); ++i)
+	/* 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(size_t i=0; i+1<columns.size(); ++i)
 		if(!columns[i].basic && columns[i].values.front()>0)
-			if(unsigned row = find_minimal_ratio(i))
+			if(size_t row = find_minimal_ratio(i))
 			{
 				make_basic_column(i, row);
 				return true;
@@ -470,12 +862,12 @@ bool Layout::LinearProgram::pivot()
 }
 
 
-Layout::LinearProgram::Row::Row(LinearProgram &lp, unsigned i):
+Layout::LinearProgram::Row::Row(LinearProgram &lp, size_t i):
 	linprog(lp),
 	index(i)
 { }
 
-float &Layout::LinearProgram::Row::operator[](unsigned c)
+float &Layout::LinearProgram::Row::operator[](size_t c)
 {
 	if(c>=linprog.n_columns)
 		throw out_of_range("Row::operator[]");