Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
distinct.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Gabor Szokoli <szokoli@gecode.org>
6  *
7  * Contributing authors:
8  * Roberto Castaņeda Lozano <rcas@kth.se>
9  *
10  * Copyright:
11  * Roberto Castaņeda Lozano, 2015
12  * Christian Schulte, 2002
13  * Gabor Szokoli, 2003
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/int/distinct.hh>
41 #include <gecode/int/bool.hh>
42 
43 namespace Gecode {
44 
45  void
46  distinct(Home home, const IntVarArgs& x, IntPropLevel ipl) {
47  using namespace Int;
48  if (x.same())
49  throw ArgumentSame("Int::distinct");
51  ViewArray<IntView> xv(home,x);
52  switch (vbd(ipl)) {
53  case IPL_BND:
55  break;
56  case IPL_DOM:
58  break;
59  default:
61  }
62  }
63 
64  void
65  distinct(Home home, const IntArgs& c, const IntVarArgs& x,
66  IntPropLevel ipl) {
67  using namespace Int;
68  if (x.same())
69  throw ArgumentSame("Int::distinct");
70  if (c.size() != x.size())
71  throw ArgumentSizeMismatch("Int::distinct");
73  ViewArray<OffsetView> cx(home,x.size());
74  for (int i = c.size(); i--; ) {
75  long long int cx_min = (static_cast<long long int>(c[i]) +
76  static_cast<long long int>(x[i].min()));
77  long long int cx_max = (static_cast<long long int>(c[i]) +
78  static_cast<long long int>(x[i].max()));
79  Limits::check(c[i],"Int::distinct");
80  Limits::check(cx_min,"Int::distinct");
81  Limits::check(cx_max,"Int::distinct");
82  cx[i] = OffsetView(x[i],c[i]);
83  }
84  switch (vbd(ipl)) {
85  case IPL_BND:
87  break;
88  case IPL_DOM:
90  break;
91  default:
93  }
94  }
95 
96  void
97  distinct(Home home, const BoolVarArgs& b, const IntVarArgs& x,
98  IntPropLevel ipl) {
99  using namespace Int;
100  if (x.same())
101  throw ArgumentSame("Int::distinct");
102  if (b.size() != x.size())
103  throw ArgumentSizeMismatch("Int::distinct");
104  GECODE_POST;
105 
106  int n = x.size();
107  int min = Limits::max;
108  int max = Limits::min;
109  int m = 0;
110  for (int i=n; i--; )
111  if (!b[i].zero()) {
112  min = std::min(min,x[i].min());
113  max = std::max(max,x[i].max());
114  m++;
115  }
116 
117  if (m < 2)
118  return;
119 
120  int start;
121  if (max < Limits::max-m)
122  start = max+1;
123  else if (min > Limits::min+m)
124  start = min-(m+1);
125  else
126  throw OutOfLimits("Int::distinct");
127 
128  ViewArray<IntView> y(home,m);
129  int j = 0;
130  for (int i=n; i--; )
131  if (b[i].one()) {
132  y[j] = x[i]; j++;
133  } else if (b[i].none()) {
134  y[j] = IntVar(home, Limits::min, Limits::max);
136  (home, b[i], x[i], start+j, y[j])));
137  j++;
138  }
139  assert(j == m);
140 
141  switch (vbd(ipl)) {
142  case IPL_BND:
144  break;
145  case IPL_DOM:
147  break;
148  default:
150  }
151  }
152 
153  void
154  distinct(Home home, const IntVarArgs& x, int c,
155  IntPropLevel ipl) {
156  using namespace Int;
157  if (x.same())
158  throw ArgumentSame("Int::distinct");
159  GECODE_POST;
160 
161  int n = x.size();
162  int min = Limits::max;
163  int max = Limits::min;
164  int m = 0;
165  for (int i=n; i--; )
166  if (!(x[i].assigned() && (x[i].val() == c))) {
167  min = std::min(min,x[i].min());
168  max = std::max(max,x[i].max());
169  m++;
170  }
171 
172  if (m < 2)
173  return;
174 
175  int start;
176  if (max < Limits::max-m)
177  start = max+1;
178  else if (min > Limits::min+m)
179  start = min-(m+1);
180  else
181  throw OutOfLimits("Int::distinct");
182 
183  ViewArray<IntView> y(home,m);
184  int j = 0;
185  for (int i=n; i--; )
186  if (!x[i].in(c)) {
187  y[j] = x[i]; j++;
188  } else if (!(x[i].assigned() && (x[i].val() == c))) {
189  y[j] = IntVar(home, Limits::min, Limits::max);
191  (home, x[i], y[j], c, start+j));
192  j++;
193  }
194  assert(j == m);
195 
196  switch (vbd(ipl)) {
197  case IPL_BND:
199  break;
200  case IPL_DOM:
202  break;
203  default:
205  }
206  }
207 
208 }
209 
210 // STATISTICS: int-post
Bounds propagation.
Definition: int.hh:953
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition: ipl.hpp:37
Exception: Value out of limits
Definition: exception.hpp:44
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1653
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
bool one(const Gecode::FloatValArgs &a)
Check whether has only one coefficients.
Definition: linear.cpp:46
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
static ExecStatus post(Home home, IntView x0, IntView x1, int c0, int c1)
Post if-then-else propagator.
Definition: eqite.hpp:49
Domain consistent distinct propagator.
Definition: distinct.hh:249
const int max
Largest allowed integer value.
Definition: int.hh:112
const int min
Smallest allowed integer value.
Definition: int.hh:114
Gecode::FloatVal c(-8, 8)
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Gecode::IntArgs i(4, 1, 2, 3, 4)
bool same(void) const
Test whether array contains same variable multiply.
Definition: array.hpp:2065
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:46
Offset integer view.
Definition: view.hpp:434
Passing integer variables.
Definition: int.hh:633
Passing integer arguments.
Definition: int.hh:604
Passing Boolean variables.
Definition: int.hh:687
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
If-then-else domain-consistent propagator.
Definition: bool.hh:632
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:949
Naive value distinct propagator.
Definition: distinct.hh:64
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:765
Integer variables.
Definition: int.hh:347
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Exception: Arguments contain same variable multiply
Definition: exception.hpp:80
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:954
Post propagator for SetVar x
Definition: set.hh:765
Bounds consistent distinct propagator.
Definition: distinct.hh:125
Gecode toplevel namespace
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:40
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
Home class for posting propagators
Definition: core.hpp:853
Exception: Arguments are of different size
Definition: exception.hpp:73
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:103