// This Source Code is in the Public Domain per: http://unlicense.org
package org.litesoft.servlets.iphone;

public final class AmazonInterviewCode_BitVector
{
    private int[] mValues;

    public AmazonInterviewCode_BitVector( int[] pValues )
    {
        mValues = pValues;
    }

    /**
     * @param pPos >= 0
     */
    public boolean get( int pPos )
    {
        int zBit = pPos & 31;
        int zNdx = pPos >> 5;
        if ( (pPos < 0) || (zNdx >= mValues.length) )
        {
            throw new IndexOutOfBoundsException();
        }
        return LLget( zNdx, zBit );
    }

    private boolean LLget( int pPos )
    {
        int zBit = pPos & 31;
        int zNdx = pPos >> 5;
        return LLget( zNdx, zBit );
    }

    private boolean LLget( int pNdx, int pBit )
    {
        return 0 != (mValues[pNdx] & pBit);
    }

    private void LLsetOne( int pNdx, int pBit )
    {
        mValues[pNdx] |= pBit;
    }

    /**
     * @param pPos >= 0
     * @param pLen >= 0
     */
    public AmazonInterviewCode_BitVector extract( int pPos, int pLen )
    {
        if ( pLen < 0 )
        {
            throw new IllegalArgumentException();
        }
        int zBitFrom = pPos & 31;
        int zNdxFrom = pPos >> 5;
        if ( (pPos < 0) || (zNdxFrom >= mValues.length) )
        {
            throw new IndexOutOfBoundsException();
        }
        int pTo = pPos + pLen;
        int zBitTo = pTo & 31;
        int zNdxTo = pTo >> 5;
        if ( (pTo < 0) || (zNdxTo >= mValues.length) )
        {
            throw new IndexOutOfBoundsException();
        }
        return null; // Not Done
    }

    public interface Node
    {
        Node getNext();
    }

    public Node getNthNodefromEnd( Node pHead, int pNth )
    {
        if ( pHead == null || pNth < 0 )
        {
            return null;
        }
        NodePlus zPlus = LLgetNthNodefromEnd( pHead, pNth );
        return (zPlus.mOffset == pNth) ? zPlus.mNode : null;
    }

    public NodePlus LLgetNthNodefromEnd( Node pCur, int pNth )
    {
        Node zNext = pCur.getNext();
        if ( zNext == null )
        {
            return new NodePlus( pCur, 0 );
        }
        NodePlus zPlus = LLgetNthNodefromEnd( zNext, pNth );
        return (zPlus.mOffset == pNth) ? zPlus : new NodePlus( pCur, zPlus.mOffset + 1 );
    }

    private class NodePlus
    {
        Node mNode;
        int mOffset;

        private NodePlus( Node pNode, int pOffset )
        {
            mNode = pNode;
            mOffset = pOffset;
        }
    }
}