main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Aug 25 2012 03:32:46 for Gecode by
doxygen
1.8.1.2
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: 2011-05-26 00:56:41 +1000 (Thu, 26 May 2011) $ by $Author: schulte $
11
* $Revision: 12022 $
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
= -
Int::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
OmegaTree<TaskView>::OmegaTree
(
Region
&
r
,
const
TaskViewArray<TaskView>
& t)
59
:
TaskTree
<TaskView,
OmegaNode
>(r,t) {
60
for
(
int
i
=
tasks
.size();
i
--; ) {
61
leaf
(
i
).p = 0;
leaf
(
i
).ect = -
Int::Limits::infinity
;
62
}
63
init
();
64
}
65
66
template
<
class
TaskView>
67
forceinline
void
68
OmegaTree<TaskView>::insert
(
int
i
) {
69
leaf(i).p = tasks[
i
].pmin();
70
leaf(i).ect = tasks[
i
].est()+tasks[
i
].pmin();
71
update(i);
72
}
73
74
template
<
class
TaskView>
75
forceinline
void
76
OmegaTree<TaskView>::remove
(
int
i
) {
77
leaf(i).p = 0; leaf(i).ect = -
Int::Limits::infinity
;
78
update(i);
79
}
80
81
template
<
class
TaskView>
82
forceinline
int
83
OmegaTree<TaskView>::ect
(
void
)
const
{
84
return
root().ect;
85
}
86
87
template
<
class
TaskView>
88
forceinline
int
89
OmegaTree<TaskView>::ect
(
int
i
)
const
{
90
// Check whether task i is in?
91
OmegaTree<TaskView>
& o =
const_cast<
OmegaTree<TaskView>
&
>
(*this);
92
if
(o.
leaf
(i).
ect
!= -
Int::Limits::infinity
) {
93
o.
remove
(i);
94
int
ect = o.
root
().
ect
;
95
o.
insert
(i);
96
return
ect;
97
}
else
{
98
return
root().ect;
99
}
100
}
101
102
103
104
/*
105
* Ome lambda tree
106
*/
107
108
forceinline
void
109
OmegaLambdaNode::init
(
const
OmegaLambdaNode
& l,
const
OmegaLambdaNode
&
r
) {
110
OmegaNode::init
(l,r);
111
lp
=
p
;
lect
=
ect
;
resEct
=
undef
;
resLp
=
undef
;
112
}
113
114
forceinline
void
115
OmegaLambdaNode::update
(
const
OmegaLambdaNode
& l,
const
OmegaLambdaNode
&
r
) {
116
OmegaNode::update
(l,r);
117
if
(l.
lp
+ r.
p
> l.
p
+ r.
lp
) {
118
resLp
= l.
resLp
;
119
lp
= l.
lp
+ r.
p
;
120
}
else
{
121
resLp
= r.
resLp
;
122
lp
= l.
p
+ r.
lp
;
123
}
124
if
((r.
lect
>=
plus
(l.
ect
,r.
lp
)) && (r.
lect
>=
plus
(l.
lect
,r.
p
))) {
125
lect
= r.
lect
;
resEct
= r.
resEct
;
126
}
else
if
(
plus
(l.
ect
,r.
lp
) >=
plus
(l.
lect
,r.
p
)) {
127
assert(
plus
(l.
ect
,r.
lp
) > r.
lect
);
128
lect
=
plus
(l.
ect
,r.
lp
);
resEct
= r.
resLp
;
129
}
else
{
130
assert((
plus
(l.
lect
,r.
p
) > r.
lect
) &&
131
(
plus
(l.
lect
,r.
p
) >
plus
(l.
ect
,r.
lp
)));
132
lect
=
plus
(l.
lect
,r.
p
);
resEct
= l.
resEct
;
133
}
134
}
135
136
137
template
<
class
TaskView>
138
OmegaLambdaTree<TaskView>::OmegaLambdaTree
(
Region
&
r
,
139
const
TaskViewArray<TaskView>
& t,
140
bool
inc)
141
:
TaskTree
<TaskView,
OmegaLambdaNode
>(r,t) {
142
if
(inc) {
143
// Enter all tasks into tree (omega = all tasks, lambda = empty)
144
for
(
int
i
=
tasks
.size();
i
--; ) {
145
leaf
(
i
).p =
leaf
(
i
).lp =
tasks
[
i
].pmin();
146
leaf
(
i
).ect =
leaf
(
i
).lect =
tasks
[
i
].est()+
tasks
[
i
].pmin();
147
leaf
(
i
).resEct =
OmegaLambdaNode::undef
;
148
leaf
(
i
).resLp =
OmegaLambdaNode::undef
;
149
}
150
update
();
151
}
else
{
152
// Enter no tasks into tree (omega = empty, lambda = empty)
153
for
(
int
i
=
tasks
.size();
i
--; ) {
154
leaf
(
i
).p =
leaf
(
i
).lp = 0;
155
leaf
(
i
).ect =
leaf
(
i
).lect = -
Int::Limits::infinity
;
156
leaf
(
i
).resEct =
OmegaLambdaNode::undef
;
157
leaf
(
i
).resLp =
OmegaLambdaNode::undef
;
158
}
159
init
();
160
}
161
}
162
163
template
<
class
TaskView>
164
forceinline
void
165
OmegaLambdaTree<TaskView>::shift
(
int
i
) {
166
// That means that i is in omega
167
assert(leaf(i).ect > -
Int::Limits::infinity
);
168
leaf(i).p = 0;
169
leaf(i).ect = -
Int::Limits::infinity
;
170
leaf(i).resEct =
i
;
171
leaf(i).resLp =
i
;
172
update(i);
173
}
174
175
template
<
class
TaskView>
176
forceinline
void
177
OmegaLambdaTree<TaskView>::oinsert
(
int
i
) {
178
leaf(i).p = tasks[
i
].pmin();
179
leaf(i).ect = tasks[
i
].est()+tasks[
i
].pmin();
180
update(i);
181
}
182
183
template
<
class
TaskView>
184
forceinline
void
185
OmegaLambdaTree<TaskView>::linsert
(
int
i
) {
186
leaf(i).lp = tasks[
i
].pmin();
187
leaf(i).lect = tasks[
i
].est()+tasks[
i
].pmin();
188
leaf(i).resEct =
i
;
189
leaf(i).resLp =
i
;
190
update(i);
191
}
192
193
template
<
class
TaskView>
194
forceinline
void
195
OmegaLambdaTree<TaskView>::lremove
(
int
i
) {
196
leaf(i).lp = 0;
197
leaf(i).lect = -
Int::Limits::infinity
;
198
leaf(i).resEct =
OmegaLambdaNode::undef
;
199
leaf(i).resLp =
OmegaLambdaNode::undef
;
200
update(i);
201
}
202
203
template
<
class
TaskView>
204
forceinline
bool
205
OmegaLambdaTree<TaskView>::lempty
(
void
)
const
{
206
return
root().resEct < 0;
207
}
208
209
template
<
class
TaskView>
210
forceinline
int
211
OmegaLambdaTree<TaskView>::responsible
(
void
)
const
{
212
return
root().resEct;
213
}
214
215
template
<
class
TaskView>
216
forceinline
int
217
OmegaLambdaTree<TaskView>::ect
(
void
)
const
{
218
return
root().ect;
219
}
220
221
template
<
class
TaskView>
222
forceinline
int
223
OmegaLambdaTree<TaskView>::lect
(
void
)
const
{
224
return
root().lect;
225
}
226
227
}}}
228
229
// STATISTICS: int-prop