Generated on Mon Aug 25 11:35:37 2008 for Gecode by doxygen 1.5.6

tuple-set.cc

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Mikael Lagerkvist, 2007
00008  *
00009  *  Last modified:
00010  *     $Date: 2008-07-11 09:31:51 +0200 (Fri, 11 Jul 2008) $ by $Author: tack $
00011  *     $Revision: 7288 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
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   private:
00074     int pos;
00075   public:
00076     forceinline
00077     TuplePosCompare(int p) : pos(p) {}
00078 
00079     forceinline bool
00080     operator()(const Tuple& a, const Tuple& b) {
00081       if (a[pos] == b[pos]) return a < b;
00082       return a[pos] < b[pos];
00083     }
00084   };
00085 
00086 }
00087 
00088 
00089 std::ostream&
00090 operator<<(std::ostream& os, const Gecode::TupleSet& ts) {
00091   os << "Number of tuples: " << ts.tuples() << std::endl
00092      << "Tuples:" << std::endl;
00093   for (int i = 0; i < ts.tuples(); ++i) {
00094     os << '\t';
00095     for (int j = 0; j < ts.arity(); ++j) {
00096       os.width(3);
00097       os << " " << ts[i][j];
00098     }
00099     os << std::endl;
00100   }
00101   return os;
00102 }
00103 
00104 namespace Gecode {
00105 
00106   void
00107   TupleSet::TupleSetI::finalize(void) {
00108     assert(!finalized());
00109     assert(tuples == NULL);
00110 
00111     // Add final largest tuple
00112     IntArgs ia(arity);
00113     for (int i = arity; i--; ) ia[i] = Int::Limits::max+1;
00114     int real_min = min, real_max = max;
00115     add(ia);
00116     min = real_min; max = real_max;
00117 
00118     // Domainsize
00119     domsize = max - min + 1;
00120 
00121     // Allocate tuple indexing data-structures
00122     tuples = Memory::bmalloc<Tuple*>(arity);
00123     tuple_data = Memory::bmalloc<Tuple>(size*arity+1);
00124     tuple_data[size*arity] = NULL;
00125     nullptr = tuple_data+(size*arity);
00126 
00127     // Rearrange the tuples for faster comparisons.
00128     for (int i = arity; i--; )
00129       tuples[i] = tuple_data + (i * size);
00130     for (int i = size; i--; )
00131       tuples[0][i] = data + (i * arity);
00132 
00133     FullTupleCompare ftc(arity);
00134     Support::quicksort(tuples[0], size, ftc);
00135     assert(tuples[0][size-1][0] == ia[0]);
00136     int* new_data = Memory::bmalloc<int>(size*arity);
00137     for (int t = size; t--; ) {
00138       for (int i = arity; i--; ) {
00139         new_data[t*arity + i] = tuples[0][t][i];
00140       }
00141     }
00142 
00143     Memory::free(data);
00144     data = new_data;
00145     excess = -1;
00146 
00147     // Set up indexing structure
00148     for (int i = arity; i--; )
00149       for (int t = size; t--; )
00150         tuples[i][t] = data + (t * arity);
00151     for (int i = arity; i-->1; ) {      
00152       TuplePosCompare tpc(i);
00153       Support::quicksort(tuples[i], size, tpc);
00154     }
00155 
00156     // Set up initial last-structure
00157     last = Memory::bmalloc<Tuple*>(domsize*arity);
00158     for (int i = arity; i--; ) {
00159       Tuple* t = tuples[i];
00160       for (int d = 0; d < domsize; ++d) {
00161         while (t && *t && (*t)[i] < min+d) {
00162           ++t;
00163         }
00164         if (t && *t && (*t)[i] == min+d) {
00165           last[(i*domsize) + d] = t;
00166           ++t;
00167         } else {
00168           last[(i*domsize) + d] = nullptr;
00169         }
00170       }
00171     }
00172     
00173     assert(finalized());
00174   }
00175 
00176   void
00177   TupleSet::TupleSetI::resize(void) {
00178     assert(excess == 0);
00179     int ndatasize = static_cast<int>(1+size*1.5);
00180     data = Memory::brealloc<int>(data, size * arity, 
00181                                  ndatasize * arity);
00182     excess = ndatasize - size;
00183   }
00184 
00185   SharedHandle::Object*
00186   TupleSet::TupleSetI::copy(void) const {
00187     assert(finalized());
00188     TupleSetI* d  = new TupleSetI;
00189     d->arity      = arity;
00190     d->size       = size;
00191     d->excess     = excess;
00192     d->min        = min;
00193     d->max        = max;
00194     d->domsize    = domsize;
00195 
00196     // Table data
00197     d->data = Memory::bmalloc<int>(size*arity);
00198     memcpy(&d->data[0], &data[0], sizeof(int)*size*arity);
00199 
00200     // Indexing data
00201     d->tuples = Memory::bmalloc<Tuple*>(arity);
00202     d->tuple_data = Memory::bmalloc<Tuple>(size*arity+1);
00203     d->tuple_data[size*arity] = NULL;
00204     d->nullptr = d->tuple_data+(size*arity);
00205 
00206     // Rearrange the tuples for faster comparisons.
00207     for (int i = arity; i--; )
00208       d->tuples[i] = d->tuple_data + (i * size);
00209     for (int a = arity; a--; ) {
00210       for (int i = size; i--; ) {
00211         d->tuples[a][i] = d->data + (tuples[a][i]-data);
00212       }
00213     }
00214 
00215     // Last data
00216     d->last = Memory::bmalloc<Tuple*>(domsize*arity);
00217     for (int i = domsize+arity; i--; ) {
00218       d->last[i] = d->tuple_data + (last[i]-tuple_data);
00219     }
00220 
00221     return d;
00222   }
00223 
00224   TupleSet::TupleSetI::~TupleSetI(void) {
00225     excess = -2;
00226     Memory::free(tuples);
00227     Memory::free(tuple_data);
00228     Memory::free(data);
00229     Memory::free(last);
00230   }  
00231 
00232 
00233   TupleSet::TupleSet(Reflection::VarMap& vm, Reflection::Arg* arg) {
00234     if (arg->isSharedReference()) {
00235       TupleSetI* d = 
00236         static_cast<TupleSetI*>(vm.getSharedObject(arg->toSharedReference()));
00237       object(d);
00238       return;
00239     }
00240     
00241     Reflection::IntArrayArg* a = arg->toSharedObject()->toIntArray();
00242 
00243     // All done... Construct the table
00244 
00245     int arity = (*a)[0];
00246     int n_tuples = (a->size() - 1) / arity;
00247     assert(n_tuples*arity == a->size()-1);
00248     int pos = 1;
00249     IntArgs ia(arity);
00250     for (int i = n_tuples; i--; ) {
00251       for (int j = 0; j < arity; ++j) {
00252         ia[j] = (*a)[pos++];
00253       }
00254       add(ia);
00255     }
00256     finalize();
00257 
00258     vm.putMasterObject(object());
00259   }
00260 
00261   Reflection::Arg*
00262   TupleSet::spec(Reflection::VarMap& vm) const {
00263     int sharedIndex = vm.getSharedIndex(object());
00264     if (sharedIndex >= 0)
00265       return Reflection::Arg::newSharedReference(sharedIndex);
00266     Reflection::IntArrayArg* a = 
00267       Reflection::Arg::newIntArray(static_cast<int>(1+arity()*tuples()));
00268 
00269     (*a)[0] = arity();
00270 
00271     int pos = 1;
00272     for (int i = 0; i < tuples(); ++i) {
00273       for (int j = 0; j < arity(); ++j) {
00274         (*a)[pos++] = (*this)[i][j];
00275       }
00276     }
00277 
00278     vm.putMasterObject(object());
00279     return Reflection::Arg::newSharedObject(a);    
00280   }
00281 
00282 }
00283 
00284 // STATISTICS: int-prop
00285