Generated on Tue May 22 09:40:00 2018 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 = 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 = sz; i--; )
00074        bits[i].init(false);
00075      for (unsigned int i = sbs.words(); i--; ) {
00076        bits[sbs.index[i]] = sbs.bits[i];
00077      }
00078      assert(!empty());
00079    }
00080 
00081    template<unsigned int sz>
00082    forceinline void
00083    TinyBitSet<sz>::clear_mask(BitSetData* mask) {
00084      for (unsigned int i=sz; i--; ) {
00085        mask[i].init(false);
00086        assert(mask[i].none());
00087      }
00088    }
00089 
00090    template<unsigned int sz>
00091    forceinline void
00092    TinyBitSet<sz>::add_to_mask(const BitSetData* b, BitSetData* mask) const {
00093      for (unsigned int i=sz; i--; )
00094        mask[i] = BitSetData::o(mask[i],b[i]);
00095    }
00096 
00097    template<unsigned int sz>
00098    template<bool sparse>
00099    forceinline void
00100    TinyBitSet<sz>::intersect_with_mask(const BitSetData* mask) {
00101      for (unsigned int i=sz; i--; )
00102        bits[i] = BitSetData::a(bits[i], mask[i]);
00103    }
00104 
00105    template<unsigned int sz>
00106    forceinline void
00107    TinyBitSet<sz>::intersect_with_masks(const BitSetData* a, const BitSetData* b) {
00108      for (unsigned int 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=sz; i--; )
00116        bits[i] = BitSetData::a(bits[i],~(b[i]));
00117    }
00118 
00119    template<unsigned int sz>
00120    forceinline bool
00121    TinyBitSet<sz>::intersects(const BitSetData* b) {
00122      for (unsigned int i=sz; i--; )
00123        if (!BitSetData::a(bits[i],b[i]).none())
00124          return true;
00125      return false;
00126    }
00127 
00128    template<unsigned int sz>
00129    forceinline bool
00130    TinyBitSet<sz>::empty(void) const { // Linear complexity...
00131      for (unsigned int i=sz; i--; )
00132        if (!bits[i].none())
00133          return false;
00134      return true;
00135    }
00136 
00137    template<unsigned int sz>
00138    forceinline unsigned int
00139    TinyBitSet<sz>::width(void) const {
00140      assert(!empty());
00142      for (unsigned int i=sz; i--; )
00143        if (!bits[i].none())
00144          return i+1U;
00145      GECODE_NEVER;
00146      return 0U;
00147    }
00148       
00149    template<unsigned int sz>
00150    forceinline unsigned int
00151    TinyBitSet<sz>::words(void) const {
00152      return width();
00153    }
00154 
00155    template<unsigned int sz>
00156    forceinline unsigned int
00157    TinyBitSet<sz>::size(void) const {
00158      return sz;
00159    }
00160 
00161 }}}
00162 
00163 // STATISTICS: int-prop