home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Shareware BBS: 10 Tools
/
10-Tools.zip
/
tlx501.zip
/
SRC
/
SEARCHER.CPP
< prev
next >
Wrap
C/C++ Source or Header
|
1996-09-27
|
21KB
|
628 lines
/****************************************************************************
$Id: searcher.cpp 501.0 1995/03/07 12:26:20 RON Exp $
Copyright (c) 1991-95 Tarma Software Research. All rights reserved.
Project: Tarma Library for C++ V5.0
Author: Ron van der Wal
Implementation of class TLSearcher. This class is the abstract base
class for all searcher algorithms.
$Log: searcher.cpp $
Revision 501.0 1995/03/07 12:26:20 RON
Updated for TLX 5.01
Revision 1.15 1995/02/28 15:13:24 RON
Update for release 012
Added partial support for SunPro C++ compiler
Revision 1.14 1995/01/18 10:39:01 ron
Added subproblem parameter to search monitor events
Revision 1.13 1995/01/17 17:02:21 ron
Added number of solutions to progress message
Revision 1.12 1995/01/13 16:02:54 ron
Added parameter to CreateSolution call
Revision 1.11 1995/01/13 15:34:13 ron
Changed CreateSolution() to only create new solutions if
the required number has not been reached yet
Revision 1.10 1995/01/12 13:41:03 ron
Adapted to previous Searcher/ProblemRep model
Revision 1.9 1995/01/10 16:33:13 ron
Added progress message every 100 processed problems
Added check for initial problem instead of assertion
Revision 1.8 1995/01/08 11:47:15 ron
Changed type of depth from int32 to int
Changed first level of depth counting from 1 to 0
Revision 1.7 1995/01/06 15:56:54 ron
Adapted to new Searcher/Problem model
Revision 1.6 1995/01/05 15:28:07 ron
Naming changes
Revision 1.5 1994/11/16 15:42:38 ron
Adapted to group-style tracing
Added module info; rearranged #include directives
Revision 1.4 1994/10/11 19:04:40 ron
Replaced DeadEnd() + SolveProblem() by ProcessProblem()
Revision 1.3 1994/10/10 16:54:46 ron
Moved definition of searcher events to TLSearcher
Revision 1.2 1994/10/07 17:05:05 ron
Added support for search monitors
Revision 1.1 1994/10/06 17:44:55 ron
Initial revision
****************************************************************************/
#include <tlx\501\_build.h>
TLX_MODULE_INFO("$Revision: 501.0 $");
#include <iostream.h>
#include <stdio.h>
#include <time.h>
#include <tlx\501\log.h>
#include <tlx\501\solve\searcher.h>
/*---------------------------------------------------------------------------
Template instantiations
---------------------------------------------------------------------------*/
#if defined(THINK_CPLUS)
#include "ptrseq.cpp"
#include "seq.cpp"
#pragma template TLPtrSeq<TLSolution>;
#pragma template TLPtrSeqIter<TLSolution>;
#pragma template TLSeq<TLSearcher::MonitorEntry>;
#elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__SC__) || defined(__WATCOMC__)
#include <tlx\501\template\ptrseq.cpp>
#include <tlx\501\template\seq.cpp>
#elif defined(__SUNPRO_CC)
#include <tlx\501\template\ptrseq.cpp>
#include <tlx\501\template\seq.cpp>
#elif defined(__IBMCPP__)
#if __IBMCPP__ < 300
#pragma implementation("tlx\\template\\ptrseq.cpp")
#pragma implementation("tlx\\template\\seq.cpp")
#else
#include <tlx\501\template\ptrseq.cpp>
#include <tlx\501\template\seq.cpp>
#endif
#else
#error Unsupported compiler; contact Tarma Software Research
#endif
/*-------------------------------------------------------------------------*/
TLSearcher::TLSearcher()
/* Default constructor; resets contents of searcher.
---------------------------------------------------------------------------*/
: mSolutions(100, 100), mMonitors(10, 10)
{
mSolutions.BecomeOwner(true); // Will delete contents
mPrevSearcher = 0;
mProblemRep = 0;
mStats.mMaxSol = 0;
mStats.mBTCount =
mStats.mProblemCount = 0;
mStats.mDepth = 0;
mStats.mStart =
mStats.mPrevious =
mStats.mFinish = 0;
mGlobalMask = seNone;
mMonEnabled = false;
}
/*-------------------------------------------------------------------------*/
TLSearcher::~TLSearcher()
/* Destructor. Discards the solutions (if any).
---------------------------------------------------------------------------*/
{
// Solutions are automatically discarded
TLX_ASSERT(mSolutions.IsOwner());
if (mProblemRep)
{
TLX_TRACE_ERROR(TLX, ("Searcher linked to ProblemRep on destruction"));
if (mProblemRep->mSearcher == this)
DeregisterProblemRep();
TLX_ASSERT_NULL(mProblemRep);
}
}
/*-------------------------------------------------------------------------*/
void TLSearcher::AddSolution(TLSolution *aSolution)
/* Adds the given solution and updates the relevant statistics.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aSolution);
mSolutions.Append(aSolution);
mStats.mPrevious = mStats.mFinishSearch;
time(&mStats.mFinishSearch);
TLX_LOG_ENTRY("Solution #%u (%ld nodes processed)", mSolutions.Count(),
mStats.mProblemCount);
}
/*-------------------------------------------------------------------------*/
void TLSearcher::ClearSolutions()
/* Discards all current solutions and resets the related statistics.
---------------------------------------------------------------------------*/
{
mSolutions.RemoveAll();
}
/*-------------------------------------------------------------------------*/
size_t TLSearcher::CreateInitialProblem(TLProblemList &aList)
/* Forwards the initial expansion message to the problem representation.
---------------------------------------------------------------------------*/
{
TLX_TRACE(TLX, (50, "Searcher: CreateInitialProblem"));
TLX_ASSERT_PTR(mProblemRep);
TLX_ASSERT(aList.IsEmpty());
size_t count = mProblemRep->CreateInitialProblem(aList);
if (MustSend(seInitial))
SendEvent(TLSearchMonitor::Event(seInitial, (uint32)count));
return count;
}
/*-------------------------------------------------------------------------*/
void TLSearcher::CreateSolution(TLProblemState *aProblem)
/* Asks the problem representation to create a solution based on the given
subproblem, and calls AddSolution() to store the resulting object.
---------------------------------------------------------------------------*/
{
TLX_TRACE(TLX, (50, "Searcher: CreateSolution"));
// We only create a solution if the desired number of solutions has not
// yet been reached.
if (mSolutions.Count() >= mStats.mMaxSol)
return;
#ifdef _TLXDBG
TLX_ASSERT_PTR(aProblem);
TLX_ASSERT_PTR(mProblemRep);
TLSolution *sol = mProblemRep->CreateSolution(aProblem);
TLX_ASSERT_PTR(sol);
AddSolution(sol);
#else
AddSolution(mProblemRep->CreateSolution(aProblem));
#endif
if (MustSend(seSolution))
SendEvent(TLSearchMonitor::Event(seSolution,
(uint32)mSolutions.Count(), aProblem));
}
/*-------------------------------------------------------------------------*/
void TLSearcher::DeregisterProblemRep()
/* Deregisters the searcher with the problem representation, and vice versa.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(mProblemRep);
TLX_ASSERT(mProblemRep->mSearcher == this);
mProblemRep->mSearcher = mPrevSearcher;
mPrevSearcher = 0;
mProblemRep = 0;
}
/*-------------------------------------------------------------------------*/
void TLSearcher::DeregisterMonitor(TLSearchMonitor *aMon)
/* Removes the given monitor from the list of search monitors.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aMon);
for (index_t i = mMonitors.Mini(); i <= mMonitors.Maxi(); i++)
{
if (mMonitors.PeekAt(i).mMonitor == aMon)
{
mMonitors.RemoveAt(i);
UpdateEventMask();
return;
}
}
TLX_TRACE_WARN(TLX, ("Requested monitor not found"));
}
/*-------------------------------------------------------------------------*/
bool TLSearcher::EnableMonitors(bool aFlag)
/* Enables or disables the sending of events to the search monitors. If
the monitors are disabled, no events will besent, regardless of the
individual event settings.
The function returns the previous setting of the flag.
---------------------------------------------------------------------------*/
{
bool oldflag = mMonEnabled;
mMonEnabled = aFlag;
return oldflag;
}
/*-------------------------------------------------------------------------*/
void TLSearcher::EnterState(TLProblemState *aProblem)
/* Signals the start of the processing of a given subproblem.
---------------------------------------------------------------------------*/
{
TLX_TRACE(TLX, (50, "Searcher: EnterState"));
TLX_ASSERT_PTR(aProblem);
TLX_ASSERT_PTR(mProblemRep);
TLX_ASSERT(!aProblem->mIsProcessed);
mStats.mProblemCount++;
mStats.mDepth++;
if ((mStats.mProblemCount % 1000) == 0)
cerr << "\rProcessed " << mStats.mProblemCount << " problems (" <<
mSolutions.Count() << ")...";
mProblemRep->EnterState(aProblem);
if (MustSend(seEnter))
SendEvent(TLSearchMonitor::Event(seEnter, (int32)mStats.mDepth,
aProblem));
}
/*-------------------------------------------------------------------------*/
size_t TLSearcher::GenerateBranches(
TLProblemState * aProblem,
TLProblemList & aList)
/* Forwards the decompose message to the problem representation.
---------------------------------------------------------------------------*/
{
TLX_TRACE(TLX, (50, "Searcher: GenerateBranches"));
TLX_ASSERT_PTR(aProblem);
TLX_ASSERT_PTR(mProblemRep);
size_t count = mProblemRep->GenerateBranches(aProblem, aList);
if (MustSend(seBranch))
SendEvent(TLSearchMonitor::Event(seBranch, (uint32)count, aProblem));
return count;
}
/*-------------------------------------------------------------------------*/
void TLSearcher::LeaveState(TLProblemState *aProblem, bool aUndo)
/* Signals the end of the processing of a given subproblem. If 'aUndo' is
true, the problem representation is informed; else it is not.
In any case, a few searcher statistics are updated.
---------------------------------------------------------------------------*/
{
TLX_TRACE(TLX, (50, "Searcher: LeaveState"));
TLX_ASSERT_PTR(aProblem);
TLX_ASSERT_PTR(mProblemRep);
TLX_ASSERT(aProblem->mIsProcessed);
if (aUndo) mProblemRep->LeaveState(aProblem);
mStats.mBTCount++;
mStats.mDepth--;
if (MustSend(seLeave))
SendEvent(TLSearchMonitor::Event(seLeave,
(int32)mStats.mDepth, aProblem));
}
/*-------------------------------------------------------------------------*/
void TLSearcher::PostProcess()
/* Performs whatever postprocessing is necessary after the search process
has finished. The default implementation registers the stop time of the
search, reports the search statistics, and gives the problem representation an
opportunity to do its own postprocessing.
If you override this function, you should call it in the overridden
version, probably after doing your own postprocessing.
---------------------------------------------------------------------------*/
{
TLX_TRACE(TLX, (50, "Searcher: PostProcess"));
TLX_ASSERT_PTR(mProblemRep);
// Register end of search time, and announce completion.
time(&mStats.mFinishSearch);
TLX_LOG_ENTRY("Search process finished");
// Give the problem representation a chance to do postprocessing.
mProblemRep->PostProcess();
time(&mStats.mFinish);
TLX_LOG_ENTRY("Postprocesssing finished");
if (MustSend(sePostProcess))
SendEvent(TLSearchMonitor::Event(sePostProcess));
ReportStats(); // Print statistics
ReportSolutions(); // Print solutions
}
/*-------------------------------------------------------------------------*/
bool TLSearcher::PreProcess()
/* Performs whatever preprocessing is necessary before the search process
is started. The default implementation resets all statistics, records
the start time, and gives the problem representation an opportunity to perform its
own preprocessing.
If you override this function, you should call it in the overridden
version, probably before doing your own preprocessing.
---------------------------------------------------------------------------*/
{
TLX_TRACE(TLX, (50, "Searcher: PreProcess"));
TLX_ASSERT_PTR(mProblemRep);
// Discard previous solutions (if any)
ClearSolutions();
// Reset statistics
mStats.mBTCount =
mStats.mProblemCount = 0;
mStats.mDepth = 0;
// Give the problem representation a chance to do preprocessing.
TLX_LOG_ENTRY("Preprocessing started");
time(&mStats.mStart);
if (!mProblemRep->PreProcess())
{
TLX_TRACE_INFO(TLX, ("Preprocessing failed; search aborted"));
return false;
}
if (MustSend(sePreProcess))
#ifdef _NOBOOL
SendEvent(TLSearchMonitor::Event(sePreProcess, (int32)true));
#else
SendEvent(TLSearchMonitor::Event(sePreProcess, true));
#endif
// Register the start time for the search, then announce start.
time(&mStats.mStartSearch);
mStats.mPrevious =
mStats.mFinishSearch = mStats.mStartSearch;
TLX_LOG_ENTRY("Search process started");
return true;
}
/*-------------------------------------------------------------------------*/
bool TLSearcher::Process(TLProblemState *aProblem)
/* Forwards the processing message to the problem representation.
---------------------------------------------------------------------------*/
{
TLX_TRACE(TLX, (50, "Searcher: Process"));
TLX_ASSERT_PTR(aProblem);
TLX_ASSERT_PTR(mProblemRep);
TLX_ASSERT(!aProblem->mIsProcessed);
bool result = mProblemRep->Process(aProblem);
#ifdef _TLXDBG
aProblem->mIsProcessed = true;
#endif
if (MustSend(seProcess))
#ifdef _NOBOOL
SendEvent(TLSearchMonitor::Event(seProcess, (int32)result, aProblem));
#else
SendEvent(TLSearchMonitor::Event(seProcess, result, aProblem));
#endif
return result;
}
/*-------------------------------------------------------------------------*/
void TLSearcher::RegisterMonitor(TLSearchMonitor *aMon)
/* Registers a new search monitor with the given event mask.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aMon);
mMonitors.Append(MonitorEntry(aMon, aMon->DefaultEvents()));
mGlobalMask |= aMon->DefaultEvents();
}
/*-------------------------------------------------------------------------*/
void TLSearcher::RegisterProblemRep(TLProblemRep *aRep)
/* Registers the searcher with the problem representation, and vice versa.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aRep);
TLX_ASSERT_NULL(mProblemRep);
TLX_ASSERT_NULL(mPrevSearcher);
mProblemRep = aRep;
mPrevSearcher = mProblemRep->mSearcher;
mProblemRep->mSearcher = this;
}
/*-------------------------------------------------------------------------*/
void TLSearcher::ReportProgress()
/* Prints search progress statistics on stderr.
---------------------------------------------------------------------------*/
{
fprintf(stderr, "Depth %4ld, %6lu problems, %6lu backtracks\r",
mStats.mDepth, mStats.mProblemCount, mStats.mBTCount);
}
/*-------------------------------------------------------------------------*/
void TLSearcher::ReportSolutions()
/* Prints all solution to the log stream.
---------------------------------------------------------------------------*/
{
TLX_LOG_BEGIN << mSolutions.Count() << " solutions found";
TLPtrSeqIter<TLSolution> iter(mSolutions);
for (int cnt = 0; iter.Next(); )
{
TLSolution *sol = iter.Peek();
TLX_ASSERT_PTR(sol);
TLX_LOG << "\n Solution " << ++cnt << ": " << *sol;
}
TLX_LOG << TLX_LOG_END;
}
/*-------------------------------------------------------------------------*/
void TLSearcher::ReportStats()
/* Prints search statistics on stderr and the log output.
---------------------------------------------------------------------------*/
{
fprintf(stderr, "Search process completed, %u solution(s) \n",
mSolutions.Count());
TLX_LOG_ENTRY("%lu problems tested, %lu backtracks, elapsed time %ld sec",
mStats.mProblemCount, mStats.mBTCount,
(mStats.mFinish - mStats.mStart));
// ProblemRep statistics
TLX_ASSERT_PTR(mProblemRep);
TLX_LOG_BEGIN << "ProblemRep: ";
mProblemRep->ReportStats(TLX_LOG);
TLX_LOG << TLX_LOG_END;
// Search monitor information
if (mMonEnabled && mMonitors.Count() > 0)
{
TLX_LOG_BEGIN << "Monitors: ";
for (index_t i = mMonitors.Mini(); i <= mMonitors.Maxi(); i++)
{
TLX_ASSERT_PTR(mMonitors.PeekAt(i).mMonitor);
mMonitors.PeekAt(i).mMonitor->PrintOn(TLX_LOG);
}
TLX_LOG << TLX_LOG_END;
}
}
/*-------------------------------------------------------------------------*/
void TLSearcher::SendEvent(const TLSearchMonitor::Event &aEvent)
/* Sends the event to all monitors that have the corresponding event in
their event mask.
---------------------------------------------------------------------------*/
{
TLX_ASSERT(MustSend(aEvent.mCode));
for (index_t i = mMonitors.Mini(); i <= mMonitors.Maxi(); i++)
if (mMonitors.PeekAt(i).mEventMask & aEvent.mCode)
{
TLX_ASSERT_PTR(mMonitors.PeekAt(i).mMonitor);
mMonitors.PeekAt(i).mMonitor->OnSearchEvent(this, aEvent);
}
}
/*-------------------------------------------------------------------------*/
void TLSearcher::SetMonitorEvents(TLSearchMonitor *aMon, int aMask)
/* Changes the event mask associated with the search monitor.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aMon);
for (index_t i = mMonitors.Mini(); i <= mMonitors.Maxi(); i++)
{
if (mMonitors.PeekAt(i).mMonitor == aMon)
{
mMonitors.PeekAt(i).mEventMask = aMask;
UpdateEventMask();
return;
}
}
TLX_TRACE_WARN(TLX, ("Requested monitor not found"));
}
/*-------------------------------------------------------------------------*/
size_t TLSearcher::Solve(
TLProblemRep * aRep, // ProblemRep to be searched
size_t maxsol // Maximum # solutions to find
)
/* Orchestrates the search process by performing the preprocessing, the
actual search, and the post processing. Returns number of solutions
found (up to the given maximum).
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aRep);
mStats.mMaxSol = maxsol;
RegisterProblemRep(aRep);
clock_t total_time = clock();
clock_t search_time = 0;
if (PreProcess())
{
search_time = clock();
Search();
search_time = clock() - search_time;
PostProcess();
}
total_time = clock() - total_time;
TLX_LOG_ENTRY("Total time = %.0f ms; search time = %.0f ms",
(1000.0 * total_time) / CLOCKS_PER_SEC,
(1000.0 * search_time) / CLOCKS_PER_SEC);
DeregisterProblemRep();
return mSolutions.Count();
}
/*-------------------------------------------------------------------------*/
void TLSearcher::UpdateEventMask()
/* Updates the global event mask by searching through all registered
monitors and combining their individual event masks.
---------------------------------------------------------------------------*/
{
mGlobalMask = seNone;
for (index_t i = mMonitors.Mini(); i <= mMonitors.Maxi(); i++)
mGlobalMask |= mMonitors.PeekAt(i).mEventMask;
}