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 *
6 * Copyright:
7 * Christian Schulte, 2011
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34#include <gecode/int/distinct.hh>
35
36namespace Gecode { namespace Int { namespace NValues {
37
38 template<class VY>
39 forceinline
40 IntBase<VY>::IntBase(Home home, ValSet& vs0, ViewArray<IntView>& x, VY y)
41 : MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>(home,x,y),
42 vs(vs0) {}
43
44 template<class VY>
45 forceinline
46 IntBase<VY>::IntBase(Space& home, IntBase<VY>& p)
47 : MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>(home, p) {
48 vs.update(home, p.vs);
49 }
50
51 template<class VY>
52 forceinline size_t
53 IntBase<VY>::dispose(Space& home) {
54 vs.dispose(home);
55 (void) MixNaryOnePropagator<IntView,PC_INT_DOM,VY,PC_INT_BND>
56 ::dispose(home);
57 return sizeof(*this);
58 }
59
60 template<class VY>
61 PropCost
62 IntBase<VY>::cost(const Space&, const ModEventDelta&) const {
63 return PropCost::quadratic(PropCost::HI, x.size());
64 }
65
66 template<class VY>
67 void
68 IntBase<VY>::add(Space& home) {
69 int n=x.size();
70 for (int i=n; i--; )
71 if (x[i].assigned()) {
72 vs.add(home, x[i].val());
73 x[i] = x[--n];
74 }
75 x.size(n);
76 }
77
78 template<class VY>
79 void
80 IntBase<VY>::disjoint(Space& home, Region& r, int*& dis, int& n_dis) {
81 // Compute positions of disjoint views
82 int n=x.size();
83 dis = r.alloc<int>(n); n_dis = 0;
84
85 int i=0;
86 while (i < n)
87 switch (vs.compare(x[i])) {
88 case Iter::Ranges::CS_SUBSET:
89 // All values are already contained in vs, eliminate x[i]
90 x[i].cancel(home, *this, PC_INT_DOM);
91 x[i] = x[--n];
92 break;
93 case Iter::Ranges::CS_DISJOINT:
94 dis[n_dis++] = i++;
95 break;
96 case Iter::Ranges::CS_NONE:
97 i++;
98 break;
99 default:
100 GECODE_NEVER;
101 }
102 x.size(n);
103 }
104
105 template<class VY>
106 void
107 IntBase<VY>::eliminate(Space& home) {
108 int n=x.size();
109 for (int i=n; i--; )
110 if (vs.subset(x[i])) {
111 // All values are already contained in vs, eliminate x[i]
112 x[i].cancel(home, *this, PC_INT_DOM);
113 x[i] = x[--n];
114 }
115 x.size(n);
116 }
117
118 template<class VY>
119 ExecStatus
120 IntBase<VY>::all_in_valset(Space& home) {
121 for (int i=x.size(); i--; ) {
122 ValSet::Ranges vsr(vs);
123 GECODE_ME_CHECK(x[i].inter_r(home, vsr, false));
124 }
125 return home.ES_SUBSUMED(*this);
126 }
127
128 template<class VY>
129 ExecStatus
130 IntBase<VY>::prune_lower(Space& home, int* dis, int n_dis) {
131 assert(n_dis > 0);
132
133 // At least one more value will be needed
134 GECODE_ME_CHECK(y.gq(home,vs.size() + 1));
135
136 Region r;
137
138 // Only one additional value is allowed
139 if (y.max() == vs.size() + 1) {
140 // Compute possible values
141 ViewRanges<IntView>* r_dis = r.alloc<ViewRanges<IntView> >(n_dis);
142 for (int i=n_dis; i--; )
143 r_dis[i] = ViewRanges<IntView>(x[dis[i]]);
144 Iter::Ranges::NaryInter iv(r, r_dis, n_dis);
145 // Is there a common value at all?
146 if (!iv())
147 return ES_FAILED;
148 ValSet::Ranges vsr(vs);
149 Iter::Ranges::NaryUnion pv(r,iv,vsr);
150 // Enforce common values
151 for (int i=x.size(); i--; ) {
152 pv.reset();
153 GECODE_ME_CHECK(x[i].inter_r(home, pv, false));
154 }
155 return ES_OK;
156 }
157
158 // Compute independent set for lower bound
159 // ovl is a bit-matrix defining whether two views overlap
160 SymBitMatrix ovl(r,x.size());
161 // deg[i] is the degree of x[i]
162 int* deg = r.alloc<int>(x.size());
163 // ovl_i[i] is an array of indices j such that x[j] overlaps with x[i]
164 int** ovl_i = r.alloc<int*>(x.size());
165 // n_ovl_i[i] defines how many integers are stored for ovl_i[i]
166 int* n_ovl_i = r.alloc<int>(x.size());
167 {
168#ifndef NDEBUG
169 // Initialize all to null pointers so that things crash ;-)
170 for (int i=x.size(); i--; )
171 ovl_i[i] = nullptr;
172#endif
173 // For each i there can be at most n_dis-1 entries in ovl_i[i]
174 int* m = r.alloc<int>(n_dis*(n_dis-1));
175 for (int i=n_dis; i--; ) {
176 deg[dis[i]] = 0;
177 ovl_i[dis[i]] = m; m += n_dis-1;
178 }
179 }
180
181 // Initialize overlap matrix by analyzing the view ranges
182 {
183 // Compute how many events are needed
184 // One event for the end marker
185 int n_re = 1;
186 // Two events for each range
187 for (int i=n_dis; i--; )
188 for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx)
189 n_re += 2;
190
191 // Allocate and initialize events
192 RangeEvent* re = r.alloc<RangeEvent>(n_re);
193 {
194 int j=0;
195 for (int i=n_dis; i--; )
196 for (ViewRanges<IntView> rx(x[dis[i]]); rx(); ++rx) {
197 // Event when a range starts
198 re[j].ret=RET_FST; re[j].val=rx.min(); re[j].view=dis[i]; j++;
199 // Event when a range ends
200 re[j].ret=RET_LST; re[j].val=rx.max(); re[j].view=dis[i]; j++;
201 }
202 // Make this the last event
203 re[j].ret=RET_END; re[j].val=Int::Limits::infinity;
204 assert(j+1 == n_re);
205 }
206 // Sort and process events
207 Support::quicksort(re,n_re);
208
209 // Current views with a range being active
210 Support::BitSet<Region> cur(r,static_cast<unsigned int>(x.size()));
211 // Process all events
212 for (int i=0; true; i++)
213 switch (re[i].ret) {
214 case RET_FST:
215 // Process all overlapping views
216 for (Iter::Values::BitSet<Support::BitSet<Region> > j(cur);
217 j(); ++j) {
218 int di = re[i].view, dj = j.val();
219 if (!ovl.get(di,dj)) {
220 ovl.set(di,dj);
221 ovl_i[di][deg[di]++] = dj;
222 ovl_i[dj][deg[dj]++] = di;
223 }
224 }
225 cur.set(static_cast<unsigned int>(re[i].view));
226 break;
227 case RET_LST:
228 cur.clear(static_cast<unsigned int>(re[i].view));
229 break;
230 case RET_END:
231 goto done;
232 default:
233 GECODE_NEVER;
234 }
235 done:
236 r.free<RangeEvent>(re,n_re);
237 }
238
239 // While deg changes, n_ovl_i remains unchanged and is needed, so copy it
240 for (int i=n_dis; i--; ) {
241 assert(deg[dis[i]] < n_dis);
242 n_ovl_i[dis[i]] = deg[dis[i]];
243 }
244
245 // Views in the independent set
246 int* ind = r.alloc<int>(n_dis);
247 int n_ind = 0;
248
249 while (n_dis > 0) {
250 int i_min = n_dis-1;
251 int d_min = deg[dis[i_min]];
252 unsigned int s_min = x[dis[i_min]].size();
253
254 // Find view with smallest (degree,size)
255 for (int i=n_dis-1; i--; )
256 if ((d_min > deg[dis[i]]) ||
257 ((d_min == deg[dis[i]]) && (s_min > x[dis[i]].size()))) {
258 i_min = i;
259 d_min = deg[dis[i]];
260 s_min = x[dis[i]].size();
261 }
262
263 // i_min refers to view with smallest (degree,size)
264 ind[n_ind++] = dis[i_min]; dis[i_min] = dis[--n_dis];
265
266 // Filter out non disjoint views
267 for (int i=n_dis; i--; )
268 if (ovl.get(dis[i],ind[n_ind-1])) {
269 // Update degree information
270 for (int j=n_ovl_i[dis[i]]; j--; )
271 deg[ovl_i[dis[i]][j]]--;
272 // Eliminate view
273 dis[i] = dis[--n_dis];
274 }
275 }
276 // Enforce lower bound
277 GECODE_ME_CHECK(y.gq(home,vs.size() + n_ind));
278
279 // Prune, if possible
280 if (vs.size() + n_ind == y.max()) {
281 // Only values from the indepent set a can be taken
282 ViewRanges<IntView>* r_ind = r.alloc<ViewRanges<IntView> >(n_ind);
283 for (int i=n_ind; i--; )
284 r_ind[i] = ViewRanges<IntView>(x[ind[i]]);
285 Iter::Ranges::NaryUnion v_ind(r, r_ind, n_ind);
286 ValSet::Ranges vsr(vs);
287 v_ind |= vsr;
288 for (int i=x.size(); i--; ) {
289 v_ind.reset();
290 GECODE_ME_CHECK(x[i].inter_r(home,v_ind,false));
291 }
292 }
293 return ES_OK;
294 }
295
296 template<class VY>
297 forceinline ExecStatus
298 IntBase<VY>::prune_upper(Space& home, Graph& g) {
299 if (!g) {
300 g.init(home,vs,x);
301 } else {
302 g.purge();
303 g.sync();
304 }
305 GECODE_ME_CHECK(y.lq(home, g.size()));
306 if (y.min() == g.size()) {
307 // All values must be taken on
308 if (vs.size() + x.size() == g.size()) {
309 // This is in fact a distinct, simplify and rewrite
310 for (int i=x.size(); i--; ) {
311 ValSet::Ranges vsr(vs);
312 GECODE_ME_CHECK(x[i].minus_r(home, vsr, false));
313 }
314 GECODE_REWRITE(*this,Distinct::Dom<IntView>::post(home(*this),x));
315 }
316 if (g.mark())
317 GECODE_ES_CHECK(g.prune(home));
318 }
319 return ES_OK;
320 }
321
322}}}
323
324// STATISTICS: int-prop