Generated on Thu Mar 16 2017 03:24:19 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  * Last modified:
16  * $Date: 2016-05-23 22:18:23 +0200 (Mon, 23 May 2016) $ by $Author: schulte $
17  * $Revision: 15073 $
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  *
42  */
43 
44 #include <gecode/int/distinct.hh>
45 #include <gecode/int/bool.hh>
46 
47 namespace Gecode {
48 
49  void
50  distinct(Home home, const IntVarArgs& x, IntPropLevel ipl) {
51  using namespace Int;
52  if (x.same(home))
53  throw ArgumentSame("Int::distinct");
55  ViewArray<IntView> xv(home,x);
56  switch (vbd(ipl)) {
57  case IPL_BND:
59  break;
60  case IPL_DOM:
62  break;
63  default:
65  }
66  }
67 
68  void
69  distinct(Home home, const IntArgs& c, const IntVarArgs& x,
70  IntPropLevel ipl) {
71  using namespace Int;
72  if (x.same(home))
73  throw ArgumentSame("Int::distinct");
74  if (c.size() != x.size())
75  throw ArgumentSizeMismatch("Int::distinct");
77  ViewArray<OffsetView> cx(home,x.size());
78  for (int i = c.size(); i--; ) {
79  long long int cx_min = (static_cast<long long int>(c[i]) +
80  static_cast<long long int>(x[i].min()));
81  long long int cx_max = (static_cast<long long int>(c[i]) +
82  static_cast<long long int>(x[i].max()));
83  Limits::check(c[i],"Int::distinct");
84  Limits::check(cx_min,"Int::distinct");
85  Limits::check(cx_max,"Int::distinct");
86  cx[i] = OffsetView(x[i],c[i]);
87  }
88  switch (vbd(ipl)) {
89  case IPL_BND:
91  break;
92  case IPL_DOM:
94  break;
95  default:
97  }
98  }
99 
100  void
101  distinct(Home home, const BoolVarArgs& b, const IntVarArgs& x,
102  IntPropLevel ipl) {
103  using namespace Int;
104  if (x.same(home))
105  throw ArgumentSame("Int::distinct");
106  if (b.size() != x.size())
107  throw ArgumentSizeMismatch("Int::distinct");
108  GECODE_POST;
109 
110  int n = x.size();
111  int min = Limits::max;
112  int max = Limits::min;
113  int m = 0;
114  for (int i=n; i--; )
115  if (!b[i].zero()) {
116  min = std::min(min,x[i].min());
117  max = std::max(max,x[i].max());
118  m++;
119  }
120 
121  if (m < 2)
122  return;
123 
124  int start;
125  if (max < Limits::max-m)
126  start = max+1;
127  else if (min > Limits::min+m)
128  start = min-(m+1);
129  else
130  throw OutOfLimits("Int::distinct");
131 
132  ViewArray<IntView> y(home,m);
133  int j = 0;
134  for (int i=n; i--; )
135  if (b[i].one()) {
136  y[j] = x[i]; j++;
137  } else if (b[i].none()) {
138  y[j] = IntVar(home, Limits::min, Limits::max);
140  (home, b[i], x[i], start+j, y[j])));
141  j++;
142  }
143  assert(j == m);
144 
145  switch (vbd(ipl)) {
146  case IPL_BND:
148  break;
149  case IPL_DOM:
151  break;
152  default:
154  }
155  }
156 
157  void
158  distinct(Home home, const IntVarArgs& x, int c,
159  IntPropLevel ipl) {
160  using namespace Int;
161  if (x.same(home))
162  throw ArgumentSame("Int::distinct");
163  GECODE_POST;
164 
165  int n = x.size();
166  int min = Limits::max;
167  int max = Limits::min;
168  int m = 0;
169  for (int i=n; i--; )
170  if (!(x[i].assigned() && (x[i].val() == c))) {
171  min = std::min(min,x[i].min());
172  max = std::max(max,x[i].max());
173  m++;
174  }
175 
176  if (m < 2)
177  return;
178 
179  int start;
180  if (max < Limits::max-m)
181  start = max+1;
182  else if (min > Limits::min+m)
183  start = min-(m+1);
184  else
185  throw OutOfLimits("Int::distinct");
186 
187  ViewArray<IntView> y(home,m);
188  int j = 0;
189  for (int i=n; i--; )
190  if (!x[i].in(c)) {
191  y[j] = x[i]; j++;
192  } else if (!(x[i].assigned() && (x[i].val() == c))) {
193  y[j] = IntVar(home, Limits::min, Limits::max);
195  (home, x[i], y[j], c, start+j));
196  j++;
197  }
198  assert(j == m);
199 
200  switch (vbd(ipl)) {
201  case IPL_BND:
203  break;
204  case IPL_DOM:
206  break;
207  default:
209  }
210  }
211 
212 }
213 
214 // STATISTICS: int-post
Bounds propagation.
Definition: int.hh:945
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition: ipl.hpp:41
Exception: Value out of limits
Definition: exception.hpp:48
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1669
const FloatNum max
Largest allowed float value.
Definition: float.hh:846
bool one(const Gecode::FloatValArgs &a)
Check whether has only one coefficients.
Definition: linear.cpp:50
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
static ExecStatus post(Home home, IntView x0, IntView x1, int c0, int c1)
Post if-then-else propagator.
Definition: eqite.hpp:53
Domain consistent distinct propagator.
Definition: distinct.hh:253
const int max
Largest allowed integer value.
Definition: int.hh:114
const int min
Smallest allowed integer value.
Definition: int.hh:116
Gecode::FloatVal c(-8, 8)
const FloatNum min
Smallest allowed float value.
Definition: float.hh:848
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:50
Offset integer view.
Definition: view.hpp:422
Passing integer variables.
Definition: int.hh:637
Passing integer arguments.
Definition: int.hh:608
Passing Boolean variables.
Definition: int.hh:691
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
If-then-else domain-consistent propagator.
Definition: bool.hh:636
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:941
Naive value distinct propagator.
Definition: distinct.hh:68
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Integer variables.
Definition: int.hh:351
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
Exception: Arguments contain same variable multiply
Definition: exception.hpp:84
Domain propagation Preferences: prefer speed or memory.
Definition: int.hh:946
Bounds consistent distinct propagator.
Definition: distinct.hh:129
Gecode toplevel namespace
struct Gecode::@554::NNF::@60::@61 b
For binary nodes (and, or, eqv)
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:44
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
Definition: limits.hpp:50
Home class for posting propagators
Definition: core.hpp:905
Exception: Arguments are of different size
Definition: exception.hpp:77
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:107
bool same(const Space &home) const
Test whether array contains same variable multiply.
Definition: array.hpp:2081