/*
  Copyright (C) 2018 David Robillard <d@drobilla.net>
  Copyright (C) 2006-2007 Chris Hamilton <chamilton@cs.dal.ca>

  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 2 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 <https://www.gnu.org/licenses/>.
*/

#ifndef CHILBERT_FIXBITVEC_HPP
#define CHILBERT_FIXBITVEC_HPP

#include "chilbert/Operations.hpp"

#include <cassert>
#include <climits>
#include <cstddef>
#include <cstdint>
#include <iostream>

namespace chilbert {

/* This must be an unsigned integer that is either 32 or 64 bits.  Otherwise,
   there are places in the code that simply will not work.  For speed, this
   should be the native word size. */
typedef uint64_t FBV_UINT;

#define FBV_BITS 64

#define FBV1 (FBV_UINT{1})
#define FBV1S (~FBV_UINT{0})
#define FBVN1S(n) (n == FBV_BITS ? FBV1S : (FBV1 << n) - 1)

class CFixBitVec
{
public:
	CFixBitVec(const size_t bits = FBV_BITS)
	  : m_rack{0}
	{
		assert(bits <= FBV_BITS);
	}

	/// Return the size in bits
	size_t size() const { return FBV_BITS; }

	/// Set all bits to one
	CFixBitVec& set()
	{
		m_rack = FBV1S;
		return *this;
	}

	/// Set all bits to zero
	CFixBitVec& reset()
	{
		m_rack = 0;
		return *this;
	}

	/// Return the value of the `index`th bit
	bool test(const size_t index) const
	{
		assert(index < FBV_BITS);
		return ((m_rack & (FBV1 << index)) > 0);
	}

	/// Set the `index`th bit to 1
	CFixBitVec& set(const size_t index)
	{
		assert(index < FBV_BITS);
		m_rack |= (FBV_UINT{1} << index);
		return *this;
	}

	/// Reset the `index`th bit to 0
	CFixBitVec& reset(const size_t index)
	{
		assert(index < FBV_BITS);
		m_rack &= ~(FBV_UINT{1} << index);
		return *this;
	}

	/// Set the `index`th bit to `value`
	CFixBitVec& set(const size_t index, const bool value)
	{
		assert(index < FBV_BITS);
		m_rack ^= (-FBV_UINT{value} ^ m_rack) & (FBV_UINT{1U} << index);
		return *this;
	}

	/// Flip the value of the `index`th bit
	CFixBitVec& flip(const size_t index)
	{
		assert(index < FBV_BITS);
		m_rack ^= (FBV1 << index);
		return *this;
	}

	bool operator==(const CFixBitVec& vec) const
	{
		return m_rack == vec.m_rack;
	}

	bool operator!=(const CFixBitVec& vec) const
	{
		return m_rack != vec.m_rack;
	}

	bool operator<(const CFixBitVec& vec) const { return m_rack < vec.m_rack; }

	CFixBitVec& operator=(const FBV_UINT i)
	{
		m_rack = i;
		return *this;
	}

	CFixBitVec& operator&=(const CFixBitVec& vec)
	{
		m_rack &= vec.m_rack;
		return *this;
	}

	CFixBitVec operator&(const CFixBitVec& vec) const
	{
		CFixBitVec t(*this);
		t &= vec;
		return t;
	}

	CFixBitVec& operator|=(const CFixBitVec& vec)
	{
		m_rack |= vec.m_rack;
		return *this;
	}

	CFixBitVec operator|(const CFixBitVec& vec) const
	{
		CFixBitVec t(*this);
		t |= vec;
		return t;
	}

	CFixBitVec& operator^=(const CFixBitVec& vec)
	{
		m_rack ^= vec.m_rack;
		return *this;
	}

	CFixBitVec& operator^=(const FBV_UINT i)
	{
		m_rack ^= i;
		return *this;
	}

	CFixBitVec operator^(const CFixBitVec& vec) const
	{
		CFixBitVec t(*this);
		t ^= vec;
		return t;
	}

	CFixBitVec operator~() const
	{
		CFixBitVec t(*this);
		t.flip();
		return t;
	}

	CFixBitVec& operator<<=(const size_t bits)
	{
		assert(bits < size());
		m_rack <<= bits;
		return *this;
	}

	CFixBitVec operator<<(const size_t bits) const
	{
		CFixBitVec t(*this);
		t <<= bits;
		return t;
	}

	CFixBitVec& operator>>=(const size_t bits)
	{
		assert(bits < size());
		m_rack >>= bits;
		return *this;
	}

	CFixBitVec operator>>(const size_t bits) const
	{
		CFixBitVec t(*this);
		t >>= bits;
		return t;
	}

	/// Right-rotate the least significant `width` bits by `bits` positions
	CFixBitVec& rotr(const size_t bits, const size_t width)
	{
		assert(width > 0);
		assert(bits < width);
		m_rack &= FBVN1S(width);
		m_rack = (m_rack >> bits) | (m_rack << (width - bits));
		m_rack &= FBVN1S(width);
		return *this;
	}

	/// Left-rotate the least significant `width` bits by `bits` positions
	CFixBitVec& rotl(const size_t bits, const size_t width)
	{
		assert(width > 0);
		assert(bits < width);
		m_rack &= FBVN1S(width);
		m_rack = (m_rack << bits) | (m_rack >> (width - bits));
		m_rack &= FBVN1S(width);
		return *this;
	}

	/// Return true iff all bits are zero
	bool none() const { return m_rack == 0; }

	/// Return 1 + the index of the first set bit, or 0 if there are none
	size_t find_first() const
	{
		return static_cast<size_t>(chilbert::ffs(m_rack));
	}

	/// Return the number of set bits
	size_t count() const { return static_cast<size_t>(pop_count(m_rack)); }

	/// Flip all bits (one's complement)
	CFixBitVec& flip()
	{
		m_rack = ~m_rack;
		return *this;
	}

	/// Return the first rack
	FBV_UINT& rack() { return m_rack; }
	FBV_UINT  rack() const { return m_rack; }

	/// Return a pointer to the racks
	FBV_UINT*       racks() { return &m_rack; }
	const FBV_UINT* racks() const { return &m_rack; }

	/// Return the number of racks
	int rackCount() { return 1; }

private:
	static_assert(8 * sizeof(FBV_UINT) == FBV_BITS, "");
	static_assert((sizeof(FBV_UINT) == 4) || (sizeof(FBV_UINT) == 8), "");

	FBV_UINT m_rack{};
};

template <>
void
grayCode(CFixBitVec& value)
{
	value.rack() ^= (value.rack() >> 1);
}

template <>
void
grayCodeInv(CFixBitVec& value)
{
	grayCodeInv<FBV_UINT>(value.rack());
}

inline std::ostream&
operator<<(std::ostream& os, const CFixBitVec& vec)
{
	for (size_t i = 0; i < vec.size(); ++i) {
		os << vec.test(vec.size() - i - 1);
	}
	return os;
}

} // namespace chilbert

#endif