home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SOLVE / AC6.H next >
C/C++ Source or Header  |  1996-07-11  |  12KB  |  326 lines
  1. /****************************************************************************
  2.     $Id: ac6.h 501.0 1995/03/07 12:26:52 RON Exp $
  3.  
  4.     Copyright (c) 1991-95 Tarma Software Research. All rights reserved.
  5.  
  6.     Project:    Tarma Library for C++ V5.0
  7.     Author:    Ron van der Wal
  8.  
  9.     Declarations for classes involved in the implementation of the AC-6
  10.     constraint propagation algorithm:
  11.  
  12.     VV_Assoc        - Variable/value association
  13.     TLVarValueLink     - Ditto, for use in linked lists
  14.     TLSupportList     - List of variable/value links
  15.     TLSupportPtr    - Reference-counting pointer to the above
  16.     TLDomainElement     - Domain value + supported list
  17.     TLDomainRemoval     - Describes removal of a domain element
  18.     TLWaitingList    - Queue of removals
  19.     TLDomainAC6     - Domain for AC-6 variables
  20.     TLConstraintAC6    - Base class for AC-6 constraints
  21.     TLVariableAC6    - Base class for AC-6 variables
  22.     TLPropagatorAC6     - AC-6 constraint propagator
  23.  
  24.     $Log: ac6.h $
  25.     Revision 501.0  1995/03/07 12:26:52  RON
  26.     Updated for TLX 5.01
  27.     Revision 1.2  1995/01/31 16:29:04  RON
  28.     Update for release 012
  29.     Added partial support for SunPro C++ compiler
  30.     Revision 1.1  1994/10/06  17:52:31  ron
  31.     Initial revision
  32.  
  33. ****************************************************************************/
  34.  
  35. #ifndef _TLX_AC6_H
  36. #define _TLX_AC6_H
  37.  
  38. //-----    System headers
  39.  
  40. #include <stdarg.h>
  41.  
  42. //-----    Project headers
  43.  
  44. #ifndef _TLX_CSP_H
  45. #include <tlx\501\solve\csp.h>
  46. #endif
  47. #ifndef _TLX_REFCNT_H
  48. #include <tlx\501\refcnt.h>
  49. #endif
  50. #ifndef _TLX_SLISTS_H
  51. #include <tlx\501\slists.h>
  52. #endif
  53.  
  54. class _TLXCLASS TLVariableAC6;
  55. class _TLXCLASS TLConstraintAC6;
  56.  
  57. /*---------------------------------------------------------------------------
  58.     Auxiliary declarations and definitions
  59. ---------------------------------------------------------------------------*/
  60.  
  61. typedef int32          tVarValue;    // Type for variable values
  62.  
  63. /*---------------------------------------------------------------------------
  64.     Helper classes:
  65.  
  66.     - VV_Assoc is an association between TLVariableAC6 * and tVarValue that
  67.       is used to store these pairs in various situations in the
  68.       implementation of the AC-6 algorithm.
  69. ---------------------------------------------------------------------------*/
  70.  
  71. class _TLXCLASS VV_Assoc: public TLAssoc<TLVariableAC6 *, tVarValue>
  72. {
  73. public:
  74.     VV_Assoc();
  75.     VV_Assoc(TLVariableAC6 *, tVarValue);
  76.  
  77.     friend ostream &     _TLXFUNC operator <<(ostream &, const VV_Assoc &);
  78. };
  79.  
  80. /*---------------------------------------------------------------------------
  81.     TLVarValueLink -
  82.  
  83.     Association between a variable and a value that is also a link field
  84.     for a singly-linked list. Instances of this class are used to create
  85.     support lists for use in the AC-6 algorithm.
  86. ---------------------------------------------------------------------------*/
  87.  
  88. class _TLXCLASS TLVarValueLink: public TLSLink, public VV_Assoc
  89. {
  90. public:
  91.     TLVarValueLink(const VV_Assoc &);
  92.  
  93.     TLVarValueLink &    operator =(const VV_Assoc &);
  94.     int            operator ==(const VV_Assoc &) const;
  95.  
  96.     TLVariableAC6 *     PeekVar() const { return Key(); }
  97.     tVarValue        PeekValue() const { return Value(); }
  98. };
  99.  
  100. /*---------------------------------------------------------------------------
  101.     TLSupportList -
  102.  
  103.     Mix-in class that is both a TLRefCount (for reference counting) and a
  104.     TLSList<TLVarValueLink> (to store a list of variable/value pairs).
  105.     This class is used as the head of a support list; it needs reference
  106.     counting because it must be passed on between domain elements without
  107.     being physically copied or accidentally discarded.
  108. ---------------------------------------------------------------------------*/
  109.  
  110. class _TLXCLASS TLSupportList: public TLRefCount, public TLSList<TLVarValueLink>
  111. {
  112. public:
  113.     // Only a default constructor, which invokes the default constructors
  114.     // of its base classes.
  115.  
  116.     TLSupportList();
  117.  
  118.     // All other functionality is inherited and not overridden.
  119. };
  120.  
  121. // TLSupportPtr is an alias for a reference-counting pointer to the above
  122.  
  123. typedef TLCountedPtr<TLSupportList> TLSupportPtr;
  124.  
  125. /*---------------------------------------------------------------------------
  126.     TLDomainElement -
  127.  
  128.     This class represents a domain element in the domain of variables used
  129.     in the AC-6 algorithm. Each element contains the value proper, plus
  130.     (the head of) a list that indicates which values in other variables
  131.     depend on support from this value.
  132.  
  133.     The value part of this class is a reference counting pointer to support
  134.     lists; the reference counting is used when domain elements are
  135.     removed from a domain (TLDomainAC6) and placed on a waiting list
  136.     (TLWaitingList).
  137. ---------------------------------------------------------------------------*/
  138.  
  139. class _TLXCLASS TLDomainElement: public TLAssoc<tVarValue, TLSupportPtr>
  140. {
  141. public:
  142.     TLDomainElement(tVarValue = 0);
  143.  
  144.     TLDomainElement &    operator =(const TLDomainElement &);
  145.  
  146.     tVarValue        PeekValue() const { return Key(); }
  147.     TLSupportPtr &    SupportList() { return Value(); }
  148.     const TLSupportPtr &SupportList() const { return Value(); }
  149.  
  150.     // Functions to add and remove variable/value links from the support
  151.     // list. ClearSupport() deletes the entire support list.
  152.  
  153.     void        AddSupport(const VV_Assoc &);
  154.     void        RemoveSupport(const VV_Assoc &);
  155.     void        ClearSupport();
  156.  
  157.     // Iteration through the support list of the domain element. You should
  158.     // *not* try to modify the list during the iteration without resetting
  159.     // the iterator, or havoc may result.
  160.  
  161.     bool         ResetIter(iter_t &);
  162.     bool         NextIter(iter_t &);
  163.     const TLVarValueLink *PeekIter(const iter_t &) const;
  164. };
  165.  
  166. /*---------------------------------------------------------------------------
  167.     TLDomainRemoval -
  168.  
  169.     Association between a domain element and the variable that contained
  170.     it before it was removed.
  171. ---------------------------------------------------------------------------*/
  172.  
  173. class _TLXCLASS TLDomainRemoval: public TLAssoc<TLVariableAC6 *,
  174.                         TLDomainElement>
  175. {
  176. public:
  177.     TLDomainRemoval();
  178.     TLDomainRemoval(TLVariableAC6 *, const TLDomainElement &);
  179. };
  180.  
  181. // TLWaitingList is an alias for a queue of the above
  182.  
  183. typedef TLQueue<TLDomainRemoval> TLWaitingList;
  184.  
  185. /*---------------------------------------------------------------------------
  186.     TLDomainAC6 -
  187.  
  188.     Represents the domain of variables that are used in the AC-6 algorithm.
  189.     It is a sequence of TLDomainElement instances with some added
  190.     functionality. The domain installs a comparison function that compares
  191.     (and hence sorts) its elements by their element value.
  192. ---------------------------------------------------------------------------*/
  193.  
  194. class _TLXCLASS TLDomainAC6: public TLSeq<TLDomainElement>
  195. {
  196. public:
  197.     TLDomainAC6(size_t, size_t = 0);
  198.  
  199.     // Functions to find indices of elements
  200.  
  201.     index_t        IndexOfValue(tVarValue) const;
  202.     index_t        EqualOrNextIndexOf(tVarValue) const;
  203.  
  204.     // Functions to find the element that stores a particular value
  205.  
  206.     TLDomainElement &    GetElement(tVarValue);
  207.     const TLDomainElement &GetElement(tVarValue) const;
  208.  
  209. private:
  210.     static int        DECompare(const TLDomainElement &,
  211.                       const TLDomainElement &);
  212. };
  213.  
  214. /*---------------------------------------------------------------------------
  215.     TLConstraintAC6 -
  216.  
  217.     Base class for constraints to be used in AC-6 constraint propagation
  218.     algorithms. Constraints of this type are binary constraints that assume
  219.     both their variables to be of type TLVariableAC6 or derived thereof.
  220. ---------------------------------------------------------------------------*/
  221.  
  222. class _TLXCLASS TLConstraintAC6: public TLBinCon
  223. {
  224. public:
  225.     TLConstraintAC6(TLVariableAC6 &, TLVariableAC6 &);
  226.  
  227.     // Functions that hide TLBinCon member functions of the same name
  228.     // in order to get some type safety.
  229.  
  230.     TLVariableAC6 &    Var1();
  231.     const TLVariableAC6 &Var1() const;
  232.     TLVariableAC6 &    Var2();
  233.     const TLVariableAC6 &Var2() const;
  234.  
  235.     TLVariableAC6 &    OppositeOf(TLVariableAC6 &);
  236.     const TLVariableAC6 &OppositeOf(const TLVariableAC6 &) const;
  237.  
  238.     // Functions to implement constraint-dependent support procedures.
  239.     //
  240.     // - FindNextSupport() attempts to find the next value in one variable
  241.     //   that supports a particular value in the other variable. It returns
  242.     //   nonzero if it succeeds, else zero.
  243.  
  244.     virtual bool        FindNextSupport(TLVariableAC6 &, tVarValue,
  245.                         TLVariableAC6 &, tVarValue &) = 0;
  246. };
  247.  
  248. /*---------------------------------------------------------------------------
  249.     TLVariableAC6 -
  250.  
  251.     Variable class specifically for AC-6 constraint propagation. Variables
  252.     of this class have domains that consist of tVarValue values.
  253. ---------------------------------------------------------------------------*/
  254.  
  255. class _TLXCLASS TLVariableAC6: public TLVariable
  256. {
  257. protected:
  258.     // The domain of the variable should consist of a list of integral
  259.     // values. It should be ordered by increasing value. This is accomplished
  260.     // automatically by using mDomain.InsertSorted() or AddValue() to place
  261.     // new values in the domain.
  262.  
  263.     TLDomainAC6        mDomain;    // Current domain of the variable
  264.  
  265. public:
  266.     // Constructor allows creation of domain with a given size. Derived
  267.     // classes may also resize the domain explicitly at a later stage.
  268.  
  269.     TLVariableAC6(const char *, size_t = 0);
  270.  
  271.     // Functions that hide TLVariable member functions of the same name
  272.     // in order to get some type safety.
  273.  
  274.     void         AddConstraint(TLConstraintAC6 *aCon)
  275.                 { TLVariable::AddConstraint(aCon); }
  276.     void         RemoveConstraint(TLConstraintAC6 *aCon)
  277.                 { TLVariable::RemoveConstraint(aCon); }
  278.     TLConstraintAC6 *    FindConstraintTo(const TLVariableAC6 *) const;
  279.  
  280.     // Functions to add and remove values to/from the domain
  281.  
  282.     void        AddValue(tVarValue);
  283.     void        RemoveValue(tVarValue);
  284.     TLDomainAC6 &    Domain() { return mDomain; }
  285.     const TLDomainAC6 &    Domain() const { return mDomain; }
  286.  
  287.     // Functions to manipulate the support lists in the domain
  288.  
  289.     void        AddSupport(tVarValue, const VV_Assoc &);
  290.     void        RemoveSupport(tVarValue, const VV_Assoc &);
  291.     void        ClearSupport();
  292.  
  293.     // The following functions implement the pure virtual functions inherited
  294.     // from the base class. They use TLDomainAC6 instances to store and restore
  295.     // the variable's domain.
  296.  
  297.     virtual TLDomain *    SaveDomain();
  298.     virtual void     RestoreDomain(const TLDomain *);
  299.     virtual void     DiscardDomain(TLDomain *);
  300. };
  301.  
  302. /*---------------------------------------------------------------------------
  303.     TLPropagatorAC6 -
  304.  
  305.     Class that implements the AC-6 constraint propagation algorithm.
  306. ---------------------------------------------------------------------------*/
  307.  
  308. class _TLXCLASS TLPropagatorAC6: public TLPropagator
  309. {
  310. public:
  311.     TLPropagatorAC6();
  312.  
  313.     // Consistency checking and constraint propagation algorithms:
  314.     //
  315.     // - CheckAC6() propagates the effects of the constraints that
  316.     //   originate with the given set of variables.
  317.  
  318.     bool         CheckAC6(const TLPtrSeq<TLVariable> &);
  319.  
  320. private:
  321.     bool          InitSupport(TLConstraintAC6 *, TLVariableAC6 *,
  322.                     TLVariableAC6 *, TLWaitingList &);
  323. };
  324.  
  325. #endif    // _TLX_AC6_H
  326.