////////////////////////////////////////////////////////////////////////////////
//
// bip.h
//
// by Joe Ganley, email: email at joe ganley dot com
//
// Bip is a class for enumerating combinations by adjacent swaps.
// The constructor takes the data array (of templatized type),
// that array's size, and the cut position.  The cut is to the
// right of the given cut position.  So for example, two partitions
// of size 2 each would have num==4 and cut==1.
//
// The virtual function swap() is called whenever two elements are
// swapped (the argument ix and ix+1).  The default implementation
// simply tracks the number of swaps made.
//
// This is Chase's sequence, from the description in Knuth's
// _Art_of_Computer_Programming_ pre-fascicle 2C, the draft of
// section 7.2.1.3.
//
////////////////////////////////////////////////////////////////////////////////
#ifndef BIP_H
#define BIP_H
// unsigned int shorthand typedef
typedef unsigned int uint;
// MAX is the maximum size of the set to be enumerated
#define MAX 30
// Bip is a class for enumerating combinations by adjacent swaps.
// The constructor takes the data array (of templatized type),
// that array's size, and the cut position.  The cut is to the
// right of the given cut position.  So for example, two partitions
// of size 2 each would have num==4 and cut==1.
//
// The virtual function swap() is called whenever two elements are
// swapped (the argument ix and ix+1).  The default implementation
// simply tracks the number of swaps made.
//
// This is Chase's sequence, from the description in Knuth's
// _Art_of_Computer_Programming_ pre-fascicle 2C, the draft of
// section 7.2.1.3.
template<class D>
class Bip {
  public:
			    Bip(D	data[],
				uint	num,
				uint	cut);
    bool		    makeNext();
    const D		    operator[](int  ix)	const;
    virtual void	    swap(uint    ix)	{m_swaps++;}
    uint		    getSwaps() const	{return m_swaps;}
  private:
    void		    move(uint	from,
				 uint	to);
    void		    adjSwap(uint    ix);
    void		    moveRightOne(uint	j);
    void		    moveRightTwo(uint	j);
    void		    moveLeftOne(uint	j);
    void		    moveLeftTwo(uint	j);
    void		    exchange(uint	left,
				     uint	right);
    D			    m_data[MAX];
    uint		    m_comb[MAX];
    uint		    m_ix[MAX];
    uint		    m_num;
    bool		    m_a[MAX];
    bool		    m_w[MAX];
    uint		    m_s;
    uint		    m_t;
    uint		    m_r;
    uint		    m_swaps;
};
// constructor
template<class D>
Bip<D>::Bip(D	    data[],
	    uint    num,
	    uint    cut)
:   m_num(num),
    m_s(cut + 1),
    m_t(num - m_s),
    m_r(m_s > 0 ? m_s : m_t),
    m_swaps(0)
{
    for (uint i = 0; i < num; i++) {
	m_data[i]   = data[i];
	m_comb[i]   = i;
	m_ix[i]	    = i;
	m_w[i]	    = true;
	m_a[i]	    = i >= m_s;
    }
}
// retrieve the data at index 'ix'
template<class D>
inline const D
Bip<D>::operator[](int  ix) const
{
    return m_data[m_comb[ix]];
}
	
// turn this into the next combination.  returns false when there are no more.
template<class D>
bool
Bip<D>::makeNext()
{
    if (m_s == 0 || m_t == 0) {
	return false;
    }
    // C3: Find j and branch
    uint j = m_r;
    while (j < m_num && !m_w[j]) {
	m_w[j++] = true;
    }
    if (j == m_num) {
	return false;
    }
    m_w[j] = false;
    if (j % 2 == 1) {
	if (m_a[j]) {
	    moveRightOne(j);
	} else {
	    moveLeftTwo(j);
	}
    } else {
	if (m_a[j]) {
	    moveRightTwo(j);
	} else {
	    moveLeftOne(j);
	}
    }
    return true;
}
// C4
template<class D>
void
Bip<D>::moveRightOne(uint   j)
{
    assert(j > 0);
    exchange(j, j - 1);
    if (m_r == j && j > 1) {
	m_r = j - 1;
    } else if (m_r == j - 1) {
	m_r = j;
    }
}
// C5
template<class D>
void
Bip<D>::moveRightTwo(uint   j)
{
    assert(j > 1);
    if (m_a[j - 2]) {
	moveRightOne(j);
	return;
    }
    exchange(j, j - 2);
    if (m_r == j) {
	m_r = j > 3 ? j - 2 : 1;
    } else if (m_r == j - 2) {
	m_r = j - 1;
    }
}
// C6
template<class D>
void
Bip<D>::moveLeftOne(uint    j)
{
    assert(j > 0);
    exchange(j - 1, j);
    if (m_r == j && j > 1) {
	m_r = j - 1;
    } else if (m_r == j - 1) {
	m_r = j;
    }
}
// C7
template<class D>
void
Bip<D>::moveLeftTwo(uint    j)
{
    assert(j > 0);
    if (m_a[j - 1]) {
	moveLeftOne(j);
	return;
    }
    assert(j > 1);
    exchange(j - 2, j);
    if (m_r == j - 2) {
	m_r = j;
    } else if (m_r == j - 1) {
	m_r = j - 2;
    }
}
// "bubble" the object at [from] to [to] by swapping
template<class D>
void
Bip<D>::move(uint   from,
	     uint   to)
{
    assert(from >= 0 && from < m_num);
    assert(to >= 0 && to < m_num);
    if (from < to) {
	for (uint i = from; i < to; i++) {
	    adjSwap(i);
	}
    } else {
	for (int i = int(from - 1); i >= int(to); i--) {
	    adjSwap(i);
	}
    }
}
// swap ix and (ix+1)
template<class D>
void
Bip<D>::adjSwap(uint   ix)
{
    assert(ix >= 0 && ix < (m_num - 1));
    m_ix[m_comb[ix]] = ix + 1;
    m_ix[m_comb[ix + 1]] = ix;
    std::swap(m_comb[ix], m_comb[ix + 1]);
    assert(m_ix[m_comb[ix]] == ix);
    assert(m_ix[m_comb[ix + 1]] == ix + 1);
    swap(ix);
}
// move the object at index 'left' to the index immediately left of the cut,
// and move the object at index 'right' to the index immediate right of the
// cut.
template<class D>
void
Bip<D>::exchange(uint	left,
		 uint	right)
{
    assert(left >= 0 && left < m_num);
    assert(right >= 0 && right < m_num);
    // do the moves
    assert(m_ix[left] >= m_s);	// currently right of cut
    move(m_ix[left], m_s);	// move it to immediate right of cut
    assert(m_ix[right] < m_s);	// currently left of cut
    move(m_ix[right], m_s - 1);	// move it to immediate left of cut
    adjSwap(m_s - 1);		// trade sides just across the cut
    // update the m_a array
    assert(m_a[left]);
    m_a[left]	= false;
    assert(!m_a[right]);
    m_a[right]	= true;
}
#endif