Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
val.hpp
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 * Contributing authors:
7 * Mikael Lagerkvist <lagerkvist@gecode.org>
8 *
9 * Copyright:
10 * Christian Schulte, 2006
11 * Mikael Lagerkvist, 2006
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38namespace Gecode { namespace Int { namespace Channel {
39
44 template<class View>
45 class ValInfo {
46 public:
50 bool a;
52 void init(View x, int n);
54 void update(Space& home, ValInfo<View>& vi);
56 bool doval(void) const;
58 bool dodom(void) const;
60 void assigned(void);
62 void removed(int i);
64 void done(void);
65 };
66
67 template<class View>
68 forceinline void
70 view = x; a = false;
71 }
72
73 template<class View>
74 forceinline void
76 view.update(home,vi.view); a = vi.a;
77 }
78
79 template<class View>
80 forceinline bool
82 return !a && view.assigned();
83 }
84
85 template<class View>
86 forceinline bool
88 return false;
89 }
90
91 template<class View>
92 forceinline void
94 a = true;
95 }
96
97 template<class View>
98 forceinline void
100
101 template<class View>
102 forceinline void
104
105
106 // Propagate assigned views for x
107 template<class View, class Offset, class Info>
109 doprop_val(Space& home, int n, Info* x, Offset& ox,
110 Info* y, Offset& oy,
111 int& n_na, ProcessStack& xa, ProcessStack& ya) {
112 do {
113 int i = xa.pop();
114 int j = ox(x[i].view).val();
115 // Assign the y variable to i (or test if already assigned!)
116 {
117 ModEvent me = oy(y[j].view).eq(home,i);
118 if (me_failed(me)) {
119 return ES_FAILED;
120 }
121 // Record that y[j] has been assigned and must be propagated
122 if (me_modified(me))
123 ya.push(j);
124 }
125 // Prune the value j from all x variables
126 for (int k=0; k<i; k++) {
127 ModEvent me = ox(x[k].view).nq(home,j);
128 if (me_failed(me)) {
129 return ES_FAILED;
130 }
131 if (me_modified(me)) {
132 if (me == ME_INT_VAL) {
133 // Record that x[k] has been assigned and must be propagated
134 xa.push(k);
135 } else {
136 // One value has been removed and this removal does not need
137 // to be propagated again: after all y[j] = i, so it holds
138 // that y[j] != k.
139 x[k].removed(j);
140 }
141 }
142 }
143 // The same for the other views
144 for (int k=i+1; k<n; k++) {
145 ModEvent me = ox(x[k].view).nq(home,j);
146 if (me_failed(me)) {
147 return ES_FAILED;
148 }
149 if (me_modified(me)) {
150 if (me == ME_INT_VAL) {
151 // Record that x[k] has been assigned and must be propagated
152 xa.push(k);
153 } else {
154 // One value has been removed and this removal does not need
155 // to be propagated again: after all y[j] = i, so it holds
156 // that y[j] != k.
157 x[k].removed(j);
158 }
159 }
160 }
161 x[i].assigned(); n_na--;
162 } while (!xa.empty());
163 return ES_OK;
164 }
165
166 // Just do a test whether a call to the routine is necessary
167 template<class View, class Offset, class Info>
169 prop_val(Space& home, int n, Info* x, Offset& ox, Info* y, Offset& oy,
170 int& n_na, ProcessStack& xa, ProcessStack& ya) {
171 if (xa.empty())
172 return ES_OK;
173 return doprop_val<View,Offset,Info>(home,n,x,ox,y,oy,n_na,xa,ya);
174 }
175
176 /*
177 * The actual propagator
178 *
179 */
180 template<class View, class Offset, bool shared>
185
186 template<class View, class Offset, bool shared>
189 : Base<ValInfo<View>,Offset,PC_INT_VAL>(home,p) {}
190
191 template<class View, class Offset, bool shared>
192 Actor*
194 return new (home) Val<View,Offset,shared>(home,*this);
195 }
196
197 template<class View, class Offset, bool shared>
200 Region r;
201 ProcessStack xa(r,n);
202 ProcessStack ya(r,n);
203
204 ValInfo<View>* x = xy;
205 ValInfo<View>* y = xy+n;
206
207 // Scan x and y for assigned but not yet propagated views
208 for (int i=0; i<n; i++) {
209 if (x[i].doval()) xa.push(i);
210 if (y[i].doval()) ya.push(i);
211 }
212
213 do {
214 // Propagate assigned views for x
216 (home,n,x,ox,y,oy,n_na,xa,ya)));
217 // Propagate assigned views for y
219 (home,n,y,oy,x,ox,n_na,ya,xa)));
220 assert(ya.empty());
221 } while (!xa.empty());
222
223 if (n_na == 0)
224 return home.ES_SUBSUMED(*this);
225 return shared ? ES_NOFIX : ES_FIX;
226 }
227
228 template<class View, class Offset, bool shared>
231 Offset& ox, Offset& oy) {
232 assert(n > 0);
233 if (n == 1) {
234 GECODE_ME_CHECK(ox(xy[0].view).eq(home,0));
235 GECODE_ME_CHECK(oy(xy[1].view).eq(home,0));
236 return ES_OK;
237 }
238 for (int i=0; i<n; i++) {
239 GECODE_ME_CHECK(ox(xy[i ].view).gq(home,0));
240 GECODE_ME_CHECK(ox(xy[i ].view).le(home,n));
241 GECODE_ME_CHECK(oy(xy[i+n].view).gq(home,0));
242 GECODE_ME_CHECK(oy(xy[i+n].view).le(home,n));
243 }
244 (void) new (home) Val<View,Offset,shared>(home,n,xy,ox,oy);
245 return ES_OK;
246 }
247
248}}}
249
250// STATISTICS: int-prop
251
Base-class for both propagators and branchers.
Definition core.hpp:628
Home class for posting propagators
Definition core.hpp:856
Base-class for channel propagators.
Definition channel.hh:55
Base(Space &home, Base< ValInfo< View >, Offset, pc > &p)
Definition base.hpp:47
Combine view with information for value propagation.
Definition val.hpp:45
void done(void)
Update the cardinality and bounds information after pruning.
Definition val.hpp:103
bool a
Whether it has been propagated that view is assigned.
Definition val.hpp:50
void init(View x, int n)
Initialize.
Definition val.hpp:69
void assigned(void)
Record that view got assigned.
Definition val.hpp:93
void removed(int i)
Record that one value got removed.
Definition val.hpp:99
bool dodom(void) const
Check whether propagation for domain is to be done.
Definition val.hpp:87
bool doval(void) const
Check whether propagation for assignment is to be done.
Definition val.hpp:81
void update(Space &home, ValInfo< View > &vi)
Update during cloning.
Definition val.hpp:75
Naive channel propagator.
Definition channel.hh:97
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition val.hpp:193
static ExecStatus post(Home home, int n, ValInfo< View > *xy, Offset &ox, Offset &oy)
Post propagator for channeling.
Definition val.hpp:230
Val(Space &home, Val &p)
Constructor for cloning p.
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition val.hpp:199
Converter with fixed offset.
Definition view.hpp:650
friend class Space
Definition core.hpp:1068
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1744
void push(const T &x)
Push element x on top of stack.
T pop(void)
Pop topmost element from stack and return it.
bool empty(void) const
Test whether stack is empty.
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3570
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
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition modevent.hpp:54
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition modevent.hpp:59
Channel propagators
ExecStatus prop_val(Space &home, int n, Info *x, Offset &ox, Info *y, Offset &oy, int &n_na, ProcessStack &xa, ProcessStack &ya)
Definition val.hpp:169
Support::StaticStack< int, Region > ProcessStack
Processing stack.
Definition channel.hh:48
ExecStatus doprop_val(Space &home, int n, Info *x, Offset &ox, Info *y, Offset &oy, int &n_na, ProcessStack &xa, ProcessStack &ya)
Definition val.hpp:109
Finite domain integers.
const Gecode::PropCond PC_INT_VAL
Propagate when a view becomes assigned (single value)
Definition var-type.hpp:82
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition var-type.hpp:56
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
Post propagator for SetVar SetOpType SetVar y
Definition set.hh:773
ExecStatus
Definition core.hpp:472
@ ES_OK
Execution is okay.
Definition core.hpp:476
@ 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
bool shared(ViewArray< ViewX > x, ViewArray< ViewY > y)
Definition array.hpp:1472
Post propagator for SetVar x
Definition set.hh:773
int ModEvent
Type for modification events.
Definition core.hpp:62
#define forceinline
Definition config.hpp:194