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, 2015
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/rel.hh>
35
36namespace Gecode { namespace Int { namespace Arithmetic {
37
38 template<class VA, class VB, bool tiebreak>
39 forceinline
40 ArgMax<VA,VB,tiebreak>::ArgMax(Home home, IdxViewArray<VA>& x0, VB y0)
41 : Propagator(home), x(x0), y(y0) {
42 x.subscribe(home,*this,PC_INT_BND);
43 y.subscribe(home,*this,PC_INT_DOM);
44 }
45
46 template<class VA, class VB, bool tiebreak>
47 ExecStatus
48 ArgMax<VA,VB,tiebreak>::post(Home home, IdxViewArray<VA>& x, VB y) {
49 assert(x.size() > 0);
50 if (x.size() == 1) {
51 GECODE_ME_CHECK(y.eq(home,x[0].idx));
52 } else if (y.assigned()) {
53 int max=0;
54 while (x[max].idx < y.val())
55 max++;
56 assert(x[max].idx == y.val());
57 if (tiebreak)
58 for (int i=0; i<max; i++)
59 GECODE_ES_CHECK((Rel::Le<VA,VA>::post(home,
60 x[i].view,x[max].view)));
61 else
62 for (int i=0; i<max; i++)
63 GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home,
64 x[i].view,x[max].view)));
65 for (int i=max+1; i<x.size(); i++)
66 GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home,
67 x[i].view,x[max].view)));
68 } else {
69 (void) new (home) ArgMax<VA,VB,tiebreak>(home,x,y);
70 }
71 return ES_OK;
72 }
73
74 template<class VA, class VB, bool tiebreak>
75 forceinline
76 ArgMax<VA,VB,tiebreak>::ArgMax(Space& home, ArgMax<VA,VB,tiebreak>& p)
77 : Propagator(home,p) {
78 x.update(home,p.x);
79 y.update(home,p.y);
80 }
81
82 template<class VA, class VB, bool tiebreak>
83 Actor*
84 ArgMax<VA,VB,tiebreak>::copy(Space& home) {
85 return new (home) ArgMax<VA,VB,tiebreak>(home,*this);
86 }
87
88 template<class VA, class VB, bool tiebreak>
89 PropCost
90 ArgMax<VA,VB,tiebreak>::cost(const Space&, const ModEventDelta&) const {
91 return PropCost::linear(PropCost::LO,x.size()+1);
92 }
93
94 template<class VA, class VB, bool tiebreak>
95 void
96 ArgMax<VA,VB,tiebreak>::reschedule(Space& home) {
97 x.reschedule(home,*this,PC_INT_BND);
98 y.reschedule(home,*this,PC_INT_DOM);
99 }
100
101 template<class VA, class VB, bool tiebreak>
102 ExecStatus
103 ArgMax<VA,VB,tiebreak>::propagate(Space& home, const ModEventDelta&) {
104 /*
105 * A key invariant is as follows: for each value i in the domain
106 * of y there is an index-value pair with index i in x.
107 */
108
109 // Compute lower and upper bounds for the maximum and its first position.
110 int p = x[0].idx;
111 int l = x[0].view.min();
112 int u = x[0].view.max();
113 for (int i=1; i<x.size(); i++) {
114 if (l < x[i].view.min()) {
115 p = x[i].idx; l = x[i].view.min();
116 }
117 if (u < x[i].view.max())
118 u = x[i].view.max();
119 }
120
121 // Eliminate elements from x and y that are too small
122 {
123 Region r;
124
125 // Values to delete from y
126 int* d=r.alloc<int>(y.size());
127 // Number of values to delete
128 int n = 0;
129
130 int i=0, j=0;
131 ViewValues<VB> iy(y);
132
133 while ((i < x.size()) && iy()) {
134 if (x[i].idx == iy.val()) {
135 if (x[i].view.max() < l) {
136 x[i].view.cancel(home,*this,PC_INT_BND);
137 d[n++]=x[i].idx;
138 } else {
139 x[j++]=x[i];
140 }
141 ++iy;
142 } else {
143 assert(x[i].idx < iy.val());
144 if (x[i].view.max() < l) {
145 x[i].view.cancel(home,*this,PC_INT_BND);
146 } else {
147 x[j++]=x[i];
148 }
149 }
150 i++;
151 }
152 while (i < x.size())
153 if (x[i].view.max() < l) {
154 x[i].view.cancel(home,*this,PC_INT_BND); i++;
155 } else {
156 x[j++]=x[i++];
157 }
158 x.size(j);
159
160 if (static_cast<unsigned int>(n) == y.size())
161 return ES_FAILED;
162 Iter::Values::Array id(d,n);
163 GECODE_ME_CHECK(y.minus_v(home,id,false));
164 }
165
166 /*
167 * Now the following invariant holds:
168 * - for all q in y: u >= x(q).max() >= l
169 * - if l==u, then exists q in y: x(q).max = u
170 */
171
172 if (tiebreak && (l == u))
173 GECODE_ME_CHECK(y.lq(home,p));
174
175 if (y.assigned()) {
176 int max=0;
177 while (x[max].idx < y.val())
178 max++;
179 assert(x[max].idx == y.val());
180 if (tiebreak)
181 for (int i=0; i<max; i++)
182 GECODE_ES_CHECK((Rel::Le<VA,VA>::post(home(*this),
183 x[i].view,x[max].view)));
184 else
185 for (int i=0; i<max; i++)
186 GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home(*this),
187 x[i].view,x[max].view)));
188 for (int i=max+1; i<x.size(); i++)
189 GECODE_ES_CHECK((Rel::Lq<VA,VA>::post(home(*this),
190 x[i].view,x[max].view)));
191 return home.ES_SUBSUMED(*this);
192 }
193
194 // Recompute the upper bound for elements in y
195 {
196 ViewValues<VB> iy(y);
197 int i=0;
198 // Skip smaller elements
199 while (x[i].idx < y.min())
200 i++;
201 u=x[i].view.max();
202 // Skip the minimal element
203 i++; ++iy;
204 while (iy()) {
205 if (x[i].idx == iy.val()) {
206 u = std::max(u,x[i].view.max());
207 ++iy;
208 } else {
209 assert(x[i].idx < iy.val());
210 }
211 i++;
212 }
213 }
214
215 // Constrain elements in x but not in y
216 {
217 int i = 0;
218 // Elements which must be smaller (for tiebreaking)
219 if (tiebreak)
220 while ((i < x.size()) && (x[i].idx < y.min())) {
221 GECODE_ME_CHECK(x[i].view.le(home,u));
222 i++;
223 }
224 else
225 while ((i < x.size()) && (x[i].idx < y.min())) {
226 GECODE_ME_CHECK(x[i].view.lq(home,u));
227 i++;
228 }
229 assert(x[i].idx == y.min());
230
231 // Elements which cannot be larger
232 ViewValues<VB> iy(y);
233 // Skip the minimal element
234 i++; ++iy;
235 while ((i < x.size()) && iy()) {
236 if (x[i].idx == iy.val()) {
237 ++iy;
238 } else {
239 assert(x[i].idx < iy.val());
240 GECODE_ME_CHECK(x[i].view.lq(home,u));
241 }
242 i++;
243 }
244 while (i < x.size()) {
245 assert(x[i].idx > y.max());
246 GECODE_ME_CHECK(x[i].view.lq(home,u));
247 i++;
248 }
249 }
250 return tiebreak ? ES_NOFIX : ES_FIX;
251 }
252
253 template<class VA, class VB, bool tiebreak>
254 forceinline size_t
255 ArgMax<VA,VB,tiebreak>::dispose(Space& home) {
256 x.cancel(home,*this,PC_INT_BND);
257 y.cancel(home,*this,PC_INT_DOM);
258 (void) Propagator::dispose(home);
259 return sizeof(*this);
260 }
261
262}}}
263
264// STATISTICS: int-prop
265