main page
modules
namespaces
classes
files
Gecode home
Generated on Wed Sep 5 2012 18:51:48 for Gecode by
doxygen
1.8.1.1
gecode
int
cumulative
opt-prop.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: 2011-07-14 06:44:50 +1000 (Thu, 14 Jul 2011) $ by $Author: tack $
13
* $Revision: 12202 $
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
#include <algorithm>
41
42
namespace
Gecode {
namespace
Int {
namespace
Cumulative {
43
44
template
<
class
OptTask,
class
Cap>
45
forceinline
46
OptProp<OptTask,Cap>::OptProp
(
Home
home, Cap c0,
TaskArray<OptTask>
& t)
47
:
TaskProp
<OptTask,Int::
PC_INT_DOM
>(home,t),
c
(c0) {
48
c
.subscribe(home,*
this
,
PC_INT_BND
);
49
}
50
51
template
<
class
OptTask,
class
Cap>
52
forceinline
53
OptProp<OptTask,Cap>::OptProp
(
Space
& home,
bool
shared
,
54
OptProp<OptTask,Cap>
& p)
55
:
TaskProp
<OptTask,Int::
PC_INT_DOM
>(home,shared,p) {
56
c
.update(home,shared,p.
c
);
57
}
58
59
template
<
class
OptTask,
class
Cap>
60
forceinline
ExecStatus
61
OptProp<OptTask,Cap>::post
(
Home
home, Cap
c
,
TaskArray<OptTask>
& t) {
62
// Capacity must be nonnegative
63
GECODE_ME_CHECK
(c.gq(home, 0));
64
// Check for overload by single task and remove excluded tasks
65
int
n=t.
size
(),
m
=0;
66
for
(
int
i
=n;
i
--; ) {
67
if
(t[
i
].
c
() > c.
max
())
68
GECODE_ME_CHECK
(t[
i
].excluded(home));
69
if
(t[
i
].excluded())
70
t[
i
]=t[--n];
71
else
if
(t[
i
].mandatory())
72
m
++;
73
}
74
t.
size
(n);
75
if
(t.
size
() < 2) {
76
if
(t.
size
() == 1) {
77
if
(t[0].mandatory()) {
78
GECODE_ME_CHECK
(c.gq(home, t[0].c()));
79
return
ES_OK
;
80
}
else
if
(c.min() >= t[0].c()) {
81
return
ES_OK
;
82
}
83
}
else
{
84
return
ES_OK
;
85
}
86
}
87
if
(c.assigned() && c.val()==1) {
88
TaskArray<typename TaskTraits<OptTask>::UnaryTask
> mt(home,t.
size
());
89
for
(
int
i
=t.
size
();
i
--; )
90
mt[
i
]=t[
i
];
91
return
Unary::OptProp<typename TaskTraits<OptTask>::UnaryTask
>
92
::post
(home,mt);
93
}
94
if
(
m
== t.
size
()) {
95
TaskArray<typename TaskTraits<OptTask>::ManTask
> mt(home,
m
);
96
for
(
int
i
=
m
;
i
--; )
97
mt[
i
].init(t[
i
]);
98
return
ManProp<typename TaskTraits<OptTask>::ManTask
,Cap>
99
::post
(home,c,mt);
100
}
101
(void)
new
(home)
OptProp<OptTask,Cap>
(home,
c
,t);
102
return
ES_OK
;
103
}
104
105
template
<
class
OptTask,
class
Cap>
106
Actor
*
107
OptProp<OptTask,Cap>::copy
(
Space
& home,
bool
share) {
108
return
new
(home)
OptProp<OptTask,Cap>
(home,share,*
this
);
109
}
110
111
template
<
class
OptTask,
class
Cap>
112
forceinline
size_t
113
OptProp<OptTask,Cap>::dispose
(
Space
& home) {
114
(void)
TaskProp<OptTask,Int::PC_INT_DOM>::dispose
(home);
115
c
.cancel(home,*
this
,
PC_INT_BND
);
116
return
sizeof
(*this);
117
}
118
119
template
<
class
OptTask,
class
Cap>
120
ExecStatus
121
OptProp<OptTask,Cap>::propagate
(
Space
& home,
const
ModEventDelta
& med) {
122
// Did one of the Boolean views change?
123
if
(
Int::BoolView::me
(med) ==
Int::ME_BOOL_VAL
)
124
GECODE_ES_CHECK
((purge<OptTask,Int::PC_INT_DOM>(home,*
this
,t,
c
)));
125
// Only bounds changes?
126
if
(
Int::IntView::me
(med) !=
Int::ME_INT_DOM
)
127
GECODE_ES_CHECK
(
overload
(home,
c
.
max
(),t));
128
129
bool
subsumed
;
130
GECODE_ES_CHECK
(
basic
(home,subsumed,
c
,t));
131
if
(subsumed)
132
return
home.
ES_SUBSUMED
(*
this
);
133
134
// Partition into mandatory and optional activities
135
int
n = t.size();
136
int
i
=0, j=n-1;
137
while
(
true
) {
138
while
((i < n) && t[i].mandatory()) i++;
139
while
((j >= 0) && !t[j].mandatory()) j--;
140
if
(i >= j)
break
;
141
std::swap(t[i],t[j]);
142
}
143
144
if
(i > 1) {
145
// Truncate array to only contain mandatory tasks
146
t.size(i);
147
GECODE_ES_CHECK
(
edgefinding
(home,
c
.
max
(),t));
148
// Restore to also include optional tasks
149
t.size(n);
150
}
151
152
if
(Cap::varderived() &&
c
.assigned() &&
c
.val()==1) {
153
// Check that tasks do not overload resource
154
for
(
int
i=t.size(); i--; )
155
if
(t[i].
c
() > 1)
156
GECODE_ME_CHECK
(t[i].excluded(home));
157
// Rewrite to unary resource constraint
158
TaskArray<typename TaskTraits<OptTask>::UnaryTask
> ut(home,t.size());
159
for
(
int
i=t.size(); i--;)
160
ut[i]=t[i];
161
GECODE_REWRITE
(*
this
,
162
(
Unary::OptProp
<
typename
TaskTraits<OptTask>::UnaryTask
>
163
::
post
(home(*
this
),ut)));
164
}
else
{
165
return
ES_NOFIX
;
166
}
167
}
168
169
}}}
170
171
// STATISTICS: int-prop