Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.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  * 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 
48  Convex::propagate(Space& home, const ModEventDelta&) {
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
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
Base-class for both propagators and branchers.
Definition: core.hpp:628
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.
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Handle to region.
Definition: region.hpp:55
Propagator for the convex constraint
Definition: convex.hh:58
Convex(Space &home, Convex &p)
Constructor for cloning p.
Definition: conv.hpp:52
Range iterator for least upper bound of set variable views
Definition: set.hpp:211
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 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
unsigned int glbSize(void) const
Return the number of elements in the greatest lower bound.
Definition: set.hpp:62
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
Definition: core.hpp:472
@ ES_FIX
Propagation has computed fixpoint.
Definition: core.hpp:477
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