main page
modules
namespaces
classes
files
Gecode home
Generated on Sat Nov 9 2013 19:18:31 for Gecode by
doxygen
1.8.4
gecode
set
sequence
common.hpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Guido Tack <tack@gecode.org>
5
* Christian Schulte <schulte@gecode.org>
6
*
7
* Contributing authors:
8
* Gabor Szokoli <szokoli@gecode.org>
9
*
10
* Copyright:
11
* Guido Tack, 2004
12
* Christian Schulte, 2004
13
* Gabor Szokoli, 2004
14
*
15
* Last modified:
16
* $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
17
* $Revision: 13068 $
18
*
19
* This file is part of Gecode, the generic constraint
20
* development environment:
21
* http://www.gecode.org
22
*
23
* Permission is hereby granted, free of charge, to any person obtaining
24
* a copy of this software and associated documentation files (the
25
* "Software"), to deal in the Software without restriction, including
26
* without limitation the rights to use, copy, modify, merge, publish,
27
* distribute, sublicense, and/or sell copies of the Software, and to
28
* permit persons to whom the Software is furnished to do so, subject to
29
* the following conditions:
30
*
31
* The above copyright notice and this permission notice shall be
32
* included in all copies or substantial portions of the Software.
33
*
34
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41
*
42
*/
43
44
namespace
Gecode {
namespace
Set {
namespace
Sequence {
45
46
inline
ExecStatus
47
propagateSeq
(
Space
& home,
bool
& modified,
bool
&
assigned
,
48
ViewArray<SetView>
&
x
) {
49
int
lastElem = x.
size
()-1;
50
int
cur_max =
BndSet::MAX_OF_EMPTY
;
51
int
cur_min =
BndSet::MIN_OF_EMPTY
;
52
53
Region
r
(home);
54
Support::DynamicArray<int,Region>
ub(r);
55
56
for
(
int
i
=0;
i
<lastElem;
i
++) {
57
if
(x[
i
].glbSize() > 0)
58
cur_max =
std::max
(cur_max, x[
i
].glbMax());
59
if
(x[
i
].cardMin() > 0)
60
cur_max =
std::max
(cur_max, x[
i
].lubMinN(x[
i
].cardMin()-1));
61
if
(cur_max >=
Limits::min
)
62
GECODE_SET_ME_CHECK_VAL_B
(modified,
63
x[
i
+1].
exclude
(home,
Limits::min
,
64
cur_max),
65
assigned);
66
67
if
(x[lastElem-
i
].lubSize() > 0) {
68
cur_min =
std::min
(cur_min, x[lastElem-
i
].glbMin());
69
if
(x[lastElem-
i
].cardMin() > 0) {
70
// Compute n-th largest element in x[lastElem-i].lub
71
// for n = x[lastElem-i].cardMin()-1
72
int
maxN =
BndSet::MAX_OF_EMPTY
;
73
int
j=0;
74
for
(
LubRanges<SetView>
ubr(x[lastElem-
i
]); ubr(); ++ubr, ++j) {
75
ub[2*j]=ubr.min(); ub[2*j+1]=ubr.max();
76
}
77
unsigned
int
xcm = x[lastElem-
i
].cardMin()-1;
78
while
(j--) {
79
unsigned
int
width =
static_cast<
unsigned
int
>
(ub[2*j+1]-ub[2*j]+1);
80
if
(width > xcm) {
81
maxN =
static_cast<
int
>
(ub[2*j+1]-xcm);
82
break
;
83
}
84
xcm -= width;
85
}
86
cur_min =
std::min
(cur_min, maxN);
87
}
88
}
89
if
(
Limits::max
>=cur_min)
90
GECODE_SET_ME_CHECK_VAL_B
(modified,
91
x[lastElem-
i
-1].
exclude
(home, cur_min,
92
Limits::max
),
93
assigned);
94
}
95
return
ES_NOFIX
;
96
}
97
98
}}}
99
100
// STATISTICS: set-prop