Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
41#include <gecode/int/bool.hh>
42
43namespace Gecode {
44
45 void
46 distinct(Home home, const IntVarArgs& x, IntPropLevel ipl) {
47 using namespace Int;
48 if (same(x))
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 (same(x))
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=0; 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 (same(x))
101 throw ArgumentSame("Int::distinct");
102 if (b.size() != x.size())
103 throw ArgumentSizeMismatch("Int::distinct");
105
106 int n = x.size();
107 int min = Limits::max;
108 int max = Limits::min;
109 int m = 0;
110 for (int i=0; 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=0; 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 (same(x))
158 throw ArgumentSame("Int::distinct");
160
161 int n = x.size();
162 int min = Limits::max;
163 int max = Limits::min;
164 int m = 0;
165 for (int i=0; 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=0; 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
Passing Boolean variables.
Definition int.hh:721
FloatNum size(void) const
Return size of float value (distance between maximum and minimum)
Definition val.hpp:78
Home class for posting propagators
Definition core.hpp:856
Passing integer arguments.
Definition int.hh:634
Passing integer variables.
Definition int.hh:662
Integer variables.
Definition int.hh:371
Exception: Arguments contain same variable multiply
Definition exception.hpp:80
Exception: Arguments are of different size
Definition exception.hpp:73
static ExecStatus post(Home home, BoolView b, V0 x0, V1 x1, V2 x2)
Post if-then-else propagator.
Definition ite.hpp:176
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition bnd.hpp:476
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for views x.
Definition dom.hpp:45
static ExecStatus post(Home home, IntView x0, IntView x1, int c0, int c1)
Post if-then-else propagator.
Definition eqite.hpp:49
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition val.hpp:185
Offset integer view.
Definition view.hpp:443
Exception: Value out of limits
Definition exception.hpp:44
View arrays.
Definition array.hpp:253
#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
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:989
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:994
@ IPL_BND
Bounds propagation.
Definition int.hh:993
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
const int min
Smallest allowed integer value.
Definition int.hh:118
const int max
Largest allowed integer value.
Definition int.hh:116
Finite domain integers.
Gecode toplevel namespace
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
IntPropLevel vbd(IntPropLevel ipl)
Extract value, bounds, or domain propagation from propagation level.
Definition ipl.hpp:37
bool same(VarArgArray< Var > x, VarArgArray< Var > y)
Definition array.hpp:1943
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:773