main page
modules
namespaces
classes
files
Gecode home
Generated on Sat May 25 2013 18:00:40 for Gecode by
doxygen
1.8.3.1
gecode
set
convex
conv.cpp
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
* Gabor Szokoli <szokoli@gecode.org>
7
*
8
* Copyright:
9
* Guido Tack, 2004
10
* Christian Schulte, 2004
11
* Gabor Szokoli, 2004
12
*
13
* Last modified:
14
* $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
15
* $Revision: 13068 $
16
*
17
* This file is part of Gecode, the generic constraint
18
* development environment:
19
* http://www.gecode.org
20
*
21
* Permission is hereby granted, free of charge, to any person obtaining
22
* a copy of this software and associated documentation files (the
23
* "Software"), to deal in the Software without restriction, including
24
* without limitation the rights to use, copy, modify, merge, publish,
25
* distribute, sublicense, and/or sell copies of the Software, and to
26
* permit persons to whom the Software is furnished to do so, subject to
27
* the following conditions:
28
*
29
* The above copyright notice and this permission notice shall be
30
* included in all copies or substantial portions of the Software.
31
*
32
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39
*
40
*/
41
42
#include <
gecode/set/convex.hh
>
43
44
namespace
Gecode {
namespace
Set {
namespace
Convex
{
45
46
Actor
*
47
Convex::copy(
Space
& home,
bool
share) {
48
return
new
(home)
Convex
(home,share,*
this
);
49
}
50
51
ExecStatus
52
Convex::propagate(
Space
& home,
const
ModEventDelta
&) {
53
//I, drop ranges from UB that are shorter than cardMin
54
//II, add range LB.smallest to LB.largest to LB
55
//III, Drop ranges from UB that do not contain all elements of LB
56
//that is: range.min()>LB.smallest or range.max()<LB.largest
57
//This leaves only one range.
58
//II
59
if
(
x0
.
glbSize
()>0) {
60
GECODE_ME_CHECK
(
x0
.
include
(home,
x0
.
glbMin
(),
x0
.
glbMax
()) );
61
}
else
{
62
//If lower bound is empty, we can still constrain the cardinality
63
//maximum with the width of the longest range in UB.
64
//No need to do this if there is anything in LB because UB
65
//becomes a single range then.
66
LubRanges<SetView>
ubRangeIt(
x0
);
67
unsigned
int
maxWidth = 0;
68
for
(;ubRangeIt();++ubRangeIt) {
69
assert(ubRangeIt());
70
maxWidth =
std::max
(maxWidth, ubRangeIt.
width
());
71
}
72
GECODE_ME_CHECK
(
x0
.
cardMax
(home,maxWidth) );
73
}
74
75
76
//I + III
77
78
Region
r
(home);
79
LubRanges<SetView>
ubRangeIt(
x0
);
80
Iter::Ranges::Cache
ubRangeItC(r,ubRangeIt);
81
82
for
(; ubRangeItC(); ++ubRangeItC) {
83
if
(ubRangeItC.
width
() < (
unsigned
int)
x0
.
cardMin
()
84
|| ubRangeItC.
min
() >
x0
.
glbMin
()
//No need to test for empty lb.
85
|| ubRangeItC.
max
() <
x0
.
glbMax
()
86
) {
87
GECODE_ME_CHECK
(
x0
.
exclude
(home,ubRangeItC.
min
(), ubRangeItC.
max
()) );
88
}
89
}
90
if
(
x0
.
assigned
())
91
return
home.
ES_SUBSUMED
(*
this
);
92
return
ES_FIX
;
93
}
94
95
}}}
96
97
// STATISTICS: set-prop