Generated on Fri Jan 10 2020 11:38:25 for Gecode by doxygen 1.8.16
ldsb.hh
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christopher Mears <chris.mears@monash.edu>
5  *
6  * Copyright:
7  * Christopher Mears, 2012
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 
34 #ifndef __GECODE_INT_LDSB_HH__
35 #define __GECODE_INT_LDSB_HH__
36 
37 #include <gecode/int.hh>
38 
43 namespace Gecode { namespace Int { namespace LDSB {
44 
46  class Literal {
47  public:
49  Literal(void);
51  Literal(int _var, int _val);
52 
55  int _variable;
59  int _value;
60 
63  bool operator <(const Literal &rhs) const;
64  };
65 
78  std::pair<int,int>
79  findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index);
80 }}}
81 
82 namespace Gecode {
84  template<>
86  public:
90  };
91 
95  template<>
97  public:
101  };
102 }
103 
104 namespace Gecode { namespace Int { namespace LDSB {
107  public:
109  int nrefs;
111  SymmetryObject(void);
113  virtual ~SymmetryObject(void);
114  };
117  public:
121  int nxs;
125  ~VariableSymmetryObject(void);
126  };
129  public:
134  };
137  public:
141  int nxs;
143  int seq_size;
148  };
151  public:
155  int seq_size;
158  };
159 
161  template<class View>
162  class SymmetryImp {
163  public:
165  virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const = 0;
167  virtual void update(Literal) = 0;
169  virtual SymmetryImp<View>* copy(Space& home) const = 0;
171  virtual size_t dispose(Space& home) = 0;
173  virtual ~SymmetryImp(void);
175  static void* operator new(size_t s, Space& home);
177  static void operator delete(void*,Space&);
179  static void operator delete(void*);
180  };
182  template <class View>
183  class VariableSymmetryImp : public SymmetryImp<View> {
184  protected:
187  public:
189  VariableSymmetryImp<View>(Space& home, int* vs, unsigned int n);
193  virtual size_t dispose(Space& home);
195  void update(Literal);
197  virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
199  SymmetryImp<View>* copy(Space& home) const;
200  };
202  template <class View>
203  class ValueSymmetryImp : public SymmetryImp<View>
204  {
205  public:
209  ValueSymmetryImp<View>(Space& home, int* vs, unsigned int n);
213  virtual size_t dispose(Space& home);
215  void update(Literal);
217  virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
219  SymmetryImp<View>* copy(Space& home) const;
220  };
222  template <class View>
224  {
225  protected:
227  unsigned int *indices;
229  unsigned int n_indices;
231  unsigned int seq_size;
233  unsigned int n_seqs;
234 
236  // e.g. lookup[2] == 10 indicates that the variable with index 2
237  // occurs at position 10 in the "indices" array.
238  // If a variable occurs more than once, only the first occurrence
239  // is recorded.
240  // A value of -1 indicates that the variable does not occur in
241  // "indices".
242  int *lookup;
244  unsigned int lookup_size;
245 
248  int getVal(unsigned int sequence, unsigned int position) const;
249  public:
251  VariableSequenceSymmetryImp<View>(Space& home, int *_indices, unsigned int n, unsigned int seqsize);
255  virtual size_t dispose(Space& home);
257  void update(Literal);
259  virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
261  SymmetryImp<View>* copy(Space& home) const;
262  };
264  template <class View>
266  {
267  protected:
269  int *values;
271  unsigned int n_values;
273  unsigned int seq_size;
275  unsigned int n_seqs;
280  int getVal(unsigned int sequence, unsigned int position) const;
281  private:
283  public:
285  ValueSequenceSymmetryImp<View>(Space& home, int* _values, unsigned int n, unsigned int seqsize);
289  virtual size_t dispose(Space& home);
291  void update(Literal);
293  virtual ArgArray<Literal> symmetric(Literal, const ViewArray<View>&) const;
295  SymmetryImp<View>* copy(Space& home) const;
296  };
297 
300  template<class Val>
302  private:
304  const Literal * const _literals;
306  const int _nliterals;
307  public:
310  LDSBChoice(const Brancher& b, unsigned int a, const Pos& p, const Val& n,
311  const Literal* literals, int nliterals);
313  ~LDSBChoice(void);
315  const Literal* literals(void) const;
317  int nliterals(void) const;
319  virtual void archive(Archive& e) const;
320  };
321 
330  template<class View, int n, class Val, unsigned int a,
331  class Filter, class Print>
332  class LDSBBrancher : public ViewValBrancher<View,n,Val,a,Filter,Print> {
333  public:
338  int _nsyms;
339  // Position of variable that last choice was created for
340  int _prevPos;
341  protected:
343  LDSBBrancher(Space& home, LDSBBrancher& b);
345  LDSBBrancher(Home home,
347  ViewSel<View>* vs[n],
349  SymmetryImp<View>** syms, int nsyms,
352  public:
354  virtual const Choice* choice(Space& home);
356  virtual const Choice* choice(const Space& home, Archive& e);
358  virtual ExecStatus commit(Space& home, const Choice& c, unsigned int b);
360  virtual Actor* copy(Space& home);
362  virtual size_t dispose(Space& home);
364  static void post(Home home,
366  ViewSel<View>* vs[n],
368  SymmetryImp<View>** syms,
369  int nsyms,
372  };
373 
375  template<class View, int n, class Val, unsigned int a>
376  void postldsbbrancher(Home home,
378  ViewSel<View>* vs[n],
380  SymmetryImp<View>** syms, int nsyms,
383 
385  template<class View>
386  ModEvent prune(Space& home, View x, int v);
387 
388 }}}
389 
392 
393 #endif
394 
395 // STATISTICS: int-branch
396 
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int * values
Set of sequences.
Definition: ldsb.hh:269
int seq_size
Size of each sequence in symmetry.
Definition: ldsb.hh:143
std::function< bool(const Space &home, Var x, int i)> BranchFilter
Function type for branch filter functions.
Definition: filter.hpp:41
Post propagator for SetVar x
Definition: set.hh:767
unsigned int seq_size
Size of each sequence in symmetry.
Definition: ldsb.hh:273
unsigned int seq_size
Size of each sequence in symmetry.
Definition: ldsb.hh:231
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition: sym-imp.hpp:112
VarImpBase ** xs
Array of variables in symmetry.
Definition: ldsb.hh:139
#define GECODE_VTABLE_EXPORT
Definition: support.hh:72
Choice storing position and value, and symmetric literals to be excluded on the right branch.
Definition: ldsb.hh:301
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:318
IntSet values
Set of symmetric values.
Definition: ldsb.hh:131
VarImpBase ** xs
Array of variables in symmetry.
Definition: ldsb.hh:119
void postldsbbrancher(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, SymmetryImp< View > **syms, int nsyms, BranchFilter< typename View::VarType > bf, VarValPrint< typename View::VarType, Val > vvp)
Post LDSB brancher.
Definition: brancher.hpp:275
Implementation of a value symmetry.
Definition: ldsb.hh:203
ArgArray< VarImpBase * > StorageType
Definition: ldsb.hh:87
virtual size_t dispose(Space &home)
Delete brancher and return its size.
Definition: brancher.hpp:267
int _variable
Variable index. The ViewArray that the index is meant for is assumed to be known by context.
Definition: ldsb.hh:55
Support::BitSet< Space > dead_sequences
Which sequences are dead.
Definition: ldsb.hh:277
Implementation of a symmetry at the modelling level.
Definition: ldsb.hh:106
Archive representation
Definition: archive.hpp:42
Support::BitSetOffset< Space > values
Symmetric values.
Definition: ldsb.hh:207
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
Definition: sym-imp.hpp:226
ViewArray< View > x
Views to branch on.
Definition: view.hpp:83
Computation spaces.
Definition: core.hpp:1742
int getVal(unsigned int sequence, unsigned int position) const
Get the value in the specified sequence at the specified position. (Both are zero-based....
Definition: sym-imp.hpp:287
ArgArray< VarImpBase * > ArgsType
Definition: ldsb.hh:89
Base-class for both propagators and branchers.
Definition: core.hpp:628
virtual SymmetryImp< View > * copy(Space &home) const =0
Copy function.
Implementation of a variable symmetry.
Definition: ldsb.hh:183
void update(Literal)
Search left-branch update.
Definition: sym-imp.hpp:270
virtual size_t dispose(Space &home)=0
Disposal.
Generic brancher by view and value selection.
Definition: view-val.hpp:91
ModEvent prune(Space &home, View x, int v)
Exclude value \v from variable view \x.
Gecode toplevel namespace
IntArgs values
Array of values in symmetry.
Definition: ldsb.hh:153
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
virtual ~SymmetryImp(void)
Unused destructor.
Definition: sym-imp.hpp:48
bool operator<(const Literal &rhs) const
Less than. The ordering is the lexicographical order on the (variable,value) pair.
Definition: brancher.hpp:49
Integer sets.
Definition: int.hh:174
unsigned int n_seqs
Number of sequences in symmetry.
Definition: ldsb.hh:233
View::VarType Var
The corresponding variable.
Definition: view-val.hpp:97
ViewSel< View > * vs[n]
View selection objects.
Definition: view.hpp:87
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
Implementation of a value sequence symmetry at the modelling level.
Definition: ldsb.hh:150
Argument array for non-primitive types.
Definition: array.hpp:656
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition: sym-imp.hpp:349
virtual ExecStatus commit(Space &home, const Choice &c, unsigned int b)
Perform commit for choice c and alternative b.
Definition: brancher.hpp:232
virtual const Choice * choice(Space &home)
Return choice.
Definition: brancher.hpp:148
Base-class for branchers.
Definition: core.hpp:1442
Implementation of a variable sequence symmetry.
Definition: ldsb.hh:223
unsigned int n_values
Total number of values (n_seqs * seq_size)
Definition: ldsb.hh:271
#define GECODE_INT_EXPORT
Definition: int.hh:81
Home class for posting propagators
Definition: core.hpp:856
int _nsyms
Number of symmetry implementations.
Definition: ldsb.hh:338
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:150
int nxs
Number of variables in symmetry.
Definition: ldsb.hh:141
Implementation of a variable symmetry at the modelling level.
Definition: ldsb.hh:116
int nrefs
Number of references that point to this symmetry object.
Definition: ldsb.hh:109
virtual void update(Literal)=0
Left-branch update.
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition: sym-imp.hpp:278
int nxs
Number of variables in symmetry.
Definition: ldsb.hh:121
Implementation of a value symmetry at the modelling level.
Definition: ldsb.hh:128
unsigned int n_indices
Total number of indices (n_seqs * seq_size)
Definition: ldsb.hh:229
Implementation of a value sequence symmetry.
Definition: ldsb.hh:265
ValSelCommitBase< View, Val > * vsc
Value selection and commit object.
Definition: view-val.hpp:99
virtual Actor * copy(Space &home)
Perform cloning.
Definition: brancher.hpp:138
A Literal is a pair of variable index and value.
Definition: ldsb.hh:46
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:216
LiteralArgs StorageType
Definition: ldsb.hh:98
int ModEvent
Type for modification events.
Definition: core.hpp:62
unsigned int lookup_size
Size of lookup.
Definition: ldsb.hh:244
const int v[7]
Definition: distinct.cpp:259
Simple bitsets.
Definition: bitset.hpp:45
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:158
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
Choice storing position and value
Definition: view-val.hpp:46
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const =0
Compute symmetric literals.
Traits of arrays in Gecode.
Definition: array.hpp:94
ArgArray< Int::LDSB::Literal > LiteralArgs
An array of literals.
Definition: ldsb.hh:93
int _value
The value of the literal. For int and bool variables, this is the value itself; for set variables,...
Definition: ldsb.hh:59
Implementation of a variable sequence symmetry at the modelling level.
Definition: ldsb.hh:136
Support::BitSetOffset< Space > indices
Symmetric variable indices.
Definition: ldsb.hh:186
VarImpBase * ValueType
Definition: ldsb.hh:88
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
Definition: sequence.cpp:47
int * lookup
Map from variable's index to its sequence and position.
Definition: ldsb.hh:242
std::pair< int, int > findVar(int *indices, unsigned int n_values, unsigned int seq_size, int index)
Find the location of an integer in a collection of sequences.
Definition: ldsb.cpp:42
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:96
Base-class for variable implementations.
Definition: core.hpp:172
Symmetry-breaking brancher with generic view and value selection.
Definition: ldsb.hh:332
int seq_size
Size of each sequence in symmetry.
Definition: ldsb.hh:155
LiteralArgs ArgsType
Definition: ldsb.hh:100
static void post(Home home, ViewArray< View > &x, ViewSel< View > *vs[n], ValSelCommitBase< View, Val > *vsc, SymmetryImp< View > **syms, int nsyms, BranchFilter< Var > bf, VarValPrint< Var, Val > vvp)
Brancher post function.
Definition: brancher.hpp:112
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:104
Position information.
Definition: view.hpp:44
Gecode::FloatVal c(-8, 8)
View arrays.
Definition: array.hpp:253
unsigned int * indices
Array of variable indices.
Definition: ldsb.hh:227
Implementation of a single symmetry.
Definition: ldsb.hh:162
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
int _prevPos
Definition: ldsb.hh:340
Choice for performing commit
Definition: core.hpp:1412
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:326
Passing integer arguments.
Definition: int.hh:628
Bitsets with index offset.
std::function< void(const Space &home, const Brancher &b, unsigned int a, Var x, int i, const Val &m, std::ostream &o)> VarValPrint
Function type for printing variable and value selection.
Definition: print.hpp:43
unsigned int n_seqs
Number of sequences in symmetry.
Definition: ldsb.hh:275
int getVal(unsigned int sequence, unsigned int position) const
Get the value in the specified sequence at the specified position. (Both are zero-based....
Definition: sym-imp.hpp:174
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition: sym-imp.hpp:165
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
Literal(void)
Constructor for an empty literal.
Definition: brancher.hpp:40
LDSBBrancher(Space &home, LDSBBrancher &b)
Constructor for cloning b.
Definition: brancher.hpp:125
Int::LDSB::Literal ValueType
Definition: ldsb.hh:99
SymmetryImp< View > ** _syms
Array of symmetry implementations.
Definition: ldsb.hh:336
double position(const Space &home, IntVar x, int i)
Definition: ldsb.cpp:1266
ExecStatus
Definition: core.hpp:472