Generated on Sat Apr 10 2021 00:00:00 for Gecode by doxygen 1.9.1
sequence.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * David Rijsman <David.Rijsman@quintiq.com>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  *
9  * Copyright:
10  * David Rijsman, 2009
11  * Christian Schulte, 2009
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/int/sequence.hh>
39 
40 #include <algorithm>
41 
42 namespace Gecode {
43 
44  using namespace Int;
45 
46  void
47  sequence(Home home, const IntVarArgs& x, const IntSet &s,
48  int q, int l, int u, IntPropLevel) {
49  Limits::check(s.min(),"Int::sequence");
50  Limits::check(s.max(),"Int::sequence");
51 
52  if (x.size() == 0)
53  throw TooFewArguments("Int::sequence");
54 
55  Limits::check(q,"Int::sequence");
56  Limits::check(l,"Int::sequence");
57  Limits::check(u,"Int::sequence");
58 
59  if (same(x))
60  throw ArgumentSame("Int::sequence");
61 
62  if ((q < 1) || (q > x.size()))
63  throw OutOfLimits("Int::sequence");
64 
66 
67  // Normalize l and u
68  l=std::max(0,l); u=std::min(q,u);
69 
70  // Lower bound of values taken can never exceed upper bound
71  if (u < l) {
72  home.fail(); return;
73  }
74 
75  // Already subsumed as any number of values taken is okay
76  if ((0 == l) && (q == u))
77  return;
78 
79  // All variables must take a value in s
80  if (l == q) {
81  for (int i=0; i<x.size(); i++) {
82  IntView xv(x[i]);
83  IntSetRanges ris(s);
84  GECODE_ME_FAIL(xv.inter_r(home,ris,false));
85  }
86  return;
87  }
88 
89  // No variable can take a value in s
90  if (0 == u) {
91  for (int i=0; i<x.size(); i++) {
92  IntView xv(x[i]);
93  IntSetRanges ris(s);
94  GECODE_ME_FAIL(xv.minus_r(home,ris,false));
95  }
96  return;
97  }
98 
99  ViewArray<IntView> xv(home,x);
100  if (s.size() == 1) {
103  (home,xv,s.min(),q,l,u)));
104  } else {
107  (home,xv,s,q,l,u)));
108  }
109  }
110 
111  void
112  sequence(Home home, const BoolVarArgs& x, const IntSet& s,
113  int q, int l, int u, IntPropLevel) {
114  if ((s.min() < 0) || (s.max() > 1))
115  throw NotZeroOne("Int::sequence");
116 
117  if (x.size() == 0)
118  throw TooFewArguments("Int::sequence");
119 
120  Limits::check(q,"Int::sequence");
121  Limits::check(l,"Int::sequence");
122  Limits::check(u,"Int::sequence");
123 
124  if (same(x))
125  throw ArgumentSame("Int::sequence");
126 
127  if ((q < 1) || (q > x.size()))
128  throw OutOfLimits("Int::sequence");
129 
130  GECODE_POST;
131 
132  // Normalize l and u
133  l=std::max(0,l); u=std::min(q,u);
134 
135  // Lower bound of values taken can never exceed upper bound
136  if (u < l) {
137  home.fail(); return;
138  }
139 
140  // Already subsumed as any number of values taken is okay
141  if ((0 == l) && (q == u))
142  return;
143 
144  // Check whether the set is {0,1}, then the number of values taken is q
145  if ((s.min() == 0) && (s.max() == 1)) {
146  if ((l > 0) || (u < q))
147  home.fail();
148  return;
149  }
150  assert(s.min() == s.max());
151 
152  // All variables must take a value in s
153  if (l == q) {
154  if (s.min() == 0) {
155  for (int i=0; i<x.size(); i++) {
156  BoolView xv(x[i]); GECODE_ME_FAIL(xv.zero(home));
157  }
158  } else {
159  assert(s.min() == 1);
160  for (int i=0; i<x.size(); i++) {
161  BoolView xv(x[i]); GECODE_ME_FAIL(xv.one(home));
162  }
163  }
164  return;
165  }
166 
167  // No variable can take a value in s
168  if (0 == u) {
169  if (s.min() == 0) {
170  for (int i=0; i<x.size(); i++) {
171  BoolView xv(x[i]); GECODE_ME_FAIL(xv.one(home));
172  }
173  } else {
174  assert(s.min() == 1);
175  for (int i=0; i<x.size(); i++) {
176  BoolView xv(x[i]); GECODE_ME_FAIL(xv.zero(home));
177  }
178  }
179  return;
180  }
181 
182  ViewArray<BoolView> xv(home,x);
183 
186  (home,xv,s.min(),q,l,u)));
187  }
188 
189 }
190 
191 // STATISTICS: int-post
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
union Gecode::@602::NNF::@65 u
Union depending on nodetype t.
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
Passing Boolean variables.
Definition: int.hh:712
Home class for posting propagators
Definition: core.hpp:856
void fail(void)
Mark space as failed.
Definition: core.hpp:4039
Range iterator for integer sets.
Definition: int.hh:292
Integer sets.
Definition: int.hh:174
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:152
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:158
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:198
Passing integer variables.
Definition: int.hh:656
Exception: Arguments contain same variable multiply
Definition: exception.hpp:80
Boolean view for Boolean variables.
Definition: view.hpp:1380
bool zero(void) const
Test whether view is assigned to be zero.
Definition: bool.hpp:220
bool one(void) const
Test whether view is assigned to be one.
Definition: bool.hpp:224
Integer view for integer variables.
Definition: view.hpp:129
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: int.hpp:186
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: int.hpp:191
Exception: Not 0/1 integer
Definition: exception.hpp:51
Exception: Value out of limits
Definition: exception.hpp:44
Sequence propagator for array of integers
Definition: sequence.hh:101
Exception: Too few arguments available in argument array
Definition: exception.hpp:66
View arrays.
Definition: array.hpp:253
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
Definition: sequence.cpp:47
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:40
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:103
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:77
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:974
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition: array.hpp:1937
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition: limits.hpp:46
Gecode::IntArgs i({1, 2, 3, 4})