/******************************************************************************\
* Copyright (c) 2016, Robert van Engelen, Genivia Inc. All rights reserved.    *
*                                                                              *
* Redistribution and use in source and binary forms, with or without           *
* modification, are permitted provided that the following conditions are met:  *
*                                                                              *
*   (1) Redistributions of source code must retain the above copyright notice, *
*       this list of conditions and the following disclaimer.                  *
*                                                                              *
*   (2) Redistributions in binary form must reproduce the above copyright      *
*       notice, this list of conditions and the following disclaimer in the    *
*       documentation and/or other materials provided with the distribution.   *
*                                                                              *
*   (3) The name of the author may not be used to endorse or promote products  *
*       derived from this software without specific prior written permission.  *
*                                                                              *
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED *
* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF         *
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO   *
* EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,       *
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;  *
* OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,     *
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR      *
* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF       *
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.                                   *
\******************************************************************************/

/**
@file      bits.h
@brief     RE/flex operations on dynamic bit vectors
@author    Robert van Engelen - engelen@genivia.com
@copyright (c) 2016-2020, Robert van Engelen, Genivia Inc. All rights reserved.
@copyright (c) BSD-3 License - see LICENSE.txt
*/

#ifndef REFLEX_BITS_H
#define REFLEX_BITS_H

#include <cstring>

#if defined(__WIN32__) || defined(_WIN32) || defined(WIN32) || defined(_WIN64) || defined(__BORLANDC__)
namespace reflex {
typedef unsigned __int8  uint8_t;
typedef unsigned __int16 uint16_t;
typedef unsigned __int32 uint32_t;
typedef unsigned __int64 uint64_t;
}
#elif !defined(CONFIG_H)
# include <stdint.h>
#endif

namespace reflex {

/// RE/flex Bits class for dynamic bit vectors.
/**
Dynamic bit vectors are stored in Bits objects, which can be manipulated
with the usual bit-operations (`|` (bitor), `&` (bitand), `^` (bitxor)).
Supports comparison relations on bit vectors, check if all bits set, check if
any bits are set, flip bits, shift bits left or right, count bits, check if a
bit vectors intersects another, check if a bit vector contains another.
find_first bit, find_next bit.

Example:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~{.cpp}
    reflex::Bits digit('0', '9'); // bits '0' (48th bit) to '9' (57th bit)
    reflex::Bits upper('A', 'Z'); // bits 'A' (65th bit) to 'Z' (92th bit)
    reflex::Bits lower('a', 'z'); // bits 'a' (97th bit) to 'z' (122th bit)
    if (upper.intersects(lower) == false)
      std::cout << "upper and lower are disjoint\n";
    reflex::Bits alnum = digit | upper | lower;
    if (alnum.contains(digit) == true)
      std::cout << "digit is a subset of alnum\n";
    if (alnum['_'] == false)
      std::cout << "_ is not in alnum\n";
    alnum['_'] = true;
    if (alnum['_'] == true)
      std::cout << "_ is in updated alnum\n";
    std::cout << alnum.count() << " bits in alnum\n";
    for (size_t i = alnum.find_first(); i != reflex::Bits::npos; i = alnum.find_next(i))
      std::cout << (char)i;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Output:

    upper and lower are disjoint
    digit is a subset of alnum
    _ is not in alnum
    _ is in updated alnum
    63 bits in alnum
    0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz

*/
class Bits {
 public:
  static const size_t npos = static_cast<size_t>(-1); ///< npos returned by find_first() and find_next()
  /// References a single bit, returned by operator[].
  struct Bitref {
    Bitref(
        size_t    n, ///< n'th bit
        uint64_t *p) ///< in this word
      :
        m(1ULL << n),
        p(p)
    { }
    uint64_t  m; ///< mask m = 2^n
    uint64_t *p; ///< in this word
    /// Returns bit value.
    operator bool() const
      /// @returns bit value true or false.
    {
      return (*p & m) != 0;
    }
    /// Assign bit value.
    const Bitref& operator=(bool b) ///< bit to assign
      /// @returns result value true or false.
      const
    {
      if (b)
        *p |= m;
      else
        *p &= ~m;
      return *this;
    }
    /// Bit-or bit value.
    bool operator|=(bool b) ///< bit-or with this bit
      /// @returns result value true or false.
      const
    {
      if (b)
        *p |= m;
      return (*p & m) != 0;
    }
    /// Bit-and bit value.
    bool operator&=(bool b) ///< bit-and with this bit
      /// @returns result value true or false.
      const
    {
      if (!b)
        *p &= ~m;
      return (*p & m) != 0;
    }
    /// Bit-xor bit value.
    bool operator^=(bool b) ///< bit-xor with this bit
      /// @returns result value true or false.
      const
    {
      if (b)
        *p ^= m;
      return (*p & m) != 0;
    }
  };
  /// Construct an empty bit vector.
  Bits()
    :
      len_(0),
      vec_(NULL)
  { }
  /// Copy constructor
  Bits(const Bits& bits) ///< bits to copy
  {
    operator=(bits);
  }
  /// Construct a bit vector and set n'th bit.
  Bits(size_t n) ///< n'th bit to set
    :
      len_(0),
      vec_(NULL)
  {
    insert(n);
  }
  /// Construct a bit vector and set a range of bits n1'th to n2'th.
  Bits(
      size_t n1, ///< first bit to set
      size_t n2) ///< last bit to set
    :
      len_(0),
      vec_(NULL)
  {
    insert(n1, n2);
  }
  /// Destroy bits.
  ~Bits()
  {
    if (vec_)
      delete[] vec_;
  }
  /// Assign bits.
  Bits& operator=(const Bits& bits) ///< bits to copy
    /// @returns reference to this object.
  {
    len_ = bits.len_;
    if (len_)
      std::memcpy(vec_ = new uint64_t[len_], bits.vec_, len_ << 3);
    else
      vec_ = NULL;
    return *this;
  }
  /// Reference n'th bit in the bit vector to assign a value to that bit.
  Bitref operator[](size_t n) ///< n'th bit
    /// @returns bit reference to assign.
  {
    alloc((n >> 6) + 1);
    return Bitref(n & 0x3F, &vec_[n >> 6]);
  }
  /// Returns n'th bit.
  bool operator[](size_t n) ///< n'th bit to return
    /// @returns true if n'th bit is set, false otherwise.
    const
  {
    return n >> 6 < len_ && (vec_[n >> 6] & 1ULL << (n & 0x3F)) != 0;
  }
  /// Insert and set a bit in the bit vector.
  Bits& insert(size_t n) ///< n'th bit to set
    /// @returns reference to this object.
  {
    alloc((n >> 6) + 1);
    vec_[n >> 6] |= 1ULL << (n & 0x3F);
    return *this;
  }
  /// Erase a bit in the bit vector.
  Bits& erase(size_t n) ///< n'th bit to erase
    /// @returns reference to this object.
  {
    if (n >> 6 < len_)
      vec_[n >> 6] &= ~(1ULL << (n & 0x3F));
    return *this;
  }
  /// Flips a bit in the bit vector.
  Bits& flip(size_t n) ///< n'th bit to flip
    /// @returns reference to this object.
  {
    alloc((n >> 6) + 1);
    vec_[n >> 6] ^= 1ULL << (n & 0x3F);
    return *this;
  }
  /// Insert and set a range of bits in the bit vector.
  Bits& insert(
      size_t n1, ///< first bit to set
      size_t n2) ///< last bit to set
    /// @returns reference to this object.
  {
    alloc((n2 >> 6) + 1);
    for (size_t i = n1; i <= n2; ++i)
      vec_[i >> 6] |= 1ULL << (i & 0x3F);
    return *this;
  }
  /// Erase a range of bits in the bit vector.
  Bits& erase(
      size_t n1, ///< first bit to erase
      size_t n2) ///< last bit to erase
    /// @returns reference to this object.
  {
    if (n1 >> 6 < len_)
    {
      if (n2 >> 6 >= len_)
        n2 = (len_ - 1) << 6;
      for (size_t i = n1; i <= n2; ++i)
        vec_[i >> 6] &= ~(1ULL << (i & 0x3F));
    }
    return *this;
  }
  /// Flip a range of bits in the bit vector.
  Bits& flip(
      size_t n1, ///< first bit to flip
      size_t n2) ///< last bit to flip
    /// @returns reference to this object.
  {
    alloc((n2 >> 6) + 1);
    for (size_t i = n1; i <= n2; ++i)
      vec_[i >> 6] ^= 1ULL << (i & 0x3F);
    return *this;
  }
  /// Bit-shift left by one.
  Bits& lshift()
  {
    if (len_ > 0)
    {
      uint64_t lo = 0;
      for (size_t i = 0; i < len_; ++i)
      {
        uint64_t hi = vec_[i] & (1ULL << 63);
        vec_[i] = (vec_[i] << 1) | lo;
        lo = hi >> 63;
      }
      if (lo)
      {
        alloc(len_ + 1);
        vec_[len_ - 1] = 1;
      }
    }
    return *this;
  }
  /// Bit-shift right by one.
  Bits& rshift()
  {
    uint64_t hi = 0;
    for (size_t i = 1; i <= len_; ++i)
    {
      uint64_t lo = vec_[len_ - i] & 1;
      vec_[len_ - i] = (vec_[len_ - i] >> 1) | hi;
      hi = lo << 63;
    }
    return *this;
  }
  /// Bit-or (set union) the bit vector with the given bits.
  Bits& operator|=(const Bits& bits) ///< bits
    /// @returns reference to this object.
  {
    alloc(bits.len_);
    for (size_t i = 0; i < bits.len_; ++i)
      vec_[i] |= bits.vec_[i];
    return *this;
  }
  /// Bit-and (set intersection) the bit vector with the given bits.
  Bits& operator&=(const Bits& bits) ///< bits
    /// @returns reference to this object.
  {
    alloc(bits.len_);
    for (size_t i = 0; i < bits.len_; ++i)
      vec_[i] &= bits.vec_[i];
    for (size_t i = bits.len_; i < len_; ++i)
      vec_[i] = 0;
    return *this;
  }
  /// Bit-xor the bit vector with the given bits.
  Bits& operator^=(const Bits& bits) ///< bits
    /// @returns reference to this object.
  {
    alloc(bits.len_);
    for (size_t i = 0; i < bits.len_; ++i)
      vec_[i] ^= bits.vec_[i];
    return *this;
  }
  /// Bit-delete (set minus) the bit vector with the given bits.
  Bits& operator-=(const Bits& bits) ///< bits
    /// @returns reference to this object.
  {
    size_t k = len_;
    if (bits.len_ < k)
      k = bits.len_;
    for (size_t i = 0; i < k; ++i)
      vec_[i] = (vec_[i] | bits.vec_[i]) - bits.vec_[i];
    return *this;
  }
  /// Bit-or (set union) of two bit vectors.
  Bits operator|(const Bits& bits) ///< bits
    /// @returns bit vector of the result.
    const
  {
    return Bits(*this) |= bits;
  }
  /// Bit-and (set intersection) of two bit vectors.
  Bits operator&(const Bits& bits) ///< bits
    /// @returns bit vector of the result.
    const
  {
    return Bits(*this) &= bits;
  }
  /// Bit-xor of two bit vectors.
  Bits operator^(const Bits& bits) ///< bits
    /// @returns bit vector of the result.
    const
  {
    return Bits(*this) ^= bits;
  }
  /// Bit-delete (set minus) of two bit vectors.
  Bits operator-(const Bits& bits) ///< bits
    /// @returns bit vector of the result.
    const
  {
    return Bits(*this) -= bits;
  }
  /// Complement of the bit vector with all bits flipped.
  Bits operator~() const
    /// @returns bit vector of the result.
  {
    return Bits(*this).flip();
  }
  /// Returns true if bit vectors are equal.
  bool operator==(const Bits& bits) ///< rhs bits
    /// @returns true (equal) or false (unequal).
    const
  {
    size_t k = len_;
    if (bits.len_ < k)
      k = bits.len_;
    for (size_t i = 0; i < k; ++i)
      if (vec_[i] != bits.vec_[i])
        return false;
    for (size_t i = bits.len_; i < len_; ++i)
      if (vec_[i] != 0)
        return false;
    for (size_t i = len_; i < bits.len_; ++i)
      if (bits.vec_[i] != 0)
        return false;
    return true;
  }
  /// Returns true if bit vectors are unequal.
  bool operator!=(const Bits& bits) ///< rhs bits
    /// @returns true (unequal) or false (equal).
    const
  {
    return !operator==(bits);
  }
  /// Returns true if the bit vector is lexicographically less than the given right-hand side bits.
  bool operator<(const Bits& bits) ///< rhs bits
    /// @returns true (less) or false (greater-or-equal).
    const
  {
    size_t k = len_;
    if (bits.len_ < k)
      k = bits.len_;
    for (size_t i = 0; i < k; ++i)
    {
      if (vec_[i] < bits.vec_[i])
        return true;
      if (vec_[i] > bits.vec_[i])
        return false;
    }
    for (size_t i = bits.len_; i < len_; ++i)
      if (vec_[i] != 0)
        return false;
    for (size_t i = len_; i < bits.len_; ++i)
      if (bits.vec_[i] != 0)
        return true;
    return false;
  }
  /// Returns true if the bit vector is lexicographically greater than the given right-hand side bits.
  bool operator>(const Bits& bits) ///< rhs bits
    /// @returns true (greater) or false (less-or-equal).
    const
  {
    return bits.operator<(*this);
  }
  /// Returns true if the bit vector is lexicographically less-or-equal to the given right-hand side bits.
  bool operator<=(const Bits& bits) ///< rhs bits
    /// @returns true (less-or-equal) or false (greater).
    const
  {
    return !operator>(bits);
  }
  /// Returns true if the bit vector is lexicographically greater-or-equal to the given right-hand side bits.
  bool operator>=(const Bits& bits) ///< rhs bits
    /// @returns true (greater-or-equal) or false (less).
    const
  {
    return !operator<(bits);
  }
  /// Returns true if all bits are set.
  bool all() const
    /// @returns true if all bits set, false otherwise.
  {
    for (size_t i = 0; i < len_; ++i)
      if (vec_[i] + 1 != 0)
        return false;
    return true;
  }
  /// Returns true if any bit is set.
  bool any() const
    /// @returns true if any bit set, false if none.
  {
    for (size_t i = 0; i < len_; ++i)
      if (vec_[i] != 0)
        return true;
    return false;
  }
  /// Erase all bits.
  Bits& clear()
    /// @returns reference to this object.
  {
    if (vec_)
      std::memset(vec_, 0, len_ << 3);
    return *this;
  }
  /// Flip all bits.
  Bits& flip()
    /// @returns reference to this object.
  {
    for (size_t i = 0; i < len_; ++i)
      vec_[i] = ~vec_[i];
    return *this;
  }
  /// Reserves space in the bit vector for len bits without changing its current content.
  Bits& reserve(size_t len) ///< number of bits to reserve
    /// @returns reference to this object.
  {
    if (len)
      alloc(((len - 1) >> 6) + 1);
    return *this;
  }
  /// Returns the current length of the bit vector.
  size_t size() const
    /// @returns number of bits.
  {
    return len_ << 6;
  }
  /// Returns the number of bits set.
  size_t count() const
    /// @returns number of 1 bits.
  {
    size_t n = 0, k = 0;
    while ((n = find_first(n)) != npos)
      ++n, ++k;
    return k;
  }
  /// Returns true if the bit vector intersects with the given bits, false if the bit vectors are disjoint.
  bool intersects(const Bits& bits) ///< bits
    /// @returns true if bits intersect or false if disjoint.
    const
  {
    size_t k = len_;
    if (bits.len_ < k)
      k = bits.len_;
    for (size_t i = 0; i < k; ++i)
      if (vec_[i] & bits.vec_[i])
        return true;
    return false;
  }
  /// Returns true if the given bits are a subset of the bit vector, i.e. for each bit in bits, the corresponding bit in the bit vector is set.
  bool contains(const Bits& bits) ///< bits
    /// @returns true if bits is a subset.
    const
  {
    size_t k = len_;
    if (bits.len_ < k)
      k = bits.len_;
    for (size_t i = 0; i < k; ++i)
      if (vec_[i] != (vec_[i] | bits.vec_[i]))
        return false;
    for (size_t i = len_; i < bits.len_; ++i)
      if (bits.vec_[i] != 0)
        return false;
    return true;
  }
  /// Returns the position of the first bit set in the bit vector, or Bits::npos if none.
  size_t find_first(size_t n = 0) ///< internal parameter (do not use)
    /// @returns first position or Bits::npos.
    const
  {
    size_t i = n >> 6;
    if (i < len_ && vec_[i])
      for (size_t j = n & 0x3F; j < 64; ++j)
        if (vec_[i] & 1ULL << j)
          return (i << 6) + j;
    for (i = i + 1; i < len_; ++i)
      if (vec_[i])
        for (size_t j = 0; j < 64; ++j)
          if (vec_[i] & 1ULL << j)
            return (i << 6) + j;
    return npos;
  }
  /// Returns the next position of a bit set in the bit vector, or Bits::npos if none.
  size_t find_next(size_t n) ///< the current position to search from
    /// @returns next position or Bits::npos.
    const
  {
    return find_first(n + 1);
  }
  /// Swap bit vectors.
  void swap(Bits& bits) ///< bits
  {
    size_t k = len_;
    uint64_t *p = vec_;
    len_ = bits.len_;
    vec_ = bits.vec_;
    bits.len_ = k;
    bits.vec_ = p;
  }
 private:
  /// On-demand allocator.
  void alloc(size_t len) ///< number of words required
  {
    if (len > len_)
    {
      size_t k = 1;
      while (k < len)
        k <<= 1;
      uint64_t *p = new uint64_t[k]();
      if (vec_)
      {
        std::memcpy(p, vec_, len_ << 3);
        delete[] vec_;
      }
      len_ = k;
      vec_ = p;
    }
  }
  size_t    len_; ///< number of words
  uint64_t *vec_; ///< array of words
};

} // namespace reflex

#endif