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
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: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
15
* $Revision: 14967 $
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
Gecode::Set::SetView::cardMax
unsigned int cardMax(void) const
Return maximum cardinality.
Definition:
set.hpp:90
Gecode::VarImpView::assigned
bool assigned(void) const
Test whether view is assigned.
Gecode::Set::LubRanges< SetView >
Range iterator for least upper bound of set variable views
Definition:
set.hpp:205
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition:
core.hpp:3614
Gecode::Space
Computation spaces.
Definition:
core.hpp:1748
Gecode::Actor
Base-class for both propagators and branchers.
Definition:
core.hpp:696
Gecode::Set::SetView::glbSize
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition:
set.hpp:66
Gecode
Gecode toplevel namespace
Gecode::Set::SetView::glbMax
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition:
set.hpp:110
Gecode::Set::SetView::cardMin
unsigned int cardMin(void) const
Return minimum cardinality.
Definition:
set.hpp:86
Gecode::Iter::Ranges::RangeListIter::max
int max(void) const
Return largest value of range.
Definition:
ranges-list.hpp:253
Gecode::Region
Handle to region.
Definition:
region.hpp:61
Gecode::Set::Convex::Convex::Convex
Convex(Space &home, bool share, Convex &p)
Constructor for cloning p.
Definition:
conv.hpp:56
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:784
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:160
Gecode::Iter::Ranges::RangeListIter::min
int min(void) const
Return smallest value of range.
Definition:
ranges-list.hpp:249
Gecode::Iter::Ranges::Cache
Range iterator cache
Definition:
ranges-cache.hpp:49
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition:
core.hpp:545
Gecode::Set::SetView::glbMin
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition:
set.hpp:106
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition:
macros.hpp:56
Gecode::Iter::Ranges::RangeList::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition:
ranges-rangelist.hpp:109
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition:
core.hpp:169
Gecode::UnaryPropagator< SetView, PC_SET_ANY >::x0
SetView x0
Single view.
Definition:
propagator.hpp:62
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:848
Gecode::Iter::Ranges::RangeListIter::width
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition:
ranges-list.hpp:257
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:130
Gecode::Set::Convex::Convex
Propagator for the convex constraint
Definition:
convex.hh:62
Gecode::ExecStatus
ExecStatus
Definition:
core.hpp:540