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 SPECIAL,
00054 STEP
00055 };
00056
00057 static const unsigned int FIRSTBIT = 25;
00058 static const unsigned int STATUSMASK = 15<<20;
00059 static const unsigned int MAXDISTANCE = (1<<20)-1;
00060 static const unsigned int DISTANCEMASK = (1<<20)-1;
00061
00063 class StepDesc {
00064 public:
00065 int noOfSteps;
00066 bool debug;
00067 StepDesc(int steps);
00068 void toggleDebug(void);
00069 };
00070
00072 class SpecialDesc {
00073 public:
00074 const std::string vn;
00075 const int v;
00076 const int rel;
00077 SpecialDesc(std::string varName, int rel0, int v0);
00078 };
00079
00081 class Statistics : public StatusStatistics {
00082 public:
00084 int solutions;
00086 int failures;
00088 int choices;
00090 int undetermined;
00092 int maxDepth;
00093
00095 Statistics(void)
00096 : solutions(0), failures(0), choices(0), undetermined(1), maxDepth(0) {}
00097 };
00098
00099 class SpaceNode;
00100
00102 class BestNode {
00103 public:
00105 SpaceNode* s;
00107 BestNode(SpaceNode* s0);
00108 };
00109
00111 class SpaceNode : public Node {
00112 protected:
00114 Space* copy;
00116 Space* workingSpace;
00117 private:
00119 SpaceNode* ownBest;
00126 unsigned int nstatus;
00127 protected:
00128 union {
00130 const Choice* branch;
00132 const SpecialDesc* special;
00134 StepDesc* step;
00135 } desc;
00136
00138 void setDistance(unsigned int d);
00139
00141 unsigned int getDistance(void) const;
00142
00144 void setFlag(int flag, bool value);
00145
00147 bool getFlag(int flag) const;
00148
00150 enum SpaceNodeFlags {
00151 HASOPENCHILDREN = FIRSTBIT,
00152 HASFAILEDCHILDREN,
00153 HASSOLVEDCHILDREN
00154 };
00156 static const int LASTBIT = HASSOLVEDCHILDREN;
00157
00158 private:
00160 void setHasOpenChildren(bool b);
00162 void setHasFailedChildren(bool b);
00164 void setHasSolvedChildren(bool b);
00166 void setStatus(NodeStatus s);
00167
00169 int recompute(BestNode* curBest, int c_d, int a_d);
00170
00172 void closeChild(bool hadFailures, bool hadSolutions);
00173 protected:
00175 void acquireSpace(BestNode* curBest, int c_d, int a_d);
00176 public:
00178 SpaceNode(void);
00180 SpaceNode(Space* root);
00182 ~SpaceNode(void);
00183
00185 Space* getSpace(BestNode* curBest, int c_d, int a_d);
00186
00188 const Space* getWorkingSpace(void) const;
00189
00191 void purge(void);
00192
00194 bool isCurrentBest(BestNode* curBest);
00195
00206 int getNumberOfChildNodes(NodeAllocator& na,
00207 BestNode* curBest,
00208 Statistics& stats,
00209 int c_d, int a_d);
00210
00212 NodeStatus getStatus(void) const;
00214 bool isStepNode(void);
00216 void setSpecialDesc(const SpecialDesc* d);
00218 void setStepDesc(StepDesc* d);
00220 StepDesc* getStepDesc(void);
00221
00223 bool isOpen(void);
00225 bool hasFailedChildren(void);
00227 bool hasSolvedChildren(void);
00229 bool hasOpenChildren(void);
00231 int getNoOfOpenChildren(void);
00233 void setNoOfOpenChildren(int n);
00235 bool hasCopy(void);
00237 bool hasWorkingSpace(void);
00238
00240 SpaceNode* getParent(void);
00242 SpaceNode* getChild(int i);
00244 int getAlternative(void);
00245 };
00246
00247 }}
00248
00249 #include <gecode/gist/spacenode.hpp>
00250
00251 #endif
00252
00253