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