Generated on Sun Aug 9 2020 05:34:08 for Gecode by doxygen 1.9.4
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
55
56 do {
57
58 //intersect x1 with (x0.lubMin(),x0.lubMax())
59 //This empties x1 if x0.ub is empty. twice.
61 x0.lubMin()-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 ) {
83 ubRangeItC.min(), ubRangeItC.max()) );
84 }
85 }
86
87 LubRanges<SetView> ubRangeIt2(x1);
88 GECODE_ME_CHECK(x0.intersectI(home,ubRangeIt2) );
89
91 if(x1.lubMin()==x1.glbMin()) {
93 }
94 if(x1.lubMax()==x1.glbMax()) {
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.
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 least upper bound of set variable views
Definition: set.hpp:211
ModEvent intersectI(Space &home, I &iter)
Intersect least upper bound with range sequence described by i.
Definition: set.hpp:164
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 lubMax(void) const
Return maximum of the least upper bound.
Definition: set.hpp:94
int lubMin(void) const
Return minimum of the least upper bound.
Definition: set.hpp:90
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
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
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
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
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
ExecStatus
Definition: core.hpp:472
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition: core.hpp:475