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, 2007
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/channel.hh>
35
36namespace Gecode { namespace Int { namespace Channel {
37
38 /// Iterates the values to be removed as defined by an array of Boolean views
39 class BoolIter {
40 private:
41 /// The array of Boolean views
42 const ViewArray<BoolView>& x;
43 /// The offset
44 const int o;
45 /// Current position in the array
46 int i;
47 public:
48 /// Initialize iterator
49 BoolIter(const ViewArray<BoolView>& x0, int o0);
50 /// Test whether further values available
51 bool operator ()(void) const;
52 /// Return value
53 int val(void) const;
54 /// Move to the next value
55 void operator ++(void);
56 };
57
58 forceinline
59 BoolIter::BoolIter(const ViewArray<BoolView>& x0, int o0) :
60 x(x0), o(o0), i(0) {
61 while ((i<x.size()) && !x[i].zero())
62 i++;
63 }
64 forceinline bool
65 BoolIter::operator ()(void) const {
66 return i<x.size();
67 }
68 forceinline int
69 BoolIter::val(void) const {
70 assert(x[i].zero());
71 return i+o;
72 }
73 forceinline void
74 BoolIter::operator ++(void) {
75 do {
76 i++;
77 } while ((i<x.size()) && !x[i].zero());
78 }
79
80
81 Actor*
82 LinkMulti::copy(Space& home) {
83 return new (home) LinkMulti(home,*this);
84 }
85
86 forceinline size_t
87 LinkMulti::dispose(Space& home) {
88 Advisors<Advisor> as(c);
89 x.cancel(home,as.advisor());
90 c.dispose(home);
91 (void) MixNaryOnePropagator<BoolView,PC_BOOL_NONE,IntView,PC_INT_DOM>
92 ::dispose(home);
93 return sizeof(*this);
94 }
95
96 PropCost
97 LinkMulti::cost(const Space&, const ModEventDelta& med) const {
98 if ((status == S_ONE) || (IntView::me(med) == ME_INT_VAL))
99 return PropCost::unary(PropCost::LO);
100 else
101 return PropCost::linear(PropCost::LO, x.size());
102 }
103
104 void
105 LinkMulti::reschedule(Space& home) {
106 if (status == S_ONE)
107 BoolView::schedule(home,*this,ME_BOOL_VAL);
108 y.reschedule(home,*this,PC_INT_DOM);
109 }
110
111 ExecStatus
112 LinkMulti::advise(Space&, Advisor&, const Delta& d) {
113 if (status == S_RUN)
114 return ES_FIX;
115 // Detect a one
116 if (BoolView::one(d))
117 status = S_ONE;
118 return ES_NOFIX;
119 }
120
121 ExecStatus
122 LinkMulti::propagate(Space& home, const ModEventDelta& med) {
123 int n = x.size();
124
125 // Always maintain the invariant that y lies inside the x-array
126 assert((y.min()-o >= 0) && (y.max()-o < n));
127
128 if (y.assigned()) {
129 status = S_RUN;
130 int j=y.val()-o;
131 GECODE_ME_CHECK(x[j].one(home));
132 for (int i=0; i<j; i++)
133 GECODE_ME_CHECK(x[i].zero(home));
134 for (int i=j+1; i<n; i++)
135 GECODE_ME_CHECK(x[i].zero(home));
136 return home.ES_SUBSUMED(*this);
137 }
138
139 // Check whether there is a one
140 if (status == S_ONE) {
141 status = S_RUN;
142 for (int i=0; true; i++)
143 if (x[i].one()) {
144 for (int j=0; j<i; j++)
145 GECODE_ME_CHECK(x[j].zero(home));
146 for (int j=i+1; j<n; j++)
147 GECODE_ME_CHECK(x[j].zero(home));
148 GECODE_ME_CHECK(y.eq(home,i+o));
149 return home.ES_SUBSUMED(*this);
150 }
151 GECODE_NEVER;
152 }
153
154 status = S_RUN;
155
156 redo:
157
158 // Assign all Boolean views to zero that are outside bounds
159 {
160 int min=y.min()-o;
161 for (int i=0; i<min; i++)
162 GECODE_ME_CHECK(x[i].zero(home));
163 x.drop_fst(min); o += min; n = x.size();
164
165 int max=y.max()-o;
166 for (int i=max+1; i<n; i++)
167 GECODE_ME_CHECK(x[i].zero(home));
168 x.drop_lst(max); n = x.size();
169 }
170
171 {
172 // Remove zeros on the left
173 int i=0;
174 while ((i < n) && x[i].zero()) i++;
175 if (i >= n)
176 return ES_FAILED;
177 x.drop_fst(i); o += i; n = x.size();
178 }
179
180 {
181 // Remove zeros on the right
182 int i=n-1;
183 while ((i >= 0) && x[i].zero()) i--;
184 assert(i >= 0);
185 x.drop_lst(i); n = x.size();
186 }
187
188 assert(n >= 1);
189
190 // Is there only one left?
191 if (n == 1) {
192 GECODE_ME_CHECK(x[0].one(home));
193 GECODE_ME_CHECK(y.eq(home,o));
194 return home.ES_SUBSUMED(*this);
195 }
196
197 // Update bounds
198 GECODE_ME_CHECK(y.gq(home,o));
199 GECODE_ME_CHECK(y.lq(home,o+n-1));
200 if ((y.min() > o) || (y.max() < o+n-1))
201 goto redo;
202
203 assert((n >= 2) && x[0].none() && x[n-1].none());
204 assert((y.min()-o == 0) && (y.max()-o == n-1));
205
206 // Propagate from y to Boolean views
207 if ((IntView::me(med) == ME_INT_BND) || (IntView::me(med) == ME_INT_DOM)) {
208 ViewValues<IntView> v(y);
209 int i=0;
210 do {
211 int j = v.val()-o;
212 if (i < j) {
213 GECODE_ME_CHECK(x[i].zero(home));
214 ++i;
215 } else if (i > j) {
216 ++v;
217 } else {
218 assert(i == j);
219 ++i; ++v;
220 }
221 } while (v() && (i < n));
222 }
223
224 // Propagate from Boolean views to y
225 if (BoolView::me(med) == ME_BOOL_VAL) {
226 BoolIter bv(x,o);
227 GECODE_ME_CHECK(y.minus_v(home,bv,false));
228 }
229 status = S_NONE;
230 return ES_FIX;
231 }
232
233}}}
234
235// STATISTICS: int-prop
236