Generated on Sat Feb 7 2015 02:01:23 for Gecode by doxygen 1.8.9.1
tuple-set.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Mikael Lagerkvist <lagerkvist@gecode.org>
5  *
6  * Copyright:
7  * Mikael Lagerkvist, 2007
8  *
9  * Last modified:
10  * $Date: 2010-07-14 17:46:18 +0200 (Wed, 14 Jul 2010) $ by $Author: schulte $
11  * $Revision: 11192 $
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 #include <gecode/int.hh>
39 
40 namespace {
41 
43 
47  class FullTupleCompare {
48  private:
50  int arity;
51  public:
54  FullTupleCompare(int a) : arity(a) {}
56  forceinline bool
57  operator ()(const Tuple& a, const Tuple& b) {
58  for (int i = 0; i < arity; i++)
59  if (a[i] < b[i])
60  return true;
61  else if (a[i] > b[i])
62  return false;
63  return a < b;
64  }
65  };
66 
73  class TuplePosCompare {
74  private:
76  int pos;
77  public:
80  TuplePosCompare(int p) : pos(p) {}
82  forceinline bool
83  operator ()(const Tuple& a, const Tuple& b) {
84  if (a[pos] == b[pos])
85  return a < b;
86  else
87  return a[pos] < b[pos];
88  }
89  };
90 
91 }
92 
93 namespace Gecode {
94 
95  void
97  assert(!finalized());
98  assert(tuples == NULL);
99 
100  // Add final largest tuple
101  IntArgs ia(arity);
102  for (int i = arity; i--; )
103  ia[i] = Int::Limits::max+1;
104  int real_min = min, real_max = max;
105  add(ia);
106  min = real_min; max = real_max;
107 
108  // Domainsize
109  domsize = static_cast<unsigned int>(max - min) + 1;
110 
111  // Allocate tuple indexing data-structures
112  tuples = heap.alloc<Tuple*>(arity);
113  tuple_data = heap.alloc<Tuple>(size*arity+1);
114  tuple_data[size*arity] = NULL;
115  nullpointer = tuple_data+(size*arity);
116 
117  // Rearrange the tuples for faster comparisons.
118  for (int i = arity; i--; )
119  tuples[i] = tuple_data + (i * size);
120  for (int i = size; i--; )
121  tuples[0][i] = data + (i * arity);
122 
123  FullTupleCompare ftc(arity);
124  Support::quicksort(tuples[0], size, ftc);
125  assert(tuples[0][size-1][0] == ia[0]);
126  int* new_data = heap.alloc<int>(size*arity);
127  for (int t = size; t--; )
128  for (int i = arity; i--; )
129  new_data[t*arity + i] = tuples[0][t][i];
130 
131  heap.rfree(data);
132  data = new_data;
133  excess = -1;
134 
135  // Set up indexing structure
136  for (int i = arity; i--; )
137  for (int t = size; t--; )
138  tuples[i][t] = data + (t * arity);
139  for (int i = arity; i-->1; ) {
140  TuplePosCompare tpc(i);
141  Support::quicksort(tuples[i], size, tpc);
142  }
143 
144  // Set up initial last-structure
145  last = heap.alloc<Tuple*>(domsize*arity);
146  for (int i = arity; i--; ) {
147  Tuple* t = tuples[i];
148  for (unsigned int d = 0; d < domsize; ++d) {
149  while (t && *t && (*t)[i] < static_cast<int>(min+d)) {
150  ++t;
151  }
152  if (t && *t && (*t)[i] == static_cast<int>(min+d)) {
153  last[(i*domsize) + d] = t;
154  ++t;
155  } else {
156  last[(i*domsize) + d] = nullpointer;
157  }
158  }
159  }
160 
161  assert(finalized());
162  }
163 
164  void
166  assert(excess == 0);
167  int ndatasize = static_cast<int>(1+size*1.5);
168  data = heap.realloc<int>(data, size * arity, ndatasize * arity);
169  excess = ndatasize - size;
170  }
171 
174  assert(finalized());
175  TupleSetI* d = new TupleSetI;
176  d->arity = arity;
177  d->size = size;
178  d->excess = excess;
179  d->min = min;
180  d->max = max;
181  d->domsize = domsize;
182 
183  // Table data
184  d->data = heap.alloc<int>(size*arity);
185  heap.copy(&d->data[0], &data[0], size*arity);
186 
187  // Indexing data
188  d->tuples = heap.alloc<Tuple*>(arity);
189  d->tuple_data = heap.alloc<Tuple>(size*arity+1);
190  d->tuple_data[size*arity] = NULL;
191  d->nullpointer = d->tuple_data+(size*arity);
192 
193  // Rearrange the tuples for faster comparisons.
194  for (int i = arity; i--; )
195  d->tuples[i] = d->tuple_data + (i * size);
196  for (int a = arity; a--; ) {
197  for (int i = size; i--; ) {
198  d->tuples[a][i] = d->data + (tuples[a][i]-data);
199  }
200  }
201 
202  // Last data
203  d->last = heap.alloc<Tuple*>(domsize*arity);
204  for (int i = static_cast<int>(domsize)*arity; i--; ) {
205  d->last[i] = d->tuple_data + (last[i]-tuple_data);
206  }
207 
208  return d;
209  }
210 
212  excess = -2;
213  heap.rfree(tuples);
214  heap.rfree(tuple_data);
215  heap.rfree(data);
216  heap.rfree(last);
217  }
218 
219 }
220 
221 // STATISTICS: int-prop
222 
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition: heap.hpp:552
NodeType t
Type of node.
Definition: bool-expr.cpp:234
int min(void) const
Minimum domain element.
Definition: tuple-set.hpp:155
void rfree(void *p)
Free memory block starting at p.
Definition: heap.hpp:355
int arity(void) const
Arity of tuple set.
Definition: tuple-set.hpp:134
int excess
Excess storage.
Definition: int.hh:2048
bool pos(const View &x)
Test whether x is postive.
Definition: mult.hpp:45
void resize(void)
Resize data cache.
Definition: tuple-set.cpp:165
const int max
Largest allowed integer value.
Definition: int.hh:113
int tuples(void) const
Number of tuples.
Definition: tuple-set.hpp:141
Heap heap
The single global heap.
Definition: heap.cpp:49
Gecode::IntSet d(v, 7)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition: heap.hpp:400
Gecode::IntArgs i(4, 1, 2, 3, 4)
TupleSet::Tuple Tuple
Definition: extensional.hh:227
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:134
Tuple ** last
Initial last structure.
Definition: int.hh:2054
unsigned int size(I &i)
Size of all ranges of range iterator i.
virtual SharedHandle::Object * copy(void) const
Create a copy.
Definition: tuple-set.cpp:173
unsigned int domsize
Domain size.
Definition: int.hh:2052
Tuple ** tuples
Tuples index.
Definition: int.hh:2042
int min
Minimum and maximum in domain-values.
Definition: int.hh:2050
Tuple * nullpointer
Pointer to NULL-pointer.
Definition: int.hh:2056
Data stored for a Table.
Definition: int.hh:2034
bool finalized(void) const
Is datastructure finalized.
Definition: tuple-set.hpp:43
int * data
Tuples data.
Definition: int.hh:2046
Passing integer arguments.
Definition: int.hh:607
Tuple * tuple_data
Tuple index data.
Definition: int.hh:2044
int max(void) const
Maximum domain element.
Definition: tuple-set.hpp:162
bool finalized(void) const
Is tuple set finalized.
Definition: tuple-set.hpp:127
void add(T t)
Add Tuple. Assumes that arity matches.
Definition: tuple-set.hpp:67
void finalize(void)
Finalize datastructure (disallows additions of more Tuples)
Definition: tuple-set.cpp:96
#define forceinline
Definition: config.hpp:132
The shared object.
Definition: core.hpp:88
virtual ~TupleSetI(void)
Delete implementation.
Definition: tuple-set.cpp:211
T * realloc(T *b, long unsigned int n, long unsigned int m)
Reallocate block of n objects starting at b to m objects of type T from heap.
Definition: heap.hpp:451
int size
Number of Tuples.
Definition: int.hh:2040
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.