34#ifndef GECODE_INT_EXTENSIONAL_OPEN_HPP
35#define GECODE_INT_EXTENSIONAL_OPEN_HPP
44 inline SharedArray<int>
49 int* first = r.
alloc<
int>(k);
52 int* queue = r.
alloc<
int>(k);
53 for (
int s=0; s<k; s++) {
61 source[e] = t.i_state();
62 next[e] = first[t.o_state()];
63 first[t.o_state()] = e;
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;
98 template<
class View, PropCond pc>
114 start(static_cast<
Space&>(home).alloc<unsigned char>(
dfa.n_states())),
123 if (!
list[i].assigned())
124 list[i].subscribe(home,*
this,pc);
129 start(home.alloc<unsigned char>(p.
dfa.n_states())),
140 if ((reachable[s] != 0) &&
149 compute_backward_support(
Region& r,
int remaining)
const {
152 const unsigned long long cells =
153 static_cast<unsigned long long>(n+1) *
154 static_cast<unsigned long long>(k);
156 static_cast<unsigned long long>
157 ((std::numeric_limits<unsigned long>::max)()))
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++)
165 unsigned char* last = backward +
static_cast<size_t>(n)*k;
166 for (
int s=0; s<k; s++)
170 for (
int i=n; i--; ) {
171 unsigned char* in = backward +
static_cast<size_t>(i)*k;
172 unsigned char* out = in+k;
176 if (out[t.o_state()] != 0)
198 if (!
list[i].assigned())
212 x.subscribe(home,*
this,pc,
false);
216 const int n = size-
offset;
219 const bool closed = remaining == 0;
227 const unsigned char* backward = compute_backward_support(r,remaining);
230 for (
int s=0; s<k; s++)
231 any |= (
start[s] != 0) && (backward[s] != 0);
235 unsigned char* reachable = r.
alloc<
unsigned char>(k);
236 unsigned char*
next = r.
alloc<
unsigned char>(k);
238 for (
int s=0; s<k; s++)
239 reachable[s] =
start[s];
240 for (
int i=0; i<n; i++) {
243 const unsigned char* out = backward +
static_cast<size_t>(i+1)*k;
244 for (
int s=0; s<k; s++)
247 bool support =
false;
249 if ((reachable[t.i_state()] != 0) &&
250 (out[t.o_state()] != 0)) {
252 next[t.o_state()] = 1;
255 supported[n_supported++] = v.val();
257 if (n_supported == 0)
261 std::swap(reachable,
next);
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++)
275 const int value =
list[
offset+consumed].val();
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++)
286 if (closed && (
offset == size))
299 if (!
list[i].assigned())
303 list.~OpenViewList();
305 return sizeof(*this);
ActorLink * next(void) const
Base-class for both propagators and branchers.
virtual size_t dispose(Space &home)
Delete actor and return its size.
Iterator for DFA symbols.
Iterator for DFA transitions (sorted by symbols).
Finite automaton with deterministic construction by default.
int n_states(void) const
Return the number of states.
int final_lst(void) const
Return the number of the last final state.
int n_transitions(void) const
Return the number of transitions.
unsigned int n_symbols(void) const
Return the number of symbols.
int final_fst(void) const
Return the number of the first final state.
Home class for posting propagators
void notice(Actor &a, ActorProperty p, bool duplicate=false)
Notice actor property.
OpenViewList< View > list
SharedArray< int > distance
virtual ExecStatus propagate(Space &home, const ModEventDelta &)
Propagation function.
OpenRegular(Space &home, OpenRegular &p)
bool has_accepting_suffix(const unsigned char *reachable, int remaining) const
static ExecStatus post(Home home, OpenViewList< View > list, DFA dfa)
OpenRegular(Home home, OpenViewList< View > list0, DFA dfa0)
virtual PropCost cost(const Space &, const ModEventDelta &) const
Cost function.
virtual Actor * copy(Space &home)
Create copy.
virtual size_t dispose(Space &home)
Delete actor and return its size.
virtual void reschedule(Space &home)
Schedule function.
Integer view for integer variables.
int max(void) const
Return maximum of domain.
OutOfLimits(const char *l)
Initialize with location l.
Value iterator for integer views.
Value iterator for array of integers
View interface to a space-local list with an open length.
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.
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Propagator(Home home)
Constructor for posting.
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Shared array with arbitrary number of elements.
void update(Space &home, VarImpView< Var > &y)
Update this view to be a clone of view y.
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to view.
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to view.
ExecStatus ES_SUBSUMED(Propagator &p)
Propagator p is subsumed
void ignore(Actor &a, ActorProperty p, bool duplicate=false)
Ignore actor property.
int ModEventDelta
Modification event deltas.
bool failed(void) const
Check whether space is failed.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
@ AP_DISPOSE
Actor must always be disposed.
SharedArray< int > accepting_distances(const DFA &dfa)
Shortest accepting suffix length from each state, or -1 if none exists.
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Gecode toplevel namespace
@ ES_OK
Execution is okay.
@ ES_FIX
Propagation has computed fixpoint.
@ ES_FAILED
Execution has resulted in failure.
@ ES_NOFIX
Propagation has not computed fixpoint.