Generated on Sat Oct 20 2018 12:43:45 for Gecode by doxygen 1.8.13
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 
40 namespace Gecode { namespace Set { namespace Convex {
41 
42  Actor*
43  Convex::copy(Space& home) {
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) {
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
unsigned int cardMax(void) const
Return maximum 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:126
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3490
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
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
Handle to region.
Definition: region.hpp:55
Propagation has computed fixpoint.
Definition: core.hpp:476
Computation spaces.
Definition: core.hpp:1701
Base-class for both propagators and branchers.
Definition: core.hpp:627
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: conv.cpp:48
int max(void) const
Return largest value of range.
Range iterator for least upper bound of set variable views
Definition: set.hpp:211
Convex(Space &home, Convex &p)
Constructor for cloning p.
Definition: conv.hpp:52
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
int min(void) const
Return smallest value of range.
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
bool assigned(void) const
Test whether view is assigned.
Definition: view.hpp:516
Range iterator cache
ExecStatus
Definition: core.hpp:471
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
int glbMax(void) const
Return maximum of the greatest lower bound.
Definition: set.hpp:106
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
Gecode toplevel namespace
Propagator for the convex constraint
Definition: convex.hh:58
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition: set.hpp:62