Generated on Sat Feb 7 2015 02:01:21 for Gecode by doxygen 1.8.9.1
tree.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2009
9  * Guido Tack, 2010
10  *
11  * Last modified:
12  * $Date: 2013-03-11 06:26:07 +0100 (Mon, 11 Mar 2013) $ by $Author: tack $
13  * $Revision: 13487 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 namespace Gecode { namespace Int {
41 
42  forceinline int
43  plus(int x, int y) {
44  assert(y != -Int::Limits::infinity);
45  return (x == -Int::Limits::infinity) ? x : x+y;
46  }
47 
48  forceinline long long int
49  plus(long long int x, long long int y) {
50  assert(y != -Int::Limits::llinfinity);
51  return (x == -Int::Limits::llinfinity) ? x : x+y;
52  }
53 
54  template<class TaskView, class Node>
55  forceinline int
57  return tasks.size()-1;
58  }
59  template<class TaskView, class Node>
60  forceinline int
62  return 2*tasks.size() - 1;
63  }
64 
65  template<class TaskView, class Node>
66  forceinline bool
68  return i == 0;
69  }
70  template<class TaskView, class Node>
71  forceinline bool
73  return i >= n_inner();
74  }
75  template<class TaskView, class Node>
76  forceinline int
78  return 2*(i+1) - 1;
79  }
80  template<class TaskView, class Node>
81  forceinline bool
83  assert(!n_root(i));
84  // A left node has an odd number
85  return (i & 1) != 0;
86  }
87  template<class TaskView, class Node>
88  forceinline int
90  return 2*(i+1);
91  }
92  template<class TaskView, class Node>
93  forceinline bool
95  assert(!n_root(i));
96  // A left node has an even number
97  return (i & 1) == 0;
98  }
99  template<class TaskView, class Node>
100  forceinline int
102  return (i+1)/2 - 1;
103  }
104 
105  template<class TaskView, class Node>
106  forceinline Node&
108  return node[_leaf[i]];
109  }
110 
111  template<class TaskView, class Node>
112  forceinline const Node&
114  return node[0];
115  }
116 
117  template<class TaskView, class Node>
118  forceinline void
120  for (int i=n_inner(); i--; )
121  node[i].init(node[n_left(i)],node[n_right(i)]);
122  }
123 
124  template<class TaskView, class Node>
125  forceinline void
127  for (int i=n_inner(); i--; )
128  node[i].update(node[n_left(i)],node[n_right(i)]);
129  }
130 
131  template<class TaskView, class Node>
132  forceinline void
134  if (l)
135  i = _leaf[i];
136  assert(!n_root(i));
137  do {
138  i = n_parent(i);
139  node[i].update(node[n_left(i)],node[n_right(i)]);
140  } while (!n_root(i));
141  }
142 
143  template<class TaskView, class Node>
146  const TaskViewArray<TaskView>& t)
147  : tasks(t),
148  node(r.alloc<Node>(n_nodes())),
149  _leaf(r.alloc<int>(tasks.size())) {
150  // Compute a sorting map to order by non decreasing est
151  int* map = r.alloc<int>(tasks.size());
152  sort<TaskView,STO_EST,true>(map, tasks);
153  // Compute inverse of sorting map
154  for (int i=tasks.size(); i--; )
155  _leaf[map[i]] = i;
156  r.free<int>(map,tasks.size());
157  // Compute index of first leaf in tree: the next larger power of two
158  int fst = 1;
159  while (fst < tasks.size())
160  fst <<= 1;
161  fst--;
162  // Remap task indices to leaf indices
163  for (int i=tasks.size(); i--; )
164  if (_leaf[i] + fst >= n_nodes())
165  _leaf[i] += fst - tasks.size();
166  else
167  _leaf[i] += fst;
168  }
169 
170  template<class TaskView, class Node> template<class Node2>
174  : tasks(t.tasks),
175  node(r.alloc<Node>(n_nodes())),
176  _leaf(r.alloc<int>(tasks.size())) {
177  for (int i=tasks.size(); i--; )
178  _leaf[i] = t._leaf[i];
179  }
180 
181 }}
182 
183 // STATISTICS: int-prop
static int n_right(int i)
Return index of right child of node i.
Definition: tree.hpp:89
NodeType t
Type of node.
Definition: bool-expr.cpp:234
Task view array.
Definition: task.hh:233
static int n_left(int i)
Return index of left child of node i.
Definition: tree.hpp:77
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
static bool right(int i)
Test whether node i is a right child.
Definition: tree.hpp:94
Handle to region.
Definition: region.hpp:61
Gecode::IntArgs i(4, 1, 2, 3, 4)
static int n_parent(int i)
Return index of parent of node i.
Definition: tree.hpp:101
void update(void)
Update all inner nodes of tree after leaves have been initialized.
Definition: tree.hpp:126
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
void init(void)
Initialize tree after leaves have been initialized.
Definition: tree.hpp:119
int plus(int x, int y)
Safe addition in case x is -IntLimits::infinity.
Definition: tree.hpp:43
friend class TaskTree
Definition: task.hh:366
unsigned int size(I &i)
Size of all ranges of range iterator i.
int * _leaf
Map task number to leaf node number in right order.
Definition: task.hh:373
int n_inner(void) const
Return number of inner nodes.
Definition: tree.hpp:56
const int infinity
Infinity for integers.
Definition: int.hh:117
bool n_leaf(int i) const
Whether node i is leaf.
Definition: tree.hpp:72
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
static bool left(int i)
Test whether node i is a left child.
Definition: tree.hpp:82
#define forceinline
Definition: config.hpp:132
void free(T *b, long unsigned int n)
Delete n objects allocated from the region starting at b.
Definition: region.hpp:352
Node & leaf(int i)
Return leaf for task i.
Definition: tree.hpp:107
static bool n_root(int i)
Whether node i is index of root.
Definition: tree.hpp:67
Gecode toplevel namespace
const Node & root(void) const
Return root node.
Definition: tree.hpp:113
const TaskViewArray< TaskView > & tasks
The tasks from which the tree is computed.
Definition: task.hh:369
const long long int llinfinity
Infinity for long long integers.
Definition: int.hh:123
int n_nodes(void) const
Return number of nodes for balanced binary tree.
Definition: tree.hpp:61
Task trees for task views with node type Node.
Definition: task.hh:365