40#ifndef __GECODE_SET_HH__
41#define __GECODE_SET_HH__
53#if !defined(GECODE_STATIC_LIBS) && \
54 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
56#ifdef GECODE_BUILD_SET
57#define GECODE_SET_EXPORT __declspec( dllexport )
59#define GECODE_SET_EXPORT __declspec( dllimport )
64#ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
65#define GECODE_SET_EXPORT __attribute__ ((visibility("default")))
67#define GECODE_SET_EXPORT
73#ifndef GECODE_BUILD_SET
74#define GECODE_LIBRARY_NAME "Set"
92namespace Gecode {
namespace Set {
103 void check(
int n,
const char* l);
105 void check(
unsigned int n,
const char* l);
235 unsigned int glbSize(
void)
const;
237 unsigned int lubSize(
void)
const;
241 unsigned int cardMin(
void)
const;
243 unsigned int cardMax(
void)
const;
297 unsigned int width(
void)
const;
329 unsigned int width(
void)
const;
361 unsigned int width(
void)
const;
455 template<
class Char,
class Traits>
456 std::basic_ostream<Char,Traits>&
505 template<
class InputIterator>
506 SetVarArgs(InputIterator first, InputIterator last);
515 int lubMin,
int lubMax,
516 unsigned int minCard = 0,
526 int lubMin,
int lubMax,
527 unsigned int minCard = 0,
538 unsigned int minCard = 0,
549 unsigned int minCard = 0,
590 unsigned int minCard = 0,
600 unsigned int minCard = 0,
610 unsigned int minCard = 0,
621 unsigned int minCard = 0,
684 dom(Home home,
const SetVarArgs& x,
SetRelType r,
int i,
int j);
690 dom(Home home,
const SetVarArgs& x,
SetRelType r,
const IntSet& s);
693 cardinality(Home home, SetVar x,
unsigned int i,
unsigned int j);
696 cardinality(Home home,
const SetVarArgs& x,
unsigned int i,
unsigned int j);
702 dom(Home home, SetVar x,
SetRelType rt,
int i,
int j, Reify r);
705 dom(Home home, SetVar x,
SetRelType rt,
const IntSet& s, Reify r);
708 dom(Home home, SetVar x, SetVar d);
711 dom(Home home,
const SetVarArgs& x,
const SetVarArgs& d);
1082 typedef std::function<bool(
const Space& home,
SetVar x,
int i)>
1094 typedef std::function<double(
const Space& home,
SetVar x,
int i)>
1107 typedef std::function<int(
const Space& home,
SetVar x,
int i)>
1121 typedef std::function<void(
Space& home,
unsigned int a,
1281 typedef std::function<void(
const Space &home,
const Brancher& b,
1283 SetVar x,
int i,
const int& n,
1587 branch(Home home,
const SetVarArgs& x,
1588 SetVarBranch vars, SetValBranch vals,
1597 branch(Home home,
const SetVarArgs& x,
1598 TieBreak<SetVarBranch> vars, SetValBranch vals,
1607 branch(Home home, SetVar x, SetValBranch vals,
1616 assign(Home home,
const SetVarArgs& x,
1617 SetVarBranch vars, SetAssign vals,
1626 assign(Home home,
const SetVarArgs& x,
1627 TieBreak<SetVarBranch> vars, SetAssign vals,
1636 assign(Home home, SetVar x, SetAssign vals,
1755 Iter::Ranges::RangeList> {
1772 Set::LubRanges<Set::SetView> > {
AFC(void)
Construct as not yet intialized.
Action(void)
Construct as not yet intialized.
Passing Boolean variables.
Boolean integer variables.
CHB(void)
Construct as not yet intialized.
Generic domain change information to be supplied to advisors.
Home class for posting propagators
Passing integer arguments.
Passing integer variables.
Range iterator for computing set difference.
Range iterator for range lists
Value iterator from range iterator.
Lists of ranges (intervals).
Reification specification.
Recording AFC information for set variables.
SetAFC & operator=(const SetAFC &a)
Assignment operator.
void init(Home home, const SetVarArgs &x, double d=1.0, bool share=true)
Initialize for set variables x with decay factor d.
SetAFC(void)
Construct as not yet initialized.
Recording actions for set variables.
SetAction(void)
Construct as not yet initialized.
SetAction & operator=(const SetAction &a)
Assignment operator.
void init(Home home, const SetVarArgs &x, double d=1.0, SetBranchMerit bm=nullptr)
Initialize for set variables x with decay factor d.
Which value to select for assignment.
SetAssign(Select s=SEL_MIN_INC)
Initialize with selection strategy s.
Select s
Which value to select.
Select
Which value selection.
@ SEL_MED_EXC
Exclude median element (rounding downwards).
@ SEL_MIN_EXC
Exclude smallest element.
@ SEL_RND_EXC
Exclude random element.
@ SEL_MIN_INC
Include smallest element.
@ SEL_VAL_COMMIT
Select value according to user-defined functions.
@ SEL_MAX_INC
Include largest element.
@ SEL_MAX_EXC
Exclude largest element.
@ SEL_MED_INC
Include median element (rounding downwards).
@ SEL_RND_INC
Include random element.
Select select(void) const
Return selection strategy.
Recording CHB for set variables.
SetCHB & operator=(const SetCHB &chb)
Assignment operator.
void init(Home home, const SetVarArgs &x, SetBranchMerit bm=nullptr)
Initialize for set variables x.
SetCHB(void)
Construct as not yet initialized.
Delta for the greatest lower bound.
Set::GlbRanges< Set::SetView > n
Iterator over new glb.
Iter::Ranges::RangeList o
Iterator over old glb.
Glb(RangeList *o, Set::SetView n)
Initialize with old glb and new glb.
Delta for the least upper bound.
Iter::Ranges::RangeList o
Iterator over old lub.
Lub(RangeList *o, Set::SetView n)
Initialize with old lub o and new lub n.
Set::LubRanges< Set::SetView > n
Iterator over new lub.
Trace delta information for set variables.
Glb & glb(void)
Give access to iterator for delta in greatest lower bound (values that have been included).
SetTraceDelta(Set::SetTraceView o, Set::SetView n, const Delta &d)
Initialize with old trace view o, new view n, and delta d.
Lub & lub(void)
Give access iterator for delta in leat bound (values that have been removed).
Which values to select for branching first.
SetValBranch(Select s=SEL_MIN_INC)
Initialize with selection strategy s.
Select
Which value selection.
@ SEL_VAL_COMMIT
Select value according to user-defined functions.
@ SEL_MAX_INC
Include largest element.
@ SEL_MIN_EXC
Exclude smallest element.
@ SEL_RND_EXC
Exclude random element.
@ SEL_MIN_INC
Include smallest element.
@ SEL_MAX_EXC
Exclude largest element.
@ SEL_MED_EXC
Exclude median element (rounding downwards).
@ SEL_RND_INC
Include random element.
@ SEL_MED_INC
Include median element (rounding downwards).
Select s
Which value to select.
Select select(void) const
Return selection strategy.
SetVarArgs(void)
Allocate empty array.
SetVarArray(void)
Default constructor (array of size 0).
Which variable to select for branching.
void expand(Home home, const SetVarArgs &x)
Expand AFC, action, and CHB.
Select
Which variable selection.
@ SEL_ACTION_SIZE_MIN
With smallest action divided by domain size.
@ SEL_CHB_MIN
With lowest CHB Q-score.
@ SEL_CHB_MAX
With highest CHB Q-score.
@ SEL_MERIT_MIN
With least merit.
@ SEL_DEGREE_SIZE_MAX
With largest degree divided by domain size.
@ SEL_AFC_SIZE_MIN
With smallest accumulated failure count divided by domain size.
@ SEL_AFC_MIN
With smallest accumulated failure count.
@ SEL_CHB_SIZE_MAX
With largest CHB Q-score divided by domain size.
@ SEL_NONE
First unassigned.
@ SEL_ACTION_SIZE_MAX
With largest action divided by domain size.
@ SEL_DEGREE_MAX
With largest degree.
@ SEL_AFC_MAX
With largest accumulated failure count.
@ SEL_CHB_SIZE_MIN
With smallest CHB Q-score divided by domain size.
@ SEL_MERIT_MAX
With highest merit.
@ SEL_SIZE_MIN
With smallest unknown set.
@ SEL_RND
Random (uniform, for tie breaking).
@ SEL_ACTION_MAX
With highest action.
@ SEL_AFC_SIZE_MAX
With largest accumulated failure count divided by domain size.
@ SEL_ACTION_MIN
With lowest action.
@ SEL_MIN_MAX
With largest minimum unknown element.
@ SEL_MAX_MAX
With largest maximum unknown element.
@ SEL_MAX_MIN
With smallest maximum unknown element.
@ SEL_DEGREE_SIZE_MIN
With smallest degree divided by domain size.
@ SEL_MIN_MIN
With smallest minimum unknown element.
@ SEL_DEGREE_MIN
With smallest degree.
@ SEL_SIZE_MAX
With largest unknown set.
SetVarBranch(void)
Initialize with strategy SEL_NONE.
Select s
Which variable to select.
Select select(void) const
Return selection strategy.
bool operator()(void) const
Test whether iterator is still at a range or done.
int max(void) const
Return largest value of range.
void operator++(void)
Move iterator to next range (if possible).
int min(void) const
Return smallest value of range.
unsigned int width(void) const
Return width of range (distance between minimum and maximum).
SetVarGlbRanges(void)
Default constructor.
bool operator()(void) const
Test whether iterator is still at a value or done.
int val(void) const
Return current value.
void operator++(void)
Move iterator to next value (if possible).
SetVarGlbValues(void)
Default constructor.
void operator++(void)
Move iterator to next range (if possible).
SetVarLubRanges(void)
Default constructor.
unsigned int width(void) const
Return width of range (distance between minimum and maximum).
int max(void) const
Return largest value of range.
bool operator()(void) const
Test whether iterator is still at a range or done.
int min(void) const
Return smallest value of range.
bool operator()(void) const
Test whether iterator is still at a value or done.
int val(void) const
Return current value.
SetVarLubValues(void)
Default constructor.
void operator++(void)
Move iterator to next value (if possible).
int max(void) const
Return largest value of range.
bool operator()(void) const
Test whether iterator is still at a range or done.
unsigned int width(void) const
Return width of range (distance between minimum and maximum).
void operator++(void)
Move iterator to next range (if possible).
int min(void) const
Return smallest value of range.
SetVarUnknownRanges(void)
Default constructor.
int val(void) const
Return current value.
bool operator()(void) const
Test whether iterator is still at a value or done.
SetVarUnknownValues(void)
Default constructor.
void operator++(void)
Move iterator to next value (if possible).
unsigned int cardMax(void) const
Return cardinality maximum.
SetVar(void)
Default constructor.
bool notContains(int i) const
Test whether i is not in the least upper bound.
int lubMin(void) const
Return minimum element of least upper bound.
unsigned int lubSize(void) const
Return number of elements in the least upper bound.
int lubMax(void) const
Return maximum element of least upper bound.
unsigned int glbSize(void) const
Return number of elements in the greatest lower bound.
int glbMin(void) const
Return minimum element of greatest lower bound.
unsigned int unknownSize(void) const
Return number of unknown elements (elements in lub but not in glb).
int glbMax(void) const
Return maximum of greatest lower bound.
bool contains(int i) const
Test whether i is in greatest lower bound.
unsigned int cardMin(void) const
Return cardinality minimum.
Range iterator for the greatest lower bound.
Range iterator for the least upper bound.
Finite integer set variable implementation.
Set view for set variables
Range iterator for the unknown set.
virtual void done(const Space &home, const SetTraceRecorder &t)
Print that trace recorder is done.
virtual void init(const Space &home, const SetTraceRecorder &t)
Print init information.
StdSetTracer(std::ostream &os0=std::cerr)
Initialize with output stream os0.
virtual void fail(const Space &home, const SetTraceRecorder &t)
Print failure information.
virtual void prune(const Space &home, const SetTraceRecorder &t, const ViewTraceInfo &vti, int i, SetTraceDelta &d)
Print prune information.
virtual void fix(const Space &home, const SetTraceRecorder &t)
Print fixpoint information.
std::ostream & os
Output stream to use.
static StdSetTracer def
Default tracer (printing to std::cerr).
Collection of symmetries.
A reference-counted pointer to a SymmetryObject.
Combine variable selection criteria for tie-breaking.
Propagator for recording view trace information.
Tracer that process view trace information.
#define GECODE_SET_EXPORT
GECODE_FLOAT_EXPORT void trace(Home home, const FloatVarArgs &x, TraceFilter tf, int te=(TE_INIT|TE_PRUNE|TE_FIX|TE_FAIL|TE_DONE), FloatTracer &t=StdFloatTracer::def)
Create a tracer for float variables.
std::function< double(const Space &home, double w, double b)> BranchTbl
Tie-break limit function.
void assign(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatAssign vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Assign all x with variable selection vars and value selection vals.
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.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
void ite(Home home, BoolVar b, FloatVar x, FloatVar y, FloatVar z)
Post propagator for if-then-else constraint.
void precede(Home home, const IntVarArgs &x, int s, int t, IntPropLevel=IPL_DEF)
Post propagator that s precedes t in x.
IntRelType
Relation types for integers.
std::function< bool(const Space &home, SetVar x, int i)> SetBranchFilter
Branch filter function type for set variables.
std::function< double(const Space &home, SetVar x, int i)> SetBranchMerit
Branch merit function type for set variables.
std::function< int(const Space &home, SetVar x, int i)> SetBranchVal
Branch value function type for set variables.
std::function< void(Space &home, unsigned int a, SetVar x, int i, int n)> SetBranchCommit
Branch commit function type for set variables.
void weights(Home home, IntSharedArray elements, IntSharedArray weights, SetVar x, IntVar y)
Post propagator for .
void notMin(Home home, SetVar s, IntVar x)
Post propagator that x is not the minimal element of s.
void notMax(Home home, SetVar s, IntVar x)
Post propagator that x is not the maximal element of s.
SetOpType
Common operations for sets.
SetRelType
Common relation types for sets.
@ SOT_DUNION
Disjoint union.
@ SRT_GQ
Greater or equal ( ).
@ SRT_LQ
Less or equal ( ).
ViewTracer< Set::SetView > SetTracer
Tracer for set variables.
ViewTraceRecorder< Set::SetView > SetTraceRecorder
Trace recorder for set variables.
@ TE_INIT
Trace init events.
@ TE_PRUNE
Trace prune events.
@ TE_FIX
Trace fixpoint events.
@ TE_FAIL
Trace fail events.
@ TE_DONE
Trace done events.
Numerical limits for integer variables.
void check(int n, const char *l)
Check whether n is in range, otherwise throw out of limits with information l.
const int max
Largest allowed integer value.
const int min
Smallest allowed integer in integer set.
const unsigned int card
Maximum cardinality of an integer set.
const int max
Largest allowed integer in integer set.
Gecode toplevel namespace
SetVarBranch SET_VAR_MERIT_MAX(SetBranchMerit bm, BranchTbl tbl=nullptr)
Select variable with highest merit according to branch merit function bm.
SetValBranch SET_VAL_MED_INC(void)
Include median element (rounding downwards).
ArgArray< IntSet > IntSetArgs
Passing set arguments.
void atmostOne(Home home, const SetVarArgs &x, unsigned int c)
Post propagator for and .
SetVarBranch SET_VAR_ACTION_SIZE_MIN(double d=1.0, BranchTbl tbl=nullptr)
Select variable with smallest action divided by domain size with decay factor d.
SetVarBranch SET_VAR_CHB_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest CHB Q-score divided by domain size.
SetVarBranch SET_VAR_ACTION_SIZE_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest action divided by domain size with decay factor d.
SetAssign SET_ASSIGN_RND_EXC(Rnd r)
Exclude random element.
void channel(Home home, FloatVar x0, IntVar x1)
Post propagator for channeling a float and an integer variable .
SetVarBranch SET_VAR_NONE(void)
Select first unassigned variable.
SetValBranch SET_VAL_RND_INC(Rnd r)
Include random element.
SetVarBranch SET_VAR_DEGREE_SIZE_MAX(BranchTbl tbl=nullptr)
Select variable with largest degree divided by domain size.
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel ipl=IPL_DEF)
Post propagator for .
void channelSorted(Home home, const IntVarArgs &x, SetVar y)
Post propagator for and .
SharedArray< int > IntSharedArray
Arrays of integers that can be shared among several element constraints.
Archive & operator<<(Archive &e, FloatNumBranch nl)
SetValBranch SET_VAL_RND_EXC(Rnd r)
Exclude random element.
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
SetVarBranch SET_VAR_CHB_MIN(BranchTbl tbl=nullptr)
Select variable with lowest CHB Q-score.
SetVarBranch SET_VAR_MIN_MAX(BranchTbl tbl=nullptr)
Select variable with largest minimum unknown element.
SetAssign SET_ASSIGN_MED_EXC(void)
Exclude median element (rounding downwards).
SetVarBranch SET_VAR_CHB_MAX(BranchTbl tbl=nullptr)
Select variable with highest CHB Q-score.
SetAssign SET_ASSIGN_MED_INC(void)
Include median element (rounding downwards).
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
void element(Home home, IntSharedArray n, IntVar x0, IntVar x1, IntPropLevel ipl=IPL_DEF)
Post domain consistent propagator for .
SetValBranch SET_VAL(SetBranchVal v, SetBranchCommit c=nullptr)
Select value as defined by the value function v and commit function c.
SetVarBranch SET_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest unknown set.
SetVarBranch SET_VAR_RND(Rnd r)
Select random variable (uniform distribution, for tie breaking).
SetVarBranch SET_VAR_MAX_MAX(BranchTbl tbl=nullptr)
Select variable with largest maximum unknown element.
SetVarBranch SET_VAR_AFC_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count with decay factor d.
SetAssign SET_ASSIGN_MAX_INC(void)
Include largest element.
SetVarBranch SET_VAR_MIN_MIN(BranchTbl tbl=nullptr)
Select variable with smallest minimum unknown element.
SetValBranch SET_VAL_MED_EXC(void)
Exclude median element (rounding downwards).
SetValBranch SET_VAL_MAX_INC(void)
Include largest element.
SetAssign SET_ASSIGN_RND_INC(Rnd r)
Include random element.
SetVarBranch SET_VAR_CHB_SIZE_MAX(BranchTbl tbl=nullptr)
Select variable with largest CHB Q-score divided by domain size.
SetVarBranch SET_VAR_DEGREE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest degree.
SymmetryHandle VariableSymmetry(const IntVarArgs &x)
Variables in x are interchangeable.
GECODE_FLOAT_EXPORT void relax(Home home, const FloatVarArgs &x, const FloatVarArgs &sx, Rnd r, double p)
void convex(Home home, SetVar x)
Post propagator that propagates that x is convex.
SetVarBranch SET_VAR_AFC_MIN(double d=1.0, BranchTbl tbl=nullptr)
Select variable with smallest accumulated failure count with decay factor d.
SetVarBranch SET_VAR_MAX_MIN(BranchTbl tbl=nullptr)
Select variable with smallest maximum unknown element.
void wait(Home home, FloatVar x, std::function< void(Space &home)> c)
Execute c when x becomes assigned.
SetVarBranch SET_VAR_DEGREE_MAX(BranchTbl tbl=nullptr)
Select variable with largest degree.
SetValBranch SET_VAL_MIN_INC(void)
Include smallest element.
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
SetVarBranch SET_VAR_AFC_SIZE_MIN(double d=1.0, BranchTbl tbl=nullptr)
Select variable with smallest accumulated failure count divided by domain size with decay factor d.
SymmetryHandle VariableSequenceSymmetry(const IntVarArgs &x, int ss)
Variable sequences in x of size ss are interchangeable.
SetAssign SET_ASSIGN_MIN_EXC(void)
Exclude smallest element.
SetAssign SET_ASSIGN_MIN_INC(void)
Include smallest element.
SetValBranch SET_VAL_MAX_EXC(void)
Exclude largest element.
SetAssign SET_ASSIGN(SetBranchVal v, SetBranchCommit c=nullptr)
Select value as defined by the value function v and commit function c.
SetAssign SET_ASSIGN_MAX_EXC(void)
Exclude largest element.
SetVarBranch SET_VAR_AFC_SIZE_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count divided by domain size with decay factor d.
SetVarBranch SET_VAR_ACTION_MIN(double d=1.0, BranchTbl tbl=nullptr)
Select variable with lowest action with decay factor d.
LinIntExpr cardinality(const SetExpr &)
Cardinality of set expression.
std::function< void(const Space &home, const Brancher &b, unsigned int a, SetVar x, int i, const int &n, std::ostream &o)> SetVarValPrint
Function type for printing branching alternatives for set variables.
SetVarBranch SET_VAR_MERIT_MIN(SetBranchMerit bm, BranchTbl tbl=nullptr)
Select variable with least merit according to branch merit function bm.
SetVarBranch SET_VAR_DEGREE_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest degree divided by domain size.
SetValBranch SET_VAL_MIN_EXC(void)
Exclude smallest element.
SetVarBranch SET_VAR_SIZE_MAX(BranchTbl tbl=nullptr)
Select variable with largest unknown set.
SetVarBranch SET_VAR_ACTION_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with highest action with decay factor d.