libs/cassowary/ClTableau.cc

   1 // $Id$
   2 //
   3 // Cassowary Incremental Constraint Solver
   4 // Original Smalltalk Implementation by Alan Borning
   5 // This C++ Implementation by Greg J. Badros, <gjb@cs.washington.edu>
   6 // http://www.cs.washington.edu/homes/gjb
   7 // (C) 1998, 1999 Greg J. Badros and Alan Borning
   8 // See ../LICENSE for legal details regarding this software
   9 //
  10 // ClTableau.cc
  11
  12 using namespace std;
  13
  14 #include <cassowary/ClTableau.h>
  15 #include <cassowary/debug.h>
  16
  17 #ifdef HAVE_CONFIG_H
  18 #include <config.h>
  19 #define CONFIG_H_INCLUDED
  20 #endif
  21
  22
  23 // delete the linear expressions
  24 // let ClSimplexSolver worry about deleting the variables
  25 ClTableau::~ClTableau()
  26 {
  27   ClTableauRowsMap::iterator it = _rows.begin();
  28   for (; it != _rows.end(); ++it)
  29     {
  30     // free the ClLinearExpression that we new-ed
  31 #ifdef CL_TRACE
  32     cerr << "Deleting row  delete@ " << ((*it).second) << endl;
  33 #endif
  34     delete (*it).second;
  35     }
  36 }
  37
  38 #ifndef CL_NO_IO
  39 // Some extra debugging info
  40 ostream &
  41 ClTableau::PrintInternalInfo(ostream &xo) const
  42 {
  43   xo << "ncns:" << _rows.size() -1
  44      << "; cols:" << _columns.size()
  45      << "; infrows:" << _infeasibleRows.size()
  46      << "; ebvars:" << _externalRows.size()
  47      << "; epvars:" << _externalParametricVars.size();
  48   return xo;
  49 }
  50
  51
  52 ostream &
  53 ClTableau::printExternalVariablesTo(ostream &xo) const
  54 {
  55   xo << "Parametric: ";
  56   ClVarSet::iterator itParVars = _externalParametricVars.begin();
  57   for ( ; itParVars != _externalParametricVars.end(); ++itParVars ) {
  58     ClVariable v = *itParVars;
  59     xo << v << " ";
  60   }
  61   xo << "\nBasic: ";
  62   ClVarSet::iterator itRowVars = _externalRows.begin();
  63   for ( ; itRowVars != _externalRows.end() ; ++itRowVars ) {
  64     ClVariable v = *itRowVars;
  65     xo << v << " ";
  66   }
  67   return xo << endl;
  68 }
  69
  70 #endif
  71
  72
  73 // Add v, update column cross indices
  74 // v becomes a basic variable
  75 // expr is now owned by ClTableau class,
  76 // and ClTableauis responsible for deleting it
  77 // (also, expr better be allocated on the heap!)
  78 void
  79 ClTableau::addRow(ClVariable var, const ClLinearExpression &expr)
  80 {
  81 #ifdef CL_TRACE
  82   Tracer TRACER(__FUNCTION__);
  83   cerr << "(" << var << ", " << expr << ")" << endl;
  84 #endif
  85   _rows[var] = const_cast<ClLinearExpression *>(&expr);
  86   ClVarToNumberMap::const_iterator it = expr.Terms().begin();
  87   // for each variable in expr, Add var to the set of rows which have that variable
  88   // in their Expression
  89   for (; it != expr.Terms().end(); ++it)
  90     {
  91     ClVariable v = (*it).first;
  92     _columns[v].insert(var);
  93     if (v.IsExternal() && !FIsBasicVar(v))
  94       {
  95       _externalParametricVars.insert(v);
  96       }
  97     }
  98   if (var.IsExternal())
  99     {
 100     _externalRows.insert(var);
 101     }
 102 #ifdef CL_TRACE
 103   cerr << *this << endl;
 104 #endif
 105 }
 106
 107 // Remove var from the tableau -- remove the column cross indices for var
 108 // and remove var from every Expression in rows in which v occurs
 109 // Remove the parametric variable var, updating the appropriate column and row entries.
 110 // (Renamed from Smalltalk implementation's `removeParametricVar')
 111 ClVariable
 112 ClTableau::RemoveColumn(ClVariable var)
 113 {
 114 #ifdef CL_TRACE
 115   Tracer TRACER(__FUNCTION__);
 116   cerr << "(" << var << ")" << endl;
 117 #endif
 118   ClTableauColumnsMap::iterator it_var = _columns.find(var);
 119   if (it_var == _columns.end())
 120     return var;  // nothing to do
 121
 122   ClVarSet &varset = (*it_var).second;
 123   // remove the rows with the variables in varset
 124   ClVarSet::iterator it = varset.begin();
 125   for (; it != varset.end(); ++it)
 126     {
 127     ClVariable v = (*it);
 128     ClVarToNumberMap &Terms = _rows[v]->Terms();
 129     Terms.erase(Terms.find(var));
 130     }
 131   if (var.IsExternal())
 132     {
 133     _externalRows.erase(var);
 134     _externalParametricVars.erase(var);
 135     }
 136   _columns.erase(it_var);
 137   return var;
 138 }
 139
 140 // Remove the basic variable v from the tableau row v=expr
 141 // Then update column cross indices
 142 ClLinearExpression *
 143 ClTableau::RemoveRow(ClVariable var)
 144 {
 145 #ifdef CL_TRACE
 146   Tracer TRACER(__FUNCTION__);
 147   cerr << "(" << var << ")" << endl;
 148 #endif
 149   ClTableauRowsMap::iterator it = _rows.find(var);
 150   assert(it != _rows.end());
 151   ClLinearExpression *pexpr = (*it).second;
 152   ClVarToNumberMap &Terms = pexpr->Terms();
 153   ClVarToNumberMap::iterator it_term = Terms.begin();
 154   for (; it_term != Terms.end(); ++it_term)
 155     {
 156     ClVariable v = (*it_term).first;
 157     _columns[v].erase(var);
 158     if (_columns[v].size() == 0)
 159       {
 160       _columns.erase(v);
 161       _externalParametricVars.erase(v);
 162       }
 163     }
 164
 165   _infeasibleRows.erase(var);
 166
 167   if (var.IsExternal())
 168     {
 169     _externalRows.erase(var);
 170     _externalParametricVars.erase(var);
 171     }
 172
 173   _rows.erase(it);
 174 #ifdef CL_TRACE
 175   cerr << "- returning " << *pexpr << endl;
 176 #endif
 177   return pexpr;
 178 }
 179
 180 // Replace all occurrences of oldVar with expr, and update column cross indices
 181 // oldVar should now be a basic variable
 182 // Uses the Columns data structure and calls SubstituteOut on each
 183 // row that has oldVar in it
 184 // oldVar is leaving the basis, and becoming parametric
 185 void
 186 ClTableau::SubstituteOut(ClVariable oldVar, const ClLinearExpression &expr)
 187 {
 188 #ifdef CL_TRACE
 189   cerr << "* ClTableau::";
 190   Tracer TRACER(__FUNCTION__);
 191   cerr << "(" << oldVar << ", " << expr << ")" << endl;
 192   cerr << (*this) << endl;
 193 #endif
 194
 195   ClTableauColumnsMap::iterator it_oldVar = _columns.find(oldVar);
 196   if (it_oldVar == _columns.end())
 197     return;
 198
 199   ClVarSet &varset = (*it_oldVar).second;
 200   ClVarSet::iterator it = varset.begin();
 201   for (; it != varset.end(); ++it)
 202     {
 203     ClVariable v = (*it);
 204     ClLinearExpression *prow = _rows[v];
 205     prow->SubstituteOut(oldVar,expr,v,*this);
 206     if (v.IsRestricted() && prow->Constant() < 0.0)
 207       {
 208       _infeasibleRows.insert(v);
 209       }
 210     }
 211   _columns.erase(it_oldVar);
 212   if (oldVar.IsExternal())
 213     {
 214     if (_columns[oldVar].size() > 0)
 215       {
 216       _externalRows.insert(oldVar);
 217       }
 218     _externalParametricVars.erase(oldVar);
 219     }
 220 }
 221
 222
 223 #ifndef CL_NO_IO
 224
 225 ostream &
 226 PrintTo(ostream &xo, const ClVarSet & varset)
 227 {
 228   ClVarSet::const_iterator it = varset.begin();
 229   xo << "{ ";
 230   if (it != varset.end())
 231     {
 232     xo << *it;
 233     ++it;
 234     }
 235   for (; it != varset.end(); ++it)
 236     {
 237     xo << ", " << *it;
 238     }
 239   xo << " }";
 240   return xo;
 241 }
 242
 243 ostream &operator<<(ostream &xo, const ClVarSet & varset)
 244 { return PrintTo(xo,varset); }
 245
 246 ostream &
 247 PrintTo(ostream &xo, const ClTableauColumnsMap & varmap)
 248 {
 249   ClTableauColumnsMap::const_iterator it = varmap.begin();
 250   for (; it != varmap.end(); ++it)
 251     {
 252     xo << (*it).first << " -> " << (*it).second << endl;
 253     }
 254   return xo;
 255 }
 256
 257 ostream &operator<<(ostream &xo, const ClTableauColumnsMap & varmap)
 258 { return PrintTo(xo,varmap); }
 259
 260 ostream &
 261 PrintTo(ostream &xo, const ClTableauRowsMap & rows)
 262 {
 263   ClTableauRowsMap::const_iterator it = rows.begin();
 264   for (; it != rows.end(); ++it)
 265     {
 266     ClVariable v = it->first;
 267     const ClLinearExpression *pe = it->second;
 268     xo << v << " <-=-> ";
 269     if (pe) xo << *pe; else xo << "NilExpr";
 270     xo << endl;
 271     }
 272   return xo;
 273 }
 274
 275 ostream &operator<<(ostream &xo, const ClTableauRowsMap & rows)
 276 { return PrintTo(xo,rows); }
 277
 278 ostream &
 279 ClTableau::PrintOn(ostream &xo) const
 280 {
 281   xo << "Tableau:\n"
 282      << _rows << endl;
 283   xo << "Columns:\n"
 284      << _columns << endl;
 285   xo << "Infeasible rows: "
 286      << _infeasibleRows << endl;
 287   xo << "External basic variables: "
 288      << _externalRows << endl;
 289   xo << "External parametric variables: "
 290      << _externalParametricVars << endl;
 291   return xo;
 292 }
 293
 294 ostream &operator<<(ostream &xo, const ClTableau &clt)
 295 { return clt.PrintOn(xo); }
 296
 297 #endif