bitset.h

Go to the documentation of this file.

/*
 *  This file is a part of TiledArray.
 *  Copyright (C) 2013  Virginia Tech
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#ifndef TILEDARRAY_BITSET_H__INCLUDED
#define TILEDARRAY_BITSET_H__INCLUDED

#include <TiledArray/error.h>
#include <TiledArray/transform_iterator.h>
#include <climits>
#include <iosfwd>
#include <iomanip>

namespace TiledArray {
  namespace detail {


    template <typename Block = unsigned long>
    class Bitset {
    private:
      static_assert( (std::is_integral<Block>::value || std::is_same<Block, char>::value),
          "Bitset template type Block must be an integral or char type");

      static const std::size_t block_bits; 
      static const Block zero;
      static const Block one;
      static const Block xffff;

    public:

      class reference {

        friend class Bitset<Block>;

        reference(Block& block, Block mask) : block_(block), mask_(mask) { }

        // Not allowed
        void operator&();

      public:

        reference& operator=(bool value) {
          assign(value);
          return *this;
        }

        reference& operator=(const reference& other) {
          assign(other);
          return *this;
        }

        reference& operator|=(bool value) {
          if(value) set();
          return *this;
        }

        reference& operator&=(bool value) {
          if(!value) reset();
          return *this;
        }

        reference& operator^=(bool value) {
          if(value) flip();
          return *this;
        }

        reference& operator-=(bool value) {
          if(value) reset();
          return *this;
        }

        operator bool() const { return block_ & mask_; }

        bool operator~() const { return !(block_ & mask_); }

        reference& flip() {
          block_ ^= mask_;
          return *this;
        }

     private:

        void assign(bool value) {
          if(value)
            set();
          else
            reset();
        }

        void set() { block_ |= mask_; }

        void reset() { block_ &= ~mask_; }

        Block& block_;
        const Block mask_;
      }; // class reference

    private:

      class ConstTransformOp {
      public:
        typedef std::size_t argument_type;
        typedef Block result_type;

        ConstTransformOp(const Bitset<Block>& bitset) : bitset_(&bitset) { }

        ConstTransformOp(const ConstTransformOp& other) : bitset_(other.bitset_) { }


        ConstTransformOp& operator=(const ConstTransformOp& other) {
          bitset_ = other.bitset_;

          return *this;
        }

        Block operator()(std::size_t i) const { return (*bitset_)[i]; }

      private:
        const Bitset<Block>* bitset_;
      }; // class ConstTransformOp

      class TransformOp {
      public:
        typedef std::size_t argument_type;
        typedef reference result_type;

        TransformOp(const Bitset<Block>& bitset) : bitset_(bitset) { }
        reference operator()(std::size_t i) const { return const_cast<Bitset<Block>&>(bitset_)[i]; }
      private:
        const Bitset<Block>& bitset_;
      }; // class TransformOp

    public:
      typedef Bitset<Block> Bitset_; 
      typedef Block block_type; 
      typedef Block value_type; 
      typedef Block const_reference; 
      typedef std::size_t size_type; 
      typedef UnaryTransformIterator<Block, ConstTransformOp> const_iterator; 
      typedef UnaryTransformIterator<Block, TransformOp> iterator; 


      Bitset(size_type s) :
          size_(s),
          blocks_((size_ / block_bits) + (size_ % block_bits ? 1 : 0)),
          set_((size_ ? new block_type[blocks_] : NULL))
      {
        std::fill_n(set_, blocks_, zero);
      }


      template <typename InIter>
      Bitset(InIter first, InIter last) :
          size_(std::distance(first, last)),
          blocks_((size_ / block_bits) + (size_ % block_bits ? 1 : 0)),
          set_((size_ ? new block_type[blocks_] : NULL))
      {
        // Initialize to zero
        std::fill_n(set_, blocks_, zero);

        for(size_type i = 0; first != last; ++i, ++first)
          if(*first)
            set(i);
      }


      Bitset(const Bitset<Block>& other) :
          size_(other.size_),
          blocks_(other.blocks_),
          set_((size_ ? new block_type[blocks_] : NULL))
      {
        std::copy(other.set_, other.set_ + blocks_, set_);
      }

      ~Bitset() { delete [] set_; }


      Bitset<Block>& operator=(const Bitset<Block>& other) {
        if(blocks_ == other.blocks_) {
          if(this != &other) {
            size_ = other.size_;
            std::copy(other.set_, other.set_ + blocks_, set_);
          }
        } else {
          Bitset<Block>(other).swap(*this);
        }

        return *this;
      }


      Bitset<Block>& operator|=(const Bitset<Block>& other) {
        TA_ASSERT(size_ == other.size_);
        for(size_type i = 0; i < blocks_; ++i)
          set_[i] |= other.set_[i];

        return *this;
      }


      Bitset<Block>& operator&=(const Bitset<Block>& other) {
        TA_ASSERT(size_ == other.size_);
        for(size_type i = 0; i < blocks_; ++i)
          set_[i] &= other.set_[i];

        return *this;
      }



      Bitset<Block>& operator^=(const Bitset<Block>& other) {
        TA_ASSERT(size_ == other.size_);
        for(size_type i = 0; i < blocks_; ++i)
          set_[i] ^= other.set_[i];

        return *this;
      }

    private:

      static void left_shift(Bitset<Block>& dest, const Bitset<Block>& source, size_type n) {
        // Compute shifts
        const size_type block_shift = dest.block_index(n);
        const size_type bit_shift = dest.bit_index(n);

        // Compute iteration ranges
        block_type* last = dest.set_ + dest.blocks_ - 1;
        const block_type* const first = dest.set_ + block_shift;
        const block_type* base = source.set_ + source.blocks_ - 1 - block_shift;

        if(bit_shift == 0) {
          // Shift by unit strides
          while(last >= first)
            *last-- = *base--;
        } else {
          // Shift by non-unit strides
          const block_type* base1 = base - 1;
          const size_type reverse_bit_shift = block_bits - bit_shift;
          while(last > first) {
            *last-- = (*base << bit_shift) | (*base1 >> reverse_bit_shift);
            base = base1--;
          }
          *last-- = (*base << bit_shift);
        }

        // Zero the head
        while(last >= dest.set_)
          *last-- = zero;

        // Zero the tail
        const size_type extra_bits = dest.size_ % block_bits;
        if (extra_bits != 0)
            dest.set_[dest.blocks_ - 1] &= ~(xffff << extra_bits);
      }

      static void right_shift(Bitset<Block>& dest, const Bitset<Block>& source, size_type n) {
        // Compute shifts
        size_type  const block_shift = block_index(n);
        size_type const bit_shift = bit_index(n);

        // Compute iterator ranges
        const block_type* base = source.set_ + block_shift;
        block_type* first = dest.set_;
        const block_type* const end = dest.set_ + dest.blocks_;
        const block_type* const last = end - 1 - block_shift;

        if (bit_shift == 0) {
          // Shift by unit strides
          while(first <= last)
              *first++ = *base++;
        } else {
          // Shift by non-unit strides
            size_type const reverse_bit_shift = block_bits - bit_shift;
            const block_type* base1 = base + 1;

            while(first < last) {
                *first++ = (*base >> bit_shift) | (*base1  << reverse_bit_shift);
                base = base1++;
            }
            *first++ = *base >> bit_shift;
        }

        // Zero the tail
        while(first < end)
          *first++ = zero;
      }


    public:

      Bitset<Block>& operator<<=(size_type n) {
        if(n >= size_)
          reset();
        else if(n > 0ul)
          left_shift(*this, *this, n);
        return *this;
      }

      Bitset<Block> operator<<(size_type n) {
        Bitset<Block> temp = Bitset<Block>(size_);
        if(n < size_)
          left_shift(temp, *this, n);
        return temp;
      }

      Bitset<Block>& operator>>=(size_type n) {
        if(n >= size_)
          reset();
        else if(n > 0ul)
          right_shift(*this, *this, n);
        return *this;
      }

      Bitset<Block> operator>>(size_type n) {
        Bitset<Block> temp = Bitset<Block>(size_);
        if(n < size_)
          right_shift(temp, *this, n);
        return temp;
      }


      const_reference operator[](size_type i) const {
        TA_ASSERT(i < size_);
        return mask(i) & set_[block_index(i)];
      }

      reference operator[](size_type i) {
        TA_ASSERT(i < size_);
        return reference(set_[block_index(i)], mask(i));
      }

      operator bool() const {
        const block_type* const end = set_ + blocks_;
        for(const block_type* first = set_; first != end; ++first)
          if(*first)
            return true;

        return false;
      }

      bool operator!() const {
        const block_type* const end = set_ + blocks_;
        for(const block_type* first = set_; first != end; ++first)
          if(*first)
            return false;

        return true;
      }

      const_iterator begin() const {
        return const_iterator(0, ConstTransformOp(*this));
      }

      iterator begin() {
        return iterator(0, TransformOp(*this));
      }

      const_iterator end() const {
        return const_iterator(size_, ConstTransformOp(*this));
      }

      iterator end() {
        return iterator(size_, TransformOp(*this));
      }


      void set(size_type i, bool value = true) {
        TA_ASSERT(i < size_);
        if(value)
          set_[block_index(i)] |= mask(i);
        else
          reset(i);
      }


      void set() {
        std::fill_n(set_, blocks_, xffff);

        // Zero the tail
        const size_type extra_bits = bit_index(size_);
        if (extra_bits != 0)
            set_[blocks_ - 1] &= ~(xffff << extra_bits);
      }


      void set_range(size_type first, size_type last) {
        if(last >= size_)
          last = size_ - 1;
        TA_ASSERT(first < last);

        // Get iterator and shift values
        block_type* first_block = set_ + block_index(first);
        const size_type first_shift = bit_index(first);
        block_type* const last_block = set_ + block_index(last);
        const size_type last_shift = block_bits - bit_index(last) - 1;

        // Set the first and last bits
        if(first_block == last_block) {
          *first_block |= (xffff << first_shift) & (xffff >> last_shift);
        } else {
          *first_block++ |= (xffff << first_shift);
          *last_block |= (xffff >> last_shift);
        }

        // Set all blocks between the first and last blocks.
        while(first_block < last_block)
          *first_block++ = xffff;
      }


      void set_stride(size_type first, size_type stride) {
        for(; first < size_; first += stride)
          set_[block_index(first)] |= mask(first);
      }


      void reset(size_type i) {
        TA_ASSERT(i < size_);
        set_[block_index(i)] &= ~mask(i);
      }


      void reset() {
        std::fill_n(set_, blocks_, zero);
      }


      void flip(size_type i) {
        TA_ASSERT(i < size_);
        set_[block_index(i)] ^= mask(i);
      }


      void flip() {
        for(size_type i = 0; i < blocks_; ++i)
          set_[i] = ~set_[i];
      }


      size_type count() const {
        size_type c = 0ul;
        for(size_type i = 0ul; i < blocks_; ++i) {
          block_type v = set_[i]; // temp
          v = v - ((v >> 1) & xffff / 3);
          v = (v & xffff / 15 * 3) + ((v >> 2) & xffff / 15 * 3);
          v = (v + (v >> 4)) & xffff / 255 * 15;
          c += block_type(v * (xffff / 255)) >> (sizeof(block_type) - 1) * CHAR_BIT; // count
        }
        return c;
      }


      const block_type* get() const { return set_; }



      block_type* get() { return set_; }


      size_type size() const { return size_; }


      size_type num_blocks() const { return blocks_; }

      void swap(Bitset_& other) {
        std::swap(size_, other.size_);
        std::swap(blocks_, other.blocks_);
        std::swap(set_, other.set_);
      }

    private:


      static size_type block_index(size_type i) { return i / block_bits; }


      static size_type bit_index(size_type i) { return i % block_bits; }


      static block_type mask(size_type i) { return one << bit_index(i); }

      size_type size_;    
      size_type blocks_;  
      block_type* set_;   
    }; // class Bitset

    template <typename B>
    inline void swap(Bitset<B>& b0, Bitset<B>& b1) {
      b0.swap(b1);
    }

    // Bitset static constant data
    template <typename Block>
    const std::size_t Bitset<Block>::block_bits =
        8ul * sizeof(typename Bitset<Block>::block_type);
    template <typename Block>
    const Block Bitset<Block>::zero = Block(0);
    template <typename Block>
    const Block Bitset<Block>::one = Block(1);
    template <typename Block>
    const Block Bitset<Block>::xffff = ~Block(0);


    template <typename Block>
    Bitset<Block> operator&(Bitset<Block> left, const Bitset<Block>& right) {
      left &= right;
      return left;
    }


    template <typename Block>
    Bitset<Block> operator|(Bitset<Block> left, const Bitset<Block>& right) {
      left |= right;
      return left;
    }



    template <typename Block>
    Bitset<Block> operator^(Bitset<Block> left, const Bitset<Block>& right) {
      left ^= right;
      return left;
    }

    template <typename Block>
    std::ostream& operator<<(std::ostream& os, const Bitset<Block>& bitset) {
      os << std::hex;
      for(long i = bitset.num_blocks() - 1l; i >= 0l; --i)
        os << std::setfill('0') << std::setw(sizeof(Block)*2) << bitset.get()[i] << " ";

      os << std::setbase(10) << std::setw(0);
      return os;
    }


  } // namespace detail
} // namespace TiledArray

#endif // TILEDARRAY_BITSET_H__INCLUDED