bitset.h

Go to the documentation of this file.

/******************************************************************************
The MIT License(MIT)

Embedded Template Library.

Copyright(c) 2014 jwellbelove

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.
******************************************************************************/

#ifndef __ETL_BITSET__
#define __ETL_BITSET__

#include <algorithm>
#include <iterator>
#include <string.h>
#include <stdint.h>
#include <stddef.h>

#include "integral_limits.h"
#include "smallest.h"
#include "array.h"
#include "nullptr.h"
#include "log.h"
#include "ibitset.h"

#if WIN32
#undef min
#endif

//*****************************************************************************
//*****************************************************************************

namespace etl
{
  //*************************************************************************
  //*************************************************************************
  template <const size_t N>
  class bitset : public ibitset
  {
  public:

    //*************************************************************************
    //*************************************************************************
    class bit_reference
    {
    public:

      friend class bitset<N>;

      //*******************************
      //*******************************
      operator bool() const
      {
        return p_bitset->test(position);
      }

      //*******************************
      //*******************************
      bit_reference& operator = (bool b)
      {
        p_bitset->set(position, b);
        return *this;
      }

      //*******************************
      //*******************************
      bit_reference& operator = (const bit_reference& r)
      {
        p_bitset->set(position, bool(r));
        return *this;
      }

      //*******************************
      //*******************************
      bit_reference& flip()
      {
        p_bitset->flip(position);
        return *this;
      }

      //*******************************
      //*******************************
      bool operator~() const
      {
        return !p_bitset->test(position);
      }

    private:

      //*******************************
      //*******************************
      bit_reference()
        : p_bitset(nullptr),
          position(0)
      {
      }

      //*******************************
      //*******************************
      bit_reference(bitset<N>& r_bitset, size_t position)
        : p_bitset(&r_bitset),
          position(position)
      {
      }

      bitset<N>* p_bitset; 
      size_t     position; 
    };

    //*************************************************************************
    //*************************************************************************
    class iterator : public std::iterator<std::random_access_iterator_tag, bool>
    {
    public:

      friend class bitset<N>;
      friend class const_iterator;

      //*******************************
      //*******************************
      iterator()
        : position(0)
      {
      }

      //*******************************
      //*******************************
      iterator(const iterator& other)
        : position(other.position)
      {
      }

      //*******************************
      //*******************************
      iterator& operator ++()
      {
        ++position;
                return *this;
      }

      //*******************************
      //*******************************
      iterator operator ++(int)
      {
        iterator temp(*this);
        ++position;
        return temp;
      }

      //*******************************
      //*******************************
      iterator& operator --()
      {
        --position;
                return *this;
      }

      //*******************************
      //*******************************
      iterator operator --(int)
      {
        iterator temp(*this);
        --position;
        return temp;
      }

      //*******************************
      //*******************************
      bit_reference operator *()
      {
        return bit_reference(*p_bitset, position);
      }

      //*******************************
      //*******************************
      bool operator *() const
      {
        return p_bitset->test(position);
      }

      //*******************************
      //*******************************
      iterator& operator +=(int i)
      {
        position += i;
        return *this;
      }

      //*******************************
      //*******************************
      iterator& operator -=(int i)
      {
        position -= i;
        return *this;
      }

      //*******************************
      //*******************************
      iterator& operator =(const iterator& other)
      {
        position = other.position;
        p_bitset = other.p_bitset;
        return *this;
      }

      //*******************************
      //*******************************
      friend iterator operator +(const iterator& other, int i)
      {
        iterator temp(other);
        temp += i;
        return temp;
      }

      //*******************************
      //*******************************
      friend iterator operator -(const iterator& other, int i)
      {
        iterator temp(other);
        temp -= i;
        return temp;
      }

      //*******************************
      //*******************************
      friend bool operator ==(const iterator& lhs, const iterator& rhs)
      {
        return lhs.position == rhs.position;
      }

      //*******************************
      //*******************************
      friend bool operator !=(const iterator& lhs, const iterator& rhs)
      {
        return lhs.position != rhs.position;
      }

      //*******************************
      //*******************************
      friend bool operator <(const iterator& lhs, const iterator& rhs)
      {
        return lhs.position < rhs.position;
      }

      //*******************************
      //*******************************
      friend bool operator >(const iterator& lhs, const iterator& rhs)
      {
        return lhs.position > rhs.position;
      }

      //*******************************
      //*******************************
      friend bool operator <=(const iterator& lhs, const iterator& rhs)
      {
        return lhs.position <= rhs.position;
      }

      //*******************************
      //*******************************
      friend bool operator >=(const iterator& lhs, const iterator& rhs)
      {
        return lhs.position >-rhs.position;
      }

    private:

      //*******************************
      //*******************************
      iterator(bitset<N>& r_bitset, size_t position)
        : p_bitset(&r_bitset),
          position(position)
      {}

      bitset<N>* p_bitset;
      size_t     position;
    };

    //*************************************************************************
    //*************************************************************************
    class const_iterator : public std::iterator<std::random_access_iterator_tag, const bool>
    {
    public:

      friend class bitset<N>;

      //*******************************
      //*******************************
      const_iterator()
        : position(0)
      {
      }

      //*******************************
      //*******************************
      const_iterator(const typename bitset<N>::iterator& other)
        : position(other.position)
      {
      }

      //*******************************
      //*******************************
      const_iterator(const const_iterator& other)
        : position(other.position)
      {
      }

      //*******************************
      //*******************************
      const_iterator& operator ++()
      {
        ++position;
                return *this;
      }

      //*******************************
      //*******************************
      const_iterator operator ++(int)
      {
        const_iterator temp(*this);
        ++position;
        return temp;
      }

      //*******************************
      //*******************************
      const_iterator& operator --()
      {
        --position;
                return *this;
      }

      //*******************************
      //*******************************
      const_iterator operator --(int)
      {
        const_iterator temp(*this);
        --position;
        return temp;
      }

      //*******************************
      //*******************************
      bool operator *() const
      {
        return p_bitset->test(position);
      }

      //*******************************
      //*******************************
      const_iterator& operator +=(int i)
      {
        position += i;
        return *this;
      }

      //*******************************
      //*******************************
      const_iterator& operator -=(int i)
      {
        position -= i;
        return *this;
      }

      //*******************************
      //*******************************
      const_iterator& operator =(const const_iterator& other)
      {
        position = other.position;
        p_bitset = other.p_bitset;
        return *this;
      }

      //*******************************
      //*******************************
      friend const_iterator operator +(const const_iterator& other, int i)
      {
        const_iterator temp(other);
        temp += i;
        return temp;
      }

      //*******************************
      //*******************************
      friend const_iterator operator -(const const_iterator& other, int i)
      {
        const_iterator temp(other);
        temp -= i;
        return temp;
      }

      //*******************************
      //*******************************
      friend bool operator ==(const const_iterator& lhs, const const_iterator& rhs)
      {
        return lhs.position == rhs.position;
      }

      //*******************************
      //*******************************
      friend bool operator !=(const const_iterator& lhs, const const_iterator& rhs)
      {
        return lhs.position != rhs.position;
      }

      //*******************************
      //*******************************
      friend bool operator <(const const_iterator& lhs, const const_iterator& rhs)
      {
        return lhs.position < rhs.position;
      }

      //*******************************
      //*******************************
      friend bool operator >(const const_iterator& lhs, const const_iterator& rhs)
      {
        return lhs.position > rhs.position;
      }

      //*******************************
      //*******************************
      friend bool operator <=(const const_iterator& lhs, const const_iterator& rhs)
      {
        return lhs.position <= rhs.position;
      }

      //*******************************
      //*******************************
      friend bool operator >=(const const_iterator& lhs, const const_iterator& rhs)
      {
        return lhs.position >- rhs.position;
      }

    private:

      //*******************************
      //*******************************
      const_iterator(bitset<N>& r_bitset, size_t position)
        : p_bitset(&r_bitset),
          position(position)
      {
      }

      bitset<N>* p_bitset;
      size_t     position;
    };

    //*************************************************************************
    //*************************************************************************
    bitset()
    {
      reset();
    }

    //*************************************************************************
    //*************************************************************************
    bitset(const bitset<N>& other)
    {
      data = other.data;
    }

    //*************************************************************************
    //*************************************************************************
    bitset(unsigned long long value)
    {
      reset();

      const size_t SHIFT = (integral_limits<unsigned long long>::bits <= BITS_PER_ELEMENT) ? 0 : BITS_PER_ELEMENT;

      // Can we do it in one hit?
      if (SHIFT == 0)
      {
        data[0] = value;
      }
      else
      {
        size_t i = 0;

        while ((value != 0) && (i < ARRAY_SIZE))
        {
          data[i++] = value & ALL_SET;
          value = value >> SHIFT;
        }
      }

      data.back() &= TOP_MASK;
    }

    //*************************************************************************
    //*************************************************************************
    bitset(const char* text)
    {
      reset();

      size_t i = std::min(N, strlen(text));

      while (i > 0)
      {
        set(--i, *text++ == '1');
      }
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N>& set()
    {
      data.fill(ALL_SET);
      data.back() &= TOP_MASK;

      return *this;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N>& set(size_t position, bool value = true)
    {     
      if (position < N)
      {
        size_t       index;
        element_type bit;

        if (ARRAY_SIZE == 1)
        {
          index = 0;
          bit   = element_type(1) << position;
        }
        else
        {
          index = position >> log2<BITS_PER_ELEMENT>::value;
          bit   = element_type(1) << (position & (BITS_PER_ELEMENT - 1));
        }

        if (value)
        {
          data[index] |= bit;
        }
        else
        {
          data[index] &= ~bit;
        }
      }

      return *this;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N>&  set(const char* text)
    {
      reset();

      size_t i = std::min(N, strlen(text));

      while (i > 0)
      {
        set(--i, *text++ == '1');
      }

      return *this;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N>& reset()
    {
      data.fill(ALL_CLEAR);
      return *this;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N>& reset(size_t position)
    {
      if (position < N)
      {
        size_t       index;
        element_type bit;

        if (ARRAY_SIZE == 1)
        {
          index = 0;
          bit   = element_type(1) << position;
        }
        else
        {
          index = position >> log2<BITS_PER_ELEMENT>::value;
          bit   = element_type(1) << (position & (BITS_PER_ELEMENT - 1));
        }

        data[index] &= ~bit;
      }

      return *this;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N>& flip()
    {
      for (size_t i = 0; i < ARRAY_SIZE; ++i)
      {
        data[i] = ~data[i];
      }

      data.back() &= TOP_MASK;

      return *this;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N>& flip(size_t position)
    {
      if (position < N)
      {
        size_t       index;
        element_type bit;

        if (ARRAY_SIZE == 1)
        {
          index = 0;
          bit   = element_type(1) << position;
        }
        else
        {
          index = position >> log2<BITS_PER_ELEMENT>::value;
          bit   = element_type(1) << (position & (BITS_PER_ELEMENT - 1));
        }

        data[index] ^= bit;
      }

      return *this;
    }

    //*************************************************************************
    //*************************************************************************
    bool operator[] (size_t position) const
    {
      return test(position);
    }

    //*************************************************************************
    //*************************************************************************
    bit_reference operator [] (size_t position)
    {
      return bit_reference(*this, position);
    }

    //*************************************************************************
    //*************************************************************************
    bool test(size_t position) const
    {
      if (position < N)
      {
        size_t       index;
        element_type bit;

        if (ARRAY_SIZE == 1)
        {
          index = 0;
          bit   = element_type(1) << position;
        }
        else
        {
          index = position >> log2<BITS_PER_ELEMENT>::value;
          bit   = element_type(1) << (position & (BITS_PER_ELEMENT - 1));
        }

        return (data[index] & bit) != 0;
      }
      else
      {
        return false;
      }
    }

    //*************************************************************************
    // Are all the bits sets?
    //*************************************************************************
    bool all() const
    {
      // All but the last.
      for (size_t i = 0; i < (ARRAY_SIZE - 1); ++i)
      {
        if (data[i] != ALL_SET)
        {
          return false;
        }
      }

      // The last.
      if (data[ARRAY_SIZE - 1] != (ALL_SET & TOP_MASK))
      {
        return false;
      }

      return true;
    }

    //*************************************************************************
    //*************************************************************************
    bool any() const
    {
      return !none();
    }

    //*************************************************************************
    //*************************************************************************
    bool none() const
    {
      for (size_t i = 0; i < ARRAY_SIZE; ++i)
      {
        if (data[i] != 0)
        {
          return false;
        }
      }

      return true;
    }

    //*************************************************************************
    //*************************************************************************
    size_t count() const
    {
      size_t n = 0;

      for (size_t i = 0; i < ARRAY_SIZE; ++i)
      {
        element_type value = data[i];

        while (value != 0)
        {
          n += (value & 1);

          value >>= 1;
        }
      }

      return n;
    }

    //*************************************************************************
    //*************************************************************************
    size_t size() const
    {
      return N;
    }

    //*************************************************************************
    //*************************************************************************
    size_t find_first(bool state) const
    {
      return find_next(state, 0);
    }

    //*************************************************************************
    //*************************************************************************
    size_t find_next(bool state, size_t position) const
    {
      // Where to start.
      size_t element_index = position >> log2<BITS_PER_ELEMENT>::value;
      size_t bit_index     = position &  log2<BITS_PER_ELEMENT>::value;;
      element_type mask    = 1 << bit_index;

      // For each element in the bitset...
      while (element_index < ARRAY_SIZE)
      {
        const element_type& element = data[element_index];

        // For each bit in the element...
        while ((bit_index < BITS_PER_ELEMENT) && (position != N))
        {
          // Equal to the required state?
          if (((element & mask) != 0) == state)
          {
            return position;
          }

          // Move on to the next bit.
          mask <<= 1;
          ++position;
          ++bit_index;
        }

        // Start at the beginning for all other elements.
        bit_index = 0;
        mask      = 1;

        ++element_index;
      }

      return N;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N>& operator &=(const bitset<N>& other)
    {
      for (size_t i = 0; i < ARRAY_SIZE; ++i)
      {
        data[i] &= other.data[i];
      }

      return *this;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N>& operator |=(const bitset<N>& other)
    {
      for (size_t i = 0; i < ARRAY_SIZE; ++i)
      {
        data[i] |= other.data[i];
      }

      return *this;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N>& operator ^=(const bitset<N>& other)
    {
      for (size_t i = 0; i < ARRAY_SIZE; ++i)
      {
        data[i] ^= other.data[i];
      }

      return *this;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N> operator ~() const
    {
      bitset<N> temp;

      for (size_t i = 0; i < ARRAY_SIZE; ++i)
      {
        temp[i] = ~data[i];
      }

      return temp;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N> operator<<(size_t shift) const
    {
      bitset<N> temp;

      if (ARRAY_SIZE == 1)
      {
        temp.data[0] = data[0] << shift;
      }
      else
      {
        size_t source      = N - shift - 1;
        size_t destination = N - 1;

        for (size_t i = 0; i < (N - shift); ++i)
        {
          temp.set(destination--, test(source--));
        }
      }

      return temp;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N>& operator<<=(size_t shift)
    {
      if (ARRAY_SIZE == 1)
      {
        data[0] <<= shift;
      }
      else
      {
        size_t source      = N - shift - 1;
        size_t destination = N - 1;

        for (size_t i = 0; i < (N - shift); ++i)
        {
          set(destination--, test(source--));
        }

        for (size_t i = 0; i < shift; ++i)
        {
          reset(destination--);
        }
      }

      return *this;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N> operator>>(size_t shift) const
    {
      bitset<N> temp;

      if (ARRAY_SIZE == 1)
      {
        temp.data[0] = data[0] >> shift;
      }
      else
      {
        size_t source      = shift;
        size_t destination = 0;

        while (source != N)
        {
          temp.set(destination++, test(source++));
        }
      }

      return temp;
    }

    //*************************************************************************
    //*************************************************************************
    bitset<N>& operator>>=(size_t shift)
    {
      if (ARRAY_SIZE == 1)
      {
        data[0] >>= shift;
      }
      else
      {
        size_t source      = shift;
        size_t destination = 0;

        for (size_t i = 0; i < (N - shift); ++i)
        {
          set(destination++, test(source++));
        }

        for (size_t i = 0; i < shift; ++i)
        {
          reset(destination++);
        }
      }

      return *this;
    }

    //*************************************************************************
    //*************************************************************************
    void swap(bitset<N>& other)
    {
      data.swap(other.data);
    }

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

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

    //*************************************************************************
    //*************************************************************************
    const_iterator cbegin()
    {
      return const_iterator(*this, 0);
    }

    //*************************************************************************
    //*************************************************************************
    iterator end()
    {
      return iterator(*this, N - 1);
    }

    //*************************************************************************
    //*************************************************************************
    const_iterator end() const
    {
      return const_iterator(*this, N - 1);
    }

    //*************************************************************************
    //*************************************************************************
    const_iterator cend()
    {
      return const_iterator(*this, N - 1);
    }


    //*************************************************************************
    //*************************************************************************
    friend bool operator == (const bitset<N>& lhs, const bitset<N>& rhs)
    {
      for (size_t i = 0; i < ARRAY_SIZE; ++i)
      {
        if (lhs.data[i] != rhs.data[i])
        {
          return false;
        }
      }

      return true;
    }

  private:
       
    // The type used for each element in the array.
    typedef typename smallest_uint_for_bits<N>::type element_type;

    static const element_type ALL_SET          = etl::integral_limits<element_type>::max;
    static const element_type ALL_CLEAR        = 0;
    static const size_t       BITS_PER_ELEMENT = etl::integral_limits<element_type>::bits;
    static const size_t       ARRAY_SIZE       = (N % BITS_PER_ELEMENT == 0) ? N / BITS_PER_ELEMENT : N / BITS_PER_ELEMENT + 1;
    static const size_t       TOTAL_BITS       = ARRAY_SIZE * BITS_PER_ELEMENT;
    static const size_t       TOP_MASK_SHIFT   = ((BITS_PER_ELEMENT - (TOTAL_BITS - N)) % BITS_PER_ELEMENT);
    static const element_type TOP_MASK         = element_type(TOP_MASK_SHIFT == 0 ? ALL_SET : ~(ALL_SET << TOP_MASK_SHIFT));

    etl::array<element_type, ARRAY_SIZE> data;
  };

  //***************************************************************************
  //***************************************************************************
  template <const size_t N>
  bitset<N> operator & (const bitset<N>& lhs, const bitset<N>& rhs)
  {
    bitset<N> temp(lhs);
    temp &= rhs;
    return temp;
  }

  //***************************************************************************
  //***************************************************************************
  template<const size_t N>
  bitset<N> operator | (const bitset<N>& lhs, const bitset<N>& rhs)
  {
    bitset<N> temp(lhs);
    temp |= rhs;
    return temp;
  }

  //***************************************************************************
  //***************************************************************************
  template<const size_t N>
  bitset<N> operator ^ (const bitset<N>& lhs, const bitset<N>& rhs)
  {
    bitset<N> temp(lhs);
    temp ^= rhs;
    return temp;
  }

  //***************************************************************************
  //***************************************************************************
  template<const size_t N>
  bool operator != (const bitset<N>& lhs, const bitset<N>& rhs)
  {
    return !(lhs == rhs);
  }
}

//*************************************************************************
//*************************************************************************
template <const size_t N>
void swap(etl::bitset<N>& lhs, etl::bitset<N>& rhs)
{
  lhs.swap(rhs);
}

#if WIN32
#define min(a,b) (((a) < (b)) ? (a) : (b))
#endif

#endif