package com.test.playground;

/**
 * Simple Single Linked List backed by an Array.
 */
public class ArrayLinkList<T> {
    public static class Node<T> {
        private T mValue;
        private CtrlStructure<T> mCtrlStructure;
        private Integer mNextIndex;

        public Node( T pValue ) {
            mValue = pValue;
        }

        public T getValue() {
            return mValue;
        }

        public Node<T> getNext() {
            return ((mCtrlStructure != null) && (mNextIndex != null)) ? mCtrlStructure.mArray[mNextIndex] : null;
        }

        public void insertAfter( Node<T> pNode ) {
            pNode.validateAddable(); // implicit NPE
            if ( mCtrlStructure == null ) {
                throw new IllegalStateException( "Can't insert after a Node that is not currently attached to a list" );
            }
            int zIndex = mCtrlStructure.add( pNode ); // implicit space check
            pNode.mNextIndex = mNextIndex;
            mNextIndex = zIndex;
        }

        private void validateAddable() {
            if ( mCtrlStructure != null ) {
                throw new IllegalArgumentException( "Node already attached to a list, and removal not currently supported" );
            }
        }
    }

    private CtrlStructure<T> mCtrlStructure;
    private Integer mFirstIndex;

    public ArrayLinkList( int pMaxNodes ) {
        mCtrlStructure = new CtrlStructure( pMaxNodes );
    }

    public Node<T> getFirstNode() {
        return (mFirstIndex != null) ? mCtrlStructure.mArray[mFirstIndex] : null;
    }

    /**
     * Note: this requires a scan of the List!
     */
    public void insertAfter( Node<T> pNodeToLocate, Node<T> pNodeToInsert ) {
        mCtrlStructure.findRequired( pNodeToLocate ).insertAfter( pNodeToInsert );
    }

    /**
     * Note: this requires a scan of the List!
     */
    public void append( Node<T> pNode ) {
        if ( mCtrlStructure.mCellsUsed == 0 ) {
            insertFront( pNode );
        } else {
            mCtrlStructure.findTail().insertAfter( pNode );
        }
    }

    public void insertFront( Node<T> pNode ) {
        pNode.validateAddable(); // implicit NPE
        int zIndex = mCtrlStructure.add( pNode );
        pNode.mNextIndex = mFirstIndex;
        mFirstIndex = zIndex;
    }

    private static class CtrlStructure<T> {
        private int mCellsUsed = 0;
        private Node<T>[] mArray;

        CtrlStructure( int pMaxNodes ) {
            mArray = new Node[pMaxNodes]; // implicit negative check
        }

        public int add( Node<T> pNode ) {
            if ( mArray.length <= mCellsUsed ) {
                throw new IllegalStateException( "Max Nodes (" + mArray.length + ") already used" );
            }
            pNode.mCtrlStructure = this;
            mArray[mCellsUsed] = pNode;
            return mCellsUsed++;
        }

        public Node<T> findTail() {
            for ( int i = 0; i < mCellsUsed; i++ ) {
                Node<T> zNode = mArray[i];
                if ( zNode.mNextIndex == null ) {
                    return zNode;
                }
            }
            return null;
        }

        public Node<T> findRequired( Node<T> pNode ) {
            if ( pNode.mCtrlStructure == this ) // implicit NPE
            {
                for ( int i = 0; i < mCellsUsed; i++ ) {
                    Node<T> zNode = mArray[i];
                    if ( zNode == pNode ) // Ownership controlled, so instance == is acceptable
                    {
                        return zNode;
                    }
                }
            }
            throw new IllegalArgumentException( "Node Not a member of this list" );
        }
    }
}