Generated on Fri Oct 19 11:25:05 2018 for Gecode by doxygen 1.6.3

tuple-set.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Linnea Ingmar <linnea.ingmar@hotmail.com>
00005  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00006  *     Christian Schulte <schulte@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Linnea Ingmar, 2017
00010  *     Mikael Lagerkvist, 2007
00011  *     Christian Schulte, 2017
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 #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    * Tuple set data
00100    *
00101    */
00102   void
00103   TupleSet::Data::finalize(void) {
00104     using namespace Int::Extensional;
00105     assert(!finalized());
00106     // Mark as finalized
00107     n_free = -1;
00108 
00109     // Initialization
00110     if (n_tuples == 0) {
00111       delete td; td=nullptr;
00112       return;
00113     }
00114 
00115     // Compact and copy data
00116     Region r;
00117     // Set up tuple pointers
00118     Tuple* tuple = r.alloc<Tuple>(n_tuples);
00119     {
00120       for (int t=0; t<n_tuples; t++)
00121         tuple[t] = td + t*arity;
00122       TupleCompare tc(arity);
00123       Support::quicksort(tuple, n_tuples, tc);
00124       // Remove duplicates
00125       int j=1;
00126       for (int t=1; t<n_tuples; t++) {
00127         for (int a=0; 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       // Initialize hash key
00138       key = static_cast<std::size_t>(n_tuples);
00139       cmb_hash(key, arity);
00140       // Copy into now possibly smaller area
00141       int* new_td = heap.alloc<int>(n_tuples*arity);
00142       for (int t=0; t<n_tuples; t++) {
00143         for (int a=0; 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     // Only now compute how many tuples are needed!
00154     n_words = BitSetData::data(n_tuples);
00155 
00156     // Compute range information
00157     {
00158       /*
00159        * Pass one: compute how many values and ranges are needed
00160        */
00161       // How many values
00162       unsigned int n_vals = 0U;
00163       // How many ranges
00164       unsigned int n_ranges = 0U;
00165       for (int a=0; a<arity; a++) {
00166         // Sort tuple according to position
00167         PosCompare pc(a);
00168         Support::quicksort(tuple, n_tuples, pc);
00169         // Scan values
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        * Pass 2: allocate memory and fill data structures
00189        */
00190       // Allocate memory for ranges
00191       Range* cr = range = heap.alloc<Range>(n_ranges);
00192       // Allocate and initialize memory for supports
00193       BitSetData* cs = support = heap.alloc<BitSetData>(n_words * n_vals);
00194       for (unsigned int i=0; i<n_vals * n_words; i++)
00195         cs[i].init();
00196       for (int a=0; a<arity; a++) {
00197         // Set range pointer
00198         vd[a].r = cr;
00199         // Sort tuple according to position
00200         PosCompare pc(a);
00201         Support::quicksort(tuple, n_tuples, pc);
00202         // Update min and max
00203         min = std::min(min,tuple[0][a]);
00204         max = std::max(max,tuple[n_tuples-1][a]);
00205         // Compress into non-overlapping ranges
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         // Set support pointer and set bits
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    * Tuple set
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     // Initialize
00306     object(new Data(a));
00307 
00308     Region r;
00309     // Number of states
00310     int max_states = dfa.n_states();
00311     // Allocate memory for all layers and states
00312     Layer* layers = r.alloc<Layer>(a+1);
00313     State* states = r.alloc<State>(max_states*(a+1));
00314 
00315     for (int i=0; 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=0; i<a+1; i++) {
00321       layers[i].states = states + i*max_states;
00322       layers[i].n_supports = 0U;
00323     }
00324 
00325     // Mark initial state as being reachable
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     // Allocate temporary memory for edges and supports
00332     Edge* edges = r.alloc<Edge>(dfa.max_degree());
00333     Support* supports = r.alloc<Support>(dfa.n_symbols());
00334   
00335     // Forward pass: accumulate
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             // Create edge
00343             edges[n_edges].i_state = t.i_state();
00344             edges[n_edges].o_state = t.o_state();
00345             n_edges++;
00346             // Adjust degrees
00347             layers[i].states[t.i_state()].o_deg++;
00348             layers[i+1].states[t.o_state()].i_deg++;
00349             // Adjust number of tuples
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         // Found a support for the value
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       // Create supports
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     // Mark final states as being reachable
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     // Backward pass: validate
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           // State is unreachable
00388           if (layers[i+1].states[o_state].o_deg == 0U) {
00389             // Adjust degree
00390             --layers[i+1].states[o_state].i_deg;
00391             --layers[i].states[i_state].o_deg;
00392             // Remove edge
00393             assert(s.n_edges > 0U);
00394             s.edges[k] = s.edges[--s.n_edges];
00395           }
00396         }
00397         // Lost support
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     // Generate tuples
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           // Allocate memory for tuples if not done
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           // Write tuples
00422           for (unsigned int t=0; t < layers[i].states[i_state].n_tuples; t++) {
00423             // Copy the first i number of digits from the previous layer
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             // Write the last digit
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     // Add tuples to tuple set
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=0; i<tuples(); i++)
00453       for (int j=0; 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=0; i<t.size(); i++)
00469       a[i]=t[i];
00470   }
00471 
00472 }
00473 
00474 // STATISTICS: int-prop
00475