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), ds(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 ds.reset();
00045 cur = s;
00046 d = 0;
00047 EngineCtrl::reset(s);
00048 }
00049
00050 forceinline size_t
00051 DfsEngine::stacksize(void) const {
00052 return ds.size();
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 unsigned int alt;
00063 switch (cur->status(alt,propagate)) {
00064 case SS_FAILED:
00065 fail++;
00066 delete cur;
00067 cur = NULL;
00068 EngineCtrl::current(NULL);
00069 break;
00070 case SS_SOLVED:
00071 {
00072 Space* s = cur;
00073 cur = NULL;
00074 EngineCtrl::current(NULL);
00075 return s;
00076 }
00077 case SS_BRANCH:
00078 {
00079 Space* c;
00080 if ((d == 0) || (d >= c_d)) {
00081 clone++;
00082 c = cur->clone();
00083 d = 1;
00084 } else {
00085 c = NULL;
00086 if (alt > 1)
00087 d++;
00088 }
00089 BranchingDesc* desc = ds.push(cur,c,alt);
00090 EngineCtrl::push(c,desc);
00091 commit++;
00092 cur->commit(0, desc);
00093 break;
00094 }
00095 }
00096 }
00097 if (!ds.next(*this))
00098 return NULL;
00099 cur = ds.recompute(d,*this);
00100 EngineCtrl::current(cur);
00101 }
00102 return NULL;
00103 }
00104
00105 forceinline
00106 DfsEngine::~DfsEngine(void) {
00107 delete cur;
00108 ds.reset();
00109 }
00110
00111 }
00112
00113
00114
00115
00116
00117
00118 template <class T>
00119 forceinline
00120 DFS<T>::DFS(T* s, unsigned int c_d, unsigned int a_d, Search::Stop* st)
00121 : Search::DFS(s,c_d,a_d,st,sizeof(T)) {}
00122
00123 template <class T>
00124 forceinline T*
00125 DFS<T>::next(void) {
00126 return static_cast<T*>(Search::DFS::next());
00127 }
00128
00129
00130
00131
00132
00133
00134
00135
00136 template <class T>
00137 forceinline T*
00138 dfs(T* s, unsigned int c_d, unsigned int a_d, Search::Stop* st) {
00139 DFS<T> d(s,c_d,a_d,st);
00140 return static_cast<T*>(d.next());
00141 }
00142
00143 }
00144
00145