Generated on Thu Apr 11 13:59:09 2019 for Gecode by doxygen 1.6.3

tuple-set.hpp

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  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Mikael Lagerkvist, 2007
00009  *     Christian Schulte, 2017
00010  *
00011  *  This file is part of Gecode, the generic constraint
00012  *  development environment:
00013  *     http://www.gecode.org
00014  *
00015  *  Permission is hereby granted, free of charge, to any person obtaining
00016  *  a copy of this software and associated documentation files (the
00017  *  "Software"), to deal in the Software without restriction, including
00018  *  without limitation the rights to use, copy, modify, merge, publish,
00019  *  distribute, sublicense, and/or sell copies of the Software, and to
00020  *  permit persons to whom the Software is furnished to do so, subject to
00021  *  the following conditions:
00022  *
00023  *  The above copyright notice and this permission notice shall be
00024  *  included in all copies or substantial portions of the Software.
00025  *
00026  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00027  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00028  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00029  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00030  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00031  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00032  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00033  *
00034  */
00035 
00036 #include <sstream>
00037 
00038 namespace Gecode {
00039 
00040   /*
00041    * Ranges
00042    *
00043    */
00044   forceinline unsigned int
00045   TupleSet::Range::width(void) const {
00046     return static_cast<unsigned int>(max - min + 1);
00047   }
00048 
00049   forceinline const TupleSet::BitSetData*
00050   TupleSet::Range::supports(unsigned int n_words, int n) const {
00051     assert((min <= n) && (n <= max));
00052     return s + n_words * static_cast<unsigned int>(n - min);
00053   }
00054 
00055   
00056   /*
00057    * Tuple set data
00058    *
00059    */
00060   forceinline
00061   TupleSet::Data::Data(int a) 
00062     : arity(a), n_words(0U), // To be initialized in finalize
00063       n_tuples(0), n_free(n_initial_free),
00064       min(Int::Limits::max), max(Int::Limits::min), key(0),
00065       td(heap.alloc<int>(n_initial_free * a)),
00066       vd(heap.alloc<ValueData>(a)),
00067       range(nullptr), support(nullptr) {
00068   }
00069   
00070   forceinline bool
00071   TupleSet::Data::finalized(void) const {
00072     return n_free < 0;
00073   }
00074 
00075   forceinline TupleSet::Tuple
00076   TupleSet::Data::add(void) {
00077     if (n_free == 0)
00078       resize();
00079     assert(n_free > 0);
00080     n_free--;
00081     Tuple t = td + n_tuples*arity;
00082     n_tuples++;
00083     return t;
00084   }
00085 
00086   forceinline TupleSet::Tuple
00087   TupleSet::Data::get(int i) const {
00088     assert((i >= 0) && (i < n_tuples));
00089     return td + i*arity;
00090   }
00091 
00092   forceinline unsigned int
00093   TupleSet::ValueData::start(int k) const {
00094     if (n > 1U) {
00095       unsigned int l=0U, h=n-1U;
00096       while (true) {
00097         assert(l<=h);
00098         unsigned int m = l + ((h-l) >> 1);
00099         if (k < r[m].min)
00100           h=m-1U;
00101         else if (k > r[m].max)
00102           l=m+1U;
00103         else
00104           return m;
00105       }
00106       GECODE_NEVER;
00107     } else {
00108       return 0U;
00109     }
00110   }
00111 
00112   forceinline void
00113   TupleSet::Data::set(BitSetData* d, unsigned int i) {
00114     d[i / BitSetData::bpb].set(i % BitSetData::bpb);
00115   }
00116 
00117   forceinline bool
00118   TupleSet::Data::get(const BitSetData* d, unsigned int i) {
00119     return d[i / BitSetData::bpb].get(i % BitSetData::bpb);
00120   }
00121 
00122   forceinline unsigned int
00123   TupleSet::Data::tuple2idx(Tuple t) const {
00124     return static_cast<unsigned int>((t - td) / static_cast<unsigned int>(arity));
00125   }
00126 
00127   forceinline const TupleSet::Range*
00128   TupleSet::Data::fst(int i) const {
00129     return &vd[i].r[0];
00130   }
00131   forceinline const TupleSet::Range*
00132   TupleSet::Data::lst(int i) const {
00133     return &vd[i].r[vd[i].n-1U];
00134   }
00135 
00136   
00137   /*
00138    * Tuple set
00139    *
00140    */
00141   forceinline TupleSet&
00142   TupleSet::add(const IntArgs& t) {
00143     _add(t); return *this;
00144   }
00145 
00146   forceinline
00147   TupleSet::TupleSet(void) {}
00148 
00149   forceinline
00150   TupleSet::operator bool(void) const {
00151     return object() != nullptr;
00152   }
00153 
00154   forceinline void
00155   TupleSet::finalize(void) {
00156     Data* d = static_cast<Data*>(object());
00157     if (!d->finalized())
00158       d->finalize();
00159   }
00160 
00161   forceinline bool
00162   TupleSet::finalized(void) const {
00163     return static_cast<Data*>(object())->finalized();
00164   }
00165 
00166   forceinline TupleSet::Data&
00167   TupleSet::data(void) const {
00168     assert(finalized());
00169     return *static_cast<Data*>(object());
00170   }
00171   forceinline TupleSet::Data&
00172   TupleSet::raw(void) const {
00173     return *static_cast<Data*>(object());
00174   }
00175 
00176   forceinline bool
00177   TupleSet::operator !=(const TupleSet& t) const {
00178     return !(*this == t);
00179   }
00180   forceinline int
00181   TupleSet::arity(void) const {
00182     return raw().arity;
00183   }
00184   forceinline int
00185   TupleSet::tuples(void) const {
00186     return raw().n_tuples;
00187   }
00188   forceinline unsigned int
00189   TupleSet::words(void) const {
00190     return data().n_words;
00191   }
00192   forceinline int
00193   TupleSet::min(void) const {
00194     return data().min;
00195   }
00196   forceinline int
00197   TupleSet::max(void) const {
00198     return data().max;
00199   }
00200   forceinline TupleSet::Tuple
00201   TupleSet::operator [](int i) const {
00202     return data().get(i);
00203   }
00204   forceinline const TupleSet::Range*
00205   TupleSet::fst(int i) const {
00206     return data().fst(i);
00207   }
00208   forceinline const TupleSet::Range*
00209   TupleSet::lst(int i) const {
00210     return data().lst(i);
00211   }
00212 
00213   forceinline bool
00214   TupleSet::operator ==(const TupleSet& t) const {
00215     if (tuples() != t.tuples())
00216       return false;
00217     if (arity() != t.arity())
00218       return false;
00219     if (min() != t.min())
00220       return false;
00221     if (max() != t.max())
00222       return false;
00223     return equal(t);
00224   }
00225 
00226   forceinline std::size_t
00227   TupleSet::hash(void) const {
00228     return data().key;
00229   }
00230 
00231 
00232   template<class Char, class Traits>
00233   std::basic_ostream<Char,Traits>&
00234   operator <<(std::basic_ostream<Char,Traits>& os, const TupleSet& ts) {
00235     std::basic_ostringstream<Char,Traits> s;
00236     s.copyfmt(os); s.width(0);
00237     s << "Number of tuples: " << ts.tuples() 
00238       << " (number of words: " << ts.words() << " with " 
00239       << Support::BitSetData::bpb << " bits)" << std::endl;
00240     for (int a=0; a < ts.arity(); a++) {
00241       unsigned int size = 0U;
00242       for (const TupleSet::Range* c=ts.fst(a); c<=ts.lst(a); c++)
00243         size += c->width();
00244       s << "\t[" << a << "] size: " << size
00245         << ", width: " 
00246         << static_cast<unsigned int>(ts.lst(a)->max - ts.fst(a)->min + 1)
00247         << ", ranges: "
00248         << (ts.lst(a) - ts.fst(a) + 1U)
00249         << std::endl;
00250     }
00251     return os << s.str();
00252   }
00253 
00254 
00255   /*
00256    * Range iterator
00257    *
00258    */
00259   forceinline
00260   TupleSet::Ranges::Ranges(const TupleSet& ts, int i) {
00261     c = &(ts.data().vd[i].r[0]);
00262     l = c + ts.data().vd[i].n;
00263   }
00264 
00265   forceinline bool
00266   TupleSet::Ranges::operator ()(void) const {
00267     return c<l;
00268   }
00269   forceinline void
00270   TupleSet::Ranges::operator ++(void) {
00271     c++;
00272   }
00273 
00274   forceinline int
00275   TupleSet::Ranges::min(void) const {
00276     return c->min;
00277   }
00278   forceinline int
00279   TupleSet::Ranges::max(void) const {
00280     return c->max;
00281   }
00282   forceinline unsigned int
00283   TupleSet::Ranges::width(void) const {
00284     return c->width();
00285   }
00286 
00287 }
00288 
00289 // STATISTICS: int-prop
00290