Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
40namespace Gecode { namespace Set { namespace Convex {
41
42 Actor*
44 return new (home) Convex(home,*this);
45 }
46
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) {
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
Range iterator cache
int max(void) const
Return largest value of range.
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
int min(void) const
Return smallest value of range.
Handle to region.
Definition region.hpp:55
Propagator for the convex constraint
Definition convex.hh:58
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition conv.cpp:43
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition conv.cpp:48
Range iterator for the least upper bound.
Definition var-imp.hpp:317
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
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
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition set.hpp:106
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition set.hpp:102
unsigned int cardMin(void) const
Return minimum cardinality.
Definition set.hpp:82
unsigned int cardMax(void) const
Return maximum cardinality.
Definition set.hpp:86
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition set.hpp:62
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
Computation spaces.
Definition core.hpp:1742
bool assigned(void) const
Test whether view is assigned.
Definition view.hpp:516
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:767
ExecStatus
Definition core.hpp:472
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477