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
unary
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
*
6
* Copyright:
7
* Christian Schulte, 2009
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
#include <algorithm>
35
36
namespace
Gecode
{
namespace
Int {
namespace
Unary {
37
38
/*
39
* Omega tree
40
*/
41
42
forceinline
void
43
OmegaNode::init
(
const
OmegaNode
&,
const
OmegaNode
&) {
44
p
= 0;
ect
= -
Limits::infinity
;
45
}
46
47
forceinline
void
48
OmegaNode::update
(
const
OmegaNode
&
l
,
const
OmegaNode
&
r
) {
49
p
=
l
.p +
r
.p;
50
ect
=
std::max
(
plus
(
l
.ect,
r
.p),
r
.ect);
51
}
52
53
template
<
class
TaskView>
54
forceinline
55
OmegaTree<TaskView>::OmegaTree
(
Region
&
r
,
const
TaskViewArray<TaskView>
&
t
)
56
:
TaskTree
<TaskView,
OmegaNode
>(
r
,
t
) {
57
for
(
int
i
=0;
i
<
tasks
.size();
i
++) {
58
leaf
(
i
).p = 0;
leaf
(
i
).ect = -
Limits::infinity
;
59
}
60
init
();
61
}
62
63
template
<
class
TaskView>
64
forceinline
void
65
OmegaTree<TaskView>::insert
(
int
i
) {
66
leaf(
i
).p = tasks[
i
].pmin();
67
leaf(
i
).ect = tasks[
i
].est()+tasks[
i
].pmin();
68
update
(
i
);
69
}
70
71
template
<
class
TaskView>
72
forceinline
void
73
OmegaTree<TaskView>::remove
(
int
i
) {
74
leaf(
i
).p = 0; leaf(
i
).ect = -
Limits::infinity
;
75
update
(
i
);
76
}
77
78
template
<
class
TaskView>
79
forceinline
int
80
OmegaTree<TaskView>::ect
(
void
)
const
{
81
return
root().ect;
82
}
83
84
template
<
class
TaskView>
85
forceinline
int
86
OmegaTree<TaskView>::ect
(
int
i
)
const
{
87
// Check whether task i is in?
88
OmegaTree<TaskView>
& o =
const_cast<
OmegaTree<TaskView>
&
>
(*this);
89
if
(o.
leaf
(
i
).
ect
!= -
Limits::infinity
) {
90
o.
remove
(
i
);
91
int
ect = o.
root
().
ect
;
92
o.
insert
(
i
);
93
return
ect;
94
}
else
{
95
return
root().ect;
96
}
97
}
98
99
100
101
/*
102
* Omega lambda tree
103
*/
104
105
forceinline
void
106
OmegaLambdaNode::init
(
const
OmegaLambdaNode
&
l
,
const
OmegaLambdaNode
&
r
) {
107
OmegaNode::init
(
l
,
r
);
108
lp
=
p
;
lect
=
ect
;
resEct
=
undef
;
resLp
=
undef
;
109
}
110
111
forceinline
void
112
OmegaLambdaNode::update
(
const
OmegaLambdaNode
&
l
,
const
OmegaLambdaNode
&
r
) {
113
OmegaNode::update
(
l
,
r
);
114
if
(
l
.lp +
r
.p >
l
.p +
r
.lp) {
115
resLp
=
l
.resLp;
116
lp
=
l
.lp +
r
.p;
117
}
else
{
118
resLp
=
r
.resLp;
119
lp
=
l
.p +
r
.lp;
120
}
121
if
((
r
.lect >=
plus
(
l
.ect,
r
.lp)) && (
r
.lect >=
plus
(
l
.lect,
r
.p))) {
122
lect
=
r
.lect;
resEct
=
r
.resEct;
123
}
else
if
(
plus
(
l
.ect,
r
.lp) >=
plus
(
l
.lect,
r
.p)) {
124
assert(
plus
(
l
.ect,
r
.lp) >
r
.lect);
125
lect
=
plus
(
l
.ect,
r
.lp);
resEct
=
r
.resLp;
126
}
else
{
127
assert((
plus
(
l
.lect,
r
.p) >
r
.lect) &&
128
(
plus
(
l
.lect,
r
.p) >
plus
(
l
.ect,
r
.lp)));
129
lect
=
plus
(
l
.lect,
r
.p);
resEct
=
l
.resEct;
130
}
131
}
132
133
134
template
<
class
TaskView>
135
forceinline
136
OmegaLambdaTree<TaskView>::OmegaLambdaTree
(
Region
&
r
,
137
const
TaskViewArray<TaskView>
&
t
,
138
bool
inc)
139
:
TaskTree
<TaskView,
OmegaLambdaNode
>(
r
,
t
) {
140
if
(inc) {
141
// Enter all tasks into tree (omega = all tasks, lambda = empty)
142
for
(
int
i
=0;
i
<
tasks
.size();
i
++) {
143
leaf
(
i
).p =
leaf
(
i
).lp =
tasks
[
i
].pmin();
144
leaf
(
i
).ect =
leaf
(
i
).lect =
tasks
[
i
].est()+
tasks
[
i
].pmin();
145
leaf
(
i
).resEct =
OmegaLambdaNode::undef
;
146
leaf
(
i
).resLp =
OmegaLambdaNode::undef
;
147
}
148
update
();
149
}
else
{
150
// Enter no tasks into tree (omega = empty, lambda = empty)
151
for
(
int
i
=0;
i
<
tasks
.size();
i
++) {
152
leaf
(
i
).p =
leaf
(
i
).lp = 0;
153
leaf
(
i
).ect =
leaf
(
i
).lect = -
Limits::infinity
;
154
leaf
(
i
).resEct =
OmegaLambdaNode::undef
;
155
leaf
(
i
).resLp =
OmegaLambdaNode::undef
;
156
}
157
init
();
158
}
159
}
160
161
template
<
class
TaskView>
162
forceinline
void
163
OmegaLambdaTree<TaskView>::shift
(
int
i
) {
164
// That means that i is in omega
165
assert(leaf(
i
).ect > -
Limits::infinity
);
166
leaf(
i
).p = 0;
167
leaf(
i
).ect = -
Limits::infinity
;
168
leaf(
i
).resEct =
i
;
169
leaf(
i
).resLp =
i
;
170
update
(
i
);
171
}
172
173
template
<
class
TaskView>
174
forceinline
void
175
OmegaLambdaTree<TaskView>::oinsert
(
int
i
) {
176
leaf(
i
).p = tasks[
i
].pmin();
177
leaf(
i
).ect = tasks[
i
].est()+tasks[
i
].pmin();
178
update
(
i
);
179
}
180
181
template
<
class
TaskView>
182
forceinline
void
183
OmegaLambdaTree<TaskView>::linsert
(
int
i
) {
184
leaf(
i
).lp = tasks[
i
].pmin();
185
leaf(
i
).lect = tasks[
i
].est()+tasks[
i
].pmin();
186
leaf(
i
).resEct =
i
;
187
leaf(
i
).resLp =
i
;
188
update
(
i
);
189
}
190
191
template
<
class
TaskView>
192
forceinline
void
193
OmegaLambdaTree<TaskView>::lremove
(
int
i
) {
194
leaf(
i
).lp = 0;
195
leaf(
i
).lect = -
Limits::infinity
;
196
leaf(
i
).resEct =
OmegaLambdaNode::undef
;
197
leaf(
i
).resLp =
OmegaLambdaNode::undef
;
198
update
(
i
);
199
}
200
201
template
<
class
TaskView>
202
forceinline
bool
203
OmegaLambdaTree<TaskView>::lempty
(
void
)
const
{
204
return
root().resEct < 0;
205
}
206
207
template
<
class
TaskView>
208
forceinline
int
209
OmegaLambdaTree<TaskView>::responsible
(
void
)
const
{
210
return
root().resEct;
211
}
212
213
template
<
class
TaskView>
214
forceinline
int
215
OmegaLambdaTree<TaskView>::ect
(
void
)
const
{
216
return
root().ect;
217
}
218
219
template
<
class
TaskView>
220
forceinline
int
221
OmegaLambdaTree<TaskView>::lect
(
void
)
const
{
222
return
root().lect;
223
}
224
225
}}}
226
227
// STATISTICS: int-prop
Gecode::Int::Unary::OmegaTree::OmegaTree
OmegaTree(Region &r, const TaskViewArray< TaskView > &t)
Initialize tree for tasks t.
Definition:
tree.hpp:55
Gecode::Int::Unary::OmegaLambdaTree::shift
void shift(int i)
Shift task with index i from omega to lambda.
Definition:
tree.hpp:163
Gecode::Int::Unary::OmegaLambdaNode::undef
static const int undef
Undefined task.
Definition:
unary.hh:698
Gecode::Int::Unary::OmegaLambdaTree::lect
int lect(void) const
Return earliest completion time of all tasks excluding lambda tasks.
Definition:
tree.hpp:221
Gecode::Int::TaskTree< TaskView, OmegaNode >::leaf
OmegaNode & leaf(int i)
Return leaf for task i.
Definition:
tree.hpp:103
Gecode::Int::Unary::OmegaNode
Node for an omega tree.
Definition:
unary.hh:660
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::Unary::OmegaNode::p
int p
Processing time for subtree.
Definition:
unary.hh:663
Gecode::Int::Unary::OmegaTree::insert
void insert(int i)
Insert task with index i.
Definition:
tree.hpp:65
Gecode::Int::Unary::OmegaLambdaNode::lect
int lect
Earliest completion times for subtree.
Definition:
unary.hh:702
Gecode::Int::Unary::OmegaLambdaTree::OmegaLambdaTree
OmegaLambdaTree(Region &r, const TaskViewArray< TaskView > &t, bool inc=true)
Initialize tree for tasks t with all tasks included, if inc is true.
Definition:
tree.hpp:136
Gecode::Int::Unary::OmegaLambdaNode::lp
int lp
Processing times for subtree.
Definition:
unary.hh:700
Gecode::Int::Unary::OmegaLambdaNode::init
void init(const OmegaLambdaNode &l, const OmegaLambdaNode &r)
Initialize node from left child l and right child r.
Definition:
tree.hpp:106
Gecode::Int::Unary::OmegaLambdaNode::update
void update(const OmegaLambdaNode &l, const OmegaLambdaNode &r)
Update node from left child l and right child r.
Definition:
tree.hpp:112
Gecode::Int::Unary::OmegaNode::ect
int ect
Earliest completion time for subtree.
Definition:
unary.hh:665
Gecode
Gecode toplevel namespace
Gecode::Int::Count::update
void update(IntSet &y, Space &home, IntSet &py)
Definition:
rel.hpp:103
Gecode::Int::Unary::OmegaLambdaTree::responsible
int responsible(void) const
Return responsible task.
Definition:
tree.hpp:209
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< TaskView, OmegaNode >::root
const OmegaNode & root(void) const
Return root node.
Definition:
tree.hpp:109
Gecode::Int::Unary::OmegaLambdaNode::resLp
int resLp
Node which is responsible for lp.
Definition:
unary.hh:706
Gecode::Int::TaskTree< TaskView, OmegaNode >::init
void init(void)
Initialize tree after leaves have been initialized.
Definition:
tree.hpp:115
Gecode::Int::Unary::OmegaTree::remove
void remove(int i)
Remove task with index i.
Definition:
tree.hpp:73
Gecode::Int::Unary::OmegaLambdaTree::oinsert
void oinsert(int i)
Insert task with index i to omega.
Definition:
tree.hpp:175
Gecode::Int::Unary::OmegaLambdaTree::linsert
void linsert(int i)
Insert task with index i to lambda.
Definition:
tree.hpp:183
Gecode::Int::Unary::OmegaNode::init
void init(const OmegaNode &l, const OmegaNode &r)
Initialize node from left child l and right child r.
Definition:
tree.hpp:43
Gecode::Int::Unary::OmegaTree
Omega trees for computing ect of task sets.
Definition:
unary.hh:674
Gecode::Int::TaskTree< TaskView, OmegaLambdaNode >::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::Unary::OmegaLambdaTree::ect
int ect(void) const
Return earliest completion time of all tasks.
Definition:
tree.hpp:215
Gecode::Int::Limits::infinity
const int infinity
Infinity for integers.
Definition:
int.hh:120
Gecode::Int::Unary::OmegaLambdaTree::lempty
bool lempty(void) const
Whether has responsible task.
Definition:
tree.hpp:203
Gecode::Int::Unary::OmegaLambdaNode
Node for an omega lambda tree.
Definition:
unary.hh:695
Gecode::Int::Unary::OmegaTree::ect
int ect(void) const
Return earliest completion time of all tasks.
Definition:
tree.hpp:80
Gecode::Int::Unary::OmegaLambdaNode::resEct
int resEct
Node which is responsible for lect.
Definition:
unary.hh:704
forceinline
#define forceinline
Definition:
config.hpp:192
Gecode::Int::TaskViewArray
Task view array.
Definition:
task.hh:233
Gecode::Int::Unary::OmegaLambdaTree::lremove
void lremove(int i)
Remove task with index i from lambda.
Definition:
tree.hpp:193
Gecode::Int::TaskTree< TaskView, OmegaNode >::tasks
const TaskViewArray< TaskView > & tasks
The tasks from which the tree is computed.
Definition:
task.hh:369
Gecode::Int::Unary::OmegaNode::update
void update(const OmegaNode &l, const OmegaNode &r)
Update node from left child l and right child r.
Definition:
tree.hpp:48
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:844