home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SOLVE / SEARCHER.H < prev    next >
C/C++ Source or Header  |  1996-07-08  |  36KB  |  1,048 lines
  1. /****************************************************************************
  2.     $Id: searcher.h 501.0 1995/03/07 12:26:54 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 related to all forms of enumerative and
  10.     branch & bound searching:
  11.  
  12.     TLSolution        - Generic solution wrapper
  13.     TLProblemInfo    - Additional information about a subproblem
  14.     TLBBInfo        - Problem info for branch & bound search
  15.     TLProblemState    - Generic subproblem in the search tree
  16.     TLProblemList    - Ordered list of subproblems
  17.     TLProblemRep    - Generic problem representation interface
  18.     TLSearchMonitor    - Base class for search monitors
  19.     TLSearchStats    - Search monitors that collects statistics
  20.     TLSearchWatchdog    - Search monitors that terminates after node count
  21.     TLSearchBreaker    - Ctrl-Break handler for searchers
  22.     TLSearcher        - Generic enumerative searcher
  23.     TLBTSearcher    - Backtrack searcher algorithm (non-recursive)
  24.     TLBTSearcherRcsv    - Backtrack searcher algorithm (recursive)
  25.     TLBBSearcher    - General branch & bound searcher
  26.     TLBBSearcherDF    - Depth-first branch & bound searcher
  27.  
  28.     $Log: searcher.h $
  29.     Revision 501.0  1995/03/07 12:26:54  RON
  30.     Updated for TLX 5.01
  31.     Revision 1.16  1995/02/22 12:21:50  RON
  32.     Update for release 012
  33.     Added partial support for SunPro C++ compiler
  34.     Revision 1.15  1995/01/18  10:36:05  ron
  35.     Added TLSubProblem parameter to TLSearchMonitor::Event
  36.  
  37.     Revision 1.14  1995/01/16  12:22:14  ron
  38.     Removed best gap; added GetIncumbent()
  39.  
  40.     Revision 1.13  1995/01/13  15:26:45  ron
  41.     Added ContinueSearch() to BTSearcher and derived classes
  42.  
  43.     Revision 1.12  1995/01/12  13:34:56  ron
  44.     Restored previous Searcher/ProblemRep design
  45.  
  46.     Revision 1.11  1995/01/10  16:35:27  ron
  47.     Added ReportStats() and best lower bound to TLBBSearcherDF
  48.  
  49.     Revision 1.10  1995/01/08  11:52:21  ron
  50.     Changed searcher depth type from int32 to int
  51.     Renamed TLCSProblem to TLCSSubProblem
  52.  
  53.     Revision 1.9  1995/01/06  16:03:20  ron
  54.     Adapted to new Searcher/Problem model
  55.  
  56.     Revision 1.8  1995/01/05  15:37:48  ron
  57.     Brought inline with thesis
  58.  
  59.     Revision 1.7  1994/11/16  15:31:40  ron
  60.     Added optional 'bool' variant to TLSearchMonitor::Event
  61.  
  62.     Revision 1.6  1994/10/13  11:57:16  ron
  63.     Moved standard search monitors to this file
  64.     Added AddFront() and AddRear() synonyms to TLProblemList
  65.  
  66.     Revision 1.5  1994/10/12  10:08:57  ron
  67.     Added TLProblemInfo as an optional extension of the TLSubProblem
  68.     interface
  69.     Adapted TLBBInfo to the introduction of TLProblemInfo
  70.  
  71.     Revision 1.4  1994/10/11  19:09:19  ron
  72.     Replaced DeadEnd()/SolveProblem() by ProcessProblem()
  73.     Removed specialized B&B problem representation
  74.     Removed several TLBTSearcher::Frame member functions
  75.  
  76.     Revision 1.3  1994/10/10  17:07:07  ron
  77.     Moved searcher events to TLSearcher
  78.     Added Terminate() function to the searcher interface
  79.     Added Description() function to the searcher interface
  80.  
  81.     Revision 1.2  1994/10/07  17:11:33  ron
  82.     Added search monitors and their support
  83.  
  84.     Revision 1.1  1994/10/06  17:53:00  ron
  85.     Initial revision
  86.  
  87. ****************************************************************************/
  88.  
  89. #ifndef _TLX_SEARCHER_H
  90. #define _TLX_SEARCHER_H
  91.  
  92. //-----    System headers
  93.  
  94. #include <time.h>
  95.  
  96. //-----    Project headers
  97.  
  98. #ifndef _TLX_ARRAYS_H
  99. #include <tlx\501\arrays.h>
  100. #endif
  101. #ifndef _TLX_PTRARRAY_H
  102. #include <tlx\501\ptrarray.h>
  103. #endif
  104. #ifndef _TLX_REFCNT_H
  105. #include <tlx\501\refcnt.h>
  106. #endif
  107. #ifndef _TLX_SLISTS_H
  108. #include <tlx\501\slists.h>
  109. #endif
  110. #ifndef _TLX_STATS_H
  111. #include <tlx\501\stats.h>
  112. #endif
  113.  
  114. class _RTLCLASS ostream;    // In iostream.h
  115. class _TLXCLASS TLVariable;    // In solve\csp.h
  116. class _TLXCLASS TLSearcher;    // Below
  117.  
  118. /*---------------------------------------------------------------------------
  119.     TLSolution -
  120.  
  121.     Abstract base class representing a solution in the search process.
  122. ---------------------------------------------------------------------------*/
  123.  
  124. class _TLXCLASS TLSolution: public TLRefCount
  125. {
  126. public:
  127.     // Only required functionality is the ability to print itself.
  128.  
  129.     virtual ostream &    PrintOn(ostream &) const = 0;
  130.     friend ostream &     _TLXFUNC operator <<(ostream &, const TLSolution &);
  131. };
  132.  
  133. typedef TLPtrSeq<TLSolution> TLSolutionSet;
  134.  
  135. /*---------------------------------------------------------------------------
  136.     TLProblemInfo -
  137.  
  138.     Base class for classes that supply additional information about a
  139.     subproblem. They are used as part of a TLProblemState, to introduce
  140.     flexibility with respect to the interface composition mechanism:
  141.     (multiple) inheritance, data member, or external data.
  142. ---------------------------------------------------------------------------*/
  143.  
  144. class _TLXCLASS TLProblemInfo
  145. {
  146. public:
  147.     virtual ~TLProblemInfo();
  148. };
  149.  
  150. /*---------------------------------------------------------------------------
  151.     TLBBInfo -
  152.  
  153.     Subproblem information for use in branch & bound algorithms.
  154. ---------------------------------------------------------------------------*/
  155.  
  156. class _TLXCLASS TLBBInfo: public TLProblemInfo
  157. {
  158.     // Implementation hints: you may either store the values for the upper
  159.     // and lower bound on first constructing an instance of the solution,
  160.     // or you may have them recalculated each time one of the corresponding
  161.     // functions is called. In the latter case, it may be necessary to
  162.     // store a pointer or reference to the problem representation to which
  163.     // this solution belongs.
  164. public:
  165.     // Derived classes must override and implement the following functions
  166.     // that are used to direct the B & B searching process. The functions
  167.     // are called after the problem representation has solved the subproblem.
  168.     //
  169.     // - IsDominated() must return nonzero if the problem is dominated
  170.     //   by another one in the search tree.
  171.     //
  172.     // - UpperBound() must return the value of the upper bound for this
  173.     //   problem. If the solution is exact, it is also the value of the
  174.     //   solution.
  175.     //
  176.     // - LowerBound() must return the value of the lower bound for this
  177.     //   problem if it's feasible.
  178.  
  179.     virtual double    UpperBound() = 0;
  180.     virtual double    LowerBound() = 0;
  181.     virtual bool     IsDominated() { return false; }
  182. };
  183.  
  184. /*---------------------------------------------------------------------------
  185.     TLProblemState -
  186.  
  187.     Represents the information that describes a subproblem in the search
  188.     tree. It is an abstract base class which should be derived from to
  189.     create problem-specific subproblems.
  190. ---------------------------------------------------------------------------*/
  191.  
  192. class _TLXCLASS TLProblemState: public TLRefCount
  193. {
  194.   #ifdef _TLXDBG
  195. public:
  196.     bool        mIsProcessed;    // Set by Searcher if debugging
  197.   #endif
  198.  
  199. public:
  200.     // For extensibility, we define a function that returns a pointer to
  201.     // additional node information. The default implementation has none,
  202.     // but for other searching purposes (e.g. branch and bound), the
  203.     // additional information must be added.
  204.  
  205.     virtual TLProblemInfo *GetInfo();
  206.  
  207.     // Derived classes may override GetRank() if they implement some sort
  208.     // of best-first searching. The higher the rank value, the better the
  209.     // node is considered to be.
  210.  
  211.     virtual double    GetRank() const;
  212.  
  213.     // PrintOn() should print some suitably formatted description of the
  214.     // contents of current value of the selection; it is used for tracing
  215.     // the execution of the search algorithm.
  216.  
  217.     virtual ostream &    PrintOn(ostream &) const = 0;
  218.     friend ostream &     _TLXFUNC operator <<(ostream &, const TLProblemState &);
  219.  
  220. protected:
  221.     TLProblemState();
  222. };
  223.  
  224. /*---------------------------------------------------------------------------
  225.     TLProblemList -
  226.  
  227.     Specialized ordered list of TLProblemState instances that is used to keep
  228.     track of active nodes during the search processes.
  229. ---------------------------------------------------------------------------*/
  230.  
  231. class _TLXCLASS TLProblemList: public TLPtrSeq<TLProblemState>
  232. {
  233. public:
  234.     // Constructor sets the proper comparison function and makes the list
  235.     // owner of the nodes stored in it.
  236.  
  237.     TLProblemList(TLProblemState *);
  238.     TLProblemList(size_t, size_t);
  239.  
  240.     // The public interface of this class is very limited, since it is
  241.     // exposed to problem-specific problem representation instances. They
  242.     // should use one of the following functions to add new nodes to the list
  243.     // when asked to expand an existing node.
  244.     //
  245.     // - AddDepthFirst() causes the search tree to be traversed depth-first,
  246.     //   exploring the most recently added node first;
  247.     //
  248.     // - AddBreadthFirst() causes a breadth-first search, exploring the most
  249.     //   recently added node last;
  250.     //
  251.     // - AddBestFirst() causes a best-first search, where nodes with higher
  252.     //   rank values are considered better and are explored before nodes with
  253.     //   lower rank values.
  254.     //
  255.     // AddFront() and AddRear() are synonyms for AddDepthFirst() and
  256.     // AddBreadthFirst().
  257.  
  258.     void        AddDepthFirst(TLProblemState *);
  259.     void        AddBreadthFirst(TLProblemState *);
  260.     void        AddBestFirst(TLProblemState *);
  261.     void        AddFront(TLProblemState *);
  262.     void        AddRear(TLProblemState *);
  263.  
  264.     // Functions to be used to retrieve the next eligible subproblem.
  265.     // The inherited IsEmpty() function should be used to check for
  266.     // emptiness first.
  267.  
  268.     TLProblemState *    PeekFirst() const;
  269.     TLProblemState *    ExtractFirst();
  270.  
  271. private:
  272.     static int        CompareProblems(const void *, const void *);
  273. };
  274.  
  275. /*---------------------------------------------------------------------------
  276.     TLProblemRep -
  277.  
  278.     Manages the problem-specific data structures that are used during the
  279.     various search processes. TLProblemRep is the abstract base class for
  280.     more specialized problem representations that are fitted to different
  281.     problem types.
  282. ---------------------------------------------------------------------------*/
  283.  
  284. class _TLXCLASS TLProblemRep
  285. {
  286.     friend class _TLXCLASS TLSearcher;
  287.  
  288.     TLSearcher *    mSearcher;    // Currently active searcher
  289.  
  290. public:
  291.     virtual ~TLProblemRep();
  292.  
  293.     // Access to the current searcher (if any)
  294.  
  295.     TLSearcher *    GetSearcher() const;
  296.  
  297.     // Overridables that have a default implementation; derived classes need
  298.     // only override them if they need different behavior. In those cases,
  299.     // the original version should be called as part of the overridden
  300.     // implementation.
  301.     //
  302.     // - PreProcess() is called prior to the search process and must be
  303.     //   used to prepare the TLProblemRep for the search process.
  304.     //
  305.     // - PostProcess() is called when the search process is completed and
  306.     //   may be used to do some kind of clean up.
  307.  
  308.     virtual bool      PreProcess();
  309.     virtual void     PostProcess();
  310.  
  311.     // Overridables that must be implemented by derived classes. They are
  312.     // used by all searchers as part of the searcher protocol.
  313.     //
  314.     // - CreateInitialProblem() must create the initial set of problems to
  315.     //   explore (which may be a single node). The default implementation
  316.     //   calls Decompose() with a 0 argument for the problem to decompose.
  317.     //
  318.     // - Decompose() should create the subproblems of the given problem.
  319.     //   The preferred order of exploration is determined by the order in
  320.     //   which they are inserted in the problem list.
  321.     //
  322.     // - Process() should accept a previously created subproblem and
  323.     //   perform the associated value assignment. It should store sufficient
  324.     //   information in the subproblem to undo the assignment later on. It
  325.     //   should then perform whatever further processing is necessary.
  326.     //
  327.     // - DoneProcessing() is called with a processed subproblem when
  328.     //   all processing by the searcher has been finished. It is the place
  329.     //   to restore the effects of all processing since StartProcessing()
  330.     //   was called on the subproblem.
  331.     //
  332.     // - CreateSolution() is called when a complete solution has been found,
  333.     //   and should create and return a solution object that describes the
  334.     //   solution.
  335.     //
  336.     // - Size() must return the "size" of the problem, i.e. the
  337.     //   number of variables involved. This number must remain the same
  338.     //   throughout the execution of the search process.
  339.  
  340.     virtual size_t     CreateInitialProblem(TLProblemList &);
  341.     virtual size_t     GenerateBranches(TLProblemState *, TLProblemList &) = 0;
  342.     virtual void      EnterState(TLProblemState *) = 0;
  343.     virtual bool      Process(TLProblemState *) = 0;
  344.     virtual void     LeaveState(TLProblemState *);
  345.     virtual TLSolution *CreateSolution(TLProblemState *) = 0;
  346.     virtual size_t     Size() const = 0;
  347.  
  348.     // Output functions:
  349.     //
  350.     // - ReportStats() is called to report on any statistics the problem
  351.     //   representation might have collected;
  352.     //
  353.     // - PrintOn() is used to produce a print of the problem representation
  354.     //   state on an output stream.
  355.  
  356.     virtual void    ReportStats(ostream &) const {}
  357.     virtual ostream &    PrintOn(ostream &) const = 0;
  358.     friend ostream &     _TLXFUNC operator <<(ostream &, const TLProblemRep &);
  359.  
  360. protected:
  361.     TLProblemRep();
  362. };
  363.  
  364. /*---------------------------------------------------------------------------
  365.     TLSearchMonitor -
  366.  
  367.     Base for classes that monitor the progress of a search, e.g. to capture
  368.     statistics or to give an graphical representation of the search process.
  369.     After registering a search monitor class with a searcher, the monitor
  370.     will be informed of the relevant events within the search process.
  371. ---------------------------------------------------------------------------*/
  372.  
  373. class _TLXCLASS TLSearchMonitor
  374. {
  375. public:
  376.     // Events are sent to a search monitor in an Event structure. This is
  377.     // done for efficiency and flexibility in the searcher class. It does
  378.     // require the search monitor to decode the event, however.
  379.     //
  380.     // Events store basic information associated with them; for more details,
  381.     // the search monitor should call back to the searcher that sent the
  382.     // event.
  383.  
  384.     struct _TLXCLASS Event
  385.     {
  386.     int        mCode;        // Event code (see TLSearcher)
  387.     TLProblemState *    mProblem;    // Subproblem for the event (optional)
  388.     union
  389.     {
  390.         bool    mBoolParm;    // (PreProcess, Processing)
  391.         int16    mInt16Parm;    // (reserved)
  392.         int32    mInt32Parm;    // (DoneProcess)
  393.         uint16    mUint16Parm;    // (reserved)
  394.         uint32    mUint32Parm;    // (Initial, Decompose, Solution)
  395.         double    mDoubleParm;    // (reserved)
  396.     };
  397.  
  398.     Event(int, TLProblemState * = 0);
  399.       #ifndef _NOBOOL
  400.     Event(int, bool, TLProblemState * = 0);
  401.       #endif
  402.     Event(int, int16, TLProblemState * = 0);
  403.     Event(int, int32, TLProblemState * = 0);
  404.     Event(int, uint16, TLProblemState * = 0);
  405.     Event(int, uint32, TLProblemState * = 0);
  406.     Event(int, double, TLProblemState * = 0);
  407.     };
  408.  
  409. public:
  410.     virtual ~TLSearchMonitor();
  411.  
  412.     // The following function is called when an event occurs for which the
  413.     // monitor has been registered with a searcher.
  414.  
  415.     virtual void    OnSearchEvent(TLSearcher *, const Event &);
  416.     virtual int        DefaultEvents() const;
  417.  
  418.     // Output operators. PrintOn() is called by the searcher as part of its
  419.     // own ReportStats() processing.
  420.  
  421.     virtual ostream &    PrintOn(ostream &) const;
  422.     friend ostream &    _TLXFUNC operator <<(ostream &,
  423.                              const TLSearchMonitor &);
  424. };
  425.  
  426. /*---------------------------------------------------------------------------
  427.     TLSearchStats -
  428.  
  429.     Search monitor that collects statistics about the searching process.
  430.     The following data are captured:
  431.  
  432.     - average, minimum, and maximum search depth
  433.     - average, minimum, and maximum branching factor
  434.     - average, minimum, and maximum branching factor at each search depth
  435. ---------------------------------------------------------------------------*/
  436.  
  437. class _TLXCLASS TLSearchStats: public TLSearchMonitor
  438. {
  439.     // Statistics that are kept by this monitor are all one-dimensional
  440.  
  441.     typedef TLStats1<int32> IntStats;
  442.  
  443.     IntStats        mDepth;        // Search depth statistics
  444.     IntStats        mBranching;    // Overall branching statistics
  445.     TLArray<IntStats>    mLevelBranch;    // Branching stats per level
  446.  
  447. public:
  448.     TLSearchStats();
  449.  
  450.     // Overridden search monitor behavior.
  451.  
  452.     virtual int        DefaultEvents() const;
  453.     virtual void    OnSearchEvent(TLSearcher *, const Event &);
  454.     virtual ostream &    PrintOn(ostream &) const;
  455. };
  456.  
  457. /*---------------------------------------------------------------------------
  458.     TLBBStats -
  459.  
  460.     Search monitor that collects statistics about a branch and bound
  461.     searching process. The following data are captured:
  462.  
  463.     - average, minimum, and maximum lowerbounds during the search
  464.     - average, minimum, and maximum lowerbounds at each search depth
  465. ---------------------------------------------------------------------------*/
  466.  
  467. class _TLXCLASS TLBBStats: public TLSearchMonitor
  468. {
  469.     // Statistics that are kept by this monitor are all one-dimensional
  470.  
  471.     typedef TLStats1<double> DoubleStats;
  472.  
  473.     DoubleStats        mLBounds;    // Overall lowerbound statistics
  474.     TLArray<DoubleStats>  mLBDepth;    // Per-depth lowerbounds statistics
  475.  
  476. public:
  477.     TLBBStats();
  478.  
  479.     // Overridden search monitor behavior.
  480.  
  481.     virtual int        DefaultEvents() const;
  482.     virtual void    OnSearchEvent(TLSearcher *, const Event &);
  483.     virtual ostream &    PrintOn(ostream &) const;
  484. };
  485.  
  486. /*---------------------------------------------------------------------------
  487.     TLSearchWatchdog -
  488.  
  489.     Search monitor that terminates the search process if too many problems
  490.     have been explored.
  491. ---------------------------------------------------------------------------*/
  492.  
  493. class _TLXCLASS TLSearchWatchdog: public TLSearchMonitor
  494. {
  495.     int32        mProblemCount;    // Number of problems so far
  496.     int32        mMaxProblems;    // Maximum allowed number of problems
  497.  
  498. public:
  499.     TLSearchWatchdog(int32);
  500.  
  501.     // Overridden search monitor behavior.
  502.  
  503.     virtual int        DefaultEvents() const;
  504.     virtual void    OnSearchEvent(TLSearcher *, const Event &);
  505.     virtual ostream &    PrintOn(ostream &) const;
  506. };
  507.  
  508. /*---------------------------------------------------------------------------
  509.     TLSearchBreaker -
  510.  
  511.     Search monitor that terminates the search process if Ctrl-Break or
  512.     Ctrl-C have been detected.
  513. ---------------------------------------------------------------------------*/
  514.  
  515. class _TLXCLASS TLSearchBreaker: public TLSearchMonitor
  516. {
  517.     static bool        sBreak;        // true if break detected
  518.     static bool        sNotified;    // true if user has been notified
  519.     static int        sBCount;    // Number of search breakers
  520.  
  521. public:
  522.     TLSearchBreaker();
  523.     virtual ~TLSearchBreaker();
  524.  
  525.     // Overridden search monitor behavior.
  526.  
  527.     virtual int        DefaultEvents() const;
  528.     virtual void    OnSearchEvent(TLSearcher *, const Event &);
  529.     virtual ostream &    PrintOn(ostream &) const;
  530.  
  531. private:
  532.     // Signal handler for Ctrl-Break and Ctrl-C
  533.  
  534.     static void __cdecl BreakHandler(int);
  535. };
  536.  
  537. /*---------------------------------------------------------------------------
  538.     TLSearcher -
  539.  
  540.     Base class for all searcher classes. It is an abstract class, so users
  541.     should instatiate one of its derivations.
  542. ---------------------------------------------------------------------------*/
  543.  
  544. class _TLXCLASS TLSearcher
  545. {
  546.     friend class _TLXCLASS TLProblemRep;
  547.  
  548. public:
  549.     // The following interface defines the events that search monitors will
  550.     // receive. They may filter one or more events if they are not
  551.     // interested in them at all; this will improve search performance.
  552.     //
  553.     // Classes derived from TLSearcher may add their own event codes.
  554.  
  555.     enum
  556.     {
  557.     seNone        = 0x0000,    // No events
  558.     sePreProcess    = 0x0001,    // Preprocessing started
  559.     sePostProcess    = 0x0002,    // Postprocessing started
  560.     seInitial    = 0x0004,    // Initial problem(s) created
  561.     seBranch    = 0x0008,    // Problem decomposed
  562.     seEnter        = 0x0010,    // Problem state entered
  563.     seProcess    = 0x0020,    // Problem processed
  564.     seLeave        = 0x0040,       // Problem state left
  565.     seSolution    = 0x0080,    // Solution found
  566.     seAll        = 0xffff    // All events
  567.     };
  568.  
  569.     // We keep a number of statistics about the search process that is
  570.     // going on. They are used by this base class for report generation,
  571.     // and should be filled in by derived classes as the search progresses.
  572.  
  573.     struct _TLXCLASS Stats
  574.     {
  575.         size_t         mMaxSol;    // Maximum number of solutions to find
  576.         uint32     mBTCount;    // Number of backtracks performed
  577.         uint32        mProblemCount;    // Number of nodes visited
  578.     int        mDepth;        // Current search depth
  579.         time_t         mStart;        // Start time of solver
  580.         time_t         mStartSearch;    // Start time of the search process
  581.         time_t        mPrevious;    // Time of the previous solution
  582.         time_t        mFinishSearch;    // Finish time of the search process
  583.         time_t        mFinish;    // Finish time of solver
  584.     };
  585.  
  586. private:
  587.     TLSearcher *    mPrevSearcher;    // Previous searcher if we're nested
  588.     TLProblemRep *    mProblemRep;    // ProblemRep for the problem
  589.     TLSolutionSet    mSolutions;    // Solutions
  590.     Stats        mStats;        // Statistics
  591.  
  592.     // References to search monitors are stored along with their event mask
  593.  
  594.     struct _TLXCLASS MonitorEntry
  595.     {
  596.     TLSearchMonitor *mMonitor;    // The monitor
  597.     int        mEventMask;    // Its event mask
  598.  
  599.     MonitorEntry();
  600.     MonitorEntry(TLSearchMonitor *, int);
  601.     };
  602.  
  603.     // Data members to keep track of the active monitors. We also store
  604.     // a global event mask that is the union of all individual masks, so
  605.     // there is a cheap check whether or not to broadcast an event.
  606.  
  607.     TLSeq<MonitorEntry>    mMonitors;    // Registered monitors
  608.     int            mGlobalMask;    // Global event mask
  609.     bool        mMonEnabled;    // Must be true to send events at all
  610.  
  611. public:
  612.     TLSearcher();
  613.     virtual ~TLSearcher();
  614.  
  615.     // - Solve() performs the actual search process, finding up to a given
  616.     //   maximum number of solutions. It is really a wrapper that calls the
  617.     //   algorithm-specific member functions of its derived classes.
  618.     //
  619.     // - Terminate() can be called during the search process to terminate it
  620.     //   right away.
  621.  
  622.     size_t         Solve(TLProblemRep *, size_t = 1);
  623.     virtual void    Terminate() = 0;
  624.  
  625.     // Information about the search process. The solutions are bound to
  626.     // change during the search.
  627.  
  628.     virtual const char *Description() const = 0;
  629.  
  630.     size_t        SolutionCount() const;
  631.     const TLSolutionSet&GetSolutions() const;
  632.  
  633.     const Stats &    GetStats() const;
  634.     int            GetLevel() const;
  635.  
  636.     // Functions to register and unregister a monitor, and to indicate the
  637.     // events it will receive.
  638.  
  639.     void        RegisterMonitor(TLSearchMonitor *);
  640.     void        DeregisterMonitor(TLSearchMonitor *);
  641.     void        SetMonitorEvents(TLSearchMonitor *, int);
  642.     bool        EnableMonitors(bool = true);
  643.  
  644.     // Access to the current problem representation
  645.  
  646.     TLProblemRep *    GetProblemRep() const;
  647.  
  648. protected:
  649.     // The following interface must be implemented by derived classes.
  650.     // The non-pure virtual functions have a reasonable default
  651.     // implementation and need not always be overridden.
  652.  
  653.     virtual bool     PreProcess();
  654.     virtual void    PostProcess();
  655.     virtual void    Search() = 0;
  656.  
  657.     // The following functions should be called to report the solution and
  658.     // search statistics. They may be overridden if desired.
  659.  
  660.     virtual void     ReportProgress();
  661.     virtual void     ReportSolutions();
  662.     virtual void     ReportStats();
  663.  
  664.     // The following functions mirror the problem representation interface.
  665.     // They should be called by derived searcher classes rather than
  666.     // addressing the problem representation directly, since this allows the
  667.     // searcher to inform its monitors of the pertinent events.
  668.  
  669.     size_t         CreateInitialProblem(TLProblemList &);
  670.     size_t        GenerateBranches(TLProblemState *, TLProblemList &);
  671.     void        EnterState(TLProblemState *);
  672.     bool        Process(TLProblemState *);
  673.     void        LeaveState(TLProblemState *, bool = true);
  674.     void        CreateSolution(TLProblemState *);
  675.  
  676.     // The following functions manage the storage of solutions.
  677.  
  678.     void        AddSolution(TLSolution *);
  679.     void        ClearSolutions();
  680.  
  681.     // Functions to register (with) an problem representation
  682.  
  683.     void        RegisterProblemRep(TLProblemRep *);
  684.     void        DeregisterProblemRep();
  685.  
  686. private:
  687.     // Implementation helper functions
  688.  
  689.     bool        MustSend(int);
  690.     void         SendEvent(const TLSearchMonitor::Event &);
  691.     void        UpdateEventMask();
  692. };
  693.  
  694. /*---------------------------------------------------------------------------
  695.     TLBTSearcherRcsv -
  696.  
  697.     Searcher class that implements a recursive backtrack search algorithm.
  698. ---------------------------------------------------------------------------*/
  699.  
  700. class _TLXCLASS TLBTSearcherRcsv: public TLSearcher
  701. {
  702.     bool        mTerminate;    // Termination flag
  703.  
  704. public:
  705.     TLBTSearcherRcsv();
  706.  
  707.     // Overridden version of the searcher functions
  708.  
  709.     virtual const char *Description() const;
  710.     virtual void    Terminate();
  711.  
  712. protected:
  713.     // Overridden version of the inherited search interface.
  714.  
  715.     virtual void    Search();
  716.  
  717. private:
  718.     // Recursive searching step
  719.  
  720.     bool         StepForward(TLProblemList &);
  721. };
  722.  
  723. /*---------------------------------------------------------------------------
  724.     TLBTSearcher -
  725.  
  726.     Non-recursive backtrack search algorithm.
  727. ---------------------------------------------------------------------------*/
  728.  
  729. class _TLXCLASS TLBTSearcher: public TLSearcher
  730. {
  731. protected:
  732.     // The non-recursive search algorithm maintains an explicit stack to
  733.     // keep track of the search progress. The stack consists of a linked
  734.     // list of search frames.
  735.  
  736.     class _TLXCLASS Frame: public TLSLink
  737.     {
  738.     friend class _TLXCLASS TLBTSearcher;
  739.     friend class _TLXCLASS TLBBSearcherDF;
  740.  
  741.     TLProblemList    mBranches;    // Branches at this level
  742.     index_t        mCurProblem;    // Index of current problem
  743.  
  744.     private:
  745.     Frame();
  746.     virtual ~Frame();
  747.  
  748.     // Access to parent frame (if any)
  749.  
  750.     Frame *        GetParent() const;
  751.  
  752.     // Subproblem iteration functions
  753.  
  754.     TLProblemState *CurrentProblem() const;
  755.     bool        NextProblem();
  756.     void        PrevProblem();
  757.     void        ResetProblem();
  758.     size_t        ProblemCount() const;
  759.     };
  760.  
  761.     enum {        // Searcher actions
  762.     actStop,       // Stop search
  763.     actExpand,    // Expand the current branch
  764.     actExplore,    // Explore the next branch of the current frame
  765.     actBacktrack,    // Leave the current branch
  766.     actBackjump,    // Backjump to a previous state
  767.     actRestart    // Restart from a previous state
  768.     };
  769.  
  770.     TLSLStack<Frame>    mStack;        // Search stack
  771.     int            mNextAction;    // Next searcher action
  772.     const Frame *    mMark;        // Target of backjump
  773.     bool         mUndoAll;    // Undo mode of backjump
  774.  
  775. public:
  776.     // We allow our clients to mark a position during the search and
  777.     // jump back to it later on.
  778.  
  779.     typedef const Frame *tMark;        // Marker type
  780.  
  781. public:
  782.     TLBTSearcher();
  783.     virtual ~TLBTSearcher();
  784.  
  785.     // Overridden versions of searcher functions
  786.  
  787.     virtual const char *Description() const;
  788.     virtual void    Terminate();
  789.  
  790.     // This version of the backtrack searcher allows a different mode of
  791.     // operation:
  792.     //
  793.     //        StartSearch(problem);
  794.     //       while (NextSolution())
  795.     //           PeekSolution()...
  796.     //       StopSearch();
  797.  
  798.     bool        StartSearch(TLProblemRep *);
  799.     bool        NextSolution();
  800.     void        StopSearch();
  801.     TLSolution *    PeekSolution() const;
  802.  
  803.     // Functions to influence the searcher's behavior. They may be called
  804.     // at any time. BackTrack() causes the searcher to fail the current
  805.     // variable/value assignment and continue with the next one; Terminate()
  806.     // terminates the search process altogether.
  807.  
  808.     tMark        GetMark() const;
  809.     void        BackTrack();
  810.  
  811.     // Functions to jump back to previous search levels. The back jump
  812.     // functions have an optional parameter that indicates whether all
  813.     // intermediate levels must be undone individually, or whether it
  814.     // suffices to undo only the last level before the target level. true
  815.     // indicates a complete undo of all levels.
  816.  
  817.     void        BackToLevel(int, bool = true);
  818.     void        BackToMark(tMark, bool = true);
  819.     void        BackToProblem(TLProblemState *, bool = true);
  820.     void        BackToVariable(TLVariable *, bool = true);
  821.  
  822.     // Functions to restart the search at a previous level. They are similar
  823.     // to the backjump functions, but they start node expansion all over
  824.     // again at the target node, instead of continuing with its next branch.
  825.  
  826.     void        RestartAtLevel(int, bool = true);
  827.     void        RestartAtMark(tMark, bool = true);
  828.     void        RestartAtProblem(TLProblemState *, bool = true);
  829.     void        RestartAtVariable(TLVariable *, bool = true);
  830.  
  831. protected:
  832.     // Overridden versions of the inherited search interface.
  833.  
  834.     virtual bool     PreProcess();
  835.     virtual void    PostProcess();
  836.     virtual void    Search();
  837.  
  838.     // The following functions may be overridden to modify 'fail' behavior.
  839.  
  840.     virtual bool        ContinueProblem(TLProblemState *);
  841.     virtual bool    ContinueSearch();
  842.  
  843. private:
  844.     // Implementation helper functions
  845.  
  846.     void        Push(Frame *);
  847.     Frame *        Pop();
  848.     Frame *        FindLevel(int);
  849.     Frame *        FindProblem(TLProblemState *);
  850.     Frame *        FindVariable(TLVariable *);
  851.     Frame *        UnwindToMark();
  852. };
  853.  
  854. /*---------------------------------------------------------------------------
  855.     TLBBSearcher -
  856.  
  857.     Branch & bound searching class. This class supports all variations of
  858.     search order: best-first, depth-first, breadth-first, or any
  859.     combination thereof. It must be used in conjunction with a
  860.     TLBBProblemRep-derived class.
  861. ---------------------------------------------------------------------------*/
  862.  
  863. class _TLXCLASS TLBBSearcher: public TLSearcher
  864. {
  865.     double        mIncumbent;    // Incumbent value
  866.     bool        mTerminate;    // Termination flag
  867.  
  868. public:
  869.     TLBBSearcher();
  870.  
  871.     // Overridden version of searcher functions
  872.  
  873.     virtual const char *Description() const;
  874.     virtual void    Terminate();
  875.  
  876.     // Function to set the incumbent value, possibly to establish a good
  877.     // lower bound before the search process proper starts.
  878.  
  879.     void        SetIncumbent(double);
  880.  
  881. protected:
  882.     // Overridden versions of the inherited search interface.
  883.  
  884.     virtual bool     PreProcess();
  885.     virtual void    Search();
  886. };
  887.  
  888. /*---------------------------------------------------------------------------
  889.     TLBBSearcherDF -
  890.  
  891.     Branch & bound searching class supporting only depth-first searches.
  892. ---------------------------------------------------------------------------*/
  893.  
  894. class _TLXCLASS TLBBSearcherDF: public TLBTSearcher
  895. {
  896.     double        mIncumbent;    // Incumbent value
  897.  
  898. public:
  899.     TLBBSearcherDF();
  900.  
  901.     // Overridden versions of searcher functions
  902.  
  903.     virtual const char *Description() const;
  904.  
  905.     // Function to set the incumbent value, possibly to estabish a good
  906.     // lower bound before the search process proper starts.
  907.  
  908.     double        GetIncumbent() const;
  909.     void        SetIncumbent(double);
  910.  
  911. protected:
  912.     // Overridden versions of the inherited search interface.
  913.  
  914.     virtual bool     PreProcess();
  915.     virtual void     ReportStats();
  916.  
  917.     // Overridden version of continuation functions - performs bounds checks
  918.  
  919.     virtual bool        ContinueProblem(TLProblemState *);
  920.     virtual bool    ContinueSearch();
  921. };
  922.  
  923. /*---------------------------------------------------------------------------
  924.     Inline functions
  925. ---------------------------------------------------------------------------*/
  926.  
  927. //----- TLSolution
  928.  
  929. inline ostream & _TLXFUNC operator <<(ostream &os, const TLSolution &s)
  930.     { return s.PrintOn(os); }
  931.  
  932. //----- TLProblemState
  933.  
  934. //inline TLProblemState *TLProblemState::GetParent() const
  935. //    { return mParent; }
  936.  
  937. inline ostream & _TLXFUNC operator <<(ostream &os, const TLProblemState &s)
  938.     { return s.PrintOn(os); }
  939.  
  940. //-----    TLProblemList
  941.  
  942. inline void TLProblemList::AddFront(TLProblemState *aProblem)
  943.     { TLPtrSeq<TLProblemState>::Append(aProblem); }
  944.  
  945. inline void TLProblemList::AddRear(TLProblemState *aProblem)
  946.     { TLPtrSeq<TLProblemState>::Prepend(aProblem); }
  947.  
  948. inline void TLProblemList::AddDepthFirst(TLProblemState *aProblem)
  949.     { AddFront(aProblem); }
  950.  
  951. inline void TLProblemList::AddBreadthFirst(TLProblemState *aProblem)
  952.     { AddRear(aProblem); }
  953.  
  954. inline void TLProblemList::AddBestFirst(TLProblemState *aProblem)
  955.     { TLPtrSeq<TLProblemState>::Insert(aProblem); }
  956.  
  957. inline TLProblemState *TLProblemList::PeekFirst() const
  958.     { return TLPtrSeq<TLProblemState>::PeekLast(); }
  959.  
  960. inline TLProblemState *TLProblemList::ExtractFirst()
  961.     { return TLPtrSeq<TLProblemState>::ExtractLast(); }
  962.  
  963. //-----    TLProblemRep
  964.  
  965. inline TLSearcher *TLProblemRep::GetSearcher() const
  966.     { return mSearcher; }
  967.  
  968. inline ostream & _TLXFUNC operator <<(ostream &os, const TLProblemRep &a)
  969.     { return a.PrintOn(os); }
  970.  
  971. //-----    TLSearchMonitor
  972.  
  973. inline TLSearchMonitor::Event::Event(int aCode, TLProblemState *aProblem)
  974.     : mCode(aCode), mProblem(aProblem) {}
  975.  
  976. #ifndef _NOBOOL
  977. inline
  978. TLSearchMonitor::Event::Event(int aCode, bool aP, TLProblemState *aProblem)
  979.     : mCode(aCode), mProblem(aProblem), mBoolParm(aP) {}
  980. #endif
  981.  
  982. inline
  983. TLSearchMonitor::Event::Event(int aCode, int16 aP, TLProblemState *aProblem)
  984.     : mCode(aCode), mProblem(aProblem), mInt16Parm(aP) {}
  985.  
  986. inline
  987. TLSearchMonitor::Event::Event(int aCode, int32 aP, TLProblemState *aProblem)
  988.     : mCode(aCode), mProblem(aProblem), mInt32Parm(aP) {}
  989.  
  990. inline
  991. TLSearchMonitor::Event::Event(int aCode, uint16 aP, TLProblemState *aProblem)
  992.     : mCode(aCode), mProblem(aProblem), mUint16Parm(aP) {}
  993.  
  994. inline
  995. TLSearchMonitor::Event::Event(int aCode, uint32 aP, TLProblemState *aProblem)
  996.     : mCode(aCode), mProblem(aProblem), mUint32Parm(aP) {}
  997.  
  998. inline
  999. TLSearchMonitor::Event::Event(int aCode, double aP, TLProblemState *aProblem)
  1000.     : mCode(aCode), mProblem(aProblem), mDoubleParm(aP) {}
  1001.  
  1002. inline int TLSearchMonitor::DefaultEvents() const
  1003.     { return TLSearcher::seAll; }
  1004.  
  1005. inline ostream & _TLXFUNC operator <<(ostream &os, const TLSearchMonitor &m)
  1006.     { return m.PrintOn(os); }
  1007.  
  1008. //-----    TLSearcher
  1009.  
  1010. inline TLSearcher::MonitorEntry::MonitorEntry()
  1011.     : mMonitor(0), mEventMask(0) {}
  1012.  
  1013. inline TLSearcher::MonitorEntry::MonitorEntry(TLSearchMonitor *aMon, int aMask)
  1014.     : mMonitor(aMon), mEventMask(aMask) {}
  1015.  
  1016. inline const TLSearcher::Stats &TLSearcher::GetStats() const
  1017.     { return mStats; }
  1018.  
  1019. inline size_t TLSearcher::SolutionCount() const
  1020.     { return mSolutions.Count(); }
  1021.  
  1022. inline const TLSolutionSet &TLSearcher::GetSolutions() const
  1023.     { return mSolutions; }
  1024.  
  1025. inline TLProblemRep *TLSearcher::GetProblemRep() const
  1026.     { return mProblemRep; }
  1027.  
  1028. inline int TLSearcher::GetLevel() const
  1029.     { return mStats.mDepth; }
  1030.  
  1031. inline bool TLSearcher::MustSend(int aEvent)
  1032.     { return mMonEnabled && ((mGlobalMask & aEvent) == aEvent); }
  1033.  
  1034. //-----    TLBTSearcher
  1035.  
  1036. inline TLBTSearcher::Frame *TLBTSearcher::Frame::GetParent() const
  1037.     { return (Frame *)Next(); }
  1038.  
  1039. inline size_t TLBTSearcher::Frame::ProblemCount() const
  1040.     { return mBranches.Count(); }
  1041.  
  1042. //-----    TLBBSearcherDF
  1043.  
  1044. inline double TLBBSearcherDF::GetIncumbent() const
  1045.     { return mIncumbent; }
  1046.  
  1047. #endif    // _TLX_SEARCHER_H
  1048.