libs/cassowary/cassowary/ClTableau.h

   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.h
  11
  12 #ifndef ClTableau_H
  13 #define ClTableau_H
  14
  15 #include <iostream>
  16
  17 #if defined(HAVE_CONFIG_H) && !defined(CONFIG_H_INCLUDED) && !defined(CONFIG_INLINE_H_INCLUDED)
  18 #include <cassowary/config-inline.h>
  19 #define CONFIG_INLINE_H_INCLUDED
  20 #endif
  21
  22 #include "Cassowary.h"
  23 #include "ClLinearExpression.h"
  24 #include "ClVariable.h"
  25 #include "ClTypedefs.h"
  26
  27
  28 #ifndef CL_NO_IO
  29 class ClTableau;
  30
  31 ostream &operator<<(ostream &xo, const ClTableau &clt);
  32
  33 ostream &operator<<(ostream &xo, const ClVarSet &varset);
  34
  35 ostream &operator<<(ostream &xo, const ClTableauColumnsMap &varmap);
  36
  37 ostream &operator<<(ostream &xo, const ClTableauRowsMap &rows);
  38
  39 ostream &operator<<(ostream &xo, const ClVarVector &varlist);
  40 #endif // CL_NO_IO
  41
  42 class ClTableau {
  43
  44  public:
  45   // No public constructor, since this does nothing but support
  46   // an ADT for the ClSimplexSolver
  47
  48   // Variable v has been removed from an Expression.  If the
  49   // Expression is in a tableau the corresponding basic variable is
  50   // subject (or if subject is nil then it's in the objective function).
  51   // Update the column cross-indices.
  52   void NoteRemovedVariable(ClVariable v, ClVariable subject)
  53     {
  54 #ifdef CL_TRACE
  55     Tracer TRACER(__FUNCTION__);
  56     std::cerr << "(" << v << ", " << subject << ")" << std::endl;
  57 #endif
  58     ClVarSet &column = _columns[v];
  59     ClVarSet::const_iterator it = column.find(subject);
  60     assert(it != column.end());
  61     column.erase(it);
  62 #ifdef CL_TRACE_VERBOSE
  63     std::cerr << "v = " << v << " and Columns[v].size() = "
  64          << column.size() << std::endl;
  65 #endif
  66     if (column.size() == 0)
  67       {
  68       _columns.erase(v);
  69       _externalRows.erase(v);
  70       _externalParametricVars.erase(v);
  71       }
  72     }
  73
  74   // v has been added to the linear Expression for subject
  75   // update column cross indices
  76   void NoteAddedVariable(ClVariable v, ClVariable subject)
  77     {
  78 #ifdef CL_TRACE
  79     Tracer TRACER(__FUNCTION__);
  80     std::cerr << "(" << v << ", " << subject << ")" << std::endl;
  81 #endif
  82     _columns[v].insert(subject);
  83     if (v.IsExternal() && !FIsBasicVar(v))
  84       {
  85       _externalParametricVars.insert(v);
  86       }
  87     }
  88
  89 #ifndef CL_NO_IO
  90   std::ostream &PrintOn(ostream &xo) const;
  91
  92   ostream &PrintInternalInfo(ostream &xo) const;
  93
  94   ostream &printExternalVariablesTo(ostream &xo) const;
  95
  96 #endif
  97
  98   // Check integrity of the tableau
  99   // not complete, yet, but a start, at least
 100   // Guard calls to AssertValid with CL_SOLVER_CHECK_INTEGRITY,
 101   // since this is expensive
 102   virtual void AssertValid() const {
 103 #ifndef NDEBUG
 104     // all external basic variables are in _externalRows
 105     // and all external parametric variables are in _externalParametricVars
 106     ClTableauRowsMap::const_iterator itRow = _rows.begin();
 107     for (; itRow != _rows.end(); ++itRow)
 108       {
 109       const ClVariable clv = (*itRow).first;
 110       if (clv.IsExternal())
 111         {
 112         if (_externalRows.find(clv) == _externalRows.end())
 113           {
 114 #ifndef CL_NO_IO
 115           std::cerr << "External basic variable " << clv
 116                << " is not in _externalRows" << std::endl;
 117 #endif
 118           }
 119         }
 120       const ClLinearExpression *pcle = RowExpression(clv);
 121       assert(pcle);
 122       ClVarToNumberMap::const_iterator it = pcle->Terms().begin();
 123       for (; it != pcle->Terms().end(); ++it)
 124         {
 125         ClVariable clv = (*it).first;
 126         if (clv.IsExternal())
 127           {
 128           if (_externalParametricVars.find(clv) == _externalParametricVars.end())
 129             {
 130 #ifndef CL_NO_IO
 131             std::cerr << "External parametric variable " << clv
 132                  << " is not in _externalParametricVars" << std::endl;
 133 #endif
 134             }
 135           }
 136         }
 137       }
 138 #endif /* !NDEBUG */
 139   }
 140
 141
 142  protected:
 143   // Constructor -- want to start with empty objects so not much to do
 144   ClTableau()
 145     { }
 146
 147   virtual ~ClTableau();
 148
 149   // Add v=expr to the tableau, update column cross indices
 150   // v becomes a basic variable
 151   // expr is now owned by ClTableau class,
 152   // and ClTableauis responsible for deleting it
 153   // (also, expr better be allocated on the heap!)
 154   void addRow(ClVariable v, const ClLinearExpression &expr);
 155
 156   // Remove v from the tableau -- remove the column cross indices for v
 157   // and remove v from every Expression in rows in which v occurs
 158   // returns a pointer to the variable (since we often want to delete
 159   // the variable)
 160   ClVariable RemoveColumn(ClVariable v);
 161
 162   // Remove the basic variable v from the tableau row v=expr
 163   // Then update column cross indices
 164   // Probably want to call delete on the ClLinearExpression * returned
 165   // unless you're adding that same Expression back into the
 166   // tableau
 167   ClLinearExpression *RemoveRow(ClVariable v);
 168
 169   // Replace all occurrences of oldVar with expr, and update column cross indices
 170   // oldVar should now be a basic variable
 171   void SubstituteOut(ClVariable oldVar, const ClLinearExpression &expr);
 172
 173   ClTableauColumnsMap Columns()
 174     { return _columns; }
 175
 176   ClTableauRowsMap Rows()
 177     { return _rows; }
 178
 179   // return true iff the variable subject is in the Columns keys
 180   bool ColumnsHasKey(ClVariable subject) const
 181     {
 182     ClTableauColumnsMap::const_iterator i = _columns.find(subject);
 183     return (i != _columns.end());
 184     }
 185
 186   const ClLinearExpression *RowExpression(ClVariable v) const
 187     {
 188     ClTableauRowsMap::const_iterator i = _rows.find(v);
 189     if (i != _rows.end())
 190       return (*i).second;
 191     else
 192       return 0;
 193     }
 194
 195   ClLinearExpression *RowExpression(ClVariable v)
 196     {
 197       const ClTableau *pthis = const_cast<const ClTableau *>(this);
 198       return const_cast<ClLinearExpression *>(pthis->RowExpression(v));
 199     }
 200
 201
 202   bool FIsBasicVar(ClVariable v)
 203     { return RowExpression(v) != 0; }
 204
 205   // private: FIXGJB: can I improve the encapsulation?
 206
 207   // _columns is a mapping from variables which occur in expressions to the
 208   // set of basic variables whose expressions contain them
 209   // i.e., it's a mapping from variables in expressions (a column) to the
 210   // set of rows that contain them
 211   ClTableauColumnsMap _columns;
 212
 213   // _rows maps basic variables to the expressions for that row in the tableau
 214   ClTableauRowsMap _rows;
 215
 216   // the collection of basic variables that have infeasible rows
 217   // (used when reoptimizing)
 218   ClVarSet _infeasibleRows;
 219
 220   // the set of rows where the basic variable is external
 221   // this was added to the C++ version to reduce time in SetExternalVariables()
 222   ClVarSet _externalRows;
 223
 224   // the set of external variables which are parametric
 225   // this was added to the C++ version to reduce time in SetExternalVariables()
 226   ClVarSet _externalParametricVars;
 227
 228 };
 229
 230 #endif