Generated on for Gecode by doxygen 1.18.0
open.hpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main author:
4 * Mikael Zayenz Lagerkvist <lagerkvist@gecode.dev>
5 *
6 * Copyright:
7 * Mikael Zayenz Lagerkvist, 2026
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.dev
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#ifndef GECODE_INT_EXTENSIONAL_OPEN_HPP
35#define GECODE_INT_EXTENSIONAL_OPEN_HPP
36
38#include <limits>
39#include <utility>
40
41namespace Gecode { namespace Int { namespace Extensional {
42
44 inline SharedArray<int>
46 const int k = dfa.n_states();
47 SharedArray<int> distance(k);
48 Region r;
49 int* first = r.alloc<int>(k);
50 int* source = r.alloc<int>(dfa.n_transitions());
51 int* next = r.alloc<int>(dfa.n_transitions());
52 int* queue = r.alloc<int>(k);
53 for (int s=0; s<k; s++) {
54 distance[s] = -1;
55 first[s] = -1;
56 }
57
58 // Index incoming transitions for breadth-first traversal from final states.
59 int e = 0;
60 for (DFA::Transitions t(dfa); t(); ++t, e++) {
61 source[e] = t.i_state();
62 next[e] = first[t.o_state()];
63 first[t.o_state()] = e;
64 }
65 int end = 0;
66 for (int s=dfa.final_fst(); s<dfa.final_lst(); s++) {
67 distance[s] = 0;
68 queue[end++] = s;
69 }
70 // The default DFA accepts only the empty word.
71 if ((dfa.final_fst() == 0) && (dfa.final_lst() == 0)) {
72 distance[0] = 0;
73 queue[end++] = 0;
74 }
75 for (int i=0; i<end; i++) {
76 const int s = queue[i];
77 for (int e=first[s]; e != -1; e=next[e]) {
78 const int p = source[e];
79 if (distance[p] == -1) {
80 distance[p] = distance[s]+1;
81 queue[end++] = p;
82 }
83 }
84 }
85 return distance;
86 }
87
98 template<class View, PropCond pc>
99 class OpenRegular : public Propagator {
100 protected:
105 unsigned char* start;
108
110 OpenViewList<View> list0, DFA dfa0)
111 : Propagator(home), list(list0),
112 length(list0.length()),
113 dfa(dfa0), distance(accepting_distances(dfa0)),
114 start(static_cast<Space&>(home).alloc<unsigned char>(dfa.n_states())),
115 offset(0), subscribed(list0.known_length()) {
116 home.notice(*this,AP_DISPOSE);
117 for (int i=0; i<dfa.n_states(); i++)
118 start[i] = 0;
119 start[0] = 1;
120 length.subscribe(home,*this,PC_INT_BND);
121 list.subscribe(home,*this);
122 for (int i=0; i<subscribed; i++)
123 if (!list[i].assigned())
124 list[i].subscribe(home,*this,pc);
125 }
126
128 : Propagator(home,p), dfa(p.dfa), distance(p.distance),
129 start(home.alloc<unsigned char>(p.dfa.n_states())),
131 list.update(home,p.list);
132 length.update(home,p.length);
133 for (int i=0; i<dfa.n_states(); i++)
134 start[i] = p.start[i];
135 }
136
137 bool
138 has_accepting_suffix(const unsigned char* reachable, int remaining) const {
139 for (int s=0; s<dfa.n_states(); s++)
140 if ((reachable[s] != 0) &&
141 (distance[s] >= 0) && (distance[s] <= remaining))
142 return true;
143 return false;
144 }
145
146 private:
148 const unsigned char*
149 compute_backward_support(Region& r, int remaining) const {
150 const int n = list.known_length()-offset;
151 const int k = dfa.n_states();
152 const unsigned long long cells =
153 static_cast<unsigned long long>(n+1) *
154 static_cast<unsigned long long>(k);
155 if (cells >
156 static_cast<unsigned long long>
157 ((std::numeric_limits<unsigned long>::max)()))
158 throw OutOfLimits("Int::extensional");
159
160 unsigned char* backward =
161 r.alloc<unsigned char>(static_cast<unsigned long>(cells));
162 for (size_t i=0; i<static_cast<size_t>(cells); i++)
163 backward[i] = 0;
164
165 unsigned char* last = backward + static_cast<size_t>(n)*k;
166 for (int s=0; s<k; s++)
167 if ((distance[s] >= 0) && (distance[s] <= remaining))
168 last[s] = 1;
169
170 for (int i=n; i--; ) {
171 unsigned char* in = backward + static_cast<size_t>(i)*k;
172 unsigned char* out = in+k;
173 View x(list[offset+i]);
174 for (ViewValues<View> v(x); v(); ++v)
175 for (DFA::Transitions t(dfa,v.val()); t(); ++t)
176 if (out[t.o_state()] != 0)
177 in[t.i_state()] = 1;
178 }
179 return backward;
180 }
181
182 public:
183 virtual Actor*
184 copy(Space& home) {
185 return new (home) OpenRegular(home,*this);
186 }
187
188 virtual PropCost
189 cost(const Space&, const ModEventDelta&) const {
191 }
192
193 virtual void
195 length.reschedule(home,*this,PC_INT_BND);
196 list.reschedule(home,*this);
197 for (int i=offset; i<subscribed; i++)
198 if (!list[i].assigned())
199 list[i].reschedule(home,*this,pc);
200 }
201
202 virtual ExecStatus
204 const int size = list.known_length();
205 assert(size <= length.max());
206
207 for (int i=subscribed; i<size; i++) {
208 View x(list[i]);
209 DFA::Symbols symbols(dfa);
210 GECODE_ME_CHECK(x.inter_v(home,symbols,false));
211 if (!x.assigned())
212 x.subscribe(home,*this,pc,false);
213 }
214 subscribed = size;
215
216 const int n = size-offset;
217 const int k = dfa.n_states();
218 const int remaining = length.max()-size;
219 const bool closed = remaining == 0;
220 if (n == 0) {
221 if (!has_accepting_suffix(start,remaining))
222 return ES_FAILED;
223 return closed ? home.ES_SUBSUMED(*this) : ES_FIX;
224 }
225
226 Region r;
227 const unsigned char* backward = compute_backward_support(r,remaining);
228
229 bool any = false;
230 for (int s=0; s<k; s++)
231 any |= (start[s] != 0) && (backward[s] != 0);
232 if (!any)
233 return ES_FAILED;
234
235 unsigned char* reachable = r.alloc<unsigned char>(k);
236 unsigned char* next = r.alloc<unsigned char>(k);
237 int* supported = r.alloc<int>(dfa.n_symbols());
238 for (int s=0; s<k; s++)
239 reachable[s] = start[s];
240 for (int i=0; i<n; i++) {
241 View x(list[offset+i]);
242 int n_supported = 0;
243 const unsigned char* out = backward + static_cast<size_t>(i+1)*k;
244 for (int s=0; s<k; s++)
245 next[s] = 0;
246 for (ViewValues<View> v(x); v(); ++v) {
247 bool support = false;
248 for (DFA::Transitions t(dfa,v.val()); t(); ++t)
249 if ((reachable[t.i_state()] != 0) &&
250 (out[t.o_state()] != 0)) {
251 support = true;
252 next[t.o_state()] = 1;
253 }
254 if (support)
255 supported[n_supported++] = v.val();
256 }
257 if (n_supported == 0)
258 return ES_FAILED;
259 Iter::Values::Array v(supported,n_supported);
260 GECODE_ME_CHECK(x.narrow_v(home,v,false));
261 std::swap(reachable,next);
262 }
263
264 // Pruning an item that aliases length can reduce the suffix budget.
265 // Recompute support before consuming the prefix.
266 if (length.max()-size < remaining)
267 return ES_NOFIX;
268
269 int consumed = 0;
270 while ((consumed < n) && list[offset+consumed].assigned()) {
271 const unsigned char* live =
272 backward + static_cast<size_t>(consumed+1)*k;
273 for (int s=0; s<k; s++)
274 next[s] = 0;
275 const int value = list[offset+consumed].val();
276 for (DFA::Transitions t(dfa,value); t(); ++t)
277 if ((start[t.i_state()] != 0) &&
278 (live[t.o_state()] != 0))
279 next[t.o_state()] = 1;
280 for (int s=0; s<k; s++)
281 start[s] = next[s];
282 consumed++;
283 }
284 offset += consumed;
285
286 if (closed && (offset == size))
287 return home.ES_SUBSUMED(*this);
288 return ES_FIX;
289 }
290
291 virtual size_t
292 dispose(Space& home) {
293 home.ignore(*this,AP_DISPOSE);
294 length.cancel(home,*this,PC_INT_BND);
295 list.cancel(home,*this);
296 // During space deletion, the list buffer may already have been freed.
297 if (!home.failed())
298 for (int i=offset; i<subscribed; i++)
299 if (!list[i].assigned())
300 list[i].cancel(home,*this,pc);
301 dfa.~DFA();
302 distance.~SharedArray();
303 list.~OpenViewList();
304 (void) Propagator::dispose(home);
305 return sizeof(*this);
306 }
307
308 static ExecStatus
310 for (int i=0; i<list.known_length(); i++) {
311 DFA::Symbols symbols(dfa);
312 View x(list[i]);
313 GECODE_ME_CHECK(x.inter_v(home,symbols,false));
314 }
315 (void) new (home) OpenRegular(home,list,dfa);
316 return ES_OK;
317 }
318 };
319
320}}}
321
322#endif
323
324// STATISTICS: int-prop
Base-class for both propagators and branchers.
Definition core.hpp:635
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3430
Iterator for DFA symbols.
Definition int.hh:2663
Iterator for DFA transitions (sorted by symbols).
Definition int.hh:2640
Finite automaton with deterministic construction by default.
Definition int.hh:2620
int n_states(void) const
Return the number of states.
Definition dfa.hpp:139
int final_lst(void) const
Return the number of the last final state.
Definition dfa.hpp:169
int n_transitions(void) const
Return the number of transitions.
Definition dfa.hpp:151
unsigned int n_symbols(void) const
Return the number of symbols.
Definition dfa.hpp:145
int final_fst(void) const
Return the number of the first final state.
Definition dfa.hpp:163
Home class for posting propagators
Definition core.hpp:863
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
Definition core.hpp:3373
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Propagation function.
Definition open.hpp:203
OpenRegular(Space &home, OpenRegular &p)
Definition open.hpp:127
bool has_accepting_suffix(const unsigned char *reachable, int remaining) const
Definition open.hpp:138
static ExecStatus post(Home home, OpenViewList< View > list, DFA dfa)
Definition open.hpp:309
OpenRegular(Home home, OpenViewList< View > list0, DFA dfa0)
Definition open.hpp:109
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
Definition open.hpp:189
virtual Actor * copy(Space &home)
Create copy.
Definition open.hpp:184
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition open.hpp:292
virtual void reschedule(Space &home)
Schedule function.
Definition open.hpp:194
Integer view for integer variables.
Definition view.hpp:129
int max(void) const
Return maximum of domain.
Definition int.hpp:62
OutOfLimits(const char *l)
Initialize with location l.
Value iterator for integer views.
Definition view.hpp:94
Value iterator for array of integers
View interface to a space-local list with an open length.
Definition int.hh:1044
void reschedule(Space &home, Propagator &p)
Reschedule p for construction of positions.
int known_length(void) const
Return the number of constructed positions.
void update(Space &home, OpenViewList< View > &s)
Update during cloning.
void cancel(Space &home, Propagator &p)
Cancel the subscription of p to construction of positions.
void subscribe(Space &home, Propagator &p)
Subscribe p to construction of positions.
Propagation cost.
Definition core.hpp:493
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition core.hpp:5080
@ HI
Expensive.
Definition core.hpp:521
friend class Space
Definition core.hpp:1075
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3707
Handle to region.
Definition region.hpp:55
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition region.hpp:386
Shared array with arbitrary number of elements.
void update(Space &home, VarImpView< Var > &y)
Update this view to be a clone of view y.
Definition view.hpp:567
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
Definition view.hpp:527
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition view.hpp:532
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
Definition view.hpp:521
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
Definition core.hpp:3780
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
Definition core.hpp:4321
int ModEventDelta
Modification event deltas.
Definition core.hpp:94
bool failed(void) const
Check whether space is failed.
Definition core.hpp:4289
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
@ AP_DISPOSE
Actor must always be disposed.
Definition core.hpp:569
Extensional propagators
Definition int.hh:2774
SharedArray< int > accepting_distances(const DFA &dfa)
Shortest accepting suffix length from each state, or -1 if none exists.
Definition open.hpp:45
Finite domain integers.
Definition lastval.hh:52
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition var-type.hpp:99
Gecode toplevel namespace
ExecStatus
Definition core.hpp:479
@ ES_OK
Execution is okay.
Definition core.hpp:483
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:484
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:481
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:482