bitset-base.hpp

Go to the documentation of this file.

/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
 *  Main authors:
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 *
 *  Contributing authors:
 *     Christian Schulte <schulte@gecode.org>
 *
 *  Copyright:
 *     Mikael Lagerkvist, 2007
 *     Christian Schulte, 2007
 *
 *  Last modified:
 *     $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
 *     $Revision: 14967 $
 *
 *  This file is part of Gecode, the generic constraint
 *  development environment:
 *     http://www.gecode.org
 *
 *  Permission is hereby granted, free of charge, to any person obtaining
 *  a copy of this software and associated documentation files (the
 *  "Software"), to deal in the Software without restriction, including
 *  without limitation the rights to use, copy, modify, merge, publish,
 *  distribute, sublicense, and/or sell copies of the Software, and to
 *  permit persons to whom the Software is furnished to do so, subject to
 *  the following conditions:
 *
 *  The above copyright notice and this permission notice shall be
 *  included in all copies or substantial portions of the Software.
 *
 *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 */

#include <climits>

#ifdef _MSC_VER

#include <intrin.h>

#if defined(_M_IX86)
#pragma intrinsic(_BitScanForward)
#define GECODE_SUPPORT_MSVC_32
#endif

#if defined(_M_X64) || defined(_M_IA64)
#pragma intrinsic(_BitScanForward64)
#define GECODE_SUPPORT_MSVC_64
#endif

#endif

namespace Gecode { namespace Support {

  class RawBitSetBase;

  class BitSetData {
    friend class RawBitSetBase;
  protected:
#ifdef GECODE_SUPPORT_MSVC_64

    typedef unsigned __int64 Base;
#else

    typedef unsigned long int Base;
#endif

    Base bits;
    static const unsigned int bpb =
      static_cast<unsigned int>(CHAR_BIT * sizeof(Base));
  public:
    void init(bool setbits=false);
    static unsigned int data(unsigned int s);
    bool operator ()(unsigned int i=0U) const;
    bool get(unsigned int i) const;
    void set(unsigned int i);
    void clear(unsigned int i);
    unsigned int next(unsigned int i=0U) const;
    bool all(void) const;
    bool all(unsigned int i) const;
    bool none(void) const;
    bool none(unsigned int i) const;
    void a(BitSetData a);
    void a(BitSetData a, unsigned int i);
    static BitSetData a(BitSetData a, BitSetData b);
    void o(BitSetData a);
    void o(BitSetData a, unsigned int i);
    static BitSetData o(BitSetData a, BitSetData b);
  };

  enum BitSetStatus {
    BSS_NONE, 
    BSS_ALL,  
    BSS_SOME  
  };

  class RawBitSetBase {
  protected:
    static const unsigned int bpb = BitSetData::bpb;
    BitSetData* data;
  private:
    RawBitSetBase(const RawBitSetBase&);
    RawBitSetBase& operator =(const RawBitSetBase&);
  public:
    RawBitSetBase(void);
    template<class A>
    RawBitSetBase(A& a, unsigned int sz, bool setbits=false);
    template<class A>
    RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs);
    template<class A>
    void allocate(A& a, unsigned int sz);
    template<class A>
    void init(A& a, unsigned int sz, bool setbits=false);
    void clearall(unsigned int sz, bool setbits=false);
    void copy(unsigned int sz, const RawBitSetBase& bs);
    bool get(unsigned int i) const;
    void set(unsigned int i);
    void clear(unsigned int i);
    unsigned int next(unsigned int i) const;
    BitSetStatus status(unsigned int sz) const;
    bool all(unsigned int sz) const;
    bool none(unsigned int sz) const;
    template<class A>
    void resize(A& a, unsigned int sz, unsigned int n, bool setbits=false);
    template<class A>
    void dispose(A& a, unsigned int sz);
  };

  class BitSetBase : public RawBitSetBase {
  protected:
    unsigned int sz;
  private:
    BitSetBase(const BitSetBase&);
    BitSetBase& operator =(const BitSetBase&);
  public:
    BitSetBase(void);
    template<class A>
    BitSetBase(A& a, unsigned int s, bool setbits=false);
    template<class A>
    BitSetBase(A& a, const BitSetBase& bs);
    template<class A>
    void init(A& a, unsigned int s, bool setbits=false);
    void clearall(bool setbits=false);
    void copy(const BitSetBase& bs);
    unsigned int size(void) const;
    bool get(unsigned int i) const;
    void set(unsigned int i);
    void clear(unsigned int i);
    unsigned int next(unsigned int i) const;
    BitSetStatus status(void) const;
    bool all(void) const;
    bool none(void) const;
    template<class A>
    void resize(A& a, unsigned int n, bool setbits=false);
    template<class A>
    void dispose(A& a);
  };


  /*
   * Bitset data
   *
   */

  forceinline void
  BitSetData::init(bool setbits) {
    bits = setbits ? ~static_cast<Base>(0) : static_cast<Base>(0);
  }
  forceinline unsigned int
  BitSetData::data(unsigned int s) {
    return s == 0 ? 0 : ((s-1) / bpb + 1);
  }
  forceinline bool
  BitSetData::operator ()(unsigned int i) const {
    return (bits >> i) != static_cast<Base>(0U);
  }
  forceinline bool
  BitSetData::get(unsigned int i) const {
    return (bits & (static_cast<Base>(1U) << i)) != static_cast<Base>(0U);
  }
  forceinline void
  BitSetData::set(unsigned int i) {
    bits |= (static_cast<Base>(1U) << i);
  }
  forceinline void
  BitSetData::clear(unsigned int i) {
    bits &= ~(static_cast<Base>(1U) << i);
  }
  forceinline unsigned int
  BitSetData::next(unsigned int i) const {
    assert(bits != static_cast<Base>(0));
#if defined(GECODE_SUPPORT_MSVC_32)
    assert(bpb == 32);
    unsigned long int p;
    _BitScanForward(&p,bits >> i);
    return static_cast<unsigned int>(p)+i;
#elif defined(GECODE_SUPPORT_MSVC_64)
    assert(bpb == 64);
    unsigned long int p;
    _BitScanForward64(&p,bits >> i);
    return static_cast<unsigned int>(p)+i;
#elif defined(GECODE_HAS_BUILTIN_FFSL)
    if ((bpb == 32) || (bpb == 64)) {
      int p = __builtin_ffsl(bits >> i);
      assert(p > 0);
      return static_cast<unsigned int>(p-1)+i;
    }
#else
    while (!get(i)) i++;
    return i;
#endif
  }
  forceinline bool
  BitSetData::all(void) const {
    return bits == ~static_cast<Base>(0U);
  }
  forceinline bool
  BitSetData::all(unsigned int i) const {
    const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
    return (bits & mask) == mask;
  }
  forceinline bool
  BitSetData::none(void) const {
    return bits == static_cast<Base>(0U);
  }
  forceinline bool
  BitSetData::none(unsigned int i) const {
    const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
    return (bits & mask) == static_cast<Base>(0U);
  }

  forceinline void
  BitSetData::a(BitSetData a) {
    bits &= a.bits;
  }
  forceinline void
  BitSetData::a(BitSetData a, unsigned int i) {
    const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
    bits &= (a.bits & mask);
  }
  forceinline BitSetData
  BitSetData::a(BitSetData a, BitSetData b) {
    BitSetData ab;
    ab.bits = a.bits & b.bits;
    return ab;
  }

  forceinline void
  BitSetData::o(BitSetData a) {
    bits |= a.bits;
  }
  forceinline void
  BitSetData::o(BitSetData a, unsigned int i) {
    const Base mask = (static_cast<Base>(1U) << i) - static_cast<Base>(1U);
    bits |= (a.bits & mask);
  }
  forceinline BitSetData
  BitSetData::o(BitSetData a, BitSetData b) {
    BitSetData ab;
    ab.bits = a.bits | b.bits;
    return ab;
  }


  /*
   * Basic bit sets
   *
   */

  forceinline bool
  RawBitSetBase::get(unsigned int i) const {
    return data[i / bpb].get(i % bpb);
  }
  forceinline void
  RawBitSetBase::set(unsigned int i) {
    data[i / bpb].set(i % bpb);
  }
  forceinline void
  RawBitSetBase::clear(unsigned int i) {
    data[i / bpb].clear(i % bpb);
  }

  template<class A>
  void
  RawBitSetBase::resize(A& a, unsigned int sz, unsigned int n, bool setbits) {
    if (n>sz) {
      data = a.template realloc<BitSetData>(data,BitSetData::data(sz+1),
                                            BitSetData::data(n+1));
      for (unsigned int i=BitSetData::data(sz)+1;
           i<BitSetData::data(n+1); i++) {
        data[i].init(setbits);
      }
      for (unsigned int i=(sz%bpb); i<bpb; i++)
        if (setbits)
          data[sz / bpb].set(i);
        else
          data[sz / bpb].clear(i);
    }
    set(n);
  }

  template<class A>
  forceinline void
  RawBitSetBase::dispose(A& a, unsigned int sz) {
    a.template free<BitSetData>(data,BitSetData::data(sz+1));
  }

  forceinline
  RawBitSetBase::RawBitSetBase(void)
    : data(NULL) {}

  template<class A>
  forceinline
  RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, bool setbits)
    : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
    for (unsigned int i = BitSetData::data(sz+1); i--; )
      data[i].init(setbits);
    // Set a bit at position sz as sentinel (for efficient next)
    set(sz);
  }

  template<class A>
  forceinline
  RawBitSetBase::RawBitSetBase(A& a, unsigned int sz, const RawBitSetBase& bs)
    : data(a.template alloc<BitSetData>(BitSetData::data(sz+1))) {
    for (unsigned int i = BitSetData::data(sz+1); i--; )
      data[i] = bs.data[i];
    // Set a bit at position sz as sentinel (for efficient next)
    set(sz);
  }

  template<class A>
  forceinline void
  RawBitSetBase::allocate(A& a, unsigned int sz) {
    assert(data == NULL);
    data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
  }

  template<class A>
  forceinline void
  RawBitSetBase::init(A& a, unsigned int sz, bool setbits) {
    assert(data == NULL);
    data=a.template alloc<BitSetData>(BitSetData::data(sz+1));
    for (unsigned int i=BitSetData::data(sz+1); i--; )
      data[i].init(setbits);
    // Set a bit at position sz as sentinel (for efficient next)
    set(sz);
  }

  forceinline void
  RawBitSetBase::copy(unsigned int sz, const RawBitSetBase& bs) {
    for (unsigned int i=BitSetData::data(sz+1); i--; )
      data[i] = bs.data[i];
  }

  forceinline void
  RawBitSetBase::clearall(unsigned int sz, bool setbits) {
    for (unsigned int i=BitSetData::data(sz+1); i--; )
      data[i].init(setbits);
  }

  forceinline unsigned int
  RawBitSetBase::next(unsigned int i) const {
    unsigned int pos = i / bpb;
    unsigned int bit = i % bpb;
    if (data[pos](bit))
      return pos * bpb + data[pos].next(bit);
    // The sentinel bit guarantees that this loop always terminates
    do {
      pos++;
    } while (!data[pos]());
    return pos * bpb + data[pos].next();
  }

  forceinline BitSetStatus
  RawBitSetBase::status(unsigned int sz) const {
    unsigned int pos = sz / bpb;
    unsigned int bits = sz % bpb;
    if (pos > 0) {
      if (data[0].all()) {
        for (unsigned int i=1; i<pos; i++)
          if (!data[i].all())
            return BSS_SOME;
        return data[pos].all(bits) ? BSS_ALL : BSS_SOME;
      } else if (data[0].none()) {
        for (unsigned int i=1; i<pos; i++)
          if (!data[i].none())
            return BSS_SOME;
        return data[pos].none(bits) ? BSS_NONE : BSS_SOME;
      } else {
        return BSS_SOME;
      }
    }
    if (data[0].all(bits))
      return BSS_ALL;
    if (data[0].none(bits))
      return BSS_NONE;
    return BSS_SOME;
  }

  forceinline bool
  RawBitSetBase::all(unsigned int sz) const {
    return status(sz) == BSS_ALL;
  }

  forceinline bool
  RawBitSetBase::none(unsigned int sz) const {
    return status(sz) == BSS_NONE;
  }


  template<class A>
  void
  BitSetBase::resize(A& a, unsigned int n, bool setbits) {
    RawBitSetBase::resize(a,sz,n,setbits); sz=n;
  }

  template<class A>
  forceinline void
  BitSetBase::dispose(A& a) {
    RawBitSetBase::dispose(a,sz);
  }

  forceinline
  BitSetBase::BitSetBase(void)
    : sz(0U) {}

  template<class A>
  forceinline
  BitSetBase::BitSetBase(A& a, unsigned int s, bool setbits)
    : RawBitSetBase(a,s,setbits), sz(s) {}

  template<class A>
  forceinline
  BitSetBase::BitSetBase(A& a, const BitSetBase& bs)
    : RawBitSetBase(a,bs.sz,bs), sz(bs.sz) {}

  template<class A>
  forceinline void
  BitSetBase::init(A& a, unsigned int s, bool setbits) {
    assert(sz == 0);
    RawBitSetBase::init(a,s,setbits); sz=s;
  }

  forceinline void
  BitSetBase::copy(const BitSetBase& bs) {
    assert(sz == bs.sz);
    RawBitSetBase::copy(sz,bs);
  }

  forceinline void
  BitSetBase::clearall(bool setbits) {
    RawBitSetBase::clearall(sz,setbits);
  }

  forceinline unsigned int
  BitSetBase::size(void) const {
    return sz;
  }

  forceinline bool
  BitSetBase::get(unsigned int i) const {
    assert(i < sz);
    return RawBitSetBase::get(i);
  }
  forceinline void
  BitSetBase::set(unsigned int i) {
    assert(i < sz);
    RawBitSetBase::set(i);
  }
  forceinline void
  BitSetBase::clear(unsigned int i) {
    assert(i < sz);
    RawBitSetBase::clear(i);
  }

  forceinline unsigned int
  BitSetBase::next(unsigned int i) const {
    assert(i <= sz);
    return RawBitSetBase::next(i);
  }

  forceinline BitSetStatus
  BitSetBase::status(void) const {
    return RawBitSetBase::status(sz);
  }

  forceinline bool
  BitSetBase::all(void) const {
    return RawBitSetBase::all(sz);
  }

  forceinline bool
  BitSetBase::none(void) const {
    return RawBitSetBase::none(sz);
  }

}}

#ifdef GECODE_SUPPORT_MSVC_32
#undef GECODE_SUPPORT_MSVC_32
#endif
#ifdef GECODE_SUPPORT_MSVC_64
#undef GECODE_SUPPORT_MSVC_64
#endif

// STATISTICS: support-any