Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
spacenode.hpp
Go to the documentation of this file.
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
34namespace Gecode { namespace Gist {
35
36 forceinline void
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
45 SpaceNode::getFlag(int flag) const {
46 return (nstatus & (1<<(flag-1))) != 0;
47 }
48
49 forceinline void
50 SpaceNode::setHasOpenChildren(bool b) {
52 }
53
54 forceinline void
55 SpaceNode::setHasFailedChildren(bool b) {
57 }
58
59 forceinline void
60 SpaceNode::setHasSolvedChildren(bool b) {
62 }
63
64 forceinline void
66 nstatus &= ~( STATUSMASK );
67 nstatus |= s << 20;
68 }
69
72 return static_cast<NodeStatus>((nstatus & STATUSMASK) >> 20);
73 }
74
75 forceinline void
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
85 return nstatus & DISTANCEMASK;
86 }
87
90 : Node(p), copy(NULL), nstatus(0) {
91 choice = NULL;
93 setHasSolvedChildren(false);
94 setHasFailedChildren(false);
95 }
96
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 = NULL;
105 } else {
106 ret = copy->clone();
107 }
108 return ret;
109 }
110
111 forceinline const Space*
113 assert(copy != NULL);
115 return static_cast<Space*>(Support::unmark(copy));
116 return copy;
117 }
118
119 forceinline void
121 if (!isRoot() && (getStatus() != SOLVED || !na.bab())) {
122 // only delete copies from solutions if we are not in BAB
124 delete static_cast<Space*>(Support::unmark(copy));
125 else
126 delete copy;
127 copy = NULL;
128 }
129 }
130
131
132 forceinline bool
134 return curBest != NULL && curBest->s == this;
135 }
136
137 forceinline bool
139 return ((getStatus() == UNDETERMINED) ||
141 }
142
143 forceinline bool
147
148 forceinline bool
152
153 forceinline bool
157
158 forceinline bool
160 return copy != NULL;
161 }
162
163 forceinline bool
165 return copy != NULL && Support::marked(copy);
166 }
167
168 forceinline int
170 SpaceNode* p = getParent(na);
171 if (p == NULL)
172 return -1;
173 for (int i=static_cast<int>(p->getNumberOfChildren()); i--;)
174 if (p->getChild(na,i) == this)
175 return i;
177 return -1;
178 }
179
180 forceinline const Choice*
182 return choice;
183 }
184
185}}
186
187// STATISTICS: gist-any
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
Choice for performing commit
Definition core.hpp:1412
Static reference to the currently best space.
Definition spacenode.hh:80
SpaceNode * s
The currently best node found, or NULL.
Definition spacenode.hh:83
bool bab(void) const
Return branch-and-bound flag.
Definition node.hpp:114
Base class for nodes of the search tree.
Definition node.hh:106
int getParent(void) const
Return the parent.
Definition node.hpp:182
bool isRoot(void) const
Check if this node is the root of a tree.
Definition node.hpp:211
A node of a search tree of Gecode spaces.
Definition spacenode.hh:89
Space * copy
A copy used for recomputation, or NULL.
Definition spacenode.hh:96
bool hasCopy(void)
Return whether the node has a copy.
const Choice * choice
Definition spacenode.hh:98
bool hasWorkingSpace(void)
Return whether the node has a working space.
const Choice * getChoice(void)
Return choice of this node.
const Space * getWorkingSpace(void) const
Return working space (if present).
bool isCurrentBest(BestNode *curBest)
Return whether this node is the currently best solution.
unsigned int getDistance(void) const
Return distance from copy.
Definition spacenode.hpp:84
unsigned int nstatus
Status of the node.
Definition spacenode.hh:106
void setStatus(NodeStatus s)
Set status to s.
Definition spacenode.hpp:65
bool hasFailedChildren(void)
Return whether the subtree of this node has any failed children.
void setFlag(int flag, bool value)
Set status flag.
Definition spacenode.hpp:37
void acquireSpace(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Acquire working space, either from parent or by recomputation.
bool hasSolvedChildren(void)
Return whether the subtree of this node has any solved children.
int getAlternative(const NodeAllocator &na) const
Return alternative number of this node.
bool isOpen(void)
Return whether this node still has open children.
NodeStatus getStatus(void) const
Return current status of the node.
Definition spacenode.hpp:71
Space * getSpace(NodeAllocator &na, BestNode *curBest, int c_d, int a_d)
Return working space. Receiver must delete the space.
Definition spacenode.hpp:98
SpaceNode(int p)
Construct node with parent p.
Definition spacenode.hpp:89
void purge(const NodeAllocator &na)
Clear working space and copy (if present and this is not the root).
bool getFlag(int flag) const
Return status flag.
Definition spacenode.hpp:45
void setDistance(unsigned int d)
Set distance from copy.
Definition spacenode.hpp:76
bool hasOpenChildren(void)
Return whether the subtree of this node has any open children.
Computation spaces.
Definition core.hpp:1742
Space * clone(CloneStatistics &stat=unused_clone) const
Clone space.
Definition core.hpp:3224
NodeStatus
Status of nodes in the search tree.
Definition spacenode.hh:44
@ UNDETERMINED
Node that has not been explored yet.
Definition spacenode.hh:48
@ SOLVED
Node representing a solution.
Definition spacenode.hh:45
void * unmark(void *p)
Return unmarked pointer for a marked pointer p.
bool marked(void *p)
Check whether p is marked.
Gecode toplevel namespace
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56