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

tiny-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   /*
00041    * Tiny bit-set
00042    *
00043    */
00044   template<unsigned int sz>
00045   forceinline
00046   TinyBitSet<sz>::TinyBitSet(Space&, unsigned int n) {
00047     assert(n <= sz);
00049       for (unsigned int i=0U; i<n; i++)
00050         _bits[i].init(true);
00052         for (unsigned int i=n; i<sz; i++)
00053           _bits[i].init(false);
00054   }
00055 
00056   template<unsigned int sz>
00057   template<unsigned int largersz>
00058   forceinline
00059   TinyBitSet<sz>::TinyBitSet(Space&, const TinyBitSet<largersz>& sbs) {
00060     GECODE_ASSUME(sz <= largersz);
00061     assert(!sbs.empty());
00062     for (unsigned int i=0U; i<sz; i++)
00063       _bits[i] = sbs._bits[i];
00064     assert(!empty());
00065   }
00066       
00067   template<unsigned int sz>
00068   template<class IndexType>
00069   forceinline
00070   TinyBitSet<sz>::TinyBitSet(Space&, const BitSet<IndexType>& sbs) {
00071     assert(sz == sbs.width());
00072     assert(!sbs.empty());
00073     for (unsigned int i=0U; i<sz; i++)
00074       _bits[i].init(false);
00075     for (unsigned int i=0U; i<sbs.words(); i++)
00076       _bits[sbs._index[i]] = sbs._bits[i];
00077     assert(!empty());
00078   }
00079 
00080   template<unsigned int sz>
00081   forceinline void
00082   TinyBitSet<sz>::clear_mask(BitSetData* mask) {
00083     for (unsigned int i=0U; i<sz; i++) {
00084       mask[i].init(false);
00085       assert(mask[i].none());
00086     }
00087   }
00088 
00089   template<unsigned int sz>
00090   forceinline void
00091   TinyBitSet<sz>::add_to_mask(const BitSetData* b, BitSetData* mask) const {
00092     for (unsigned int i=0U; i<sz; i++)
00093       mask[i] = BitSetData::o(mask[i],b[i]);
00094   }
00095 
00096   template<unsigned int sz>
00097   template<bool sparse>
00098   forceinline void
00099   TinyBitSet<sz>::intersect_with_mask(const BitSetData* mask) {
00100     for (unsigned int i=0U; i<sz; i++)
00101       _bits[i] = BitSetData::a(_bits[i], mask[i]);
00102   }
00103 
00104   template<unsigned int sz>
00105   forceinline void
00106   TinyBitSet<sz>::intersect_with_masks(const BitSetData* a,
00107                                        const BitSetData* b) {
00108     for (unsigned int i=0U; i<sz; i++)
00109       _bits[i] = BitSetData::a(_bits[i], BitSetData::o(a[i],b[i]));
00110   }
00111 
00112   template<unsigned int sz>
00113   forceinline void
00114   TinyBitSet<sz>::nand_with_mask(const BitSetData* b) {
00115     for (unsigned int i=0U; i<sz; i++)
00116       _bits[i] = BitSetData::a(_bits[i],~(b[i]));
00117   }
00118 
00119   template<unsigned int sz>
00120   forceinline void
00121   TinyBitSet<sz>::flush(void) {
00122     for (unsigned int i=0U; i<sz; i++)
00123       _bits[i].init(false);
00124     assert(empty());
00125   }
00126   
00127   template<unsigned int sz>
00128   forceinline bool
00129   TinyBitSet<sz>::intersects(const BitSetData* b) {
00130     for (unsigned int i=0U; i<sz; i++)
00131       if (!BitSetData::a(_bits[i],b[i]).none())
00132         return true;
00133     return false;
00134   }
00135 
00136   template<unsigned int sz>
00137   forceinline unsigned long long int
00138   TinyBitSet<sz>::ones(const BitSetData* b) const {
00139     unsigned long long int o = 0U;
00140     for (unsigned int i=0U; i<sz; i++)
00141       o += static_cast<unsigned long long int>
00142         (BitSetData::a(_bits[i],b[i]).ones());
00143     return o;
00144   }
00145     
00146   template<unsigned int sz>
00147   forceinline unsigned long long int
00148   TinyBitSet<sz>::ones(void) const {
00149     unsigned long long int o = 0U;
00150     for (unsigned int i=0U; i<sz; i++)
00151       o += static_cast<unsigned long long int>(_bits[i].ones());
00152     return o;
00153   }
00154     
00155   template<unsigned int sz>
00156   forceinline unsigned long long int
00157   TinyBitSet<sz>::bits(void) const {
00158     return (static_cast<unsigned long long int>(sz) *
00159             static_cast<unsigned long long int>(BitSetData::bpb));
00160   }
00161     
00162   template<unsigned int sz>
00163   forceinline bool
00164   TinyBitSet<sz>::empty(void) const { // Linear complexity...
00165     for (unsigned int i=0U; i<sz; i++)
00166       if (!_bits[i].none())
00167         return false;
00168     return true;
00169   }
00170 
00171   template<unsigned int sz>
00172   forceinline unsigned int
00173   TinyBitSet<sz>::width(void) const {
00174     assert(!empty());
00176       for (unsigned int i=sz; i--; )
00177         if (!_bits[i].none())
00178           return i+1U;
00179       GECODE_NEVER;
00180       return 0U;
00181   }
00182       
00183   template<unsigned int sz>
00184   forceinline unsigned int
00185   TinyBitSet<sz>::words(void) const {
00186     return width();
00187   }
00188 
00189   template<unsigned int sz>
00190   forceinline unsigned int
00191   TinyBitSet<sz>::size(void) const {
00192     return sz;
00193   }
00194 
00195 }}}
00196 
00197 // STATISTICS: int-prop