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
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
Gecode::Set::Sequence::propagateSeq
ExecStatus propagateSeq(Space &home, bool &modified, bool &assigned, ViewArray< SetView > &x)
Definition:
common.hpp:47
Gecode::x
Post propagator for SetVar x
Definition:
set.hh:784
Gecode::Int::Sequence::exclude
ModEvent exclude(Space &home, View &x, int s)
Prune view x to exclude all values from s.
Definition:
set-op.hpp:141
Gecode::Set::LubRanges< SetView >
Range iterator for least upper bound of set variable views
Definition:
set.hpp:205
Gecode::Set::Limits::min
const int min
Smallest allowed integer in integer set.
Definition:
set.hh:103
Gecode::Int::Precede::assigned
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition:
single.hpp:47
Gecode::Support::DynamicArray
Array with arbitrary number of elements.
Definition:
dynamic-array.hpp:48
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
Gecode::SetVar::cardMin
unsigned int cardMin(void) const
Return cardinality minimum.
Definition:
set.hpp:82
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:850
Gecode::Space
Computation spaces.
Definition:
core.hpp:1748
Gecode::Set::BndSet::MIN_OF_EMPTY
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition:
var-imp.hpp:116
Gecode
Gecode toplevel namespace
GECODE_SET_ME_CHECK_VAL_B
#define GECODE_SET_ME_CHECK_VAL_B(modified, tell, f)
Definition:
common.hpp:49
Gecode::Set::Limits::max
const int max
Largest allowed integer in integer set.
Definition:
set.hh:101
Gecode::Set::BndSet::MAX_OF_EMPTY
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition:
var-imp.hpp:114
Gecode::Region
Handle to region.
Definition:
region.hpp:61
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:784
Gecode::ViewArray< SetView >
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition:
core.hpp:543
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:848
Gecode::ExecStatus
ExecStatus
Definition:
core.hpp:540