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