libs/cassowary/cassowary/ClFDSolver.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 // ClSolver.h
  11
  12 #ifndef ClFDSolver_H
  13 #define ClFDSolver_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 "ClSolver.h"
  22 #include "ClVariable.h"
  23 #include "ClErrors.h"
  24 #include "ClTypedefs.h"
  25 #include "ClSymbolicWeight.h"
  26 #include <GTL/graph.h>
  27 #include <map>
  28
  29 using std::map;
  30
  31 class ClVariable;
  32 class ClFDBinaryOneWayConstraint;
  33
  34 // ClFDSolver is a concrete class
  35 // implementing a very restricted (for now --04/23/99 gjb)
  36 // finite-domain constraint solving algorithm
  37 class ClFDSolver: public ClSolver {
  38  public:
  39   ClFDSolver()
  40       : _setCns(), _mapClvToCns(), G(), nodeToVar(G)
  41     { G.make_directed(); }
  42
  43   virtual ~ClFDSolver()
  44     { }
  45
  46   virtual ClFDSolver &AddConstraint(ClConstraint *const pcn);
  47
  48   virtual ClFDSolver &RemoveConstraint(ClConstraint *const pcn);
  49
  50   virtual ClFDSolver &Solve();
  51
  52   virtual ClFDSolver &ShowSolve();
  53
  54   void ChangeClv(ClVariable clv, FDNumber n) {
  55     clv.ChangeValue(n);
  56     if (_pfnChangeClvCallback) {
  57       _pfnChangeClvCallback(&clv,this);
  58     }
  59   }
  60
  61
  62 #ifndef CL_NO_IO
  63   ostream &PrintOn(ostream &xo) const;
  64
  65   ostream &PrintInternalInfo(ostream &xo) const;
  66
  67   ostream &PrintOnVerbose(ostream &xo) const
  68     { PrintOn(xo); PrintInternalInfo(xo); xo << endl; return xo; }
  69
  70   friend ostream &operator<<(ostream &xo, const ClFDSolver &solver);
  71
  72 #endif
  73
  74  protected:
  75
  76   virtual ClFDSolver &AddConstraintInternal(ClConstraint *const pcn);
  77
  78   virtual ClFDSolver &RemoveConstraintInternal(ClConstraint *const pcn);
  79
  80   /* Create node for v in G, if necessary,
  81      otherwise return the node we already created. */
  82   node GetVarNode(ClVariable v);
  83
  84   /* return the best (lowest) incremental error and the value
  85      at which that error occurs */
  86   pair<ClSymbolicWeight,FDNumber> ComputeBest(ClFDVariable *pcldv);
  87
  88   ClSymbolicWeight ErrorForClvAtValSubjectToCn(ClFDVariable *pcldv,
  89                                                FDNumber value,const ClConstraint &cn);
  90
  91   /* Turn all FDVariable FIsSet() flags to false */
  92   void ResetSetFlagsOnVariables();
  93
  94   /* all the constraints in the solver */
  95   ClConstraintSet _setCns;
  96
  97   /* _mapClvToCns maps variable to the constraints in which
  98      it is rw (it omits where it is ro) */
  99   ClVarToConstraintSetMap _mapClvToCns;
 100
 101   /* track what edges correspond to which constraints
 102      so we can update the constraint graph when
 103      removing a constraint */
 104   map<ClConstraint *, edge> _mapCnToEdge;
 105
 106   /* track what nodes correspond to which variables */
 107   map<ClVariable, node> _mapVarToNode;
 108
 109   /* directed graph that mirrors the structure of
 110      the relations of the added constraints */
 111   graph G;
 112
 113   node_map<ClVariable> nodeToVar;
 114 };
 115
 116 #define FDN_EOL LONG_MIN
 117
 118 void ListPushOnto(list<FDNumber> *pl, ...);
 119
 120 #endif