dfs.icc
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 namespace Gecode {
00023
00024 namespace Search {
00025
00026
00027
00028
00029
00030 forceinline
00031 DfsEngine::DfsEngine(unsigned int c_d0, unsigned int a_d0,
00032 Stop* st, size_t sz)
00033 : EngineCtrl(st,sz), rcs(a_d0), cur(NULL), c_d(c_d0), d(0) {}
00034
00035
00036 forceinline void
00037 DfsEngine::init(Space* s) {
00038 cur = s;
00039 }
00040
00041 forceinline void
00042 DfsEngine::reset(Space* s) {
00043 delete cur;
00044 rcs.reset();
00045 cur = s;
00046 d = 0;
00047 EngineCtrl::reset(s);
00048 }
00049
00050 forceinline size_t
00051 DfsEngine::stacksize(void) const {
00052 return rcs.stacksize();
00053 }
00054
00055 forceinline Space*
00056 DfsEngine::explore(void) {
00057 start();
00058 while (true) {
00059 while (cur) {
00060 if (stop(stacksize()))
00061 return NULL;
00062 switch (cur->status(propagate)) {
00063 case SS_FAILED:
00064 fail++;
00065 delete cur;
00066 cur = NULL;
00067 EngineCtrl::current(NULL);
00068 break;
00069 case SS_SOLVED:
00070 {
00071 Space* s = cur;
00072 cur = NULL;
00073 EngineCtrl::current(NULL);
00074 return s;
00075 }
00076 case SS_BRANCH:
00077 {
00078 Space* c;
00079 if ((d == 0) || (d >= c_d)) {
00080 clone++;
00081 c = cur->clone(true,propagate);
00082 d = 1;
00083 } else {
00084 c = NULL;
00085 d++;
00086 }
00087 const BranchingDesc* desc = rcs.push(cur,c);
00088 EngineCtrl::push(c,desc);
00089 commit++;
00090 cur->commit(desc,0);
00091 break;
00092 }
00093 default: GECODE_NEVER;
00094 }
00095 }
00096 if (!rcs.next(*this))
00097 return NULL;
00098 cur = rcs.recompute<false>(d,*this);
00099 EngineCtrl::current(cur);
00100 }
00101 return NULL;
00102 }
00103
00104 forceinline
00105 DfsEngine::~DfsEngine(void) {
00106 delete cur;
00107 rcs.reset();
00108 }
00109
00110 }
00111
00112
00113
00114
00115
00116
00117 template <class T>
00118 forceinline
00119 DFS<T>::DFS(T* s, unsigned int c_d, unsigned int a_d, Search::Stop* st)
00120 : Search::DFS(s,c_d,a_d,st,sizeof(T)) {}
00121
00122 template <class T>
00123 forceinline T*
00124 DFS<T>::next(void) {
00125 return static_cast<T*>(Search::DFS::next());
00126 }
00127
00128
00129
00130
00131
00132
00133
00134
00135 template <class T>
00136 forceinline T*
00137 dfs(T* s, unsigned int c_d, unsigned int a_d, Search::Stop* st) {
00138 DFS<T> d(s,c_d,a_d,st);
00139 return static_cast<T*>(d.next());
00140 }
00141
00142 }
00143
00144