Generated on Sun Feb 17 15:24:18 2019 for Gecode by doxygen 1.6.3

bit-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  *     Linnea Ingmar <linnea.ingmar@hotmail.com>
00005  *
00006  *  Contributing authors:
00007  *     Christian Schulte <schulte@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Linnea Ingmar, 2017
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 namespace Gecode { namespace Int { namespace Extensional {
00039 
00040   template<class IndexType>
00041   forceinline unsigned int
00042   BitSet<IndexType>::limit(void) const {
00043     return static_cast<unsigned int>(_limit);
00044   }
00045   
00046   template<class IndexType>
00047   forceinline bool
00048   BitSet<IndexType>::empty(void) const {
00049     return _limit == 0U;
00050   }
00051   
00052   template<class IndexType>
00053   forceinline unsigned int
00054   BitSet<IndexType>::words(void) const {
00055     return static_cast<unsigned int>(_limit);
00056   }
00057 
00058   template<class IndexType>
00059   forceinline unsigned int
00060   BitSet<IndexType>::size(void) const {
00061     return words();
00062   }
00063       
00064   template<class IndexType>
00065   forceinline unsigned int
00066   BitSet<IndexType>::width(void) const {
00067     assert(!empty());
00068     IndexType width = _index[0];
00069     for (IndexType i=1; i<_limit; i++)
00070       width = std::max(width,_index[i]);
00071     assert(static_cast<unsigned int>(width+1U) >= words());
00072     return static_cast<unsigned int>(width+1U);
00073   }
00074 
00075   template<class IndexType>
00076   forceinline
00077   BitSet<IndexType>::BitSet(Space& home, unsigned int n)
00078     : _limit(static_cast<IndexType>(n)), 
00079       _index(home.alloc<IndexType>(n)),
00080       _bits(home.alloc<BitSetData>(n)) {
00081     // Set all bits in all words (including the last)
00082     for (IndexType i=0; i<_limit; i++) {
00083       _bits[i].init(true);
00084       _index[i] = i;
00085     }
00086   }
00087 
00088   template<class IndexType>
00089   template<class OldIndexType>
00090   forceinline
00091   BitSet<IndexType>::BitSet(Space& home,
00092                             const BitSet<OldIndexType>& bs)
00093     : _limit(static_cast<IndexType>(bs._limit)),
00094       _index(home.alloc<IndexType>(_limit)),
00095       _bits(home.alloc<BitSetData>(_limit)) {
00096     assert(_limit > 0U);
00097     for (IndexType i=0; i<_limit; i++) {
00098       _bits[i] = bs._bits[i];
00099       _index[i] = static_cast<IndexType>(bs._index[i]);
00100     }
00101   }
00102 
00103   template<class IndexType>
00104   forceinline void
00105   BitSet<IndexType>::flush(void) {
00106     _limit = 0U;
00107     assert(empty());
00108   }
00109     
00110   template<class IndexType>
00111   forceinline
00112   BitSet<IndexType>::BitSet(Space&, const TinyBitSet<1U>&) {
00113     GECODE_NEVER;
00114   }
00115   template<class IndexType>
00116   forceinline
00117   BitSet<IndexType>::BitSet(Space&, const TinyBitSet<2U>&) {
00118     GECODE_NEVER;
00119   }
00120   template<class IndexType>
00121   forceinline
00122   BitSet<IndexType>::BitSet(Space&, const TinyBitSet<3U>&) {
00123     GECODE_NEVER;
00124   }
00125   template<class IndexType>
00126   forceinline
00127   BitSet<IndexType>::BitSet(Space&, const TinyBitSet<4U>&) {
00128     GECODE_NEVER;
00129   }
00130 
00131   template<class IndexType>
00132   forceinline void
00133   BitSet<IndexType>::replace_and_decrease(IndexType i, BitSetData w) {
00134     assert(_limit > 0U);
00135     BitSetData w_i = _bits[i];
00136     if (w != w_i) {
00137       _bits[i] = w;
00138       if (w.none()) {
00139         assert(_bits[i].none());
00140         _limit--;
00141         _bits[i] = _bits[_limit];
00142         _index[i] = _index[_limit];
00143       }
00144     }
00145   }
00146 
00147   template<class IndexType>
00148   forceinline void
00149   BitSet<IndexType>::clear_mask(BitSetData* mask) const {
00150     assert(_limit > 0U);
00151     for (IndexType i=0; i<_limit; i++) {
00152       mask[i].init(false);
00153       assert(mask[i].none());
00154     }
00155   }
00156   
00157   template<class IndexType>
00158   forceinline void
00159   BitSet<IndexType>::add_to_mask(const BitSetData* b, BitSetData* mask) const {
00160     assert(_limit > 0U);
00161     for (IndexType i=0; i<_limit; i++)
00162       mask[i] = BitSetData::o(mask[i],b[_index[i]]);
00163   }
00164 
00165   template<class IndexType>
00166   template<bool sparse>
00167   forceinline void
00168   BitSet<IndexType>::intersect_with_mask(const BitSetData* mask) {
00169     assert(_limit > 0U);
00170     if (sparse) {
00171       for (IndexType i = _limit; i--; ) {
00172         assert(!_bits[i].none());
00173         BitSetData w_i = _bits[i];
00174         BitSetData w_a = BitSetData::a(w_i, mask[_index[i]]);
00175         replace_and_decrease(i,w_a);
00176         assert(i == _limit || !_bits[i].none());
00177       }
00178     } else { // The same except different _indexing in mask
00179       for (IndexType i = _limit; i--; ) {
00180         assert(!_bits[i].none());
00181         BitSetData w_i = _bits[i];
00182         BitSetData w_a = BitSetData::a(w_i, mask[i]);
00183         replace_and_decrease(i,w_a);
00184         assert(i == _limit || !_bits[i].none());
00185       }
00186     }
00187   }
00188   
00189   template<class IndexType>
00190   forceinline void
00191   BitSet<IndexType>::intersect_with_masks(const BitSetData* a,
00192                                           const BitSetData* b) {
00193     assert(_limit > 0U);
00194     for (IndexType i = _limit; i--; ) {
00195       assert(!_bits[i].none());
00196       BitSetData w_i = _bits[i];
00197       IndexType offset = _index[i];
00198       BitSetData w_o = BitSetData::o(a[offset], b[offset]);
00199       BitSetData w_a = BitSetData::a(w_i,w_o);
00200       replace_and_decrease(i,w_a);
00201       assert(i == _limit || !_bits[i].none());
00202     }
00203   }
00204   
00205   template<class IndexType>
00206   forceinline void
00207   BitSet<IndexType>::nand_with_mask(const BitSetData* b) {
00208     assert(_limit > 0U);
00209     for (IndexType i = _limit; i--; ) {
00210       assert(!_bits[i].none());
00211       BitSetData w = BitSetData::a(_bits[i],~(b[_index[i]]));
00212       replace_and_decrease(i,w);
00213       assert(i == _limit || !_bits[i].none());
00214     }
00215   }
00216 
00217   template<class IndexType>
00218   forceinline bool
00219   BitSet<IndexType>::intersects(const BitSetData* b) const {
00220     for (IndexType i=0; i<_limit; i++)
00221       if (!BitSetData::a(_bits[i],b[_index[i]]).none())
00222         return true;
00223     return false;
00224   }
00225     
00226   template<class IndexType>
00227   forceinline unsigned long long int
00228   BitSet<IndexType>::ones(const BitSetData* b) const {
00229     unsigned long long int o = 0U;
00230     for (IndexType i=0; i<_limit; i++)
00231       o += static_cast<unsigned long long int>
00232         (BitSetData::a(_bits[i],b[_index[i]]).ones());
00233     return o;
00234   }
00235     
00236   template<class IndexType>
00237   forceinline unsigned long long int
00238   BitSet<IndexType>::ones(void) const {
00239     unsigned long long int o = 0U;
00240     for (IndexType i=0; i<_limit; i++)
00241       o += static_cast<unsigned long long int>(_bits[i].ones());
00242     return o;
00243   }
00244     
00245   template<class IndexType>
00246   forceinline unsigned long long int
00247   BitSet<IndexType>::bits(void) const {
00248     return (static_cast<unsigned long long int>(_limit) *
00249             static_cast<unsigned long long int>(BitSetData::bpb));
00250   }
00251 
00252 }}}
00253 
00254 // STATISTICS: int-prop