Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.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) {
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
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.
friend class Space
Definition core.hpp:1068
Handle to region.
Definition region.hpp:55
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
Convex(Space &home, Convex &p)
Constructor for cloning p.
Definition conv.hpp:52
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)
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3570
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
Propagators for convexity.
Definition convex.hh:45
Finite integer sets.
Definition var-imp.hpp:137
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
ExecStatus
Definition core.hpp:472
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477