Generated on Sat Apr 10 2021 00:00:00 for Gecode by doxygen 1.9.1
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 
34 namespace 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
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
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>
88  forceinline 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>
96  forceinline 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 
187  Node::getParent(const NodeAllocator& na) const {
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);
234  GECODE_NEVER;
235  return -1;
236  }
237 
238 }}
239 
240 // STATISTICS: gist-any
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
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
Base class for nodes of the search tree.
Definition: node.hh:106
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
Definition: visualnode.hh:125
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 free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:457
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:431
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:371
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:357
Computation spaces.
Definition: core.hpp:1742
Heap heap
The single global heap.
Definition: heap.cpp:44
int bab(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for branch-and-bound search of root.
Definition: gist.hpp:208
Gecode::IntArgs i({1, 2, 3, 4})
const BoolInstr * bi[]
Definition: mm-bool.cpp:4169
#define forceinline
Definition: config.hpp:192
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56