Generated on Sat Feb 7 2015 02:01:18 for Gecode by doxygen 1.8.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  * Last modified:
10  * $Date: 2013-05-06 09:02:17 +0200 (Mon, 06 May 2013) $ by $Author: tack $
11  * $Revision: 13613 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace Gist {
39 
40  template<class T>
41  void
42  NodeAllocatorBase<T>::allocate(void) {
43  cur_b++;
44  cur_t = 0;
45  if (cur_b==n) {
46  int oldn = n;
47  n = static_cast<int>(n*1.5+1.0);
48  b = heap.realloc<Block*>(b,oldn,n);
49  }
50  b[cur_b] = static_cast<Block*>(heap.ralloc(sizeof(Block)));
51  }
52 
53  template<class T>
55  : _bab(bab) {
56  b = heap.alloc<Block*>(10);
57  n = 10;
58  cur_b = -1;
59  cur_t = NodeBlockSize-1;
60  }
61 
62  template<class T>
64  for (int i=cur_b+1; i--;)
65  heap.rfree(b[i]);
66  heap.free<Block*>(b,n);
67  }
68 
69  template<class T>
70  forceinline int
72  cur_t++;
73  if (cur_t==NodeBlockSize)
74  allocate();
75  new (&b[cur_b]->b[cur_t]) T(p);
76  b[cur_b]->best[cur_t] = -1;
77  return cur_b*NodeBlockSize+cur_t;
78  }
79 
80  template<class T>
81  forceinline int
83  cur_t++;
84  if (cur_t==NodeBlockSize)
85  allocate();
86  new (&b[cur_b]->b[cur_t]) T(root);
87  b[cur_b]->best[cur_t] = -1;
88  return cur_b*NodeBlockSize+cur_t;
89  }
90 
91  template<class T>
92  forceinline T*
94  assert(i/NodeBlockSize < n);
95  assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
96  return &(b[i/NodeBlockSize]->b[i%NodeBlockSize]);
97  }
98 
99  template<class T>
100  forceinline T*
102  assert(i/NodeBlockSize < n);
103  assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
104  int bi = b[i/NodeBlockSize]->best[i%NodeBlockSize];
105  return bi == -1 ? NULL : (*this)[bi];
106  }
107 
108  template<class T>
109  forceinline void
111  assert(i/NodeBlockSize < n);
112  assert(i/NodeBlockSize < cur_b || i%NodeBlockSize <= cur_t);
113  b[i/NodeBlockSize]->best[i%NodeBlockSize] = best;
114  }
115 
116  template<class T>
117  forceinline bool
119  return _bab;
120  }
121 
122  template<class T>
123  forceinline bool
125  return !labels.isEmpty();
126  }
127 
128  template<class T>
129  bool
131  return labels.contains(n);
132  }
133 
134  template<class T>
135  void
136  NodeAllocatorBase<T>::setLabel(T* n, const QString& l) {
137  labels[n] = l;
138  }
139 
140  template<class T>
141  void
143  labels.remove(n);
144  }
145 
146  template<class T>
147  QString
149  return labels.value(n);
150  }
151 
152  forceinline unsigned int
153  Node::getTag(void) const {
154  return static_cast<unsigned int>
155  (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & 3);
156  }
157 
158  forceinline void
159  Node::setTag(unsigned int tag) {
160  assert(tag <= 3);
161  assert(getTag() == UNDET);
162  childrenOrFirstChild = reinterpret_cast<void*>
163  ( (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) | tag);
164  }
165 
166  forceinline void*
167  Node::getPtr(void) const {
168  return reinterpret_cast<void*>
169  (reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3));
170  }
171 
172  forceinline int
173  Node::getFirstChild(void) const {
174  return static_cast<int>
175  ((reinterpret_cast<ptrdiff_t>(childrenOrFirstChild) & ~(3)) >> 2);
176  }
177 
179  Node::Node(int p, bool failed) : parent(p) {
180  childrenOrFirstChild = NULL;
181  noOfChildren = 0;
182  setTag(failed ? LEAF : UNDET);
183  }
184 
185  forceinline int
186  Node::getParent(void) const {
187  return parent;
188  }
189 
191  Node::getParent(const NodeAllocator& na) const {
192  return parent < 0 ? NULL : na[parent];
193  }
194 
195  forceinline bool
196  Node::isUndetermined(void) const { return getTag() == UNDET; }
197 
198  forceinline int
199  Node::getChild(int n) const {
200  assert(getTag() != UNDET && getTag() != LEAF);
201  if (getTag() == TWO_CHILDREN) {
202  assert(n != 1 || noOfChildren <= 0);
203  return n == 0 ? getFirstChild() : -noOfChildren;
204  }
205  assert(n < noOfChildren);
206  return static_cast<int*>(getPtr())[n];
207  }
208 
210  Node::getChild(const NodeAllocator& na, int n) const {
211  return na[getChild(n)];
212  }
213 
214  forceinline bool
215  Node::isRoot(void) const { return parent == -1; }
216 
217  forceinline unsigned int
219  switch (getTag()) {
220  case UNDET: return 0;
221  case LEAF: return 0;
222  case TWO_CHILDREN: return 1+(noOfChildren <= 0);
223  default: return noOfChildren;
224  }
225  }
226 
227  inline int
228  Node::getIndex(const NodeAllocator& na) const {
229  if (parent==-1)
230  return 0;
231  Node* p = na[parent];
232  for (int i=p->getNumberOfChildren(); i--;)
233  if (p->getChild(na,i) == this)
234  return p->getChild(i);
235  GECODE_NEVER;
236  return -1;
237  }
238 
239 }}
240 
241 // STATISTICS: gist-any
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
T * operator[](int i) const
Return node for index i.
Definition: node.hpp:93
void setLabel(T *n, const QString &l)
Set label of node n to l.
Definition: node.hpp:136
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:355
void * ralloc(size_t s)
Allocate s bytes from heap.
Definition: heap.hpp:341
Base class for nodes of the search tree.
Definition: node.hh:110
Node allocator.
Definition: node.hh:52
unsigned int getNumberOfChildren(void) const
Return the number of children.
Definition: node.hpp:218
NodeAllocatorBase(bool bab)
Constructor.
Definition: node.hpp:54
Computation spaces.
Definition: core.hpp:1362
Heap heap
The single global heap.
Definition: heap.cpp:49
const BoolInstr * bi[]
Definition: mm-bool.cpp:4169
int getParent(void) const
Return the parent.
Definition: node.hpp:186
QString getLabel(T *n) const
Get label of node n.
Definition: node.hpp:148
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
bool isRoot(void) const
Check if this node is the root of a tree.
Definition: node.hpp:215
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:400
bool bab(void) const
Return branch-and-bound flag.
Definition: node.hpp:118
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
void clearLabel(T *n)
Remove label of node n.
Definition: node.hpp:142
Node(int p, bool failed=false)
Construct node with parent p.
Definition: node.hpp:179
bool showLabels(void) const
Return branching label flag.
Definition: node.hpp:124
void setBest(int i, int b)
Set index of best node before i to b.
Definition: node.hpp:110
~NodeAllocatorBase(void)
Destructor.
Definition: node.hpp:63
void free(T *b, long unsigned int n)
Delete n objects starting at b.
Definition: heap.hpp:426
int getIndex(const NodeAllocator &na) const
Return index of this node.
Definition: node.hpp:228
#define forceinline
Definition: config.hpp:132
Node class that supports visual layout
Definition: visualnode.hh:129
int bab(Space *root, const Gist::Options &opt)
Create a new stand-alone Gist for branch-and-bound search of root.
Definition: gist.hpp:212
T * best(int i) const
Return index of best node before i.
Definition: node.hpp:101
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:451
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
int getChild(int n) const
Return index of child no n.
Definition: node.hpp:199
bool isUndetermined(void) const
Return whether this node is undetermined.
Definition: node.hpp:196
bool hasLabel(T *n) const
Return whether node n has a label.
Definition: node.hpp:130
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60