spacenode.hh
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
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #ifndef GECODE_GIST_SPACENODE_HH
00039 #define GECODE_GIST_SPACENODE_HH
00040
00041 #include <gecode/gist/node.hh>
00042 #include <gecode/kernel.hh>
00043
00044 namespace Gecode { namespace Gist {
00045
00048 enum NodeStatus {
00049 SOLVED,
00050 FAILED,
00051 BRANCH,
00052 UNDETERMINED,
00053 STOP,
00054 UNSTOP,
00055 };
00056
00057 static const unsigned int FIRSTBIT = 24;
00058 static const unsigned int STATUSMASK = 7<<20;
00059 static const unsigned int MAXDISTANCE = (1<<20)-1;
00060 static const unsigned int DISTANCEMASK = (1<<20)-1;
00061
00063 class Statistics : public StatusStatistics {
00064 public:
00066 int solutions;
00068 int failures;
00070 int choices;
00072 int undetermined;
00074 int maxDepth;
00075
00077 Statistics(void)
00078 : solutions(0), failures(0), choices(0), undetermined(1), maxDepth(0) {}
00079 };
00080
00081 class SpaceNode;
00082
00084 class BestNode {
00085 public:
00087 SpaceNode* s;
00089 BestNode(SpaceNode* s0);
00090 };
00091
00093 class SpaceNode : public Node {
00094 protected:
00096 Space* copy;
00098 Space* workingSpace;
00099 private:
00101 SpaceNode* ownBest;
00108 unsigned int nstatus;
00109 protected:
00110 const Choice* choice;
00111
00113 void setDistance(unsigned int d);
00114
00116 unsigned int getDistance(void) const;
00117
00119 void setFlag(int flag, bool value);
00120
00122 bool getFlag(int flag) const;
00123
00125 enum SpaceNodeFlags {
00126 HASOPENCHILDREN = FIRSTBIT,
00127 HASFAILEDCHILDREN,
00128 HASSOLVEDCHILDREN
00129 };
00131 static const int LASTBIT = HASSOLVEDCHILDREN;
00132
00133 private:
00135 void setHasOpenChildren(bool b);
00137 void setHasFailedChildren(bool b);
00139 void setHasSolvedChildren(bool b);
00140
00142 int recompute(BestNode* curBest, int c_d, int a_d);
00143
00145 void closeChild(bool hadFailures, bool hadSolutions);
00146 protected:
00148 void setStatus(NodeStatus s);
00150 void acquireSpace(BestNode* curBest, int c_d, int a_d);
00151 public:
00153 SpaceNode(void);
00155 SpaceNode(Space* root);
00157 ~SpaceNode(void);
00158
00160 Space* getSpace(BestNode* curBest, int c_d, int a_d);
00161
00163 const Space* getWorkingSpace(void) const;
00164
00166 void purge(void);
00167
00169 bool isCurrentBest(BestNode* curBest);
00170
00181 int getNumberOfChildNodes(NodeAllocator& na,
00182 BestNode* curBest,
00183 Statistics& stats,
00184 int c_d, int a_d);
00185
00187 NodeStatus getStatus(void) const;
00188
00190 bool isOpen(void);
00192 bool hasFailedChildren(void);
00194 bool hasSolvedChildren(void);
00196 bool hasOpenChildren(void);
00198 int getNoOfOpenChildren(void);
00200 void setNoOfOpenChildren(int n);
00202 bool hasCopy(void);
00204 bool hasWorkingSpace(void);
00205
00207 SpaceNode* getParent(void);
00209 SpaceNode* getChild(int i);
00211 int getAlternative(void);
00213 const Choice* getChoice(void);
00214 };
00215
00216 }}
00217
00218 #include <gecode/gist/spacenode.hpp>
00219
00220 #endif
00221
00222