extensional.cpp
Go to the documentation of this file.
static DFA nfa(int s, Transition t[], int f[])
Construct a nondeterministic finite automaton.
Definition dfa.cpp:545
virtual T * next(void)
Return next solution (nullptr, if none exists or search has been stopped).
Definition base.hpp:46
const BitSetData * supports(unsigned int n_words, int n) const
Return the dense supports for value n.
Definition tuple-set.hpp:50
ExtensionalPropKind representation(void) const
Return materialized tuple-set representation.
Definition tuple-set.hpp:283
void update(Space &home, VarArray< Var > &a)
Update array to be a clone of array a.
Definition array.hpp:1032
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition var.hpp:116
virtual void next(Gecode::Support::RandomGenerator &rand)
Move to next assignment.
Definition int.cpp:49
virtual bool has_more(void) const
Test whether all assignments have been iterated.
Definition int.hpp:61
Help class to create and register tests.
Definition extensional.cpp:2225
Dense-compressed iterators should skip unsupported value gaps.
Definition extensional.cpp:1944
DenseCompressedTupleSetWideGap(void)
Definition extensional.cpp:1946
Test backward pruning after appending a restricted variable.
Definition extensional.cpp:1008
OpenRegularBackward(void)
Definition extensional.cpp:1010
Test independent extension after cloning.
Definition extensional.cpp:1063
OpenRegularClone(void)
Definition extensional.cpp:1065
Check domain consistency of the regular constraint on a closed open list.
Definition extensional.cpp:1123
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
Definition extensional.cpp:1136
OpenRegularClosed(void)
Definition extensional.cpp:1125
Test domain notification on an appended variable.
Definition extensional.cpp:1036
OpenRegularDomainWake(void)
Definition extensional.cpp:1038
Test empty words and automata without accepting states.
Definition extensional.cpp:1094
virtual void post(Gecode::Space &home, Gecode::IntVarArray &)
Post constraint.
Definition extensional.cpp:1106
OpenRegularEmpty(Kind k)
Definition extensional.cpp:1100
Test appending and closing an open regular list.
Definition extensional.cpp:879
OpenRegularIncremental(void)
Definition extensional.cpp:881
Materializing required positions wakes regular filtering.
Definition extensional.cpp:916
OpenRegularLengthWake(void)
Definition extensional.cpp:918
Filter prefixes whose accepting continuations exceed the length bound.
Definition extensional.cpp:938
OpenRegularMaxLength(void)
Definition extensional.cpp:940
Space used by open regular tests.
Definition extensional.cpp:856
OpenRegularSpace(OpenRegularSpace &s)
Definition extensional.cpp:866
OpenRegularSpace(Gecode::DFA d, int max=8)
Definition extensional.cpp:861
Gecode::OpenIntVarList list
Definition extensional.cpp:859
RandomTupleSetTest(const std::string &s, bool p, Gecode::IntSet d0, Gecode::TupleSet ts0, Gecode::ExtensionalPropKind epk0)
Create and register test.
Definition extensional.cpp:1276
virtual Assignment * assignment(void) const
Create and register initial assignment.
Definition extensional.cpp:1283
Test an acyclic DFA whose states can occur at different depths
Definition extensional.cpp:396
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:411
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:403
Test the Boolean-view regular posting route
Definition extensional.cpp:507
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:514
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:521
Test a cyclic DFA whose frontier states recur across many layers
Definition extensional.cpp:427
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:441
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:434
Test with regular expression for distinct constraint
Definition extensional.cpp:154
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:170
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:159
Test repeated final states in dense and sparse DFA specifications
Definition extensional.cpp:478
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
Definition extensional.cpp:496
RegDuplicateFinals(bool minimize0, bool sparse0)
Definition extensional.cpp:483
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:331
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:326
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:350
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:345
Test cloning an assigned NFA prefix with branching and reconvergence
Definition extensional.cpp:690
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:706
virtual bool solution(const Assignment &x) const
Test whether x is a solution
Definition extensional.cpp:702
Test failure when the forward frontier misses the terminal boundary
Definition extensional.cpp:756
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:770
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:765
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:370
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:366
Test backward pruning caused by a position-specific domain
Definition extensional.cpp:730
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:741
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:737
Test deterministic generated DFAs against a reference runner
Definition extensional.cpp:537
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:584
int next[n_dfa_states][n_symbols]
Transition table, with -1 denoting no transition.
Definition extensional.cpp:544
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:572
Test nondeterministic generated automata against a reference runner
Definition extensional.cpp:610
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:650
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:667
Test with simple regular expression from Roland Yap
Definition extensional.cpp:201
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:207
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:214
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:79
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:86
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:102
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:106
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:146
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:123
Test compacting sparse external DFA state identifiers
Definition extensional.cpp:454
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:461
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:465
Test merging several reached DFA final states
Definition extensional.cpp:784
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:791
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:796
Test retaining separate terminal states when merging would overflow
Definition extensional.cpp:808
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:819
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:815
Sample both table tuples and arbitrary assignments in large domains.
Definition extensional.cpp:1290
virtual void next(Gecode::Support::RandomGenerator &rand)
Move to next assignment.
Definition extensional.cpp:1305
SparseAssignment(const Gecode::TupleSet &t0, const Gecode::IntSet &d, Gecode::Support::RandomGenerator &rand)
Definition extensional.cpp:1300
Disabled sparse propagators must defer failure until re-enabled.
Definition extensional.cpp:1413
SparseTupleSetDisabledFailure(void)
Definition extensional.cpp:1415
Tells issued after posting exercise sparse advisor updates.
Definition extensional.cpp:1368
SparseTupleSetIncremental(const std::string &name, int k)
Definition extensional.cpp:1372
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
Definition extensional.cpp:1390
The assignment harness needs one variable even for a nullary table.
Definition extensional.cpp:1348
virtual void post(Gecode::Space &home, Gecode::IntVarArray &)
Post constraint.
Definition extensional.cpp:1362
SparseTupleSetNullary(bool n)
Definition extensional.cpp:1352
Sparse delta processing must depend on supports, not numeric width.
Definition extensional.cpp:1462
SparseTupleSetWideDelta(void)
Definition extensional.cpp:1464
Sparse tables with the original large support counts and arities.
Definition extensional.cpp:1312
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint.
Definition extensional.cpp:1342
virtual Assignment * assignment(void) const
Create the assignment generator (complete by default).
Definition extensional.cpp:1330
SparseTupleSet(const std::string &name, int arity, int size)
Definition extensional.cpp:1315
AUTO finalization should work with default tuple-set posting overloads.
Definition extensional.cpp:1846
TupleSetAutoDefaultDispatch(void)
Definition extensional.cpp:1848
TupleSetBase(bool p, Gecode::ExtensionalPropKind epk0)
Create and register test.
Definition extensional.cpp:1173
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:1196
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition extensional.cpp:1212
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:1204
TupleSetBool(double prob, bool p, Gecode::ExtensionalPropKind epk0)
Create and register test.
Definition extensional.cpp:2123
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:2156
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:2142
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition extensional.cpp:2164
DFA-derived tuple sets preserve the requested support representation.
Definition extensional.cpp:1690
TupleSetDFARepresentation(void)
Definition extensional.cpp:1692
Disabled compact propagators preserve pending work when cloned.
Definition extensional.cpp:1721
TupleSetDisabledClone(void)
Definition extensional.cpp:1723
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition extensional.cpp:2105
TupleSetLarge(double prob, bool p, Gecode::ExtensionalPropKind epk0)
Create and register test.
Definition extensional.cpp:2067
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:2100
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:2087
Sparse/compressed tuplesets should materialize only requested support.
Definition extensional.cpp:1531
TupleSetSingleRepresentation(void)
Definition extensional.cpp:1533
Sparse offset arrays need a representable terminal entry.
Definition extensional.cpp:1600
TupleSetSupportOffsetBoundary(void)
Definition extensional.cpp:1602
Failed finalization is terminal and cannot expose partial support data.
Definition extensional.cpp:1622
TupleSetTerminalFinalizationFailure(void)
Definition extensional.cpp:1624
Help class to create and register tests with a fixed table size.
Definition extensional.cpp:2175
TupleSetTestSize(int size, bool pos, Gecode::ExtensionalPropKind epk, Gecode::Support::RandomGenerator &rand)
Perform creation and registration.
Definition extensional.cpp:2178
virtual bool solution(const Assignment &x) const
Test whether x is solution
Definition extensional.cpp:1242
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x, Gecode::Reify r)
Post reified constraint on x for r.
Definition extensional.cpp:1266
TupleSetTest(const std::string &s, bool p, Gecode::IntSet d0, Gecode::TupleSet ts0, bool td, Gecode::ExtensionalPropKind epk0, TestTags tags=TestTags::sweep())
Create and register test.
Definition extensional.cpp:1231
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post constraint on x.
Definition extensional.cpp:1256
int a
How many assignments still to be generated Generate new value according to domain.
Definition int.hh:113
RandomAssignment(int n, const Gecode::IntSet &d, int a0, Gecode::Support::RandomGenerator &rand)
Initialize for a assignments for n0 variables and values d0.
Definition int.hpp:88
virtual void next(Gecode::Support::RandomGenerator &rand)
Move to next assignment.
Definition int.cpp:63
LinearCongruentialGenerator< 2147483647, 48271, 44488, 3399 > RandomGenerator
Default values for linear congruential generator.
Definition random.hpp:183
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
ExtensionalPropKind
Support representation selection for extensional tuple sets.
Definition int.hh:2794
void extensional(Home home, const IntVarArgs &x, DFA d, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for extensional constraint described by a DFA.
Definition extensional-regular.cpp:39
bool support_offsets_size(unsigned long long n_vals, unsigned int &n_offsets)
Definition tuple-set.hpp:373
Gecode toplevel namespace
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
Definition channel.cpp:41
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:988
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
void unshare(Home home, IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Replace multiple variable occurrences in x by fresh variables.
Definition unshare.cpp:136
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
TupleSetSupportOffsetBoundary tuple_set_support_offset_boundary
Definition extensional.cpp:2479
RegNoAcceptingPath reg_sparse_no_accepting_path
Definition extensional.cpp:2429
SparseTupleSetWideDelta sparse_tuple_set_wide_delta
Definition extensional.cpp:2477
TupleSetSingleRepresentation tuple_set_single_representation
Definition extensional.cpp:2478
SparseTupleSet sparse_tuple_set_high_arity("HighArity", 6, 1000)
TupleSetDisabledClone tuple_set_disabled_clone
Definition extensional.cpp:2482
RegOpt ro0(CHAR_MAX-1)
OpenRegularEmpty open_regular_empty_accept(OpenRegularEmpty::Kind::ACCEPT)
SparseTupleSet sparse_tuple_set_ternary("Ternary", 3, 1500)
RegRandomNFADifferential reg_sparse_random_nfa_differential_2(2)
RegDuplicateFinals reg_duplicate_finals_sparse_keep(false, true)
SparseTupleSetIncremental sparse_tuple_set_incremental_bool("Bool", 2)
OpenRegularBackward open_regular_backward
Definition extensional.cpp:2435
RegDuplicateFinals reg_duplicate_finals_dense_minimize(true, false)
RegTerminalUnmerged reg_sparse_terminal_unmerged
Definition extensional.cpp:2431
RegRandomDifferential reg_sparse_random_differential_3(3)
TupleSetAutoDefaultDispatch tuple_set_auto_default_dispatch
Definition extensional.cpp:2483
RegNFAPrefix reg_sparse_nfa_prefix_int(false)
RegTerminalMerged reg_sparse_terminal_merged
Definition extensional.cpp:2430
RegRandomDifferential reg_sparse_random_differential_1(1)
SparseTupleSetNullary sparse_tuple_set_nullary(true)
RegDuplicateFinals reg_duplicate_finals_sparse_minimize(true, true)
std::string extensional_kind_name(Gecode::ExtensionalPropKind epk)
Definition extensional.cpp:57
Gecode::DFA tupleset2dfa(Gecode::TupleSet ts)
% Transform a TupleSet into a DFA
Definition extensional.cpp:1148
RegOpt ro7(static_cast< int >(USHRT_MAX))
RegDuplicateFinals reg_duplicate_finals_dense_keep(false, false)
OpenRegularDomainWake open_regular_domain_wake
Definition extensional.cpp:2436
OpenRegularClosed open_regular_closed
Definition extensional.cpp:2441
SparseTupleSetIncremental sparse_tuple_set_incremental_delta("Delta", 0)
RegCyclicFrontier reg_sparse_cyclic_frontier
Definition extensional.cpp:2411
RegOpt ro2(static_cast< int >(UCHAR_MAX-1))
RegRandomNFADifferential reg_sparse_random_nfa_differential_1(1)
OpenRegularIncremental open_regular_incremental
Definition extensional.cpp:2432
TupleSetDFARepresentation tuple_set_dfa_representation
Definition extensional.cpp:2481
class Test::Int::Extensional::CreateSparse create_sparse
RegAcyclicReconvergence reg_sparse_acyclic_reconvergence
Definition extensional.cpp:2410
RegSparseStateNumbering reg_sparse_state_numbering
Definition extensional.cpp:2412
OpenRegularClone open_regular_clone
Definition extensional.cpp:2437
RegOpt ro6(static_cast< int >(USHRT_MAX-1))
OpenRegularMaxLength open_regular_max_length
Definition extensional.cpp:2434
RegRoland rr2(2)
RegRandomNFADifferential reg_sparse_random_nfa_differential_4(4)
RegNFAPrefix reg_sparse_nfa_prefix_bool(true)
RegRandomNFADifferential reg_sparse_random_nfa_differential_3(3)
OpenRegularEmpty open_regular_empty_reject(OpenRegularEmpty::Kind::REJECT)
SparseTupleSetDisabledFailure sparse_tuple_set_disabled_failure
Definition extensional.cpp:2476
RegRoland rr4(4)
RegRandomDifferential reg_sparse_random_differential_4(4)
RegPositionDomainPruning reg_sparse_position_domain_pruning
Definition extensional.cpp:2428
Gecode::TupleSet randomTupleSet(int n, int min, int max, double prob, Gecode::ExtensionalPropKind epk, Gecode::Support::RandomGenerator &rand)
Definition extensional.cpp:2206
RegRandomDifferential reg_sparse_random_differential_2(2)
SparseTupleSetNullary sparse_tuple_set_empty(false)
SparseTupleSet sparse_tuple_set_unary("Unary", 1, 2000)
RegBoolCyclicFrontier reg_sparse_bool_cyclic_frontier
Definition extensional.cpp:2417
OpenRegularEmpty open_regular_no_finals(OpenRegularEmpty::Kind::NO_FINALS)
RegRoland rr1(1)
RegOpt ro4(SHRT_MAX-1)
RegRoland rr3(3)
RegOpt ro1(CHAR_MAX)
TupleSetTerminalFinalizationFailure tuple_set_terminal_failure
Definition extensional.cpp:2480
OpenRegularLengthWake open_regular_length_wake
Definition extensional.cpp:2433
RegOpt ro3(static_cast< int >(UCHAR_MAX))
RegOpt ro5(SHRT_MAX)
SparseTupleSetIncremental sparse_tuple_set_incremental_assign("Assign", 1)
DenseCompressedTupleSetWideGap dense_compressed_tuple_set_wide_gap
Definition extensional.cpp:2484
Definition flatzinc.cpp:57
