Generated on Thu Jul 25 2019 00:00:00 for Gecode by doxygen 1.8.15
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  * Last modified:
10  * $Date: 2016-06-20 16:44:21 +0200 (Mon, 20 Jun 2016) $ by $Author: schulte $
11  * $Revision: 15120 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace Int { namespace LDSB {
39 
41  template <class T, class A>
42  ArgArray<T>
44  ArgArray<T> a(s.entries());
45  for (int i = 0 ; i < s.entries() ; ++i) {
46  a[i] = s[i];
47  }
48  return a;
49  }
50 
51  template<class View>
53 
54  template<class View>
55  void*
56  SymmetryImp<View>::operator new(size_t s, Space& home) {
57  return home.ralloc(s);
58  }
59 
60  template<class View>
61  void
63 
64  template<class View>
65  void
66  SymmetryImp<View>::operator delete(void*) {}
67 
68  template <class View>
70  ::VariableSymmetryImp(Space& home, int* _indices, unsigned int n)
71  : indices(home, 0, 0) {
72  // Find minimum and maximum value in _indices: the minimum is the
73  // offset, and the maximum dictates how large the bitset needs to
74  // be.
75  int maximum = _indices[0];
76  int minimum = _indices[0];
77  for (unsigned int i = 1 ; i < n ; i++) {
78  if (_indices[i] > maximum) maximum = _indices[i];
79  if (_indices[i] < minimum) minimum = _indices[i];
80  }
81  indices.resize(home, maximum-minimum+1, minimum);
82 
83  // Set the bits for the included indices.
84  for (unsigned int i = 0 ; i < n ; i++) {
85  indices.set(_indices[i]);
86  }
87  }
88 
89 
90 
91  template <class View>
92  inline
95  indices(home, other.indices) {}
96 
97  template <class View>
98  size_t
101  indices.dispose(home);
102  return sizeof(*this);
103  }
104 
105  template <class View>
106  void
109  if (indices.valid(l._variable)) {
110  indices.clear(l._variable);
111  }
112  }
113 
114  template <class View>
117  ::copy(Space& home, bool share) const {
118  (void) share;
119  return new (home) VariableSymmetryImp<View>(home, *this);
120  }
121 
122 
123 
124  // The minimum value in vs is the bitset's offset, and the maximum
125  // dictates how large the bitset needs to be.
126  template <class View>
128  ::ValueSymmetryImp(Space& home, int* vs, unsigned int n)
129  : values(home, 0, 0) {
130  // Find minimum and maximum value in vs: the minimum is the
131  // offset, and the maximum dictates how large the bitset needs to
132  // be.
133  assert(n > 0);
134  int maximum = vs[0];
135  int minimum = vs[0];
136  for (unsigned int i = 1 ; i < n ; i++) {
137  if (vs[i] > maximum) maximum = vs[i];
138  if (vs[i] < minimum) minimum = vs[i];
139  }
140  values.resize(home, maximum-minimum+1, minimum);
141 
142  // Set the bits for the included values.
143  for (unsigned int i = 0 ; i < n ; i++) {
144  values.set(vs[i]);
145  }
146  }
147 
148  template <class View>
151  : values(home, other.values) { }
152 
153  template <class View>
154  size_t
157  values.dispose(home);
158  return sizeof(*this);
159  }
160 
161  template <class View>
162  void
165  if (values.valid(l._value))
166  values.clear(l._value);
167  }
168 
169  template <class View>
172  ::copy(Space& home, bool share) const {
173  (void) share;
174  return new (home) ValueSymmetryImp(home, *this);
175  }
176 
177 
178 
179  template <class View>
180  int
182  ::getVal(unsigned int sequence, unsigned int position) const {
183  return indices[sequence*seq_size + position];
184  }
185 
186  template <class View>
188  ::VariableSequenceSymmetryImp(Space& home, int* _indices, unsigned int n,
189  unsigned int seqsize)
190  : n_indices(n), seq_size(seqsize), n_seqs(n/seqsize) {
191  indices = home.alloc<unsigned int>(n_indices);
192  unsigned int max_index = _indices[0];
193  for (unsigned int i = 0 ; i < n_indices ; i++) {
194  indices[i] = _indices[i];
195  if (indices[i] > max_index)
196  max_index = indices[i];
197  }
198 
199  lookup_size = max_index+1;
200  lookup = home.alloc<int>(lookup_size);
201  for (unsigned int i = 0 ; i < lookup_size ; i++)
202  lookup[i] = -1;
203  for (unsigned int i = 0 ; i < n_indices ; i++) {
204  if (lookup[indices[i]] == -1)
205  lookup[indices[i]] = i;
206  }
207  }
208 
209  template <class View>
213  : n_indices(s.n_indices), seq_size(s.seq_size), n_seqs(s.n_seqs),
214  lookup_size(s.lookup_size) {
215  (void) share;
216  indices = home.alloc<unsigned int>(n_indices);
217  memcpy(indices, s.indices, n_indices * sizeof(int));
218  lookup = home.alloc<int>(lookup_size);
219  memcpy(lookup, s.lookup, lookup_size * sizeof(int));
220  }
221 
222  template <class View>
223  size_t
226  home.free<unsigned int>(indices, n_indices);
227  home.free<int>(lookup, lookup_size);
228  return sizeof(*this);
229  }
230 
232  template <class View>
237  if (l._variable < (int)lookup_size) {
238  int posIt = lookup[l._variable];
239  if (posIt == -1) {
240  return dynamicStackToArgArray(s);
241  }
242  unsigned int seqNum = posIt / seq_size;
243  unsigned int seqPos = posIt % seq_size;
244  for (unsigned int seq = 0 ; seq < n_seqs ; seq++) {
245  if (seq == seqNum) {
246  continue;
247  }
248  if (x[getVal(seq, seqPos)].assigned()) {
249  continue;
250  }
251  bool active = true;
252  const unsigned int *firstSeq = &indices[seqNum*seq_size];
253  const unsigned int *secondSeq = &indices[seq*seq_size];
254  for (unsigned int i = 0 ; i < seq_size ; i++) {
255  const View& xv = x[firstSeq[i]];
256  const View& yv = x[secondSeq[i]];
257  if ((!xv.assigned() && !yv.assigned())
258  || (xv.assigned() && yv.assigned() && xv.val() == yv.val())) {
259  continue;
260  } else {
261  active = false;
262  break;
263  }
264  }
265 
266  if (active) {
267  s.push(Literal(secondSeq[seqPos], l._value));
268  }
269  }
270  }
271  return dynamicStackToArgArray(s);
272  }
273 
274 
275  template <class View>
276  void
279  // Do nothing.
280  (void) l;
281  }
282 
283  template <class View>
286  ::copy(Space& home, bool share) const {
287  return new (home) VariableSequenceSymmetryImp<View>(home, share, *this);
288  }
289 
290 
291 
292  template <class View>
293  int
295  ::getVal(unsigned int sequence, unsigned int position) const {
296  return values[sequence*seq_size + position];
297  }
298 
299  template <class View>
301  ::ValueSequenceSymmetryImp(Space& home, int* _values, unsigned int n,
302  unsigned int seqsize)
303  : n_values(n), seq_size(seqsize), n_seqs(n/seqsize),
304  dead_sequences(home, n_seqs) {
305  values = home.alloc<int>(n_values);
306  for (unsigned int i = 0 ; i < n_values ; i++)
307  values[i] = _values[i];
308  }
309 
310  template <class View>
314  : n_values(vss.n_values),
315  seq_size(vss.seq_size),
316  n_seqs(vss.n_seqs),
317  dead_sequences(home, vss.dead_sequences) {
318  values = home.alloc<int>(n_values);
319  for (unsigned int i = 0 ; i < n_values ; i++)
320  values[i] = vss.values[i];
321  }
322 
323  template <class View>
324  size_t
327  home.free(values, n_values);
328  return sizeof(*this);
329  }
330 
331  template <class View>
332  void
335  unsigned int seq = 0;
336  unsigned int pos = 0;
337  for (unsigned int i = 0 ; i < n_values ; i++) {
338  if (values[i] == l._value) {
339  dead_sequences.set(seq);
340  // TODO: This can be slightly optimised.
341  while (pos < seq_size) {
342  i++;
343  pos++;
344  }
345  }
346  pos++;
347  if (pos == seq_size) {
348  pos = 0;
349  seq++;
350  }
351  }
352  }
353 
354  template <class View>
357  ::copy(Space& home, bool share) const {
358  (void) share;
359  return new (home) ValueSequenceSymmetryImp<View>(home, *this);
360  }
361 
362 }}}
363 
364 // STATISTICS: int-branch
SymmetryImp< View > * copy(Space &home, bool share) const
Copy function.
Definition: sym-imp.hpp:357
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:225
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
Definition: sequence.cpp:51
A Literal is a pair of variable index and value.
Definition: ldsb.hh:50
SymmetryImp< View > * copy(Space &home, bool share) const
Copy function.
Definition: sym-imp.hpp:286
ValueSymmetryImp(Space &home, int *vs, unsigned int n)
Constructor for creation.
Definition: sym-imp.hpp:128
virtual ~SymmetryImp(void)
Unused destructor.
Definition: sym-imp.hpp:52
VariableSymmetryImp(Space &home, int *vs, unsigned int n)
Constructor for creation.
Definition: sym-imp.hpp:70
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
Implementation of a variable sequence symmetry.
Definition: ldsb.hh:227
SymmetryImp< View > * copy(Space &home, bool share) const
Copy function.
Definition: sym-imp.hpp:117
int * lookup
Map from variable's index to its sequence and position.
Definition: ldsb.hh:246
Computation spaces.
Definition: core.hpp:1748
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2868
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Argument array for non-primitive types.
Definition: array.hpp:727
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:326
unsigned int * indices
Array of variable indices.
Definition: ldsb.hh:231
Implementation of a value symmetry.
Definition: ldsb.hh:207
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:182
SymmetryImp< View > * copy(Space &home, bool share) const
Copy function.
Definition: sym-imp.hpp:172
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:156
View arrays.
Definition: array.hpp:234
void free(T *b, long unsigned int n)
Delete n objects allocated from space heap starting at b.
Definition: core.hpp:2894
double position(const Space &home, IntVar x, int i)
Definition: ldsb.cpp:1277
Implementation of a single symmetry.
Definition: ldsb.hh:166
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:164
Heap heap
The single global heap.
Definition: heap.cpp:48
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
Implementation of a variable symmetry.
Definition: ldsb.hh:187
Stack with arbitrary number of elements.
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:108
Implementation of a value sequence symmetry.
Definition: ldsb.hh:269
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
Definition: sym-imp.hpp:235
void values(Home home, const IntVarArgs &x, IntSet y, IntPropLevel ipl=IPL_DEF)
Post constraint .
Definition: minimodel.hh:1868
Post propagator for SetVar x
Definition: set.hh:784
void update(Literal)
Search left-branch update.
Definition: sym-imp.hpp:278
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:43
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:100
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:295
int entries(void) const
Return number of entries currently on stack.
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:334
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:188