#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"
Column();
};
- unsigned n_columns;
- unsigned n_rows;
+ unsigned n_columns = 1;
+ unsigned n_rows = 1;
std::vector<Column> columns;
- bool solved;
- bool infeasible;
+ bool solved = false;
+ bool infeasible = false;
public:
LinearProgram(unsigned);
Row add_row();
Row operator[](unsigned);
- Row get_object_row();
- bool solve();
+ Row get_objective_row();
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();
} };
-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;
+ for(Slot *s: slots)
+ delete s;
}
void Layout::set_container(Container &c)
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.push_back(new 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](Slot *s){ return &s->widget==&wdg; });
+ if(i==slots.end())
+ return;
- delete *i;
- slots.erase(i);
+ for(Slot *s: slots)
+ if(s!=*i)
+ {
+ for(auto k=s->constraints.begin(); k!=s->constraints.end(); )
+ {
+ if(k->target==*i)
+ k = s->constraints.erase(k);
+ else
+ ++k;
+ }
+ }
- unsigned n = 0;
- for(i=slots.begin(); i!=slots.end(); ++i, ++n)
- (*i)->index = n;
+ delete *i;
+ 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;
+ unsigned n_floating = 0;
+ for(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 Slot *s: slots)
+ if(s->index>=0)
+ {
+ if(!s->floating)
+ {
+ for(unsigned j=0; j<2; ++j)
+ if((s->*(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 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);
slot.horiz_pack.gravity = h;
slot.vert_pack.gravity = v;
+ update_slot_indices();
update();
}
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();
+}
- solve_constraints(HORIZONTAL);
- solve_constraints(VERTICAL);
+void Layout::update()
+{
+ solve_constraints(HORIZONTAL, UPDATE);
+ solve_constraints(VERTICAL, UPDATE);
- for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
- (*i)->widget.set_geometry((*i)->geom);
+ for(const Slot *s: slots)
+ s->widget.set_geometry(s->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];
+ 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(slots.size()*5+1);
- float weight = slots.size();
- for(list<Slot *>::iterator i=slots.begin(); i!=slots.end(); ++i)
+ LinearProgram linprog(n_active_slots*5+n_slack_vars[dir]+1);
+ float weight = slots.size()+1;
+ unsigned k = n_active_slots*5;
+ for(const 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->*(ptrs.packing)).gravity/weight;
+ objective[s->index*5+1] = ((s->*(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->*(ptrs.packing)).gravity==0)
{
- /* Only allow the widget's dimension to increase. The geometry has
- previously been set to the smallest allowable size. */
+ /* 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->*(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;
}
- /* 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)
+ /* 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 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(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::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(unsigned s):
n_columns(s),
- n_rows(1),
- columns(n_columns),
- solved(false),
- infeasible(false)
+ columns(n_columns)
{ }
Layout::LinearProgram::Row Layout::LinearProgram::add_row()
return Row(*this, r);
}
-Layout::LinearProgram::Row Layout::LinearProgram::get_object_row()
+Layout::LinearProgram::Row Layout::LinearProgram::get_objective_row()
{
return Row(*this, 0);
}
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()
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()) ;
return false;
}
- /* 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)
- {
- 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()) ;
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> 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(unsigned 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(unsigned 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<unsigned> artificial_rows(n_rows-1);
+ for(unsigned 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(unsigned 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(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);
+ for(Column &c: columns)
+ if(!c.basic)
+ {
+ c.values.front() = c.values.back();
+ c.values.pop_back();
+ }
+}
+
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();
row = i;
}
}
-
+
return row;
}
}
float scale = columns[i].values[r]/columns[c].values[r];
-
+
+ columns[i].values[r] = scale;
for(unsigned j=0; j<columns[i].values.size(); ++j)
- {
- if(j==r)
- columns[i].values[j] = scale;
- else
+ if(j!=r)
columns[i].values[j] -= scale*columns[c].values[j];
- }
}
columns[c].basic = r;
projects / libs / gltk.git / blobdiff