Generated on Sat Feb 7 2015 02:01:24 for Gecode by doxygen 1.8.9.1
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: 2013-03-07 02:18:29 +0100 (Thu, 07 Mar 2013) $ by $Author: mears $
11  * $Revision: 13455 $
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>
52  void*
53  SymmetryImp<View>::operator new(size_t s, Space& home) {
54  return home.ralloc(s);
55  }
56 
57  template<class View>
58  void
60 
61  template<class View>
62  void
63  SymmetryImp<View>::operator delete(void*) {}
64 
65  template <class View>
67  ::VariableSymmetryImp(Space& home, int* _indices, unsigned int n)
68  : indices(home, 0, 0) {
69  // Find minimum and maximum value in _indices: the minimum is the
70  // offset, and the maximum dictates how large the bitset needs to
71  // be.
72  int maximum = _indices[0];
73  int minimum = _indices[0];
74  for (unsigned int i = 1 ; i < n ; i++) {
75  if (_indices[i] > maximum) maximum = _indices[i];
76  if (_indices[i] < minimum) minimum = _indices[i];
77  }
78  indices.resize(home, maximum-minimum+1, minimum);
79 
80  // Set the bits for the included indices.
81  for (unsigned int i = 0 ; i < n ; i++) {
82  indices.set(_indices[i]);
83  }
84  }
85 
86 
87 
88  template <class View>
89  inline
92  indices(home, other.indices) {}
93 
94  template <class View>
95  size_t
97  ::dispose(Space& home) {
98  indices.dispose(home);
99  return sizeof(*this);
100  }
101 
102  template <class View>
103  void
106  if (indices.valid(l._variable)) {
107  indices.clear(l._variable);
108  }
109  }
110 
111  template <class View>
114  ::copy(Space& home, bool share) const {
115  (void) share;
116  return new (home) VariableSymmetryImp<View>(home, *this);
117  }
118 
119 
120 
121  // The minimum value in vs is the bitset's offset, and the maximum
122  // dictates how large the bitset needs to be.
123  template <class View>
125  ::ValueSymmetryImp(Space& home, int* vs, unsigned int n)
126  : values(home, 0, 0) {
127  // Find minimum and maximum value in vs: the minimum is the
128  // offset, and the maximum dictates how large the bitset needs to
129  // be.
130  assert(n > 0);
131  int maximum = vs[0];
132  int minimum = vs[0];
133  for (unsigned int i = 1 ; i < n ; i++) {
134  if (vs[i] > maximum) maximum = vs[i];
135  if (vs[i] < minimum) minimum = vs[i];
136  }
137  values.resize(home, maximum-minimum+1, minimum);
138 
139  // Set the bits for the included values.
140  for (unsigned int i = 0 ; i < n ; i++) {
141  values.set(vs[i]);
142  }
143  }
144 
145  template <class View>
148  : values(home, other.values) { }
149 
150  template <class View>
151  size_t
154  values.dispose(home);
155  return sizeof(*this);
156  }
157 
158  template <class View>
159  void
162  if (values.valid(l._value))
163  values.clear(l._value);
164  }
165 
166  template <class View>
169  ::copy(Space& home, bool share) const {
170  (void) share;
171  return new (home) ValueSymmetryImp(home, *this);
172  }
173 
174 
175 
176  template <class View>
177  int
179  ::getVal(unsigned int sequence, unsigned int position) const {
180  return indices[sequence*seq_size + position];
181  }
182 
183  template <class View>
185  ::VariableSequenceSymmetryImp(Space& home, int* _indices, unsigned int n,
186  unsigned int seqsize)
187  : n_indices(n), seq_size(seqsize), n_seqs(n/seqsize) {
188  indices = home.alloc<unsigned int>(n_indices);
189  unsigned int max_index = _indices[0];
190  for (unsigned int i = 0 ; i < n_indices ; i++) {
191  indices[i] = _indices[i];
192  if (indices[i] > max_index)
193  max_index = indices[i];
194  }
195 
196  lookup_size = max_index+1;
197  lookup = home.alloc<int>(lookup_size);
198  for (unsigned int i = 0 ; i < lookup_size ; i++)
199  lookup[i] = -1;
200  for (unsigned int i = 0 ; i < n_indices ; i++) {
201  if (lookup[indices[i]] == -1)
202  lookup[indices[i]] = i;
203  }
204  }
205 
206  template <class View>
210  : n_indices(s.n_indices), seq_size(s.seq_size), n_seqs(s.n_seqs),
211  lookup_size(s.lookup_size) {
212  (void) share;
213  indices = home.alloc<unsigned int>(n_indices);
214  memcpy(indices, s.indices, n_indices * sizeof(int));
215  lookup = home.alloc<int>(lookup_size);
216  memcpy(lookup, s.lookup, lookup_size * sizeof(int));
217  }
218 
219  template <class View>
220  size_t
223  home.free<unsigned int>(indices, n_indices);
224  home.free<int>(lookup, lookup_size);
225  return sizeof(*this);
226  }
227 
229  template <class View>
234  if (l._variable < (int)lookup_size) {
235  int posIt = lookup[l._variable];
236  if (posIt == -1) {
237  return dynamicStackToArgArray(s);
238  }
239  unsigned int seqNum = posIt / seq_size;
240  unsigned int seqPos = posIt % seq_size;
241  for (unsigned int seq = 0 ; seq < n_seqs ; seq++) {
242  if (seq == seqNum) {
243  continue;
244  }
245  if (x[getVal(seq, seqPos)].assigned()) {
246  continue;
247  }
248  bool active = true;
249  const unsigned int *firstSeq = &indices[seqNum*seq_size];
250  const unsigned int *secondSeq = &indices[seq*seq_size];
251  for (unsigned int i = 0 ; i < seq_size ; i++) {
252  const View& xv = x[firstSeq[i]];
253  const View& yv = x[secondSeq[i]];
254  if ((!xv.assigned() && !yv.assigned())
255  || (xv.assigned() && yv.assigned() && xv.val() == yv.val())) {
256  continue;
257  } else {
258  active = false;
259  break;
260  }
261  }
262 
263  if (active) {
264  s.push(Literal(secondSeq[seqPos], l._value));
265  }
266  }
267  }
268  return dynamicStackToArgArray(s);
269  }
270 
271 
272  template <class View>
273  void
276  // Do nothing.
277  (void) l;
278  }
279 
280  template <class View>
283  ::copy(Space& home, bool share) const {
284  return new (home) VariableSequenceSymmetryImp<View>(home, share, *this);
285  }
286 
287 
288 
289  template <class View>
290  int
292  ::getVal(unsigned int sequence, unsigned int position) const {
293  return values[sequence*seq_size + position];
294  }
295 
296  template <class View>
298  ::ValueSequenceSymmetryImp(Space& home, int* _values, unsigned int n,
299  unsigned int seqsize)
300  : n_values(n), seq_size(seqsize), n_seqs(n/seqsize),
301  dead_sequences(home, n_seqs) {
302  values = home.alloc<int>(n_values);
303  for (unsigned int i = 0 ; i < n_values ; i++)
304  values[i] = _values[i];
305  }
306 
307  template <class View>
311  : n_values(vss.n_values),
312  seq_size(vss.seq_size),
313  n_seqs(vss.n_seqs),
314  dead_sequences(home, vss.dead_sequences) {
315  values = home.alloc<int>(n_values);
316  for (unsigned int i = 0 ; i < n_values ; i++)
317  values[i] = vss.values[i];
318  }
319 
320  template <class View>
321  size_t
324  home.free(values, n_values);
325  return sizeof(*this);
326  }
327 
328  template <class View>
329  void
332  unsigned int seq = 0;
333  unsigned int pos = 0;
334  for (unsigned int i = 0 ; i < n_values ; i++) {
335  if (values[i] == l._value) {
336  dead_sequences.set(seq);
337  // TODO: This can be slightly optimised.
338  while (pos < seq_size) {
339  i++;
340  pos++;
341  }
342  }
343  pos++;
344  if (pos == seq_size) {
345  pos = 0;
346  seq++;
347  }
348  }
349  }
350 
351  template <class View>
354  ::copy(Space& home, bool share) const {
355  (void) share;
356  return new (home) ValueSequenceSymmetryImp<View>(home, *this);
357  }
358 
359 }}}
360 
361 // STATISTICS: int-branch
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:222
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
A Literal is a pair of variable index and value.
Definition: ldsb.hh:50
ValueSymmetryImp(Space &home, int *vs, unsigned int n)
Constructor for creation.
Definition: sym-imp.hpp:125
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:179
VariableSymmetryImp(Space &home, int *vs, unsigned int n)
Constructor for creation.
Definition: sym-imp.hpp:67
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
Implementation of a variable sequence symmetry.
Definition: ldsb.hh:225
SymmetryImp< View > * copy(Space &home, bool share) const
Copy function.
Definition: sym-imp.hpp:354
int * lookup
Map from variable's index to its sequence and position.
Definition: ldsb.hh:244
int _value
The value of the literal. For int and bool variables, this is the value itself; for set variables...
Definition: ldsb.hh:63
int _variable
Variable index. The ViewArray that the index is meant for is assumed to be known by context...
Definition: ldsb.hh:59
Computation spaces.
Definition: core.hpp:1362
Heap heap
The single global heap.
Definition: heap.cpp:49
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2397
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntConLevel)
Post propagator for .
Definition: sequence.cpp:51
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:323
unsigned int * indices
Array of variable indices.
Definition: ldsb.hh:229
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:292
Implementation of a value symmetry.
Definition: ldsb.hh:205
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:153
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:2423
double position(const Space &home, IntVar x, int i)
Definition: ldsb.cpp:1277
void values(Home home, const IntVarArgs &x, IntSet y, IntConLevel icl=ICL_DEF)
Post constraint .
Definition: minimodel.hh:1869
Implementation of a single symmetry.
Definition: ldsb.hh:166
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:161
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
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:185
virtual ArgArray< Literal > symmetric(Literal, const ViewArray< View > &) const
Compute symmetric literals.
Definition: sym-imp.hpp:232
Stack with arbitrary number of elements.
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:105
SymmetryImp< View > * copy(Space &home, bool share) const
Copy function.
Definition: sym-imp.hpp:169
Implementation of a value sequence symmetry.
Definition: ldsb.hh:267
int entries(void) const
Return number of entries currently on stack.
void update(Literal)
Search left-branch update.
Definition: sym-imp.hpp:275
Gecode toplevel namespace
SymmetryImp< View > * copy(Space &home, bool share) const
Copy function.
Definition: sym-imp.hpp:114
ArgArray< T > dynamicStackToArgArray(const Support::DynamicStack< T, A > &s)
Convert a DynamicStack into an ArgArray
Definition: sym-imp.hpp:43
virtual size_t dispose(Space &home)
Disposal.
Definition: sym-imp.hpp:97
SymmetryImp< View > * copy(Space &home, bool share) const
Copy function.
Definition: sym-imp.hpp:283
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
void update(Literal)
Left-branch update.
Definition: sym-imp.hpp:331
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:185
int * values
Set of sequences.
Definition: ldsb.hh:271