Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
hull.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 *
7 * Contributing authors:
8 * Gabor Szokoli <szokoli@gecode.org>
9 *
10 * Copyright:
11 * Guido Tack, 2004
12 * Christian Schulte, 2004
13 * Gabor Szokoli, 2004
14 *
15 * This file is part of Gecode, the generic constraint
16 * development environment:
17 * http://www.gecode.org
18 *
19 * Permission is hereby granted, free of charge, to any person obtaining
20 * a copy of this software and associated documentation files (the
21 * "Software"), to deal in the Software without restriction, including
22 * without limitation the rights to use, copy, modify, merge, publish,
23 * distribute, sublicense, and/or sell copies of the Software, and to
24 * permit persons to whom the Software is furnished to do so, subject to
25 * the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be
28 * included in all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37 *
38 */
39
40#include <gecode/set/convex.hh>
41
42namespace Gecode { namespace Set { namespace Convex {
43
44 Actor*
46 return new (home) ConvexHull(home,*this);
47 }
48
51 //x1 is the convex hull of x0
52
53 GECODE_ME_CHECK( x1.cardMin(home,x0.cardMin()) );
54 GECODE_ME_CHECK( x0.cardMax(home,x1.cardMax()) );
55
56 do {
57
58 //intersect x1 with (x0.lubMin(),x0.lubMax())
59 //This empties x1 if x0.ub is empty. twice.
60 GECODE_ME_CHECK( x1.exclude(home,Limits::min,
61 x0.lubMin()-1) );
62 GECODE_ME_CHECK( x1.exclude(home,x0.lubMax()+1,
63 Limits::max) );
64
65 int minElement = std::min(x1.glbMin(),x0.glbMin());
66 int maxElement = std::max(x1.glbMax(),x0.glbMax());
67
68 if (minElement<maxElement) {
69 GECODE_ME_CHECK( x1.include(home, minElement, maxElement));
70 }
71
72 unsigned int cardMin = x1.cardMin();
73
74 Region r;
75 LubRanges<SetView> ubRangeIt(x1);
76 Iter::Ranges::Cache ubRangeItC(r,ubRangeIt);
77 for (;ubRangeItC();++ubRangeItC) {
78 if (ubRangeItC.width() < cardMin
79 || ubRangeItC.min() > minElement //No need to test for empty lb.
80 || ubRangeItC.max() < maxElement
81 ) {
82 GECODE_ME_CHECK( x1.exclude(home,
83 ubRangeItC.min(), ubRangeItC.max()) );
84 }
85 }
86
87 LubRanges<SetView> ubRangeIt2(x1);
88 GECODE_ME_CHECK(x0.intersectI(home,ubRangeIt2) );
89
90 if (x1.lubMin()!=BndSet::MIN_OF_EMPTY) {
91 if(x1.lubMin()==x1.glbMin()) {
92 GECODE_ME_CHECK(x0.include(home,x1.lubMin()));
93 }
94 if(x1.lubMax()==x1.glbMax()) {
95 GECODE_ME_CHECK(x0.include(home,x1.lubMax()));
96 }
97 }
98 } while(x0.assigned()&&!x1.assigned());
99
100 //If x0 is assigned, x1 should be too.
101 assert(x1.assigned() || !x0.assigned());
102
103 if (x1.assigned()) {
104 return home.ES_SUBSUMED(*this);
105 }
106
107 return ES_NOFIX;
108 }
109
110}}}
111
112// 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
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition var-imp.hpp:112
ConvexHull(Space &home, ConvexHull &)
Constructor for cloning p.
Definition hull.hpp:52
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition hull.cpp:50
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition hull.cpp:45
Range iterator for the least upper bound.
Definition var-imp.hpp:317
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
const int min
Smallest allowed integer in integer set.
Definition set.hh:99
const int max
Largest allowed integer in integer set.
Definition set.hh:97
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_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475