this repo has no description
dekker.one
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*
45 ConvexHull::copy(Space& home) {
46 return new (home) ConvexHull(home,*this);
47 }
48
49 ExecStatus
50 ConvexHull::propagate(Space& home, const ModEventDelta&) {
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