main page
modules
namespaces
classes
files
Gecode home
Generated on Mon Jul 27 2020 00:00:00 for Gecode by
doxygen
1.8.18
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
* 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 <
gecode/set/convex.hh
>
39
40
namespace
Gecode
{
namespace
Set {
namespace
Convex
{
41
42
Actor
*
43
Convex::copy(
Space
& home) {
44
return
new
(home)
Convex
(home,*
this
);
45
}
46
47
ExecStatus
48
Convex::propagate(
Space
& home,
const
ModEventDelta
&) {
49
//I, drop ranges from UB that are shorter than cardMin
50
//II, add range LB.smallest to LB.largest to LB
51
//III, Drop ranges from UB that do not contain all elements of LB
52
//that is: range.min()>LB.smallest or range.max()<LB.largest
53
//This leaves only one range.
54
//II
55
if
(
x0
.
glbSize
()>0) {
56
GECODE_ME_CHECK
(
x0
.
include
(home,
x0
.
glbMin
(),
x0
.
glbMax
()) );
57
}
else
{
58
//If lower bound is empty, we can still constrain the cardinality
59
//maximum with the width of the longest range in UB.
60
//No need to do this if there is anything in LB because UB
61
//becomes a single range then.
62
LubRanges<SetView>
ubRangeIt(
x0
);
63
unsigned
int
maxWidth = 0;
64
for
(;ubRangeIt();++ubRangeIt) {
65
assert(ubRangeIt());
66
maxWidth =
std::max
(maxWidth, ubRangeIt.
width
());
67
}
68
GECODE_ME_CHECK
(
x0
.
cardMax
(home,maxWidth) );
69
}
70
71
72
//I + III
73
74
Region
r
;
75
LubRanges<SetView>
ubRangeIt(
x0
);
76
Iter::Ranges::Cache
ubRangeItC(
r
,ubRangeIt);
77
78
for
(; ubRangeItC(); ++ubRangeItC) {
79
if
(ubRangeItC.
width
() < (
unsigned
int)
x0
.
cardMin
()
80
|| ubRangeItC.
min
() >
x0
.
glbMin
()
//No need to test for empty lb.
81
|| ubRangeItC.
max
() <
x0
.
glbMax
()
82
) {
83
GECODE_ME_CHECK
(
x0
.
exclude
(home,ubRangeItC.
min
(), ubRangeItC.
max
()) );
84
}
85
}
86
if
(
x0
.
assigned
())
87
return
home.
ES_SUBSUMED
(*
this
);
88
return
ES_FIX
;
89
}
90
91
}}}
92
93
// STATISTICS: set-prop
Gecode::Set::SetView::cardMax
unsigned int cardMax(void) const
Return maximum cardinality.
Definition:
set.hpp:86
Gecode::VarImpView::assigned
bool assigned(void) const
Test whether view is assigned.
Definition:
view.hpp:516
Gecode::Set::LubRanges< SetView >
Range iterator for least upper bound of set variable views
Definition:
set.hpp:211
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition:
core.hpp:3563
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode::Actor
Base-class for both propagators and branchers.
Definition:
core.hpp:628
Gecode::Set::SetView::glbSize
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition:
set.hpp:62
Gecode
Gecode toplevel namespace
Gecode::Set::SetView::glbMax
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition:
set.hpp:106
Gecode::Set::SetView::cardMin
unsigned int cardMin(void) const
Return minimum cardinality.
Definition:
set.hpp:82
Gecode::Iter::Ranges::RangeListIter::max
int max(void) const
Return largest value of range.
Definition:
ranges-list.hpp:249
Gecode::Region
Handle to region.
Definition:
region.hpp:55
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:767
convex.hh
Gecode::Set::SetView::exclude
ModEvent exclude(Space &home, int i, int j)
Restrict least upper bound to not contain all elements between and including i and j.
Definition:
set.hpp:156
Gecode::Set::Convex::Convex::Convex
Convex(Space &home, Convex &p)
Constructor for cloning p.
Definition:
conv.hpp:52
Gecode::Iter::Ranges::RangeListIter::min
int min(void) const
Return smallest value of range.
Definition:
ranges-list.hpp:245
Gecode::Iter::Ranges::Cache
Range iterator cache
Definition:
ranges-cache.hpp:45
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition:
core.hpp:477
Gecode::Set::SetView::glbMin
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition:
set.hpp:102
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition:
macros.hpp:52
Gecode::Iter::Ranges::RangeList::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition:
ranges-rangelist.hpp:105
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition:
core.hpp:89
Gecode::UnaryPropagator< SetView, PC_SET_ANY >::x0
SetView x0
Single view.
Definition:
pattern.hpp:58
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:844
Gecode::Iter::Ranges::RangeListIter::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition:
ranges-list.hpp:253
Gecode::Set::SetView::include
ModEvent include(Space &home, int i, int j)
Update greatest lower bound to include all elements between and including i and j.
Definition:
set.hpp:126
Gecode::Set::Convex::Convex
Propagator for the convex constraint
Definition:
convex.hh:58
Gecode::ExecStatus
ExecStatus
Definition:
core.hpp:472