Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
link-multi.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 *
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
39 class BoolIter {
40 private:
42 const ViewArray<BoolView>& x;
44 const int o;
46 int i;
47 public:
49 BoolIter(const ViewArray<BoolView>& x0, int o0);
51 bool operator ()(void) const;
53 int val(void) const;
55 void operator ++(void);
56 };
57
60 x(x0), o(o0), i(0) {
61 while ((i<x.size()) && !x[i].zero())
62 i++;
63 }
64 forceinline bool
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
75 do {
76 i++;
77 } while ((i<x.size()) && !x[i].zero());
78 }
79
80
81 Actor*
83 return new (home) LinkMulti(home,*this);
84 }
85
86 forceinline size_t
89 x.cancel(home,as.advisor());
90 c.dispose(home);
92 ::dispose(home);
93 return sizeof(*this);
94 }
95
97 LinkMulti::cost(const Space&, const ModEventDelta& med) const {
98 if ((status == S_ONE) || (IntView::me(med) == ME_INT_VAL))
100 else
102 }
103
104 void
106 if (status == S_ONE)
108 y.reschedule(home,*this,PC_INT_DOM);
109 }
110
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
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 }
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)) {
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
int n
Number of negative literals for node type.
Base-class for both propagators and branchers.
Definition core.hpp:628
Base-class for advisors.
Definition core.hpp:1292
Class to iterate over advisors of a council.
Definition core.hpp:1266
A & advisor(void) const
Return advisor.
Definition core.hpp:4010
Generic domain change information to be supplied to advisors.
Definition core.hpp:204
bool one(void) const
Test whether view is assigned to be one.
Definition bool.hpp:224
Iterates the values to be removed as defined by an array of Boolean views.
BoolIter(const ViewArray< BoolView > &x0, int o0)
Initialize iterator.
int val(void) const
Return value.
bool operator()(void) const
Test whether further values available.
void operator++(void)
Move to the next value.
Link propagator for multiple Boolean views.
Definition channel.hh:198
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function (low unary if y is assigned, low linear otherwise)
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
virtual ExecStatus advise(Space &home, Advisor &a, const Delta &d)
Give advice to propagator.
virtual Actor * copy(Space &home)
Copy propagator during cloning.
virtual size_t dispose(Space &home)
Delete propagator and return its size.
virtual void reschedule(Space &home)
Schedule function.
int min(void) const
Return minimum of domain.
Definition int.hpp:58
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition int.hpp:121
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition int.hpp:139
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition int.hpp:206
int val(void) const
Return assigned value (only if assigned)
Definition int.hpp:70
int max(void) const
Return maximum of domain.
Definition int.hpp:62
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition int.hpp:166
Value iterator for integer views.
Definition view.hpp:94
Mixed (n+1)-ary propagator.
Definition pattern.hpp:272
Propagation cost.
Definition core.hpp:486
static PropCost unary(PropCost::Mod m)
Single variable for modifier pcm.
Definition core.hpp:4813
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:4796
ModEventDelta med
A set of modification events (used during propagation)
Definition core.hpp:1075
Computation spaces.
Definition core.hpp:1742
static ModEvent me(const ModEventDelta &med)
Definition view.hpp:552
static void schedule(Space &home, Propagator &p, ModEvent me)
Definition view.hpp:547
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition view.hpp:532
bool assigned(void) const
Test whether view is assigned.
Definition view.hpp:516
View arrays.
Definition array.hpp:253
void drop_fst(int i)
Drop views from positions 0 to i-1 from array.
Definition array.hpp:1242
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition array.hpp:1349
void drop_lst(int i)
Drop views from positions i+1 to size()-1 from array.
Definition array.hpp:1249
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1156
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition var-type.hpp:65
const Gecode::ModEvent ME_BOOL_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:116
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:56
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition var-type.hpp:72
Gecode toplevel namespace
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
ExecStatus
Definition core.hpp:472
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Post propagator for SetVar x
Definition set.hh:767
#define forceinline
Definition config.hpp:187
#define GECODE_NEVER
Assert that this command is never executed.
Definition macros.hpp:56