home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SRC / BTSEARCH.CPP < prev    next >
C/C++ Source or Header  |  1996-07-08  |  27KB  |  786 lines
  1. /****************************************************************************
  2.     $Id: btsearch.cpp 501.0 1995/03/07 12:26:10 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.     Implementation of class TLBTSearcher. Class TLBTSearcher implements a
  10.     non-recursive backtrack search algorithm with provisions for
  11.     backjumping.
  12.  
  13.     $Log: btsearch.cpp $
  14.     Revision 501.0  1995/03/07 12:26:10  RON
  15.     Updated for TLX 5.01
  16.     Revision 1.10  1995/02/28 15:10:06  RON
  17.     Update for release 012
  18.     Added partial support for SunPro C++ compiler
  19.     Revision 1.9  1995/01/13  15:30:01  ron
  20.     Added extra ContinueSearch() check to replace termination by
  21.     number of solutions found
  22.  
  23.     Revision 1.8  1995/01/12  13:38:01  ron
  24.     Adapted to previous Searcher/ProblemRep model
  25.  
  26.     Revision 1.7  1995/01/06  15:55:56  ron
  27.     Adapted to new Searcher/Problem model
  28.  
  29.     Revision 1.6  1995/01/05  15:21:38  ron
  30.     Formatting and naming changes
  31.  
  32.     Revision 1.5  1994/11/16  15:37:00  ron
  33.     Adapted to group-style tracing
  34.     Added module info; rearranged #include directives
  35.  
  36.     Revision 1.4  1994/10/11  19:02:04  ron
  37.     Replaced DeadEnd() + SolveProblem() by ProcessProblem()
  38.     Changed RestartAt...() slightly
  39.     Removed several Frame member functions
  40.  
  41.     Revision 1.3  1994/10/10  16:46:23  ron
  42.     Added searcher description
  43.     Changed checking of actions to catch alternative actions sooner
  44.  
  45.     Revision 1.2  1994/10/07  17:01:16  ron
  46.     Changed UnregisterSearcher() to DeregisterSearcher()
  47.     Changed direct references to problem representation to go through
  48.     searcher interface
  49.  
  50.     Revision 1.1  1994/10/06  17:43:36  ron
  51.     Initial revision
  52.  
  53. ****************************************************************************/
  54.  
  55. #include <tlx\501\_build.h>
  56.  
  57. TLX_MODULE_INFO("$Revision: 501.0 $");
  58.  
  59. #include <stdio.h>
  60. #include <tlx\501\except.h>
  61. #include <tlx\501\solve\csp.h>
  62. #include <tlx\501\solve\searcher.h>
  63.  
  64. /*---------------------------------------------------------------------------
  65.     Template instantiations
  66. ---------------------------------------------------------------------------*/
  67.  
  68. #if defined(THINK_CPLUS)
  69.     #include "pointer.cpp"
  70.     #include "slstack.cpp"
  71.     #pragma template TLCountedPtr<TLProblemState>;
  72.     #pragma template TLSLStack<TLBTSearcher::Frame>;
  73. #elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__SC__) || defined(__WATCOMC__)
  74.     #include <tlx\501\template\pointer.cpp>
  75.     #include <tlx\501\template\slstack.cpp>
  76. #elif defined(__SUNPRO_CC)
  77.     #include <tlx\501\template\pointer.cpp>
  78.     #include <tlx\501\template\slstack.cpp>
  79. #elif defined(__IBMCPP__)
  80.   #if __IBMCPP__ < 300
  81.     #pragma implementation("tlx\\template\\pointer.cpp")
  82.     #pragma implementation("tlx\\template\\slstack.cpp")
  83.   #else
  84.     #include <tlx\501\template\pointer.cpp>
  85.     #include <tlx\501\template\slstack.cpp>
  86.   #endif
  87. #else
  88.     #error Unsupported compiler; contact Tarma Software Research
  89. #endif
  90.  
  91. /****************************************************************************
  92.     Implementation of TLBTSearcher::Frame class
  93. ****************************************************************************/
  94.  
  95. /*-------------------------------------------------------------------------*/
  96.     TLBTSearcher::Frame::Frame()
  97.  
  98. /*  Default constructor. Sets all data members to 0.
  99. ---------------------------------------------------------------------------*/
  100. : mBranches(50, 50)
  101. {
  102.     ResetProblem();            // Resets mCurProblem
  103. }
  104.  
  105. /*-------------------------------------------------------------------------*/
  106.     TLBTSearcher::Frame::~Frame()
  107.  
  108. /*  Destructor. Deletes associated branches (if any). The frame must have
  109.     been removed from the stack when the destructor is called.
  110. ---------------------------------------------------------------------------*/
  111. {
  112.     // TODO: Clean up list of branches
  113. }
  114.  
  115. /*-------------------------------------------------------------------------*/
  116.     TLProblemState *TLBTSearcher::Frame::CurrentProblem() const
  117.  
  118. /*  Returns a pointer to the current subproblem amongst the branches in
  119.     the frame. It is an error to call this routine when the Next()
  120.     iterator has been exhausted.
  121. ---------------------------------------------------------------------------*/
  122. {
  123.     TLX_ASSERT(mCurProblem >= mBranches.Mini());
  124.     TLX_ASSERT(mCurProblem <= mBranches.Maxi());
  125.  
  126.     return mBranches.PeekAt(mCurProblem);
  127. }
  128.  
  129. /*-------------------------------------------------------------------------*/
  130.     bool TLBTSearcher::Frame::NextProblem()
  131.  
  132. /*  Advances the internal node iterator, returning true iff a valid search
  133.     node is available.
  134. ---------------------------------------------------------------------------*/
  135. {
  136.     return --mCurProblem >= mBranches.Mini();
  137. }
  138.  
  139. /*-------------------------------------------------------------------------*/
  140.     void TLBTSearcher::Frame::PrevProblem()
  141.  
  142. /*  Moves the internal node iterator back to the previous node in the frame
  143.     (if any).
  144. ---------------------------------------------------------------------------*/
  145. {
  146.     if (mCurProblem <= mBranches.Maxi()) mCurProblem++;
  147. }
  148.  
  149. /*-------------------------------------------------------------------------*/
  150.     void TLBTSearcher::Frame::ResetProblem()
  151.  
  152. /*  Resets the internal subproblem iterator. After a call to this routine,
  153.     a call to NextProblem() is necessary to point the iterator at the first
  154.     subproblem (if any) in the frame.
  155. ---------------------------------------------------------------------------*/
  156. {
  157.     mCurProblem = mBranches.Maxi() + 1;
  158. }
  159.  
  160. /****************************************************************************
  161.     Implementation of TLBTSearcher class
  162. ****************************************************************************/
  163.  
  164. /*-------------------------------------------------------------------------*/
  165.     TLBTSearcher::TLBTSearcher()
  166.  
  167. /*  Default constructor. Initializes empty frame stack.
  168. ---------------------------------------------------------------------------*/
  169. {
  170.     mNextAction = actStop;
  171.     mMark     = 0;
  172.     mUndoAll     = true;
  173.  
  174.     mStack.BecomeOwner();    // Will discard frames on destruction
  175. }
  176.  
  177. /*-------------------------------------------------------------------------*/
  178.     TLBTSearcher::~TLBTSearcher()
  179.  
  180. /*  Destructor. Cleans up whatever is left on the search frame stack.
  181. ---------------------------------------------------------------------------*/
  182. {
  183.     // Performed automatically by mStack if it's the owner
  184.     TLX_ASSERT(mStack.IsOwner());
  185. }
  186.  
  187. /*-------------------------------------------------------------------------*/
  188.     void TLBTSearcher::BackToLevel(int aLevel, bool aUndoAll)
  189.  
  190. /*  Initiates a back-jump to the given search level. It is an error to
  191.     backjump if the search stack is empty.
  192. ---------------------------------------------------------------------------*/
  193. {
  194.     BackToMark(FindLevel(aLevel), aUndoAll);
  195. }
  196.  
  197. /*-------------------------------------------------------------------------*/
  198.     void TLBTSearcher::BackToMark(tMark aMark, bool aUndoAll)
  199.  
  200. /*  Jumps back to a previously obtained mark and continues searching from
  201.     there. This will only work if the search process is currently deeper
  202.     along the same search path than when the mark was first obtained. If
  203.     this is not the case, the entire search stack will unwind.
  204.  
  205.     The optional 'aUndoAll' parameter indicates whether or not each level
  206.     between the current and the target must be individually undone. If this
  207.     parameter is true (the default), this is indeed the case. If the
  208.     parameter is false, only the last level before the target is undone;
  209.     all other undo buffers are ignored. This latter behavior is useful in
  210.     cases where each undo buffer contains a full snapshot of the
  211.     problem representation's state; in those cases, it is useless and
  212.     inefficient to undo more than the last level before the target.
  213.  
  214.     The marker is simply a pointer to the current top of the stack.
  215. ---------------------------------------------------------------------------*/
  216. {
  217.     TLX_ASSERT_PTR(aMark);
  218.  
  219.     mMark     = aMark;
  220.     mUndoAll     = aUndoAll;
  221.     mNextAction = actBackjump;
  222. }
  223.  
  224. /*-------------------------------------------------------------------------*/
  225.     void TLBTSearcher::BackToProblem(TLProblemState *aProblem, bool aUndoAll)
  226.  
  227. /*  Initiates a back-jump to a given subproblem.
  228. ---------------------------------------------------------------------------*/
  229. {
  230.     TLX_ASSERT_PTR(aProblem);
  231.     BackToMark(FindProblem(aProblem), aUndoAll);
  232. }
  233.  
  234. /*-------------------------------------------------------------------------*/
  235.     void TLBTSearcher::BackToVariable(TLVariable *aVar, bool aUndoAll)
  236.  
  237. /*  Initiates a back-jump to a given variable, provided that the variable
  238.     has a link to the subproblem of which it is part.
  239. ---------------------------------------------------------------------------*/
  240. {
  241.     TLX_ASSERT_PTR(aVar);
  242.     BackToMark(FindVariable(aVar), aUndoAll);
  243. }
  244.  
  245. /*-------------------------------------------------------------------------*/
  246.     void TLBTSearcher::BackTrack()
  247.  
  248. /*  Indicates to the searcher that some dead-end has been reached, and that
  249.     a backtrack should be performed as the next action.
  250. ---------------------------------------------------------------------------*/
  251. {
  252.     mNextAction = actBacktrack;
  253. }
  254.  
  255. /*-------------------------------------------------------------------------*/
  256.     bool TLBTSearcher::ContinueProblem(TLProblemState *)
  257.  
  258. /*  Called to check if the current node may be continued after it has been
  259.     entered by the searcher. In this implementation, the check will always
  260.     succeed.
  261. ---------------------------------------------------------------------------*/
  262. {
  263.     return true;
  264. }
  265.  
  266. /*-------------------------------------------------------------------------*/
  267.     bool TLBTSearcher::ContinueSearch()
  268.  
  269. /*  Called to determine whether or not the search process at large must be
  270.     continued after finding a solution. The default version returns true
  271.     as long as not sufficient solutions are found.
  272. ---------------------------------------------------------------------------*/
  273. {
  274.     return SolutionCount() < GetStats().mMaxSol;
  275. }
  276.  
  277. /*-------------------------------------------------------------------------*/
  278.     const char *TLBTSearcher::Description() const
  279.  
  280. /*  Returns a description of the searcher.
  281. ---------------------------------------------------------------------------*/
  282. {
  283.     return "Nonrecursive backtrack searcher";
  284. }
  285.  
  286. /*-------------------------------------------------------------------------*/
  287.     TLBTSearcher::Frame *TLBTSearcher::FindLevel(int aLevel)
  288.  
  289. /*  Finds the frame corresponding to the given level. If the level is not
  290.     valid, 0 is returned.
  291. ---------------------------------------------------------------------------*/
  292. {
  293.     // Find the frame that corresponds to the given level
  294.  
  295.     TLX_ASSERT(GetLevel() == mStack.Count());
  296.     int level = GetLevel();
  297.  
  298.     for (Frame *frame = mStack.PeekTop(); frame; frame = frame->GetParent(),
  299.      level--)
  300.        if (level == aLevel)
  301.         return frame;
  302.  
  303.     // If we get here, the level wasn't found
  304.  
  305.     TLX_TRACE_ERROR(TLX, ("Level %d not found (current=%d)", aLevel, level));
  306.     return 0;
  307. }
  308.  
  309. /*-------------------------------------------------------------------------*/
  310.     TLBTSearcher::Frame *TLBTSearcher::FindProblem(TLProblemState *aProblem)
  311.  
  312. /*  Finds the frame corresponding to a given subproblem. If the node is
  313.     not found, 0 is returned.
  314. ---------------------------------------------------------------------------*/
  315. {
  316.     TLX_ASSERT_PTR(aProblem);
  317.  
  318.     // Find the frame that holds the node
  319.  
  320.     for (Frame *frame = mStack.PeekTop(); frame; frame = frame->GetParent())
  321.     if (frame->CurrentProblem() == aProblem)
  322.         return frame;
  323.  
  324.     // If we get here, the problem wasn't found
  325.  
  326.     TLX_TRACE_WARN(TLX, ("Subproblem not found"));
  327.     return 0;
  328. }
  329.  
  330. /*-------------------------------------------------------------------------*/
  331.     TLBTSearcher::Frame *TLBTSearcher::FindVariable(TLVariable *aVar)
  332.  
  333. /*  Finds the frame that corresponds to the given variable instantiation.
  334.     This will only work if the variable has a back link to its subproblem.
  335. ---------------------------------------------------------------------------*/
  336. {
  337.     TLX_ASSERT_PTR(aVar);
  338.  
  339.     if (!aVar->GetProblem())
  340.     {
  341.     TLX_TRACE_ERROR(TLX, ("Variable %s has no problem", aVar->GetName()));
  342.     return 0;
  343.     }
  344.  
  345.     // Actual target is found by looking for the node
  346.  
  347.     return FindProblem(aVar->GetProblem());
  348. }
  349.  
  350. /*-------------------------------------------------------------------------*/
  351.     TLBTSearcher::tMark TLBTSearcher::GetMark() const
  352.  
  353. /*  Returns a marker for the current position on the search stack. The
  354.     marker can be used to jump back to the current state later on.
  355.  
  356.     The marker is simply a pointer to the current top of the stack.
  357. ---------------------------------------------------------------------------*/
  358. {
  359.     return mStack.IsEmpty() ? 0 : mStack.PeekTop();
  360. }
  361.  
  362. #if defined(_MSC_VER) && _MSC_VER < 1011
  363. // This version of MSVC generates erroneous code here
  364. #pragma optimize("gia", off)
  365. #endif
  366.  
  367. /*-------------------------------------------------------------------------*/
  368.     bool TLBTSearcher::NextSolution()
  369.  
  370. /*  Searches for the next solution, returning true if it finds one. If a
  371.     solution is found, it is available through PeekSolution().
  372.  
  373.     The search routine is implemented as a loop that attempts one
  374.     variable selection or value association per iteration, or backtracks
  375.     over previous assignments. The user can influence the search loop by
  376.     a selected number of functions:
  377.  
  378.     - BackTrack() backtracks over the current selection and requests a new
  379.     - JumpToXXX() backjumps to a previous state
  380.     - Terminate() terminates the search process altogether
  381. ---------------------------------------------------------------------------*/
  382. {
  383. #if defined(_MSC_VER) && _MSC_VER < 1011
  384. // This version of MSVC generates erroneous code here
  385. #pragma message("This version of Microsoft Visual C++ generates faulty code")
  386. #endif
  387.  
  388.     while (mNextAction != actStop && !mStack.IsEmpty())
  389.     {
  390.         Frame *curframe = mStack.PeekTop();
  391.  
  392.     switch (mNextAction)
  393.     {
  394.         case actExpand:         // Try to advance the search process
  395.         {
  396.         TLX_TRACE(TLX, (50, "BTSearch: actExpand"));
  397.  
  398.         // Default action after the branch is an assignment,
  399.         // but either the user or the search process itself may
  400.         // change that. We set the default action here to leave
  401.         // room for changes by routines that are called during
  402.         // the lines that follow.
  403.  
  404.         mNextAction = actExplore;
  405.  
  406.         // Create a new frame to hold the new branches. If we have
  407.         // a current frame, then expand its current subproblem,
  408.         // else create the initial branches.
  409.  
  410.         Frame *newframe = new Frame;
  411.  
  412.         TLX_ASSERT_PTR(newframe);
  413.         TLX_ASSERT_PTR(curframe);
  414.         TLX_ASSERT_PTR(curframe->CurrentProblem());
  415.  
  416.         bool expansion = GenerateBranches(curframe->CurrentProblem(),
  417.                        newframe->mBranches);
  418.  
  419.         if (expansion)
  420.         {
  421.             // We have expanded: add the frame to the stack and
  422.             // continue the default action (actExplore) or whatever
  423.             // other action may be set in the meantime.
  424.  
  425.             Push(newframe);
  426.             newframe->ResetProblem();
  427.         }
  428.         else
  429.         {
  430.             delete newframe;
  431.             newframe = 0;
  432.  
  433.             // Cannot expand current node - assume solution found
  434.  
  435.             CreateSolution(curframe->CurrentProblem());
  436.             TLX_TRACE(TLX, (40, "BTSearch: Solution %d found",
  437.                       SolutionCount()));
  438.  
  439.             // Next action is a backtrack to obtain the next solution
  440.             // (if we ever get called back again).
  441.  
  442.             if (mNextAction == actExplore)
  443.                 mNextAction = actBacktrack;
  444.             return true;
  445.         }
  446.         break;
  447.         }
  448.         case actExplore:        // Explore branches of current frame
  449.         TLX_TRACE(TLX, (50, "BTSearch: actExplore"));
  450.         TLX_ASSERT_PTR(curframe);
  451.  
  452.         mNextAction = actExpand;
  453.  
  454.         if (curframe->NextProblem())
  455.         {
  456.             TLProblemState *curproblem = curframe->CurrentProblem();
  457.             TLX_ASSERT_PTR(curproblem);
  458.             EnterState(curproblem);
  459.  
  460.             // Check if the problem's exploration may be continued.
  461.             // This may cause the next action to be changed from its
  462.             // default action (which is to branch). In any case,
  463.             // if the node cannot be continued, we make sure that
  464.             // the next action is *not* to branch.
  465.  
  466.             if ((!Process(curproblem) ||
  467.                  !ContinueProblem(curproblem)) &&
  468.             mNextAction == actExpand)
  469.             mNextAction = actBacktrack;
  470.         }
  471.         else
  472.         {
  473.             // No (more) branches in the frame -- discard the frame
  474.             // and return to one level up.
  475.  
  476.             delete Pop();
  477.  
  478.             if (mStack.IsEmpty())
  479.             mNextAction = actStop;
  480.             else if (mNextAction == actExpand)
  481.                 mNextAction = actBacktrack;
  482.         }
  483.         break;
  484.  
  485.         case actBacktrack:        // Leave current subproblem
  486.         TLX_TRACE(TLX, (50, "BTSearch: actBacktrack"));
  487.  
  488.         TLX_ASSERT_PTR(curframe);
  489.         TLX_ASSERT_PTR(curframe->CurrentProblem());
  490.  
  491.         LeaveState(curframe->CurrentProblem());
  492.         mNextAction = actExplore;
  493.         break;
  494.  
  495.         case actBackjump:        // Backjump to a previous state
  496.         TLX_TRACE(TLX, (50, "BTSearch: actBackjump"));
  497.  
  498.         if (UnwindToMark() != 0)
  499.             mNextAction = actExplore;
  500.         else
  501.         {
  502.             TLX_TRACE_ERROR(TLX, ("Bad backjump, search stopped"));
  503.  
  504.             mNextAction = actStop;
  505.         }
  506.         break;
  507.  
  508.         case actRestart:        // Restart from a previous state
  509.         TLX_TRACE(TLX, (50, "BTSearch: actRestart"));
  510.  
  511.         if ((curframe = UnwindToMark()) != 0)
  512.         {
  513.             // Go back one position, because exploration will start
  514.             // by advancing the node iterator.
  515.  
  516.             curframe->PrevProblem();
  517.             mNextAction = actExplore;
  518.         }
  519.         else
  520.         {
  521.             TLX_TRACE_ERROR(TLX, ("Bad restart, search stopped"));
  522.  
  523.             mNextAction = actStop;
  524.         }
  525.         break;
  526.  
  527.         default:
  528.         TLX_ASSERT_UNREACHABLE;
  529.         break;
  530.     }
  531.     }
  532.  
  533.     // If we get here, there were no more solutions
  534.     return false;
  535. }
  536.  
  537. #if defined(_MSC_VER) && _MSC_VER < 1011
  538. #pragma optimize( "", on)
  539. #endif
  540.  
  541. /*-------------------------------------------------------------------------*/
  542.     TLSolution *TLBTSearcher::PeekSolution() const
  543.  
  544. /*  Returns a pointer to the current (i.e. last obtained) solution. It is
  545.     an error to call this function if there are no solutions.
  546. ---------------------------------------------------------------------------*/
  547. {
  548.     return GetSolutions().PeekLast();
  549. }
  550.  
  551. /*-------------------------------------------------------------------------*/
  552.     TLBTSearcher::Frame *TLBTSearcher::Pop()
  553.  
  554. /*  Removes the top level search frame from the search stack and returns
  555.     a pointer to it.
  556. ---------------------------------------------------------------------------*/
  557. {
  558.     TLX_ASSERT(!mStack.IsEmpty());
  559.     return mStack.Pop();
  560. }
  561.  
  562. /*-------------------------------------------------------------------------*/
  563.     void TLBTSearcher::PostProcess()
  564.  
  565. /*  Called to clean up after the search is completed. It discards the
  566.     search stack, then calls the inherited postprocessing function.
  567. ---------------------------------------------------------------------------*/
  568. {
  569.     TLSearcher::PostProcess();
  570. }
  571.  
  572. /*-------------------------------------------------------------------------*/
  573.     bool TLBTSearcher::PreProcess()
  574.  
  575. /*  Called to prepare for the search. It calls the inherited version, then
  576.     cleans up the search stack that might be left over from previous
  577.     searches (if any) and initializes the search state.
  578. ---------------------------------------------------------------------------*/
  579. {
  580.     if (!TLSearcher::PreProcess())
  581.     return false;
  582.  
  583.     mNextAction = actExplore;        // Start with exploration of root
  584.     mUndoAll     = true;
  585.     mMark     = 0;
  586.  
  587.     mStack.RemoveAll();
  588.  
  589.     return true;
  590. }
  591.  
  592. /*-------------------------------------------------------------------------*/
  593.     void TLBTSearcher::Push(Frame *aFrame)
  594.  
  595. /*  Pushes a new frame on top of the search stack.
  596. ---------------------------------------------------------------------------*/
  597. {
  598.     TLX_ASSERT_PTR(aFrame);
  599.     mStack.Push(aFrame);
  600. }
  601.  
  602. /*-------------------------------------------------------------------------*/
  603.     void TLBTSearcher::RestartAtLevel(int aLevel, bool aUndoAll)
  604.  
  605. /*  Initiates a restart from the given search level. It is an error to
  606.     restart if the search stack is empty.
  607. ---------------------------------------------------------------------------*/
  608. {
  609.     RestartAtMark(FindLevel(aLevel), aUndoAll);
  610. }
  611.  
  612. /*-------------------------------------------------------------------------*/
  613.     void TLBTSearcher::RestartAtMark(tMark aMark, bool aUndoAll)
  614.  
  615. /*  Jumps back to a previously obtained mark, then restarts from scratch
  616.     at that point. This will only work if the search process is currently
  617.     deeper along the same search path than when the mark was first obtained.
  618.     If this is not the case, the entire search stack will unwind.
  619.  
  620.     The optional 'aUndoAll' parameter indicates whether or not each level
  621.     between the current and the target must be individually undone. If this
  622.     parameter is true (the default), this is indeed the case. If the
  623.     parameter is false, only the last level before the target is undone;
  624.     all other undo buffers are ignored. This latter behavior is useful in
  625.     cases where each undo buffer contains a full snapshot of the
  626.     problem representation's state; in those cases, it is useless and inefficient to
  627.     undo more than the last level before the target.
  628.  
  629.     The marker is simply a pointer to the current top of the stack.
  630. ---------------------------------------------------------------------------*/
  631. {
  632.     TLX_ASSERT_PTR(aMark);
  633.  
  634.     mMark     = aMark;
  635.     mUndoAll     = aUndoAll;
  636.     mNextAction = actRestart;
  637. }
  638.  
  639. /*-------------------------------------------------------------------------*/
  640.     void TLBTSearcher::RestartAtProblem(TLProblemState *aProblem, bool aUndoAll)
  641.  
  642. /*  Initiates a restart from a given node.
  643. ---------------------------------------------------------------------------*/
  644. {
  645.     TLX_ASSERT_PTR(aProblem);
  646.     RestartAtMark(FindProblem(aProblem), aUndoAll);
  647. }
  648.  
  649. /*-------------------------------------------------------------------------*/
  650.     void TLBTSearcher::RestartAtVariable(TLVariable *aVar, bool aUndoAll)
  651.  
  652. /*  Initiates a restart from a given variable, provided that the variable
  653.     has a link to the subproblem of which it is part.
  654. ---------------------------------------------------------------------------*/
  655. {
  656.     TLX_ASSERT_PTR(aVar);
  657.     RestartAtMark(FindVariable(aVar), aUndoAll);
  658. }
  659.  
  660. /*-------------------------------------------------------------------------*/
  661.     void TLBTSearcher::Search()
  662.  
  663. /*  Searches up to a given maximum of solutions.
  664. ---------------------------------------------------------------------------*/
  665. {
  666.     TLX_TRACE(TLX, (40, "BTSearch: Search starts"));
  667.  
  668.     // Preprocessing must have been performed
  669.  
  670.     TLX_ASSERT(mStack.IsEmpty());
  671.     TLX_ASSERT(mNextAction == actExplore);
  672.  
  673.     // Create the initial set of problems
  674.  
  675.     Frame *root = new Frame;
  676.     TLX_ASSERT_PTR(root);
  677.  
  678.     if (CreateInitialProblem(root->mBranches) < 1)
  679.     {
  680.     TLX_TRACE_WARN(TLX, ("No initial problems created - search aborted"));
  681.     delete root;
  682.     return;
  683.     }
  684.  
  685.     root->ResetProblem();
  686.     Push(root);
  687.  
  688.     // Find the requested number of solutions
  689.  
  690.     while (NextSolution() && ContinueSearch())
  691.     ;
  692.  
  693.     TLX_TRACE(TLX, (40, "BTSearch: Search stopped"));
  694. }
  695.  
  696. /*-------------------------------------------------------------------------*/
  697.     bool TLBTSearcher::StartSearch(TLProblemRep *aRep)
  698.  
  699. /*  Starts a new search process, returning true if it succeeds.
  700. ---------------------------------------------------------------------------*/
  701. {
  702.     TLX_ASSERT_PTR(aRep);
  703.  
  704.     RegisterProblemRep(aRep);
  705.  
  706.     if (!PreProcess())
  707.     {
  708.         DeregisterProblemRep();
  709.     return false;
  710.     }
  711.  
  712.     TLX_ASSERT(mStack.IsEmpty());
  713.     TLX_ASSERT(mNextAction == actExplore);
  714.  
  715.     // Create the initial set of problems
  716.  
  717.     Frame *root = new Frame;
  718.     TLX_ASSERT_PTR(root);
  719.  
  720.     if (CreateInitialProblem(root->mBranches) < 1)
  721.     {
  722.     TLX_TRACE_WARN(TLX, ("No initial problems created - search aborted"));
  723.     delete root;
  724.     return false;
  725.     }
  726.  
  727.     Push(root);
  728.     return true;
  729. }
  730.  
  731. /*-------------------------------------------------------------------------*/
  732.     void TLBTSearcher::StopSearch()
  733.  
  734. /*  Terminates the search process.
  735. ---------------------------------------------------------------------------*/
  736. {
  737.     PostProcess();
  738.     DeregisterProblemRep();
  739. }
  740.  
  741. /*-------------------------------------------------------------------------*/
  742.     void TLBTSearcher::Terminate()
  743.  
  744. /*  Indicates to the searcher that the search process should be terminated
  745.     altogether.
  746. ---------------------------------------------------------------------------*/
  747. {
  748.     mNextAction = actStop;
  749. }
  750.  
  751. /*-------------------------------------------------------------------------*/
  752.     TLBTSearcher::Frame *TLBTSearcher::UnwindToMark()
  753.  
  754. /*  Unwinds the current search stack until the current 'mMark' mark is
  755.     found. Intermediate nodes are left if the 'mUndoAll' flag is set; the
  756.     final node (i.e. the current node of the target frame) is always left.
  757.     Intermediate frames are discarded.
  758.  
  759.     The function returns the target frame, or 0 if the stack was unwound
  760.     completely.
  761. ---------------------------------------------------------------------------*/
  762. {
  763.     Frame *frame;
  764.     while ((frame = mStack.PeekTop()) != 0)
  765.     {
  766.     TLX_ASSERT_PTR(frame->CurrentProblem());
  767.  
  768.     LeaveState(frame->CurrentProblem(), mUndoAll || mMark == frame);
  769.  
  770.     // If we found the frame, we're done
  771.  
  772.     if (mMark == frame)
  773.         return frame;
  774.  
  775.     // Still not at the desired frame - discard current level
  776.  
  777.     delete Pop();
  778.     }
  779.  
  780.     // If we get here, the stack was unwound without finding the frame
  781.  
  782.     TLX_TRACE_WARN(TLX, ("Stack unwinding completely unwound stack"));
  783.     return 0;
  784. }
  785.  
  786.