libs/cassowary/cassowary/ClLinearExpression.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 // ClLinearExpression.h
  11
  12 #ifndef ClLinearExpression_H
  13 #define ClLinearExpression_H
  14
  15 #if defined(HAVE_CONFIG_H) && !defined(CONFIG_H_INCLUDED) && !defined(CONFIG_INLINE_H_INCLUDED)
  16 #include <cassowary/config-inline.h>
  17 #define CONFIG_INLINE_H_INCLUDED
  18 #endif
  19
  20 #include "Cassowary.h"
  21 #include "debug.h"
  22 #include "ClVariable.h"
  23 #include "ClLinearExpression_fwd.h"
  24
  25 class ClSimplexSolver;
  26 class ClTableau;
  27 class ClSymbolicWeight;
  28
  29 ClLinearExpression &cleNil();
  30
  31 template <class T>
  32 class ClGenericLinearExpression  {
  33  public:
  34   typedef std::map<ClVariable,T> ClVarToCoeffMap;
  35
  36   // convert Number-s into ClLinearExpression-s
  37   ClGenericLinearExpression(T num = 0.0);
  38
  39   // Convert from ClVariable to a ClLinearExpression
  40   // this replaces ClVariable::asLinearExpression
  41   ClGenericLinearExpression(ClVariable clv, T value = 1.0, T constant = 0.0);
  42
  43   // copy ctr
  44   ClGenericLinearExpression(const ClGenericLinearExpression<T> &expr) :
  45     _constant(expr._constant),
  46     _terms(expr._terms)
  47     { }
  48
  49   virtual ~ClGenericLinearExpression();
  50
  51   // Return a new linear expression formed by multiplying self by x.
  52   // (Note that this result must be linear.)
  53   ClGenericLinearExpression<T> Times(Number x) const;
  54
  55   // Return a new linear expression formed by multiplying self by x.
  56   // (Note that this result must be linear.)
  57   ClGenericLinearExpression<T> Times(const ClGenericLinearExpression<T> &expr) const;
  58
  59   // Return a new linear expression formed by adding x to self.
  60   ClGenericLinearExpression<T> Plus(const ClGenericLinearExpression<T> &expr) const;
  61
  62   // Return a new linear expression formed by subtracting x from self.
  63   ClGenericLinearExpression<T> Minus(const ClGenericLinearExpression<T> &expr) const;
  64
  65   // Return a new linear expression formed by dividing self by x.
  66   // (Note that this result must be linear.)
  67   ClGenericLinearExpression<T> Divide(Number x) const;
  68
  69
  70
  71   // Return a new linear expression formed by multiplying self by x.
  72   // (Note that this result must be linear.)
  73   ClGenericLinearExpression<T> *P_times(Number x) const
  74     { return new ClGenericLinearExpression<T>(Times(x)); }
  75
  76   // Return a new linear expression formed by adding x to self.
  77   ClGenericLinearExpression<T> *P_plus(const ClGenericLinearExpression<T> &expr) const
  78     { return new ClGenericLinearExpression<T>(Plus(expr)); }
  79
  80   // Return a new linear expression formed by subtracting x from self.
  81   ClGenericLinearExpression<T> *P_minus(const ClGenericLinearExpression<T> &expr) const
  82     { return new ClGenericLinearExpression<T>(Minus(expr)); }
  83
  84   // Return a new linear expression formed by dividing self by x.
  85   // (Note that this result must be linear.)
  86   ClGenericLinearExpression<T> *P_divide(Number x) const
  87     { return new ClGenericLinearExpression<T>(Divide(x)); }
  88
  89   // Return a new linear expression formed by dividing self by x.
  90   // (Note that this result must be linear.)
  91   ClGenericLinearExpression<T> Divide(const ClGenericLinearExpression<T> &expr) const;
  92
  93   // Return a new linear expression (aNumber/this).  Since the result
  94   // must be linear, this is permissible only if 'this' is a constant.
  95   ClGenericLinearExpression<T> DivFrom(const ClGenericLinearExpression<T> &expr) const;
  96
  97   // Return a new linear expression (aNumber-this).
  98   ClGenericLinearExpression<T> SubtractFrom(const ClGenericLinearExpression<T> &expr) const
  99   { return expr.Minus(*this); }
 100
 101   // Add n*expr to this expression from another expression expr.
 102   ClGenericLinearExpression<T> &AddExpression(const ClGenericLinearExpression<T> &expr,
 103                                     Number n = 1.0);
 104
 105   // Add n*expr to this expression from another expression expr.
 106   // Notify the solver if a variable is added or deleted from this
 107   // expression.
 108   ClGenericLinearExpression<T> &AddExpression(const ClGenericLinearExpression<T> &expr, Number n,
 109                                     ClVariable subject,
 110                                     ClTableau &solver);
 111
 112   // Add a term c*v to this expression.  If the expression already
 113   // contains a term involving v, Add c to the existing coefficient.
 114   // If the new coefficient is approximately 0, delete v.
 115   ClGenericLinearExpression<T> &AddVariable(ClVariable v, T c = 1.0);
 116
 117   // Add a term c*v to this expression.  If the expression already
 118   // contains a term involving v, Add c to the existing coefficient.
 119   // If the new coefficient is approximately 0, delete v.
 120   ClGenericLinearExpression<T> &setVariable(ClVariable v, T c)
 121     {assert(c != 0.0);  _terms[v] = c; return *this; }
 122
 123   // Add a term c*v to this expression.  If the expression already
 124   // contains a term involving v, Add c to the existing coefficient.
 125   // If the new coefficient is approximately 0, delete v.  Notify the
 126   // solver if v appears or disappears from this expression.
 127   ClGenericLinearExpression<T> &AddVariable(ClVariable v, T c,
 128                                   ClVariable subject,
 129                                   ClTableau &solver);
 130
 131   // Return a pivotable variable in this expression.  (It is an error
 132   // if this expression is constant -- signal ExCLInternalError in
 133   // that case).  Return NULL if no pivotable variables
 134   ClVariable AnyPivotableVariable() const;
 135
 136   // Replace var with a symbolic expression expr that is equal to it.
 137   // If a variable has been added to this expression that wasn't there
 138   // before, or if a variable has been dropped from this expression
 139   // because it now has a coefficient of 0, inform the solver.
 140   // PRECONDITIONS:
 141   //   var occurs with a non-Zero coefficient in this expression.
 142   void SubstituteOut(ClVariable v,
 143                      const ClGenericLinearExpression<T> &expr,
 144                      ClVariable subject,
 145                      ClTableau &solver);
 146
 147   // This linear expression currently represents the equation
 148   // oldSubject=self.  Destructively modify it so that it represents
 149   // the equation NewSubject=self.
 150   //
 151   // Precondition: NewSubject currently has a nonzero coefficient in
 152   // this expression.
 153   //
 154   // NOTES
 155   //   Suppose this expression is c + a*NewSubject + a1*v1 + ... + an*vn.
 156   //
 157   //   Then the current equation is
 158   //       oldSubject = c + a*NewSubject + a1*v1 + ... + an*vn.
 159   //   The new equation will be
 160   //        NewSubject = -c/a + oldSubject/a - (a1/a)*v1 - ... - (an/a)*vn.
 161   //   Note that the term involving NewSubject has been dropped.
 162   void ChangeSubject(ClVariable old_subject,
 163                      ClVariable new_subject);
 164
 165   // This linear expression currently represents the equation self=0.  Destructively modify it so
 166   // that subject=self represents an equivalent equation.
 167   //
 168   // Precondition: subject must be one of the variables in this expression.
 169   // NOTES
 170   //   Suppose this expression is
 171   //     c + a*subject + a1*v1 + ... + an*vn
 172   //   representing
 173   //     c + a*subject + a1*v1 + ... + an*vn = 0
 174   // The modified expression will be
 175   //    subject = -c/a - (a1/a)*v1 - ... - (an/a)*vn
 176   //   representing
 177   //    subject = -c/a - (a1/a)*v1 - ... - (an/a)*vn
 178   //
 179   // Note that the term involving subject has been dropped.
 180   // Returns the reciprocal, so ChangeSubject can use it, too
 181   T NewSubject(ClVariable subject);
 182
 183   // Return the value of the linear expression
 184   // given the current assignments of values to contained variables
 185   T Evaluate() const;
 186
 187   // Return the coefficient corresponding to variable var, i.e.,
 188   // the 'ci' corresponding to the 'vi' that var is:
 189   //     v1*c1 + v2*c2 + .. + vn*cn + c
 190   T CoefficientFor(ClVariable var) const
 191     {
 192     typename ClVarToCoeffMap::const_iterator it = _terms.find(var);
 193     if (it != _terms.end())
 194       return (*it).second;
 195     return 0.0;
 196     }
 197
 198   T Constant() const
 199     { return _constant; }
 200
 201   void Set_constant(T c)
 202     { _constant = c; }
 203
 204   const ClVarToCoeffMap &Terms() const
 205     { return _terms; }
 206
 207   ClVarToCoeffMap &Terms()
 208     { return _terms; }
 209
 210   void IncrementConstant(T c)
 211     { _constant += c; }
 212
 213   bool IsConstant() const
 214     { return _terms.size() == 0; }
 215
 216 #ifndef CL_NO_IO
 217   virtual ostream &PrintOn(ostream &xo) const;
 218
 219   friend ostream &operator<<(ostream &xo,const ClGenericLinearExpression<T> &cle)
 220     { return cle.PrintOn(xo); }
 221 #endif
 222
 223   friend ClGenericLinearExpression<T> operator+(const ClGenericLinearExpression<T> &e1,
 224                                       const ClGenericLinearExpression<T> &e2)
 225     { return e1.Plus(e2); }
 226
 227   friend ClGenericLinearExpression<T> operator-(const ClGenericLinearExpression<T> &e1,
 228                                       const ClGenericLinearExpression<T> &e2)
 229     { return e1.Minus(e2); }
 230
 231   friend ClGenericLinearExpression<T> operator*(const ClGenericLinearExpression<T> &e1,
 232                                       const ClGenericLinearExpression<T> &e2)
 233     { return e1.Times(e2); }
 234
 235
 236   friend ClGenericLinearExpression<T> operator/(const ClGenericLinearExpression<T> &e1,
 237                                       const ClGenericLinearExpression<T> &e2)
 238     { return e1.Divide(e2); }
 239
 240   // FIXGJB -- this may be wrong -- should test underlying expression for equality
 241   friend bool operator==(const ClGenericLinearExpression<T> &e1,
 242                          const ClGenericLinearExpression<T> &e2)
 243     { return &e1 == &e2; }
 244
 245   /// Named versions of the operator functions for ease of
 246   /// wrapping, or expressing using prefix notation
 247
 248   friend ClGenericLinearExpression<T> Plus(const ClGenericLinearExpression<T> &e1,
 249                                  const ClGenericLinearExpression<T> &e2)
 250     { return e1.Plus(e2); }
 251
 252   friend ClGenericLinearExpression<T> Minus(const ClGenericLinearExpression<T> &e1,
 253                                   const ClGenericLinearExpression<T> &e2)
 254     { return e1.Minus(e2); }
 255
 256   friend ClGenericLinearExpression<T> Times(const ClGenericLinearExpression<T> &e1,
 257                                   const ClGenericLinearExpression<T> &e2)
 258     { return e1.Times(e2); }
 259
 260
 261   friend ClGenericLinearExpression<T> *Divide(const ClGenericLinearExpression<T> &e1,
 262                                    const ClGenericLinearExpression<T> &e2)
 263     { return new ClGenericLinearExpression<T>(e1.Divide(e2)); }
 264
 265   friend ClGenericLinearExpression<T> *p_Plus(const ClGenericLinearExpression<T> &e1,
 266                                    const ClGenericLinearExpression<T> &e2)
 267     { return new ClGenericLinearExpression<T>(e1.Plus(e2)); }
 268
 269   friend ClGenericLinearExpression<T> *p_Minus(const ClGenericLinearExpression<T> &e1,
 270                                     const ClGenericLinearExpression<T> &e2)
 271     { return new ClGenericLinearExpression<T>(e1.Minus(e2)); }
 272
 273   friend ClGenericLinearExpression<T> *p_Times(const ClGenericLinearExpression<T> &e1,
 274                                     const ClGenericLinearExpression<T> &e2)
 275     { return new ClGenericLinearExpression<T>(e1.Times(e2)); }
 276
 277   friend ClGenericLinearExpression<T> *p_Divide(const ClGenericLinearExpression<T> &e1,
 278                                      const ClGenericLinearExpression<T> &e2)
 279     { return new ClGenericLinearExpression<T>(e1.Divide(e2)); }
 280
 281
 282   // FIXGJB -- this may be wrong -- should test underlying expression for equality
 283   friend bool FEquals(const ClGenericLinearExpression<T> &e1,
 284                       const ClGenericLinearExpression<T> &e2)
 285     { return &e1 == &e2; }
 286
 287   ClGenericLinearExpression<T> &MultiplyMe(T x);
 288
 289  private:
 290
 291   T _constant;
 292   ClVarToCoeffMap _terms;
 293
 294 };
 295
 296 typedef ClGenericLinearExpression<Number>::ClVarToCoeffMap ClVarToNumberMap;
 297
 298 #endif