Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
sym-imp.hpp
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 namespace Gecode { namespace Int { namespace LDSB {
35 
37  template <class T, class A>
38  ArgArray<T>
40  ArgArray<T> a(s.entries());
41  for (int i = 0 ; i < s.entries() ; ++i) {
42  a[i] = s[i];
43  }
44  return a;
45  }
46 
47  template<class View>
49 
50  template<class View>
51  void*
52  SymmetryImp<View>::operator new(size_t s, Space& home) {
53  return home.ralloc(s);
54  }
55 
56  template<class View>
57  void
59 
60  template<class View>
61  void
62  SymmetryImp<View>::operator delete(void*) {}
63 
64  template <class View>
66  ::VariableSymmetryImp(Space& home, int* _indices, unsigned int n)
67  : indices(home, 0, 0) {
68  // Find minimum and maximum value in _indices: the minimum is the
69  // offset, and the maximum dictates how large the bitset needs to
70  // be.
71  int maximum = _indices[0];
72  int minimum = _indices[0];
73  for (unsigned int i = 1 ; i < n ; i++) {
74  if (_indices[i] > maximum) maximum = _indices[i];
75  if (_indices[i] < minimum) minimum = _indices[i];
76  }
77  indices.resize(home, maximum-minimum+1, minimum);
78 
79  // Set the bits for the included indices.
80  for (unsigned int i = 0 ; i < n ; i++) {
81  indices.set(_indices[i]);
82  }
83  }
84 
85 
86 
87  template <class View>
88  inline
91  indices(home, other.indices) {}
92 
93  template <class View>
94  size_t
96  ::dispose(Space& home) {
97  indices.dispose(home);
98  return sizeof(*this);
99  }
100 
101  template <class View>
102  void
105  if (indices.valid(l._variable)) {
106  indices.clear(l._variable);
107  }
108  }
109 
110  template <class View>
113  return new (home) VariableSymmetryImp<View>(home, *this);
114  }
115 
116 
117 
118  // The minimum value in vs is the bitset's offset, and the maximum
119  // dictates how large the bitset needs to be.
120  template <class View>
122  ::ValueSymmetryImp(Space& home, int* vs, unsigned int n)
123  : values(home, 0, 0) {
124  // Find minimum and maximum value in vs: the minimum is the
125  // offset, and the maximum dictates how large the bitset needs to
126  // be.
127  assert(n > 0);
128  int maximum = vs[0];
129  int minimum = vs[0];
130  for (unsigned int i = 1 ; i < n ; i++) {
131  if (vs[i] > maximum) maximum = vs[i];
132  if (vs[i] < minimum) minimum = vs[i];
133  }
134  values.resize(home, maximum-minimum+1, minimum);
135 
136  // Set the bits for the included values.
137  for (unsigned int i = 0 ; i < n ; i++) {
138  values.set(vs[i]);
139  }
140  }
141 
142  template <class View>
145  : values(home, other.values) { }
146 
147  template <class View>
148  size_t
151  values.dispose(home);
152  return sizeof(*this);
153  }
154 
155  template <class View>
156  void
159  if (values.valid(l._value))
160  values.clear(l._value);
161  }
162 
163  template <class View>
166  return new (home) ValueSymmetryImp(home, *this);
167  }
168 
169 
170 
171  template <class View>
172  int
174  ::getVal(unsigned int sequence, unsigned int position) const {
175  return indices[sequence*seq_size + position];
176  }
177 
178  template <class View>
180  ::VariableSequenceSymmetryImp(Space& home, int* _indices, unsigned int n,
181  unsigned int seqsize)
182  : n_indices(n), seq_size(seqsize), n_seqs(n/seqsize) {
183  indices = home.alloc<unsigned int>(n_indices);
184  unsigned int max_index = _indices[0];
185  for (unsigned int i = 0 ; i < n_indices ; i++) {
186  indices[i] = _indices[i];
187  if (indices[i] > max_index)
188  max_index = indices[i];
189  }
190 
191  lookup_size = max_index+1;
192  lookup = home.alloc<int>(lookup_size);
193  for (unsigned int i = 0 ; i < lookup_size ; i++)
194  lookup[i] = -1;
195  for (unsigned int i = 0 ; i < n_indices ; i++) {
196  if (lookup[indices[i]] == -1)
197  lookup[indices[i]] = i;
198  }
199  }
200 
201  template <class View>
205  : n_indices(s.n_indices), seq_size(s.seq_size), n_seqs(s.n_seqs),
206  lookup_size(s.lookup_size) {
207  indices = home.alloc<unsigned int>(n_indices);
208  memcpy(indices, s.indices, n_indices * sizeof(int));
209  lookup = home.alloc<int>(lookup_size);
210  memcpy(lookup, s.lookup, lookup_size * sizeof(int));
211  }
212 
213  template <class View>
214  size_t
217  home.free<unsigned int>(indices, n_indices);
218  home.free<int>(lookup, lookup_size);
219  return sizeof(*this);
220  }
221 
223  template <class View>
228  if (l._variable < (int)lookup_size) {
229  int posIt = lookup[l._variable];
230  if (posIt == -1) {
231  return dynamicStackToArgArray(s);
232  }
233  unsigned int seqNum = posIt / seq_size;
234  unsigned int seqPos = posIt % seq_size;
235  for (unsigned int seq = 0 ; seq < n_seqs ; seq++) {
236  if (seq == seqNum) {
237  continue;
238  }
239  if (x[getVal(seq, seqPos)].assigned()) {
240  continue;
241  }
242  bool active = true;
243  const unsigned int *firstSeq = &indices[seqNum*seq_size];
244  const unsigned int *secondSeq = &indices[seq*seq_size];
245  for (unsigned int i = 0 ; i < seq_size ; i++) {
246  const View& xv = x[firstSeq[i]];
247  const View& yv = x[secondSeq[i]];
248  if ((!xv.assigned() && !yv.assigned())
249  || (xv.assigned() && yv.assigned() && xv.val() == yv.val())) {
250  continue;
251  } else {
252  active = false;
253  break;
254  }
255  }
256 
257  if (active) {
258  s.push(Literal(secondSeq[seqPos], l._value));
259  }
260  }
261  }
262  return dynamicStackToArgArray(s);
263  }
264 
265 
266  template <class View>
267  void
270  // Do nothing.
271  (void) l;
272  }
273 
274  template <class View>
277  ::copy(Space& home) const {
278  return new (home) VariableSequenceSymmetryImp<View>(home, *this);
279  }
280 
281 
282 
283  template <class View>
284  int
286  ::getVal(unsigned int sequence, unsigned int position) const {
287  return values[sequence*seq_size + position];
288  }
289 
290  template <class View>
292  ::ValueSequenceSymmetryImp(Space& home, int* _values, unsigned int n,
293  unsigned int seqsize)
294  : n_values(n), seq_size(seqsize), n_seqs(n/seqsize),
295  dead_sequences(home, n_seqs) {
296  values = home.alloc<int>(n_values);
297  for (unsigned int i = 0 ; i < n_values ; i++)
298  values[i] = _values[i];
299  }
300 
301  template <class View>
305  : n_values(vss.n_values),
306  seq_size(vss.seq_size),
307  n_seqs(vss.n_seqs),
308  dead_sequences(home, vss.dead_sequences) {
309  values = home.alloc<int>(n_values);
310  for (unsigned int i = 0 ; i < n_values ; i++)
311  values[i] = vss.values[i];
312  }
313 
314  template <class View>
315  size_t
318  home.free(values, n_values);
319  return sizeof(*this);
320  }
321 
322  template <class View>
323  void
326  unsigned int seq = 0;
327  unsigned int pos = 0;
328  for (unsigned int i = 0 ; i < n_values ; i++) {
329  if (values[i] == l._value) {
330  dead_sequences.set(seq);
331  // TODO: This can be slightly optimised.
332  while (pos < seq_size) {
333  i++;
334  pos++;
335  }
336  }
337  pos++;
338  if (pos == seq_size) {
339  pos = 0;
340  seq++;
341  }
342  }
343  }
344 
345  template <class View>
348  ::copy(Space& home) const {
349  return new (home) ValueSequenceSymmetryImp<View>(home, *this);
350  }
351 
352 }}}
353 
354 // STATISTICS: int-branch
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:216
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition: sym-imp.hpp:277
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
Definition: sequence.cpp:47
A Literal is a pair of variable index and value.
Definition: ldsb.hh:46
ValueSymmetryImp(Space &home, int *vs, unsigned int n)
Constructor for creation.
Definition: sym-imp.hpp:122
virtual ~SymmetryImp(void)
Unused destructor.
Definition: sym-imp.hpp:48
VariableSymmetryImp(Space &home, int *vs, unsigned int n)
Constructor for creation.
Definition: sym-imp.hpp:66
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:41
Implementation of a variable sequence symmetry.
Definition: ldsb.hh:223
int * lookup
Map from variable&#39;s index to its sequence and position.
Definition: ldsb.hh:242
int _value
The value of the literal. For int and bool variables, this is the value itself; for set variables...
Definition: ldsb.hh:59
int _variable
Variable index. The ViewArray that the index is meant for is assumed to be known by context...
Definition: ldsb.hh:55
Computation spaces.
Definition: core.hpp:1701
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2794
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Argument array for non-primitive types.
Definition: array.hpp:711
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:317
unsigned int * indices
Array of variable indices.
Definition: ldsb.hh:227
Implementation of a value symmetry.
Definition: ldsb.hh:203
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
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:150
View arrays.
Definition: array.hpp:224
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Definition: core.hpp:2820
double position(const Space &home, IntVar x, int i)
Definition: ldsb.cpp:1265
Implementation of a single symmetry.
Definition: ldsb.hh:162
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:158
struct Gecode::@585::NNF::@62::@64 a
For atomic nodes.
Heap heap
The single global heap.
Definition: heap.cpp:44
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
Implementation of a variable symmetry.
Definition: ldsb.hh:183
Stack with arbitrary number of elements.
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:104
Implementation of a value sequence symmetry.
Definition: ldsb.hh:265
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
Definition: sym-imp.hpp:226
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition: minimodel.hh:1993
Post propagator for SetVar x
Definition: set.hh:765
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition: sym-imp.hpp:112
void update(Literal)
Search left-branch update.
Definition: sym-imp.hpp:269
Gecode toplevel namespace
ArgArray< T > dynamicStackToArgArray(const Support::DynamicStack< T, A > &s)
Convert a DynamicStack<T,A> into an ArgArray<T>
Definition: sym-imp.hpp:39
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition: sym-imp.hpp:165
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:96
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:286
int entries(void) const
Return number of entries currently on stack.
SymmetryImp< View > * copy(Space &home) const
Copy function.
Definition: sym-imp.hpp:348
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:325
void push(const T &x)
Push element x on top of stack.
VariableSequenceSymmetryImp(Space &home, int *_indices, unsigned int n, unsigned int seqsize)
Constructor for creation.
Definition: sym-imp.hpp:180
int * values
Set of sequences.
Definition: ldsb.hh:269