this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Mikael Lagerkvist <lagerkvist@gecode.org>
5 * Christian Schulte <schulte@gecode.org>
6 *
7 * Copyright:
8 * Mikael Lagerkvist, 2007
9 * Christian Schulte, 2017
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#include <sstream>
37
38namespace Gecode {
39
40 /*
41 * Ranges
42 *
43 */
44 forceinline unsigned int
45 TupleSet::Range::width(void) const {
46 return static_cast<unsigned int>(max - min + 1);
47 }
48
49 forceinline const TupleSet::BitSetData*
50 TupleSet::Range::supports(unsigned int n_words, int n) const {
51 assert((min <= n) && (n <= max));
52 return s + n_words * static_cast<unsigned int>(n - min);
53 }
54
55
56 /*
57 * Tuple set data
58 *
59 */
60 forceinline
61 TupleSet::Data::Data(int a)
62 : arity(a), n_words(0U), // To be initialized in finalize
63 n_tuples(0), n_free(n_initial_free),
64 min(Int::Limits::max), max(Int::Limits::min), key(0),
65 td(heap.alloc<int>(n_initial_free * a)),
66 vd(heap.alloc<ValueData>(a)),
67 range(nullptr), support(nullptr) {
68 }
69
70 forceinline bool
71 TupleSet::Data::finalized(void) const {
72 return n_free < 0;
73 }
74
75 forceinline TupleSet::Tuple
76 TupleSet::Data::add(void) {
77 if (n_free == 0)
78 resize();
79 assert(n_free > 0);
80 n_free--;
81 Tuple t = td + n_tuples*arity;
82 n_tuples++;
83 return t;
84 }
85
86 forceinline TupleSet::Tuple
87 TupleSet::Data::get(int i) const {
88 assert((i >= 0) && (i < n_tuples));
89 return td + i*arity;
90 }
91
92 forceinline unsigned int
93 TupleSet::ValueData::start(int k) const {
94 if (n > 1U) {
95 unsigned int l=0U, h=n-1U;
96 while (true) {
97 assert(l<=h);
98 unsigned int m = l + ((h-l) >> 1);
99 if (k < r[m].min)
100 h=m-1U;
101 else if (k > r[m].max)
102 l=m+1U;
103 else
104 return m;
105 }
106 GECODE_NEVER;
107 } else {
108 return 0U;
109 }
110 }
111
112 forceinline void
113 TupleSet::Data::set(BitSetData* d, unsigned int i) {
114 d[i / BitSetData::bpb].set(i % BitSetData::bpb);
115 }
116
117 forceinline bool
118 TupleSet::Data::get(const BitSetData* d, unsigned int i) {
119 return d[i / BitSetData::bpb].get(i % BitSetData::bpb);
120 }
121
122 forceinline unsigned int
123 TupleSet::Data::tuple2idx(Tuple t) const {
124 return static_cast<unsigned int>((t - td) / static_cast<unsigned int>(arity));
125 }
126
127 forceinline const TupleSet::Range*
128 TupleSet::Data::fst(int i) const {
129 return &vd[i].r[0];
130 }
131 forceinline const TupleSet::Range*
132 TupleSet::Data::lst(int i) const {
133 return &vd[i].r[vd[i].n-1U];
134 }
135
136
137 /*
138 * Tuple set
139 *
140 */
141 forceinline TupleSet&
142 TupleSet::add(const IntArgs& t) {
143 _add(t); return *this;
144 }
145
146 forceinline
147 TupleSet::TupleSet(void) {}
148
149 forceinline
150 TupleSet::operator bool(void) const {
151 return object() != nullptr;
152 }
153
154 forceinline void
155 TupleSet::finalize(void) {
156 Data* d = static_cast<Data*>(object());
157 if (!d->finalized())
158 d->finalize();
159 }
160
161 forceinline bool
162 TupleSet::finalized(void) const {
163 return static_cast<Data*>(object())->finalized();
164 }
165
166 forceinline TupleSet::Data&
167 TupleSet::data(void) const {
168 assert(finalized());
169 return *static_cast<Data*>(object());
170 }
171 forceinline TupleSet::Data&
172 TupleSet::raw(void) const {
173 return *static_cast<Data*>(object());
174 }
175
176 forceinline bool
177 TupleSet::operator !=(const TupleSet& t) const {
178 return !(*this == t);
179 }
180 forceinline int
181 TupleSet::arity(void) const {
182 return raw().arity;
183 }
184 forceinline int
185 TupleSet::tuples(void) const {
186 return raw().n_tuples;
187 }
188 forceinline unsigned int
189 TupleSet::words(void) const {
190 return data().n_words;
191 }
192 forceinline int
193 TupleSet::min(void) const {
194 return data().min;
195 }
196 forceinline int
197 TupleSet::max(void) const {
198 return data().max;
199 }
200 forceinline TupleSet::Tuple
201 TupleSet::operator [](int i) const {
202 return data().get(i);
203 }
204 forceinline const TupleSet::Range*
205 TupleSet::fst(int i) const {
206 return data().fst(i);
207 }
208 forceinline const TupleSet::Range*
209 TupleSet::lst(int i) const {
210 return data().lst(i);
211 }
212
213 forceinline bool
214 TupleSet::operator ==(const TupleSet& t) const {
215 if (tuples() != t.tuples())
216 return false;
217 if (arity() != t.arity())
218 return false;
219 if (min() != t.min())
220 return false;
221 if (max() != t.max())
222 return false;
223 return equal(t);
224 }
225
226 forceinline std::size_t
227 TupleSet::hash(void) const {
228 return data().key;
229 }
230
231
232 template<class Char, class Traits>
233 std::basic_ostream<Char,Traits>&
234 operator <<(std::basic_ostream<Char,Traits>& os, const TupleSet& ts) {
235 std::basic_ostringstream<Char,Traits> s;
236 s.copyfmt(os); s.width(0);
237 s << "Number of tuples: " << ts.tuples()
238 << " (number of words: " << ts.words() << " with "
239 << Support::BitSetData::bpb << " bits)" << std::endl;
240 for (int a=0; a < ts.arity(); a++) {
241 unsigned int size = 0U;
242 for (const TupleSet::Range* c=ts.fst(a); c<=ts.lst(a); c++)
243 size += c->width();
244 s << "\t[" << a << "] size: " << size
245 << ", width: "
246 << static_cast<unsigned int>(ts.lst(a)->max - ts.fst(a)->min + 1)
247 << ", ranges: "
248 << (ts.lst(a) - ts.fst(a) + 1U)
249 << std::endl;
250 }
251 return os << s.str();
252 }
253
254
255 /*
256 * Range iterator
257 *
258 */
259 forceinline
260 TupleSet::Ranges::Ranges(const TupleSet& ts, int i) {
261 c = &(ts.data().vd[i].r[0]);
262 l = c + ts.data().vd[i].n;
263 }
264
265 forceinline bool
266 TupleSet::Ranges::operator ()(void) const {
267 return c<l;
268 }
269 forceinline void
270 TupleSet::Ranges::operator ++(void) {
271 c++;
272 }
273
274 forceinline int
275 TupleSet::Ranges::min(void) const {
276 return c->min;
277 }
278 forceinline int
279 TupleSet::Ranges::max(void) const {
280 return c->max;
281 }
282 forceinline unsigned int
283 TupleSet::Ranges::width(void) const {
284 return c->width();
285 }
286
287}
288
289// STATISTICS: int-prop
290