this repo has no description
dekker.one
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
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");
50 GECODE_POST;
51 ViewArray<IntView> xv(home,x);
52 switch (vbd(ipl)) {
53 case IPL_BND:
54 GECODE_ES_FAIL(Distinct::Bnd<IntView>::post(home,xv));
55 break;
56 case IPL_DOM:
57 GECODE_ES_FAIL(Distinct::Dom<IntView>::post(home,xv));
58 break;
59 default:
60 GECODE_ES_FAIL(Distinct::Val<IntView>::post(home,xv));
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");
72 GECODE_POST;
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:
86 GECODE_ES_FAIL(Distinct::Bnd<OffsetView>::post(home,cx));
87 break;
88 case IPL_DOM:
89 GECODE_ES_FAIL(Distinct::Dom<OffsetView>::post(home,cx));
90 break;
91 default:
92 GECODE_ES_FAIL(Distinct::Val<OffsetView>::post(home,cx));
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");
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=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);
135 GECODE_ES_FAIL((Bool::IteDom<IntView,ConstIntView,IntView>::post
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:
143 GECODE_ES_FAIL(Distinct::Bnd<IntView>::post(home,y));
144 break;
145 case IPL_DOM:
146 GECODE_ES_FAIL(Distinct::Dom<IntView>::post(home,y));
147 break;
148 default:
149 GECODE_ES_FAIL(Distinct::Val<IntView>::post(home,y));
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");
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=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);
190 GECODE_ES_FAIL(Distinct::EqIte::post
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:
198 GECODE_ES_FAIL(Distinct::Bnd<IntView>::post(home,y));
199 break;
200 case IPL_DOM:
201 GECODE_ES_FAIL(Distinct::Dom<IntView>::post(home,y));
202 break;
203 default:
204 GECODE_ES_FAIL(Distinct::Val<IntView>::post(home,y));
205 }
206 }
207
208}
209
210// STATISTICS: int-post