main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Jan 28 2020 00:00:00 for Gecode by
doxygen
1.8.17
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
* Last modified:
12
* $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
13
* $Revision: 14967 $
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
!= -
Limits::infinity
);
45
return
(
x
== -
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
!= -
Limits::llinfinity
);
51
return
(
x
== -
Limits::llinfinity
) ?
x
:
x
+
y
;
52
}
53
54
template
<
class
TaskView,
class
Node>
55
forceinline
int
56
TaskTree<TaskView,Node>::n_inner
(
void
)
const
{
57
return
tasks.size()-1;
58
}
59
template
<
class
TaskView,
class
Node>
60
forceinline
int
61
TaskTree<TaskView,Node>::n_nodes
(
void
)
const
{
62
return
2*tasks.size() - 1;
63
}
64
65
template
<
class
TaskView,
class
Node>
66
forceinline
bool
67
TaskTree<TaskView,Node>::n_root
(
int
i
) {
68
return
i
== 0;
69
}
70
template
<
class
TaskView,
class
Node>
71
forceinline
bool
72
TaskTree<TaskView,Node>::n_leaf
(
int
i
)
const
{
73
return
i
>= n_inner();
74
}
75
template
<
class
TaskView,
class
Node>
76
forceinline
int
77
TaskTree<TaskView,Node>::n_left
(
int
i
) {
78
return
2*(
i
+1) - 1;
79
}
80
template
<
class
TaskView,
class
Node>
81
forceinline
bool
82
TaskTree<TaskView,Node>::left
(
int
i
) {
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
89
TaskTree<TaskView,Node>::n_right
(
int
i
) {
90
return
2*(
i
+1);
91
}
92
template
<
class
TaskView,
class
Node>
93
forceinline
bool
94
TaskTree<TaskView,Node>::right
(
int
i
) {
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
101
TaskTree<TaskView,Node>::n_parent
(
int
i
) {
102
return
(
i
+1)/2 - 1;
103
}
104
105
template
<
class
TaskView,
class
Node>
106
forceinline
Node&
107
TaskTree<TaskView,Node>::leaf
(
int
i
) {
108
return
node[_leaf[
i
]];
109
}
110
111
template
<
class
TaskView,
class
Node>
112
forceinline
const
Node&
113
TaskTree<TaskView,Node>::root
(
void
)
const
{
114
return
node[0];
115
}
116
117
template
<
class
TaskView,
class
Node>
118
forceinline
void
119
TaskTree<TaskView,Node>::init
(
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
126
TaskTree<TaskView,Node>::update
(
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
133
TaskTree<TaskView,Node>::update
(
int
i
,
bool
l
) {
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>
144
forceinline
145
TaskTree<TaskView,Node>::TaskTree
(
Region
&
r
,
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>
171
forceinline
172
TaskTree<TaskView,Node>::TaskTree
(
Region
&
r
,
173
const
TaskTree<TaskView,Node2>
&
t
)
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
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:784
Gecode::y
Post propagator for SetVar SetOpType SetVar y
Definition:
set.hh:784
forceinline
#define forceinline
Definition:
config.hpp:173
Gecode::Int::TaskTree::leaf
Node & leaf(int i)
Return leaf for task i.
Definition:
tree.hpp:107
Gecode::Int::TaskTree::n_left
static int n_left(int i)
Return index of left child of node i.
Definition:
tree.hpp:77
Gecode::Int::TaskTree::n_root
static bool n_root(int i)
Whether node i is index of root.
Definition:
tree.hpp:67
Gecode::Iter::Ranges::size
unsigned int size(I &i)
Size of all ranges of range iterator i.
Definition:
ranges-operations.hpp:78
Gecode::Int::TaskTree::n_inner
int n_inner(void) const
Return number of inner nodes.
Definition:
tree.hpp:56
Gecode::Int::Limits::llinfinity
const long long int llinfinity
Infinity for long long integers.
Definition:
int.hh:126
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
t
NodeType t
Type of node.
Definition:
bool-expr.cpp:234
Gecode::Int::plus
int plus(int x, int y)
Safe addition in case x is -Int::Limits::infinity.
Definition:
tree.hpp:43
Gecode::Int::TaskTree::n_leaf
bool n_leaf(int i) const
Whether node i is leaf.
Definition:
tree.hpp:72
Gecode::Int::TaskTree::left
static bool left(int i)
Test whether node i is a left child.
Definition:
tree.hpp:82
Gecode::Int::TaskTree::n_right
static int n_right(int i)
Return index of right child of node i.
Definition:
tree.hpp:89
Gecode
Gecode toplevel namespace
Gecode::Region
Handle to region.
Definition:
region.hpp:61
Gecode::Int::TaskTree
Task trees for task views with node type Node.
Definition:
task.hh:369
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:784
Gecode::Int::TaskTree::TaskTree
friend class TaskTree
Definition:
task.hh:370
Gecode::Int::TaskTree::root
const Node & root(void) const
Return root node.
Definition:
tree.hpp:113
Gecode::Int::TaskTree::n_parent
static int n_parent(int i)
Return index of parent of node i.
Definition:
tree.hpp:101
Gecode::Int::TaskTree::init
void init(void)
Initialize tree after leaves have been initialized.
Definition:
tree.hpp:119
Gecode::Int::TaskTree::update
void update(void)
Update all inner nodes of tree after leaves have been initialized.
Definition:
tree.hpp:126
l
NNF * l
Left subtree.
Definition:
bool-expr.cpp:244
Gecode::Int::Limits::infinity
const int infinity
Infinity for integers.
Definition:
int.hh:120
Gecode::Int::TaskTree::n_nodes
int n_nodes(void) const
Return number of nodes for balanced binary tree.
Definition:
tree.hpp:61
r
NNF * r
Right subtree.
Definition:
bool-expr.cpp:246
Gecode::Int::TaskViewArray
Task view array.
Definition:
task.hh:237
Gecode::Int::TaskTree::right
static bool right(int i)
Test whether node i is a right child.
Definition:
tree.hpp:94