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
00040 namespace {
00041
00042 typedef ::Gecode::TupleSet::Tuple Tuple;
00043
00047 class FullTupleCompare {
00048 int arity;
00049 public:
00050 forceinline
00051 FullTupleCompare(int a) : arity(a) {}
00052 forceinline bool
00053 operator()(const Tuple& a, const Tuple& b) {
00054 for (int i = 0; i < arity; ++i) {
00055 if (a[i] < b[i]) {
00056 return true;
00057 }
00058 if (a[i] > b[i]) {
00059 return false;
00060 }
00061 }
00062 return true;
00063 }
00064 };
00065
00072 class TuplePosCompare {
00073 int pos;
00074 public:
00075 forceinline
00076 TuplePosCompare(int p) : pos(p) {}
00077
00078 forceinline bool
00079 operator()(const Tuple& a, const Tuple& b) {
00080 if (a[pos] == b[pos]) return a < b;
00081 return a[pos] < b[pos];
00082 }
00083 };
00084
00089 class TupleKeyCompare {
00090 int pos;
00091 public:
00092 forceinline
00093 TupleKeyCompare(int p) : pos(p) {}
00094
00095 forceinline bool
00096 operator()(const Tuple& a, const Tuple& b) {
00097 return a[pos] < b[pos];
00098 }
00099
00100
00101 forceinline bool
00102 operator()(const int& a, const Tuple& b) {
00103 return a < b[pos];
00104 }
00105
00106 forceinline bool
00107 operator()(const Tuple& a, const int& b) {
00108 return a[pos] < b;
00109 }
00110 };
00111
00112 }
00113
00114
00115 std::ostream&
00116 operator<<(std::ostream& os, const Gecode::TupleSet& ts) {
00117 os << "Number of tuples: " << ts.tuples() << std::endl
00118 << "Tuples:" << std::endl;
00119 for (int i = 0; i < ts.tuples(); ++i) {
00120 os << '\t';
00121 for (int j = 0; j < ts.arity(); ++j) {
00122 os.width(3);
00123 os << " " << ts[i][j];
00124 }
00125 os << std::endl;
00126 }
00127 return os;
00128 }
00129
00130 namespace Gecode {
00131
00132 void
00133 TupleSet::TupleSetI::finalize(void) {
00134 assert(!finalized());
00135 assert(tuples == NULL);
00136
00137
00138 IntArgs ia(arity);
00139 for (int i = arity; i--; ) ia[i] = Int::Limits::max+1;
00140 int real_min = min, real_max = max;
00141 add(ia);
00142 min = real_min; max = real_max;
00143
00144
00145 domsize = max - min + 1;
00146
00147
00148 tuples = Memory::bmalloc<Tuple*>(arity);
00149 tuple_data = Memory::bmalloc<Tuple>(size*arity+1);
00150 tuple_data[size*arity] = NULL;
00151 nullptr = tuple_data+(size*arity);
00152
00153
00154 for (int i = arity; i--; )
00155 tuples[i] = tuple_data + (i * size);
00156 for (int i = size; i--; )
00157 tuples[0][i] = data + (i * arity);
00158
00159 FullTupleCompare ftc(arity);
00160 Support::quicksort(tuples[0], size, ftc);
00161 assert(tuples[0][size-1][0] == ia[0]);
00162 int* new_data = Memory::bmalloc<int>(size*arity);
00163 for (int t = size; t--; ) {
00164 for (int i = arity; i--; ) {
00165 new_data[t*arity + i] = tuples[0][t][i];
00166 }
00167 }
00168
00169 Memory::free(data);
00170 data = new_data;
00171 excess = -1;
00172
00173
00174 for (int i = arity; i--; )
00175 for (int t = size; t--; )
00176 tuples[i][t] = data + (t * arity);
00177 for (int i = arity; i-->1; ) {
00178 TuplePosCompare tpc(i);
00179 Support::quicksort(tuples[i], size, tpc);
00180 }
00181
00182
00183 last = Memory::bmalloc<Tuple*>(domsize*arity);
00184 for (int i = arity; i--; ) {
00185 Tuple* t = tuples[i];
00186 for (int d = 0; d < domsize; ++d) {
00187 while (t && *t && (*t)[i] < min+d) {
00188 ++t;
00189 }
00190 if (t && *t && (*t)[i] == min+d) {
00191 last[(i*domsize) + d] = t;
00192 ++t;
00193 } else {
00194 last[(i*domsize) + d] = nullptr;
00195 }
00196 }
00197 }
00198
00199 assert(finalized());
00200 }
00201
00202 void
00203 TupleSet::TupleSetI::resize(void) {
00204 assert(excess == 0);
00205 int ndatasize = static_cast<int>(1+size*1.5);
00206 data = Memory::brealloc<int>(data, size * arity,
00207 ndatasize * arity);
00208 excess = ndatasize - size;
00209 }
00210
00211 SharedHandle::Object*
00212 TupleSet::TupleSetI::copy(void) const {
00213 assert(finalized());
00214 TupleSetI* d = new TupleSetI;
00215 d->arity = arity;
00216 d->size = size;
00217 d->excess = excess;
00218 d->min = min;
00219 d->max = max;
00220 d->domsize = domsize;
00221
00222
00223 d->data = Memory::bmalloc<int>(size*arity);
00224 memcpy(&d->data[0], &data[0], sizeof(int)*size*arity);
00225
00226
00227 d->tuples = Memory::bmalloc<Tuple*>(arity);
00228 d->tuple_data = Memory::bmalloc<Tuple>(size*arity+1);
00229 d->tuple_data[size*arity] = NULL;
00230 d->nullptr = d->tuple_data+(size*arity);
00231
00232
00233 for (int i = arity; i--; )
00234 d->tuples[i] = d->tuple_data + (i * size);
00235 for (int a = arity; a--; ) {
00236 for (int i = size; i--; ) {
00237 d->tuples[a][i] = d->data + (tuples[a][i]-data);
00238 }
00239 }
00240
00241
00242 d->last = Memory::bmalloc<Tuple*>(domsize*arity);
00243 for (int i = domsize+arity; i--; ) {
00244 d->last[i] = d->tuple_data + (last[i]-tuple_data);
00245 }
00246
00247 return d;
00248 }
00249
00250 TupleSet::TupleSetI::~TupleSetI(void) {
00251 excess = -2;
00252 Memory::free(tuples);
00253 Memory::free(tuple_data);
00254 Memory::free(data);
00255 Memory::free(last);
00256 }
00257
00258
00259 TupleSet::TupleSet(Reflection::VarMap& vm, Reflection::Arg* arg) {
00260 if (arg->isSharedReference()) {
00261 TupleSetI* d =
00262 static_cast<TupleSetI*>(vm.getSharedObject(arg->toSharedReference()));
00263 object(d);
00264 return;
00265 }
00266
00267 Reflection::IntArrayArg* a = arg->toSharedObject()->toIntArray();
00268
00269
00270
00271 int arity = (*a)[0];
00272 int n_tuples = (a->size() - 1) / arity;
00273 assert(n_tuples*arity == a->size()-1);
00274 int pos = 1;
00275 IntArgs ia(arity);
00276 for (int i = n_tuples; i--; ) {
00277 for (int j = 0; j < arity; ++j) {
00278 ia[j] = (*a)[pos++];
00279 }
00280 add(ia);
00281 }
00282 finalize();
00283
00284 vm.putMasterObject(object());
00285 }
00286
00287 Reflection::Arg*
00288 TupleSet::spec(Reflection::VarMap& vm) const {
00289 int sharedIndex = vm.getSharedIndex(object());
00290 if (sharedIndex >= 0)
00291 return Reflection::Arg::newSharedReference(sharedIndex);
00292 Reflection::IntArrayArg* a =
00293 Reflection::Arg::newIntArray(static_cast<int>(1+arity()*tuples()));
00294
00295 (*a)[0] = arity();
00296
00297 int pos = 1;
00298 for (int i = 0; i < tuples(); ++i) {
00299 for (int j = 0; j < arity(); ++j) {
00300 (*a)[pos++] = (*this)[i][j];
00301 }
00302 }
00303
00304 vm.putMasterObject(object());
00305 return Reflection::Arg::newSharedObject(a);
00306 }
00307
00308 }
00309
00310
00311