Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
node.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 template<class T>
37 void
38 NodeAllocatorBase<T>::allocate(void) {
39 cur_b++;
40 cur_t = 0;
41 if (cur_b==n) {
42 int oldn = n;
43 n = static_cast<int>(n*1.5+1.0);
44 b = heap.realloc<Block*>(b,oldn,n);
45 }
46 b[cur_b] = static_cast<Block*>(heap.ralloc(sizeof(Block)));
47 }
48
49 template<class T>
51 : _bab(bab) {
52 b = heap.alloc<Block*>(10);
53 n = 10;
54 cur_b = -1;
55 cur_t = NodeBlockSize-1;
56 }
57
58 template<class T>
60 for (int i=cur_b+1; i--;)
61 heap.rfree(b[i]);
62 heap.free<Block*>(b,n);
63 }
64
65 template<class T>
66 forceinline int
67 NodeAllocatorBase<T>::allocate(int p) {
68 cur_t++;
69 if (cur_t==NodeBlockSize)
70 allocate();
71 new (&b[cur_b]->b[cur_t]) T(p);
72 b[cur_b]->best[cur_t] = -1;
73 return cur_b*NodeBlockSize+cur_t;
74 }
75
76 template<class T>
77 forceinline int
78 NodeAllocatorBase<T>::allocate(Space* root) {
79 cur_t++;
80 if (cur_t==NodeBlockSize)
81 allocate();
82 new (&b[cur_b]->b[cur_t]) T(root);
83 b[cur_b]->best[cur_t] = -1;
84 return cur_b*NodeBlockSize+cur_t;
85 }
86
87 template<class T>
90 assert(i/NodeBlockSize < n);
91 assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
92 return &(b[i/NodeBlockSize]->b[i%NodeBlockSize]);
93 }
94
95 template<class T>
98 assert(i/NodeBlockSize < n);
99 assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
100 int bi = b[i/NodeBlockSize]->best[i%NodeBlockSize];
101 return bi == -1 ? NULL : (*this)[bi];
102 }
103
104 template<class T>
105 forceinline void
107 assert(i/NodeBlockSize < n);
108 assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
109 b[i/NodeBlockSize]->best[i%NodeBlockSize] = best;
110 }
111
112 template<class T>
113 forceinline bool
115 return _bab;
116 }
117
118 template<class T>
119 forceinline bool
121 return !labels.isEmpty();
122 }
123
124 template<class T>
125 bool
127 return labels.contains(n);
128 }
129
130 template<class T>
131 void
132 NodeAllocatorBase<T>::setLabel(T* n, const QString& l) {
133 labels[n] = l;
134 }
135
136 template<class T>
137 void
139 labels.remove(n);
140 }
141
142 template<class T>
143 QString
145 return labels.value(n);
146 }
147
148 forceinline unsigned int
149 Node::getTag(void) const {
150 return static_cast<unsigned int>
151 (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & 3);
152 }
153
154 forceinline void
155 Node::setTag(unsigned int tag) {
156 assert(tag <= 3);
157 assert(getTag() == UNDET);
158 childrenOrFirstChild = reinterpret_cast<void*>
159 ( (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) | tag);
160 }
161
162 forceinline void*
163 Node::getPtr(void) const {
164 return reinterpret_cast<void*>
165 (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3));
166 }
167
168 forceinline int
169 Node::getFirstChild(void) const {
170 return static_cast<int>
171 ((reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) >> 2);
172 }
173
175 Node::Node(int p, bool failed) : parent(p) {
176 childrenOrFirstChild = NULL;
177 noOfChildren = 0;
178 setTag(failed ? LEAF : UNDET);
179 }
180
181 forceinline int
182 Node::getParent(void) const {
183 return parent;
184 }
185
188 return parent < 0 ? NULL : na[parent];
189 }
190
191 forceinline bool
192 Node::isUndetermined(void) const { return getTag() == UNDET; }
193
194 forceinline int
195 Node::getChild(int n) const {
196 assert(getTag() != UNDET && getTag() != LEAF);
197 if (getTag() == TWO_CHILDREN) {
198 assert(n != 1 || noOfChildren <= 0);
199 return n == 0 ? getFirstChild() : -noOfChildren;
200 }
201 assert(n < noOfChildren);
202 return static_cast<int*>(getPtr())[n];
203 }
204
206 Node::getChild(const NodeAllocator& na, int n) const {
207 return na[getChild(n)];
208 }
209
210 forceinline bool
211 Node::isRoot(void) const { return parent == -1; }
212
213 forceinline unsigned int
215 switch (getTag()) {
216 case UNDET:
217 case LEAF:
218 return 0;
219 case TWO_CHILDREN:
220 return (noOfChildren <= 0) ? 2 : 1;
221 default:
222 return static_cast<unsigned int>(noOfChildren);
223 }
224 }
225
226 forceinline int
227 Node::getIndex(const NodeAllocator& na) const {
228 if (parent==-1)
229 return 0;
230 Node* p = na[parent];
231 for (int i=p->getNumberOfChildren(); i--;)
232 if (p->getChild(na,i) == this)
233 return p->getChild(i);
235 return -1;
236 }
237
238}}
239
240// STATISTICS: gist-any
bool bab(void) const
Return branch-and-bound flag.
Definition node.hpp:114
T * best(int i) const
Return index of best node before i.
Definition node.hpp:97
QString getLabel(T *n) const
Get label of node n.
Definition node.hpp:144
bool showLabels(void) const
Return branching label flag.
Definition node.hpp:120
T * operator[](int i) const
Return node for index i.
Definition node.hpp:89
bool hasLabel(T *n) const
Return whether node n has a label.
Definition node.hpp:126
void setLabel(T *n, const QString &l)
Set label of node n to l.
Definition node.hpp:132
void setBest(int i, int b)
Set index of best node before i to b.
Definition node.hpp:106
NodeAllocatorBase(bool bab)
Constructor.
Definition node.hpp:50
void clearLabel(T *n)
Remove label of node n.
Definition node.hpp:138
~NodeAllocatorBase(void)
Destructor.
Definition node.hpp:59
NodeAllocatorBase< VisualNode > NodeAllocator
Definition node.hh:143
unsigned int getNumberOfChildren(void) const
Return the number of children.
Definition node.hpp:214
Node(int p, bool failed=false)
Construct node with parent p.
Definition node.hpp:175
int getParent(void) const
Return the parent.
Definition node.hpp:182
bool isUndetermined(void) const
Return whether this node is undetermined.
Definition node.hpp:192
int getChild(int n) const
Return index of child no n.
Definition node.hpp:195
bool isRoot(void) const
Check if this node is the root of a tree.
Definition node.hpp:211
int getIndex(const NodeAllocator &na) const
Return index of this node.
Definition node.hpp:227
Node class that supports visual layout
T * realloc(T *b, long unsigned int n, long unsigned int m)
Reallocate block of n objects starting at b to m objects of type T from heap.
Definition heap.hpp:482
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition heap.hpp:357
Computation spaces.
Definition core.hpp:1744
Heap heap
The single global heap.
Definition heap.cpp:44
The Gecode Interactive Search Tool.
Gecode toplevel namespace
Gecode::FloatVal b(9, 12)
#define forceinline
Definition config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56