tuple-set.cpp
Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/int.hh>
00039 #include <algorithm>
00040
00041 namespace Gecode { namespace Int { namespace Extensional {
00042
00044 typedef ::Gecode::TupleSet::Tuple Tuple;
00045
00047 class TupleCompare {
00048 private:
00050 int arity;
00051 public:
00053 TupleCompare(int a);
00055 bool operator ()(const Tuple& a, const Tuple& b);
00056 };
00057
00059 class PosCompare {
00060 private:
00062 int p;
00063 public:
00065 PosCompare(int p);
00067 bool operator ()(const Tuple& a, const Tuple& b);
00068 };
00069
00070
00071 forceinline
00072 TupleCompare::TupleCompare(int a) : arity(a) {}
00073
00074 forceinline bool
00075 TupleCompare::operator ()(const Tuple& a, const Tuple& b) {
00076 for (int i = 0; i < arity; i++)
00077 if (a[i] < b[i])
00078 return true;
00079 else if (a[i] > b[i])
00080 return false;
00081 return false;
00082 }
00083
00084
00085 forceinline
00086 PosCompare::PosCompare(int p0) : p(p0) {}
00087
00088 forceinline bool
00089 PosCompare::operator ()(const Tuple& a, const Tuple& b) {
00090 return a[p] < b[p];
00091 }
00092
00093
00094 }}}
00095
00096 namespace Gecode {
00097
00098
00099
00100
00101
00102 void
00103 TupleSet::Data::finalize(void) {
00104 using namespace Int::Extensional;
00105 assert(!finalized());
00106
00107 n_free = -1;
00108
00109
00110 if (n_tuples == 0) {
00111 delete td; td=nullptr;
00112 return;
00113 }
00114
00115
00116 Region r;
00117
00118 Tuple* tuple = r.alloc<Tuple>(n_tuples);
00119 {
00120 for (int t=n_tuples; t--; )
00121 tuple[t] = td + t*arity;
00122 TupleCompare tc(arity);
00123 Support::quicksort(tuple, n_tuples, tc);
00124
00125 int j=1;
00126 for (int t=1; t<n_tuples; t++) {
00127 for (int a=arity; a--; )
00128 if (tuple[t-1][a] != tuple[t][a])
00129 goto notsame;
00130 goto same;
00131 notsame: ;
00132 tuple[j++] = tuple[t];
00133 same: ;
00134 }
00135 assert(j <= n_tuples);
00136 n_tuples=j;
00137
00138 key = static_cast<std::size_t>(n_tuples);
00139 cmb_hash(key, arity);
00140
00141 int* new_td = heap.alloc<int>(n_tuples*arity);
00142 for (int t=n_tuples; t--; ) {
00143 for (int a=arity; a--; ) {
00144 new_td[t*arity+a] = tuple[t][a];
00145 cmb_hash(key,tuple[t][a]);
00146 }
00147 tuple[t] = new_td + t*arity;
00148 }
00149 heap.rfree(td);
00150 td = new_td;
00151 }
00152
00153
00154 n_words = BitSetData::data(n_tuples);
00155
00156
00157 {
00158
00159
00160
00161
00162 unsigned int n_vals = 0U;
00163
00164 unsigned int n_ranges = 0U;
00165 for (int a=arity; a--; ) {
00166
00167 PosCompare pc(a);
00168 Support::quicksort(tuple, n_tuples, pc);
00169
00170 {
00171 int max=tuple[0][a];
00172 n_vals++; n_ranges++;
00173 for (int i=1; i<n_tuples; i++) {
00174 assert(tuple[i-1][a] <= tuple[i][a]);
00175 if (max+1 == tuple[i][a]) {
00176 n_vals++;
00177 max=tuple[i][a];
00178 } else if (max+1 < tuple[i][a]) {
00179 n_vals++; n_ranges++;
00180 max=tuple[i][a];
00181 } else {
00182 assert(max == tuple[i][a]);
00183 }
00184 }
00185 }
00186 }
00187
00188
00189
00190
00191 Range* cr = range = heap.alloc<Range>(n_ranges);
00192
00193 BitSetData* cs = support = heap.alloc<BitSetData>(n_words * n_vals);
00194 for (unsigned int i=n_vals * n_words; i--; )
00195 cs[i].init();
00196 for (int a=arity; a--; ) {
00197
00198 vd[a].r = cr;
00199
00200 PosCompare pc(a);
00201 Support::quicksort(tuple, n_tuples, pc);
00202
00203 min = std::min(min,tuple[0][a]);
00204 max = std::max(max,tuple[n_tuples-1][a]);
00205
00206 {
00207 unsigned int j=0U;
00208 vd[a].r[0].max=vd[a].r[0].min=tuple[0][a];
00209 for (int i=1; i<n_tuples; i++) {
00210 assert(tuple[i-1][a] <= tuple[i][a]);
00211 if (vd[a].r[j].max+1 == tuple[i][a]) {
00212 vd[a].r[j].max=tuple[i][a];
00213 } else if (vd[a].r[j].max+1 < tuple[i][a]) {
00214 j++; vd[a].r[j].min=vd[a].r[j].max=tuple[i][a];
00215 } else {
00216 assert(vd[a].r[j].max == tuple[i][a]);
00217 }
00218 }
00219 vd[a].n = j+1U;
00220 cr += j+1U;
00221 }
00222
00223 for (unsigned int i=0U; i<vd[a].n; i++) {
00224 vd[a].r[i].s = cs;
00225 cs += n_words * vd[a].r[i].width();
00226 }
00227 {
00228 int j=0;
00229 for (int i=0; i<n_tuples; i++) {
00230 while (tuple[i][a] > vd[a].r[j].max)
00231 j++;
00232 set(const_cast<BitSetData*>
00233 (vd[a].r[j].supports(n_words,tuple[i][a])),
00234 tuple2idx(tuple[i]));
00235 }
00236 }
00237 }
00238 assert(cs == support + n_words * n_vals);
00239 assert(cr == range + n_ranges);
00240 }
00241 if ((min < Int::Limits::min) || (max > Int::Limits::max))
00242 throw Int::OutOfLimits("TupleSet::finalize()");
00243 assert(finalized());
00244 }
00245
00246 void
00247 TupleSet::Data::resize(void) {
00248 assert(n_free == 0);
00249 int n = static_cast<int>(1+n_tuples*1.5);
00250 td = heap.realloc<int>(td, n_tuples * arity, n * arity);
00251 n_free = n - n_tuples;
00252 }
00253
00254 TupleSet::Data::~Data(void) {
00255 heap.rfree(td);
00256 heap.rfree(vd);
00257 heap.rfree(range);
00258 heap.rfree(support);
00259 }
00260
00261
00262
00263
00264
00265
00266 TupleSet::TupleSet(int a)
00267 : SharedHandle(new Data(a)) {}
00268 void
00269 TupleSet::init(int a) {
00270 object(new Data(a));
00271 }
00272 TupleSet::TupleSet(const TupleSet& ts)
00273 : SharedHandle(ts) {}
00274 TupleSet&
00275 TupleSet::operator =(const TupleSet& ts) {
00276 (void) SharedHandle::operator =(ts);
00277 return *this;
00278 }
00279
00280 TupleSet::TupleSet(int a, const Gecode::DFA& dfa) {
00282 struct Edge {
00283 unsigned int i_state;
00284 unsigned int o_state;
00285 };
00287 struct State {
00288 unsigned int i_deg;
00289 unsigned int o_deg;
00290 unsigned int n_tuples;
00291 int* tuples;
00292 };
00294 struct Support {
00295 int val;
00296 unsigned int n_edges;
00297 Edge* edges;
00298 };
00300 struct Layer {
00301 State* states;
00302 Support* supports;
00303 unsigned int n_supports;
00304 };
00305
00306 object(new Data(a));
00307
00308 Region r;
00309
00310 int max_states = dfa.n_states();
00311
00312 Layer* layers = r.alloc<Layer>(a+1);
00313 State* states = r.alloc<State>(max_states*(a+1));
00314
00315 for (int i=max_states*(a+1); i--; ) {
00316 states[i].i_deg = 0U; states[i].o_deg = 0U;
00317 states[i].n_tuples = 0U;
00318 states[i].tuples = nullptr;
00319 }
00320 for (int i=a+1; i--; ) {
00321 layers[i].states = states + i*max_states;
00322 layers[i].n_supports = 0U;
00323 }
00324
00325
00326 layers[0].states[0].i_deg = 1U;
00327 layers[0].states[0].n_tuples = 1U;
00328 layers[0].states[0].tuples = r.alloc<int>(1U);
00329 assert(layers[0].states[0].tuples != nullptr);
00330
00331
00332 Edge* edges = r.alloc<Edge>(dfa.max_degree());
00333 Support* supports = r.alloc<Support>(dfa.n_symbols());
00334
00335
00336 for (int i=0; i<a; i++) {
00337 unsigned int n_supports=0;
00338 for (DFA::Symbols s(dfa); s(); ++s) {
00339 unsigned int n_edges=0;
00340 for (DFA::Transitions t(dfa,s.val()); t(); ++t) {
00341 if (layers[i].states[t.i_state()].i_deg != 0) {
00342
00343 edges[n_edges].i_state = t.i_state();
00344 edges[n_edges].o_state = t.o_state();
00345 n_edges++;
00346
00347 layers[i].states[t.i_state()].o_deg++;
00348 layers[i+1].states[t.o_state()].i_deg++;
00349
00350 layers[i+1].states[t.o_state()].n_tuples
00351 += layers[i].states[t.i_state()].n_tuples;
00352 }
00353 assert(n_edges <= dfa.max_degree());
00354 }
00355
00356 if (n_edges > 0U) {
00357 Support& support = supports[n_supports++];
00358 support.val = s.val();
00359 support.n_edges = n_edges;
00360 support.edges = Heap::copy(r.alloc<Edge>(n_edges),edges,n_edges);
00361 }
00362 }
00363
00364 if (n_supports > 0U) {
00365 layers[i].supports =
00366 Heap::copy(r.alloc<Support>(n_supports),supports,n_supports);
00367 layers[i].n_supports = n_supports;
00368 } else {
00369 finalize();
00370 return;
00371 }
00372 }
00373
00374
00375 for (int s = dfa.final_fst(); s < dfa.final_lst(); s++) {
00376 if (layers[a].states[s].i_deg != 0U)
00377 layers[a].states[s].o_deg = 1U;
00378 }
00379
00380
00381 for (int i=a; i--; ) {
00382 for (unsigned int j = layers[i].n_supports; j--; ) {
00383 Support& s = layers[i].supports[j];
00384 for (unsigned int k = s.n_edges; k--; ) {
00385 unsigned int i_state = s.edges[k].i_state;
00386 unsigned int o_state = s.edges[k].o_state;
00387
00388 if (layers[i+1].states[o_state].o_deg == 0U) {
00389
00390 --layers[i+1].states[o_state].i_deg;
00391 --layers[i].states[i_state].o_deg;
00392
00393 assert(s.n_edges > 0U);
00394 s.edges[k] = s.edges[--s.n_edges];
00395 }
00396 }
00397
00398 if (s.n_edges == 0U)
00399 layers[i].supports[j] = layers[i].supports[--layers[i].n_supports];
00400 }
00401 if (layers[i].n_supports == 0U) {
00402 finalize();
00403 return;
00404 }
00405 }
00406
00407
00408 for (int i=0; i<a; i++) {
00409 for (unsigned int j = layers[i].n_supports; j--; ) {
00410 Support& s = layers[i].supports[j];
00411 for (unsigned int k = s.n_edges; k--; ) {
00412 unsigned int i_state = s.edges[k].i_state;
00413 unsigned int o_state = s.edges[k].o_state;
00414
00415 if (layers[i+1].states[o_state].tuples == nullptr) {
00416 unsigned int n_tuples = layers[i+1].states[o_state].n_tuples;
00417 layers[i+1].states[o_state].tuples = r.alloc<int>((i+1)*n_tuples);
00418 layers[i+1].states[o_state].n_tuples = 0;
00419 }
00420 unsigned int n = layers[i+1].states[o_state].n_tuples;
00421
00422 for (unsigned int t=0; t < layers[i].states[i_state].n_tuples; t++) {
00423
00424 Heap::copy(&layers[i+1].states[o_state].tuples[n*(i+1)+t*(i+1)],
00425 &layers[i].states[i_state].tuples[t*i], i);
00426
00427 layers[i+1].states[o_state].tuples[n*(i+1)+t*(i+1)+i] = s.val;
00428 }
00429 layers[i+1].states[o_state].n_tuples
00430 += layers[i].states[i_state].n_tuples;
00431 }
00432 }
00433 }
00434
00435
00436 for (int s = dfa.final_fst(); s < dfa.final_lst(); s++) {
00437 for (unsigned int i=0; i<layers[a].states[s].n_tuples; i++) {
00438 int* tuple = &layers[a].states[s].tuples[i*a];
00439 add(IntArgs(a,tuple));
00440 }
00441 }
00442
00443 finalize();
00444 }
00445
00446 bool
00447 TupleSet::equal(const TupleSet& t) const {
00448 assert(tuples() == t.tuples());
00449 assert(arity() == t.arity());
00450 assert(min() == t.min());
00451 assert(max() == t.max());
00452 for (int i=tuples(); i--; )
00453 for (int j=arity(); j--; )
00454 if ((*this)[i][j] != t[i][j])
00455 return false;
00456 return true;
00457 }
00458
00459 void
00460 TupleSet::_add(const IntArgs& t) {
00461 if (!*this)
00462 throw Int::UninitializedTupleSet("TupleSet::add()");
00463 if (raw().finalized())
00464 throw Int::AlreadyFinalized("TupleSet::add()");
00465 if (t.size() != raw().arity)
00466 throw Int::ArgumentSizeMismatch("TupleSet::add()");
00467 Tuple a = raw().add();
00468 for (int i=t.size(); i--; )
00469 a[i]=t[i];
00470 }
00471
00472 TupleSet&
00473 TupleSet::add(int n, ...) {
00474 if (!*this)
00475 throw Int::UninitializedTupleSet("TupleSet::add()");
00476 if (raw().finalized())
00477 throw Int::AlreadyFinalized("TupleSet::add()");
00478 Tuple t = raw().add();
00479 va_list args;
00480 va_start(args, n);
00481 t[0]=n;
00482 for (int i=1; i<raw().arity; i++)
00483 t[i] = va_arg(args,int);
00484 va_end(args);
00485 return *this;
00486 }
00487
00488 }
00489
00490
00491