/*
  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:
	using Rack = uintptr_t;

	static constexpr size_t bits_per_rack = sizeof(Rack) * CHAR_BIT;

	/** Mask for a bit that can be incremented like an index.
	 *
	 * This enables fast iteration while setting or resetting bits since it is
	 * internally stored as a mask which avoids repeated index math.
	 */
	class Mask
	{
	public:
		void operator++() { m_mask <<= 1; }
		void operator--() { m_mask >>= 1; }

		bool operator==(const Mask& mask) const
		{
			return m_mask == mask.m_mask;
		}

		bool operator!=(const Mask& mask) const
		{
			return m_mask == mask.m_mask;
		}

	private:
		friend class CFixBitVec;

		Mask(const size_t index)
		  : m_mask{index < bits_per_rack ? Rack{1} << index : 0}
		{
		}

		Rack m_mask;
	};

	explicit CFixBitVec(const size_t bits)
	  : m_rack{0}
	  , m_size{bits}
	{
		assert(bits <= bits_per_rack);
	}

	CFixBitVec(const size_t bits, const Rack value)
	  : m_rack{value}
	  , m_size{bits}
	{
		assert(bits <= bits_per_rack);
	}

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

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

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

	/// Return the value of the bit covered by `mask`
	bool test(const Mask mask) const { return m_rack & mask.m_mask; }

	/// Return the value of the `index`th bit
	bool test(const size_t index) const { return test(mask(index)); }

	/// Set the bit covered by `mask` to 1
	CFixBitVec& set(const Mask mask)
	{
		m_rack |= mask.m_mask;
		return *this;
	}

	/// Set the `index`th bit to 1
	CFixBitVec& set(const size_t index) { return set(mask(index)); }

	/// Reset the bit covered by `mask` to 0
	CFixBitVec& reset(const Mask mask)
	{
		m_rack &= ~mask.m_mask;
		return *this;
	}

	/// Reset the `index`th bit to 0
	CFixBitVec& reset(const size_t index) { return reset(mask(index)); }

	/// Set the bit covered by `mask` to `value`
	CFixBitVec& set(const Mask mask, const bool value)
	{
		m_rack ^= (-Rack{value} ^ m_rack) & mask.m_mask;
		return *this;
	}

	/// Set the `index`th bit to `value`
	CFixBitVec& set(const size_t index, const bool value)
	{
		return set(mask(index), value);
	}

	/// Flip the value of the bit covered by `mask`
	CFixBitVec& flip(const Mask mask)
	{
		m_rack ^= mask.m_mask;
		return *this;
	}

	/// Flip the value of the `index`th bit
	CFixBitVec& flip(const size_t index) { return flip(mask(index)); }

	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 Rack 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 Rack 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 by `bits` positions
	CFixBitVec& rotr(const size_t bits)
	{
		if (bits) {
			assert(bits <= bits_per_rack);
			m_rack &= FBVN1S(size());
			m_rack = (m_rack >> bits) | (m_rack << (size() - bits));
			m_rack &= FBVN1S(size());
		}
		return *this;
	}

	/// Left-rotate by `bits` positions
	CFixBitVec& rotl(const size_t bits)
	{
		if (bits > 0) {
			assert(bits <= bits_per_rack);
			m_rack &= FBVN1S(size());
			m_rack = (m_rack << bits) | (m_rack >> (size() - bits));
			m_rack &= FBVN1S(size());
		}
		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
	Rack& rack() { return m_rack; }
	Rack  rack() const { return m_rack; }

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

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

	template <class BitVec>
	class iterator_base : public Mask
	{
	public:
		iterator_base& operator++()
		{
			Mask::operator++();
			return *this;
		}

		iterator_base& operator--()
		{
			Mask::operator--();
			return *this;
		}

		bool operator==(const iterator_base& iterator_base) const
		{
			return m_vec == iterator_base.m_vec &&
			       Mask::operator==(iterator_base);
		}

		bool operator!=(const iterator_base& iterator_base) const
		{
			return !operator==(iterator_base);
		}

		bool operator*() const { return m_vec->test(*this); }

	protected:
		iterator_base(BitVec& vec, const size_t index)
		  : Mask{index}
		  , m_vec{&vec}
		{
		}

		BitVec* m_vec;
	};

	class iterator : public iterator_base<CFixBitVec>
	{
	public:
		void set() { m_vec->set(*this); }
		void reset() { m_vec->reset(*this); }

	private:
		friend class CFixBitVec;

		iterator(CFixBitVec& vec, const size_t index)
		  : iterator_base{vec, index}
		{
		}
	};

	class const_iterator : public iterator_base<const CFixBitVec>
	{
	private:
		friend class CFixBitVec;

		const_iterator(const CFixBitVec& vec, const size_t index)
		  : iterator_base{vec, index}
		{
		}
	};

	Mask mask(const size_t i = 0) const
	{
		assert(i <= size());
		return Mask{i};
	}

	iterator begin(const size_t i = 0) { return iterator(*this, i); }

	iterator end() { return iterator(*this, size()); }

	const_iterator begin(const size_t i = 0) const
	{
		return const_iterator(*this, i);
	}

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

private:
	static_assert(8 * sizeof(Rack) == bits_per_rack, "");
	static_assert((sizeof(Rack) == 4) || (sizeof(Rack) == 8), "");

	Rack   m_rack{};
	size_t m_size{};
};

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

template <>
void
grayCodeInv(CFixBitVec& value)
{
	grayCodeInv<CFixBitVec::Rack>(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