1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 2 /* 3 * Main authors: 4 * Guido Tack <tack@gecode.org> 5 * 6 * Copyright: 7 * Guido Tack, 2006 8 * 9 * This file is part of Gecode, the generic constraint 10 * development environment: 11 * http://www.gecode.org 12 * 13 * Permission is hereby granted, free of charge, to any person obtaining 14 * a copy of this software and associated documentation files (the 15 * "Software"), to deal in the Software without restriction, including 16 * without limitation the rights to use, copy, modify, merge, publish, 17 * distribute, sublicense, and/or sell copies of the Software, and to 18 * permit persons to whom the Software is furnished to do so, subject to 19 * the following conditions: 20 * 21 * The above copyright notice and this permission notice shall be 22 * included in all copies or substantial portions of the Software. 23 * 24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 31 * 32 */ 33 34 namespace Gecode { namespace Gist { 35 36 forceinline void setFlag(int flag,bool value)37 SpaceNode::setFlag(int flag, bool value) { 38 if (value) 39 nstatus |= 1<<(flag-1); 40 else 41 nstatus &= ~(1<<(flag-1)); 42 } 43 44 forceinline bool getFlag(int flag) const45 SpaceNode::getFlag(int flag) const { 46 return (nstatus & (1<<(flag-1))) != 0; 47 } 48 49 forceinline void setHasOpenChildren(bool b)50 SpaceNode::setHasOpenChildren(bool b) { 51 setFlag(HASOPENCHILDREN, b); 52 } 53 54 forceinline void setHasFailedChildren(bool b)55 SpaceNode::setHasFailedChildren(bool b) { 56 setFlag(HASFAILEDCHILDREN, b); 57 } 58 59 forceinline void setHasSolvedChildren(bool b)60 SpaceNode::setHasSolvedChildren(bool b) { 61 setFlag(HASSOLVEDCHILDREN, b); 62 } 63 64 forceinline void setStatus(NodeStatus s)65 SpaceNode::setStatus(NodeStatus s) { 66 nstatus &= ~( STATUSMASK ); 67 nstatus |= s << 20; 68 } 69 70 forceinline NodeStatus getStatus(void) const71 SpaceNode::getStatus(void) const { 72 return static_cast<NodeStatus>((nstatus & STATUSMASK) >> 20); 73 } 74 75 forceinline void setDistance(unsigned int d)76 SpaceNode::setDistance(unsigned int d) { 77 if (d > MAXDISTANCE) 78 d = MAXDISTANCE; 79 nstatus &= ~( DISTANCEMASK ); 80 nstatus |= d; 81 } 82 83 forceinline unsigned int getDistance(void) const84 SpaceNode::getDistance(void) const { 85 return nstatus & DISTANCEMASK; 86 } 87 88 forceinline SpaceNode(int p)89 SpaceNode::SpaceNode(int p) 90 : Node(p), copy(nullptr), nstatus(0) { 91 choice = nullptr; 92 setStatus(UNDETERMINED); 93 setHasSolvedChildren(false); 94 setHasFailedChildren(false); 95 } 96 97 forceinline Space* getSpace(NodeAllocator & na,BestNode * curBest,int c_d,int a_d)98 SpaceNode::getSpace(NodeAllocator& na, 99 BestNode* curBest, int c_d, int a_d) { 100 acquireSpace(na,curBest,c_d,a_d); 101 Space* ret; 102 if (Support::marked(copy)) { 103 ret = static_cast<Space*>(Support::unmark(copy)); 104 copy = nullptr; 105 } else { 106 ret = copy->clone(); 107 } 108 return ret; 109 } 110 111 forceinline const Space* getWorkingSpace(void) const112 SpaceNode::getWorkingSpace(void) const { 113 assert(copy != nullptr); 114 if (Support::marked(copy)) 115 return static_cast<Space*>(Support::unmark(copy)); 116 return copy; 117 } 118 119 forceinline void purge(const NodeAllocator & na)120 SpaceNode::purge(const NodeAllocator& na) { 121 if (!isRoot() && (getStatus() != SOLVED || !na.bab())) { 122 // only delete copies from solutions if we are not in BAB 123 if (Support::marked(copy)) 124 delete static_cast<Space*>(Support::unmark(copy)); 125 else 126 delete copy; 127 copy = nullptr; 128 } 129 } 130 131 132 forceinline bool isCurrentBest(BestNode * curBest)133 SpaceNode::isCurrentBest(BestNode* curBest) { 134 return curBest != nullptr && curBest->s == this; 135 } 136 137 forceinline bool isOpen(void)138 SpaceNode::isOpen(void) { 139 return ((getStatus() == UNDETERMINED) || 140 getFlag(HASOPENCHILDREN)); 141 } 142 143 forceinline bool hasFailedChildren(void)144 SpaceNode::hasFailedChildren(void) { 145 return getFlag(HASFAILEDCHILDREN); 146 } 147 148 forceinline bool hasSolvedChildren(void)149 SpaceNode::hasSolvedChildren(void) { 150 return getFlag(HASSOLVEDCHILDREN); 151 } 152 153 forceinline bool hasOpenChildren(void)154 SpaceNode::hasOpenChildren(void) { 155 return getFlag(HASOPENCHILDREN); 156 } 157 158 forceinline bool hasCopy(void)159 SpaceNode::hasCopy(void) { 160 return copy != nullptr; 161 } 162 163 forceinline bool hasWorkingSpace(void)164 SpaceNode::hasWorkingSpace(void) { 165 return copy != nullptr && Support::marked(copy); 166 } 167 168 forceinline int getAlternative(const NodeAllocator & na) const169 SpaceNode::getAlternative(const NodeAllocator& na) const { 170 SpaceNode* p = getParent(na); 171 if (p == nullptr) 172 return -1; 173 for (int i=static_cast<int>(p->getNumberOfChildren()); i--;) 174 if (p->getChild(na,i) == this) 175 return i; 176 GECODE_NEVER; 177 return -1; 178 } 179 180 forceinline const Choice* getChoice(void)181 SpaceNode::getChoice(void) { 182 return choice; 183 } 184 185 }} 186 187 // STATISTICS: gist-any 188