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 * Copyright:
7 * Christian Schulte, 2003
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
34namespace Gecode { namespace Int { namespace Distinct {
35
36 /*
37 * Eliminating singleton variables
38 *
39 */
40 template<class View, bool complete>
43 assert(x.size() > 1);
44 int n = x.size();
45
46 Region r;
47 int* stack = r.alloc<int>(n);
48 int* c_v = &stack[0];
49 // c_n is the current number of values on stack
50 int c_n = 0;
51
52 // Collect all assigned variables on stack
53 for (int i=n; i--; )
54 if (x[i].assigned()) {
55 c_v[c_n++]=x[i].val(); x[i]=x[--n];
56 }
57
58 // The number of trips
59 int t = 0;
60 do {
61 t++;
62 if (!complete && (t > 16)) {
63 // Give up after sixteen iterations, but the values must be
64 // propagated first
65 // Maybe we are lucky in that this iteration does the trick...
66 ExecStatus es = ES_FIX;
67 while (c_n > 0) {
68 int v = c_v[--c_n];
69 // Check whether value is on stack only once
70 for (int i=0; i<c_n; i++)
71 if (c_v[i] == v)
72 goto failed;
73 // Tell and do not collect new values
74 for (int i=0; i<n; i++) {
75 ModEvent me = x[i].nq(home,v);
76 if (me_failed(me))
77 goto failed;
78 if (me == ME_INT_VAL)
79 es = ES_NOFIX;
80 }
81 }
82 x.size(n);
83 return es;
84 }
85 if (c_n > 31) {
86 // Many values, use full domain operation
87 IntSet d(&c_v[0],c_n);
88 // If the size s of d is different from the number of values,
89 // a value must have appeared multiply: failure
90 if (d.size() != static_cast<unsigned int>(c_n))
91 goto failed;
92 // We do not need the values on the stack any longer, reset
93 c_n = 0;
94 // Tell and collect new values
95 for (int i = n; i--; )
96 if ((d.min() <= x[i].max()) && (d.max() >= x[i].min())) {
97 IntSetRanges dr(d);
98 ModEvent me = x[i].minus_r(home,dr,false);
99 if (me_failed(me))
100 goto failed;
101 if (me == ME_INT_VAL) {
102 c_v[c_n++]=x[i].val(); x[i]=x[--n];
103 }
104 }
105 } else {
106 // Values for next iteration
107 int* n_v = &c_v[c_n];
108 // Stack top for the next iteration
109 int n_n = 0;
110 while (c_n > 0) {
111 int v = c_v[--c_n];
112 // Check whether value is not on current stack
113 for (int i=0; i<c_n; i++)
114 if (c_v[i] == v)
115 goto failed;
116 // Check whether value is not on next stack
117 for (int i=0; i<n_n; i++)
118 if (n_v[i] == v)
119 goto failed;
120 // Tell and collect new values
121 for (int i = n; i--; ) {
122 ModEvent me = x[i].nq(home,v);
123 if (me_failed(me))
124 goto failed;
125 if (me == ME_INT_VAL) {
126 n_v[n_n++]=x[i].val(); x[i]=x[--n];
127 }
128 }
129 }
130 c_v = n_v; c_n = n_n;
131 }
132 } while (c_n > 0);
133 x.size(n);
134 return ES_FIX;
135 failed:
136 x.size(0);
137 return ES_FAILED;
138 }
139
140
141 /*
142 * The propagator proper
143 *
144 */
145 template<class View>
149
150 template<class View>
154
155#ifdef GECODE_HAS_CBS
156 template<class View>
157 void
158 Val<View>::solndistrib(Space& home, Propagator::SendMarginal send) const {
159 cbsdistinct(home,this->id(),x,send);
160 }
161
162 template<class View>
163 void
164 Val<View>::domainsizesum(Propagator::InDecision in, unsigned int& size,
165 unsigned int& size_b) const {
166 cbssize(x,in,size,size_b);
167 }
168#endif
169
170 template<class View>
171 Actor*
173 return new (home) Val<View>(home,*this);
174 }
175
176 template<class View>
180 return (x.size() < 2) ? home.ES_SUBSUMED(*this) : ES_FIX;
181 }
182
183 template<class View>
186 if (x.size() == 2)
187 return Rel::Nq<View,View>::post(home,x[0],x[1]);
188 if (x.size() > 2)
189 (void) new (home) Val<View>(home,x);
190 return ES_OK;
191 }
192
193}}}
194
195// STATISTICS: int-prop
196
Base-class for both propagators and branchers.
Definition core.hpp:628
Home class for posting propagators
Definition core.hpp:856
Range iterator for integer sets.
Definition int.hh:292
Integer sets.
Definition int.hh:174
int min(int i) const
Return minimum of range at position i.
int max(int i) const
Return maximum of range at position i.
unsigned int size(void) const
Return size (cardinality) of set.
Naive value distinct propagator.
Definition distinct.hh:64
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition val.hpp:172
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition val.hpp:178
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for view array x.
Definition val.hpp:185
Val(Home home, ViewArray< View > &x)
Constructor for posting.
Definition val.hpp:147
static ExecStatus post(Home home, V0 x0, V1 x1)
Post propagator .
Definition nq.hpp:49
NaryPropagator(Space &home, NaryPropagator &p)
friend class Space
Definition core.hpp:1068
Handle to region.
Definition region.hpp:55
Computation spaces.
Definition core.hpp:1744
View arrays.
Definition array.hpp:253
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3570
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
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
Distinct propagators
ExecStatus prop_val(Space &home, ViewArray< View > &)
Eliminate singletons by naive value propagation.
Definition val.hpp:42
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
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
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