/*
  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_BIGBITVEC_HPP
#define CHILBERT_BIGBITVEC_HPP


#include "chilbert/FixBitVec.hpp"

#include <cassert>
#include <cstring>

#define BBV_MIN(a,b)		((a)<(b)?(a):(b))
#define BBV_MAX(a,b)		((a)>(b)?(a):(b))
#define FBVS_NEEDED(b)		((BBV_MAX(b,1)+FBV_BITS-1)/FBV_BITS)
#define BBV_MODSPLIT(r,b,k) { b=(k); r=b/FBV_BITS; b-=r*FBV_BITS; }

namespace chilbert {

class CBigBitVec
{
public:

	// Constructor, with optional number of bits.
	CBigBitVec(
		int iBits = FBV_BITS
	           )
	{
		// Determine number of racks required.
		m_iRacks = iBits == 0 ? 0 : FBVS_NEEDED(iBits);

		// Allocate the memory.
		if (m_iRacks > 0) {
			m_pcRacks = new FBV_UINT[m_iRacks];
		} else {
			m_pcRacks = nullptr;
		}
			
		return;
	}
		
		
	// Copy construct.	Creates duplicate.
	CBigBitVec(
		const CBigBitVec &cBBV
	           )
	{
		m_iRacks = cBBV.m_iRacks;
		m_pcRacks = new FBV_UINT[m_iRacks];

		// Copy the rack values.
		if (cBBV.m_pcRacks) {
			memcpy(m_pcRacks, cBBV.m_pcRacks, sizeof(FBV_UINT) * m_iRacks);
		}

		return;
	}

	// Move construct.
	CBigBitVec(
		CBigBitVec &&cBBV
	           )
	{
		m_iRacks = cBBV.m_iRacks;
		m_pcRacks = cBBV.m_pcRacks;
		cBBV.m_iRacks = 0;
		cBBV.m_pcRacks = nullptr;
	}

	// Copy constructor.
	CBigBitVec(
		const CFixBitVec &cFBV
	           )
	{
		m_iRacks = 1;
		m_pcRacks = new FBV_UINT[m_iRacks];

		m_pcRacks[0] = cFBV.rack();

		return;
	}


	// Destructor
	~CBigBitVec()
	{
		delete [] m_pcRacks;

		return;
	}


	// Returns the current size in bits.
	int
	size() const
	{
		return m_iRacks*FBV_BITS;
	}


	// zeros the bit-vector.
	CBigBitVec &
	reset()
	{
	
		memset(m_pcRacks, 0, sizeof(CFixBitVec) * m_iRacks);

		return (*this);
	}


	// truncates the bit-vector to a given precision in
	// bits (zeroes MSBs without shrinking the vector)
	CBigBitVec &
	truncate(
		int iBits
	         )
	{
		assert( iBits >= 0 && iBits <= size() );
		int r, b, i;

		BBV_MODSPLIT(r,b,iBits);
	
		if ( r >= m_iRacks )
			return (*this);

		// Truncate rack that contains the split point
		m_pcRacks[r] &= FBVN1S(iBits);
	
		for ( i = r+1; i < m_iRacks; i++ )
			m_pcRacks[i] = 0;

		return (*this);
	}


	// Assignment operator.	No resizing.
	CBigBitVec &
	operator=(
		const CBigBitVec &cBBV
	          )
	{
		if ( m_iRacks < cBBV.m_iRacks )
		{
			memcpy(m_pcRacks, cBBV.m_pcRacks, sizeof(CFixBitVec) * m_iRacks);
		} else {
			if (m_pcRacks) {
				if (cBBV.m_pcRacks) {
					memcpy(m_pcRacks,
					       cBBV.m_pcRacks,
					       sizeof(CFixBitVec) * cBBV.m_iRacks);
				}
				memset(m_pcRacks + cBBV.m_iRacks,
				       0,
				       sizeof(CFixBitVec) * (m_iRacks - cBBV.m_iRacks));
			}
		}

		return (*this);
	}
	CBigBitVec &
	operator=(
		CBigBitVec &&cBBV
	          )
	{
		if (&cBBV != this) {
			m_iRacks = cBBV.m_iRacks;
			m_pcRacks = cBBV.m_pcRacks;
			cBBV.m_iRacks = 0;
			cBBV.m_pcRacks = nullptr;
		}

		return (*this);
	}
	CBigBitVec &
	operator=(
		const CFixBitVec &cFBV
	          )
	{
		m_pcRacks[0] = cFBV.rack();
		memset(m_pcRacks + 1, 0, sizeof(FBV_UINT) * (m_iRacks - 1));
		return (*this);
	}
	CBigBitVec &
	operator=(
		FBV_UINT j
	          )
	{
		m_pcRacks[0] = j;
		memset(m_pcRacks + 1, 0, sizeof(CFixBitVec) * (m_iRacks - 1));
		return (*this);
	}

	// Returns the value of the nth bit.
	bool
	test(
		int iIndex
	       ) const
	{
		assert( iIndex >= 0 && iIndex < size() );
		int r, b;
		BBV_MODSPLIT(r,b,iIndex);
		return testBit(m_pcRacks[r], b);
	}


	// Sets the value of the nth bit.
	CBigBitVec &
	set(
		int iIndex,
		bool bBit = true
	       )
	{
		assert( iIndex >= 0 && iIndex < size() );
		int r, b;
		BBV_MODSPLIT(r,b,iIndex);
		setBit(m_pcRacks[r], b, bBit);
		return (*this);
	}


	// Toggles the value of the nth bit.
	CBigBitVec &
	toggle(
		int iIndex
	          )
	{
		assert( iIndex >= 0 && iIndex < size() );
		int r, b;
		BBV_MODSPLIT(r,b,iIndex);
		m_pcRacks[r] ^= (FBV1<<iIndex);
		return (*this);
	}


	// In place AND.
	CBigBitVec &
	operator&=(
		const CBigBitVec &cBBV
	           )
	{
		int i;
	
		for ( i = 0; i < BBV_MIN(m_iRacks,cBBV.m_iRacks); i++ )
			m_pcRacks[i] &= cBBV.m_pcRacks[i];
	
		return (*this);
	}


	// AND operator.
	CBigBitVec
	operator&(
		const CBigBitVec &cBBV
	          ) const
	{
		CBigBitVec t( *this );
		t &= cBBV;

		return t;
	}


	// In place OR.
	CBigBitVec &
	operator|=(
		const CBigBitVec &cBBV
	           )
	{
		int i;
	
		for ( i = 0; i < BBV_MIN(m_iRacks,cBBV.m_iRacks); i++ )
			m_pcRacks[i] |= cBBV.m_pcRacks[i];
	
		return (*this);
	}


	// OR operator.
	CBigBitVec
	operator|(
		const CBigBitVec &cBBV
	          ) const
	{
		CBigBitVec t( *this );
		t |= cBBV;

		return t;
	}


	// In place XOR.
	CBigBitVec &
	operator^=(
		const CBigBitVec &cBBV
	           )
	{
		int i;
	
		for ( i = 0; i < BBV_MIN(m_iRacks,cBBV.m_iRacks); i++ )
			m_pcRacks[i] ^= cBBV.m_pcRacks[i];
	
		return (*this);
	}


	// XOR operator.
	CBigBitVec
	operator^(
		const CBigBitVec &cBBV
	          ) const
	{
		CBigBitVec t( *this );
		t ^= cBBV;

		return t;
	}


	// Shift left operation, in place.
	CBigBitVec &
	operator<<=(
		int iBits
	            )
	{
		assert( iBits >= 0 );
		int r, b, i;

		// No shift?
		if ( iBits == 0 )
			return (*this);

		BBV_MODSPLIT(r,b,iBits);

		// All racks?
		if ( r >= m_iRacks )
		{
			reset();
			return (*this);
		}

		// Do rack shifts.
		if ( r > 0 )
		{
			for ( i = m_iRacks-1; i >= r; i-- )
				m_pcRacks[i] = m_pcRacks[i-r];
			for ( ; i >= 0; i-- )
				m_pcRacks[i] = 0;
		}

		// Do bit shifts.
		if ( b > 0 )
		{
			int bi = FBV_BITS - b;
			for ( i = m_iRacks-1; i >= r+1; i-- )
			{
				m_pcRacks[i] <<= b;
				m_pcRacks[i] |= m_pcRacks[i-1] >> bi;
			}
			m_pcRacks[i] <<= b;
		}

		return (*this);
	}


	// Shift left operation.
	CBigBitVec
	operator<<(
		int iBits
	           ) const
	{
		CBigBitVec t( *this );
		t <<= iBits;
		return t;
	}


	// Shift right operation, in place.
	CBigBitVec &
	operator>>=(
		int iBits
	            )
	{
		assert( iBits >= 0 );
		int r, b, i;

		// No shift?
		if ( iBits == 0 )
			return (*this);

		BBV_MODSPLIT(r,b,iBits);

		// All racks?
		if ( r >= m_iRacks )
		{
			reset();
			return (*this);
		}

		// Do rack shifts.
		if ( r > 0 )
		{
			for ( i = 0; i < m_iRacks-r; i++ )
				m_pcRacks[i] = m_pcRacks[i+r];
			for ( ; i < m_iRacks; i++ )
				m_pcRacks[i] = 0;
		}

		// Do bit shifts.
		if ( b > 0 )
		{
			int bi = FBV_BITS - b;
			for ( i = 0; i < m_iRacks-r-1; i++ )
			{
				m_pcRacks[i] >>= b;
				m_pcRacks[i] |= m_pcRacks[i+1] << bi;
			}
			m_pcRacks[i] >>= b;
		}

		return (*this);
	}


	// Shift right operation.
	CBigBitVec
	operator>>(
		int iBits
	           ) const
	{
		CBigBitVec t( *this );
		t >>= iBits;
		return t;
	}


	// Right rotation, in place.
	CBigBitVec &
	rotr(
		int iBits,
		int iWidth
	     )
	{
		assert( iBits >= 0 );

		// Fill in the width, if necessary.
		if ( iWidth <= 0 )
			iWidth = size();

		// Modulo the number of bits.
		assert( iBits < iWidth );
		if ( iBits == 0 ) return (*this);

		// Ensure we are truncated appropriately.
		truncate(iWidth);

		CBigBitVec t1( *this );
		(*this) >>= iBits;
		t1 <<= (iWidth-iBits);
		(*this) |= t1;
	
		truncate(iWidth);

		return (*this);
	}


	// Left rotation, in place.
	CBigBitVec &
	rotl(
		int iBits,
		int iWidth
	     )
	{
		assert( iBits >= 0 );

		// Fill in the width, if necessary.
		if ( iWidth <= 0 )
			iWidth = size();

		// Modulo the number of bits.
		assert( iBits < iWidth );
		if ( iBits == 0 ) return (*this);

		// Ensure we are truncated appropriately.
		truncate(iWidth);

		CBigBitVec t1( *this );
		(*this) <<= iBits;
		t1 >>= (iWidth-iBits);
		(*this) |= t1;

		truncate(iWidth);

		return (*this);
	}


	// Returns true if the rack is zero valued.
	bool
	none() const
	{
		int i;
		for ( i = 0; i < m_iRacks; i++ )
			if ( m_pcRacks[i] ) return false;
		return true;
	}


	// Returns the index of the first set bit.
	// (numbered 1 to n, with 0 meaning no bits were set)
	int
	fsb() const
	{
		for (int i = 0; i < m_iRacks; ++i )
		{
			const int j = ffs(m_pcRacks[i]);
			if ( j ) {
				return (i * FBV_BITS) + j;
			}
		}
		return 0;
	}


	// Complement
	CBigBitVec &
	flip()
	{
		int i;
		for ( i = 0; i < m_iRacks; i++ )
			m_pcRacks[i] = ~m_pcRacks[i];
		return (*this);
	}


	// Returns the first rack.
	FBV_UINT &
	rack()
	{
		return m_pcRacks[0];
	}
	FBV_UINT
	rack() const
	{
		return m_pcRacks[0];
	}


	// Returns the racks.
	FBV_UINT *
	racks()
	{
		return m_pcRacks;
	}
	const FBV_UINT *
	racks() const
	{
		return m_pcRacks;
	}


	// Returns the number of racks.
	int
	rackCount() const
	{
		return m_iRacks;
	}

	
private:
	friend void grayCode<CBigBitVec>(CBigBitVec&);
	friend void grayCodeInv<CBigBitVec>(CBigBitVec&);

	// Right rotates entire racks (in place).
	void
	rackRotr(
		int k
	         )
	{
		assert( 0 <= k && k < m_iRacks );
	
		int c, v;
		FBV_UINT tmp;

		if (k == 0) return;

		c = 0;
		for (v = 0; c < m_iRacks; v++)
		{
			int t = v, tp = v + k;
			tmp = m_pcRacks[v];
			c++;
			while (tp != v)
			{
				m_pcRacks[t] = m_pcRacks[tp];
				t = tp;
				tp += k;
				if (tp >= m_iRacks) tp -= m_iRacks;
				c++;
			}
			m_pcRacks[t] = tmp;
		}

		return;
	}
	

	FBV_UINT *m_pcRacks;
	int m_iRacks;
};

template <>
void
grayCode(CBigBitVec& value)
{
	FBV_UINT s = 0;

	for (int i = value.rackCount() - 1; i >= 0; i--) {
		const FBV_UINT t = value.racks()[i] & 1;
		grayCode(value.m_pcRacks[i]);
		value.m_pcRacks[i] ^= (s << (FBV_BITS - 1));
		s = t;
	}
}

template <>
void
grayCodeInv(CBigBitVec& value)
{
	FBV_UINT s = 0;

	for (int i = value.rackCount() - 1; i >= 0; --i) {
		FBV_UINT& rack = value.m_pcRacks[i];
		grayCodeInv(rack);
		if (s) {
			rack = ~rack;
		}
		s = rack & 1;
	}
}

} // namespace chilbert

#endif