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