Generated on Sat Feb 7 2015 02:01:29 for Gecode by doxygen 1.8.9.1
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  * Last modified:
14  * $Date: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
15  * $Revision: 13068 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <gecode/set/convex.hh>
43 
44 namespace Gecode { namespace Set { namespace Convex {
45 
46  Actor*
47  Convex::copy(Space& home, bool share) {
48  return new (home) Convex(home,share,*this);
49  }
50 
52  Convex::propagate(Space& home, const ModEventDelta&) {
53  //I, drop ranges from UB that are shorter than cardMin
54  //II, add range LB.smallest to LB.largest to LB
55  //III, Drop ranges from UB that do not contain all elements of LB
56  //that is: range.min()>LB.smallest or range.max()<LB.largest
57  //This leaves only one range.
58  //II
59  if (x0.glbSize()>0) {
61  } else {
62  //If lower bound is empty, we can still constrain the cardinality
63  //maximum with the width of the longest range in UB.
64  //No need to do this if there is anything in LB because UB
65  //becomes a single range then.
66  LubRanges<SetView> ubRangeIt(x0);
67  unsigned int maxWidth = 0;
68  for (;ubRangeIt();++ubRangeIt) {
69  assert(ubRangeIt());
70  maxWidth = std::max(maxWidth, ubRangeIt.width());
71  }
72  GECODE_ME_CHECK( x0.cardMax(home,maxWidth) );
73  }
74 
75 
76  //I + III
77 
78  Region r(home);
79  LubRanges<SetView> ubRangeIt(x0);
80  Iter::Ranges::Cache ubRangeItC(r,ubRangeIt);
81 
82  for (; ubRangeItC(); ++ubRangeItC) {
83  if (ubRangeItC.width() < (unsigned int) x0.cardMin()
84  || ubRangeItC.min() > x0.glbMin() //No need to test for empty lb.
85  || ubRangeItC.max() < x0.glbMax()
86  ) {
87  GECODE_ME_CHECK( x0.exclude(home,ubRangeItC.min(), ubRangeItC.max()) );
88  }
89  }
90  if (x0.assigned())
91  return home.ES_SUBSUMED(*this);
92  return ES_FIX;
93  }
94 
95 }}}
96 
97 // STATISTICS: set-prop
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: set.hpp:86
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:130
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition: set.hpp:66
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
int min(void) const
Return smallest value of range.
int glbMin(void) const
Return minimum of the greatest lower bound.
Definition: set.hpp:106
unsigned int cardMax(void) const
Return maximum cardinality.
Definition: set.hpp:90
Handle to region.
Definition: region.hpp:61
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
Base-class for both propagators and branchers.
Definition: core.hpp:666
Range iterator for least upper bound of set variable views
Definition: set.hpp:205
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: set.hpp:110
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
Convex(Space &home, bool share, Convex &p)
Constructor for cloning p.
Definition: conv.hpp:56
Range iterator cache
ExecStatus
Definition: core.hpp:523
bool assigned(void) const
Test whether view is assigned.
Definition: view.hpp:448
int max(void) const
Return largest value of range.
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
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:160
Gecode toplevel namespace
Propagator for the convex constraint
Definition: convex.hh:62
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173