/*
 * [LinkedList.java]
 *
 * Summary: Generified Linked List implementation that is similar to but predates Sun's LinkedList.
 *
 * Copyright: (c) 2006-2017 Roedy Green, Canadian Mind Products, http://mindprod.com
 *
 * Licence: This software may be copied and used freely for any purpose but military.
 *          http://mindprod.com/contact/nonmil.html
 *
 * Requires: JDK 1.8+
 *
 * Created with: JetBrains IntelliJ IDEA IDE http://www.jetbrains.com/idea/
 *
 * Version History:
 *  1.0 1997-05-13 initial release, not validated
 *  1.1 1997-05-30 Test harness, enumerator, toVector
 *  1.2 1998-03-16 fix bug in insertElement if there is only one element in the
 *                 list already.
 *  1.3 1998-06-24 add JavaDOC
 *  1.4 1998-11-10 new address
 *  1.5 2008-01-01 move to its own package.
 *  1.6 2008-02-18 generify
 */
/*  LinkedList.java contains LinkedList, Link and LinkedListEnumerator. */
package com.mindprod.linkedlist;

import java.util.Enumeration;
import java.util.NoSuchElementException;
import java.util.Vector;

import static java.lang.System.*;

/**
 * Generified Linked List implementation that is similar to but predates Sun's LinkedList.
 * <p/>
 * A doubly linked list with forward and back References (safe pointers). The LinkedList maintains a cursor pointing
 * to the current element. This class behaves much like Vector, except that is implemented differently.  LinkedList is
 * better designed than Vector for insert/delete, but worse for indexing.  LinkedList has the unfortunate overhead of
 * creating a little link object for each element. This was written back in Java 1.0 days, before there was a
 * Collections or List interface, much less generics, so it does not conform. This is mainly a teaching example how you
 * might implement a LinkedList. Sun since implemented their own LinkedList
 *
 * @author Roedy Green, Canadian Mind Products
 * @version 1.6 2008-02-18 generify
 * @since 1997-05-13
 */
@SuppressWarnings( { "WeakerAccess" } )
public final class LinkedList<E>
    {
    private static final int FIRST_COPYRIGHT_YEAR = 2006;

    /**
     * undisplayed copyright notice
     */
    @SuppressWarnings( { "UnusedDeclaration" } )
    private static final String EMBEDDED_COPYRIGHT =
            "Copyright: (c) 2006-2017 Roedy Green, Canadian Mind Products, http://mindprod.com";

    /**
     * when package was released.
     *
     * @noinspection UnusedDeclaration
     */
    private static final String RELEASE_DATE = "2008-02-18";

    /**
     * version of package.
     *
     * @noinspection UnusedDeclaration
     */
    private static final String VERSION_STRING = "1.6";

    /**
     * Reference to the current item on the list. The only time it can be null is if the list is empty.
     */
    protected Link<E> current = null;

    /**
     * Reference to first element on the list.
     */
    protected Link<E> head = null;

    /**
     * Reference to the last element on the list.
     */
    protected Link<E> tail = null;

    /**
     * The list cursor, "indexes" the current element, though there is no array. <br> <br> -1 = empty list <br> 0 =
     * current is first element on the list <br> 1 = current is second element on the list... <br> Once the list has
     * elements, the cursor always points to an element. It is never -1.
     */
    protected int cursor = -1;

    /**
     * Number of elements in the List. Access publicly via isEmpty() or size().
     */
    protected int elementCount = 0;

    /**
     * LinkedList constructor
     */
    public LinkedList()
        {
        }

    /**
     * LinkedList constructor, convert from Vector.
     *
     * @param v a Vector of objects that will be add to this list. The original Vector will be undisturbed.
     *          We use Vector instead of ArrayList or List because of the extreme age of this code. They did not
     *          exist at the time.
     */
    public LinkedList( Vector<E> v )
        {
        synchronized ( v )
            {
            for ( E element : v )
                {
                addElement( element );
                }
            }
        } // end LinkedList constructor

    /**
     * Convert the list to Vector form. This does not clone the elements.  It just creates a Vector of references.  The
     * original list is intact.  There is no automatic synchronisation between the two if you add more elements to the
     * list.
     *
     * @return a Vector of the list elements in order.  The Vector has no spare space.
     */
    final synchronized Vector<E> toVector()
        {
        Vector<E> v = new Vector<>( elementCount );
        for ( Enumeration<E> e = elements(); e.hasMoreElements(); )
            {
            v.addElement( e.nextElement() );
            }
        return v;
        } // end toVector

    /**
     * Append an element to the end of the list. When done, the cursor points to the newly added element.
     *
     * @param obj element to add to the list.
     */
    public final synchronized void addElement( E obj )
        {
        elementCount++;
        cursor++;
        current = new Link<>( obj, tail, null );
        if ( tail == null )
            {
            head = current;
            }
        else
            {
            tail.next = current;
            }
        tail = current;
        } // end addElement

    /**
     * Debugging tool.  Checks the list for consistent structure.
     */
    public final void consistency()
        {
        if ( elementCount == 0 )
            {
            out.println( "LinkedList empty" );
            return;
            }
        Link stepper = head;
        Link was = null;
        for ( int i = 0; i < elementCount; i++ )
            {
            if ( stepper.prev != was )
                {
                out.println( "bad prev Reference" );
                }
            was = stepper;
            if ( stepper.next == null && tail != stepper )
                {
                out.println( "bad tail" );
                }
            stepper = stepper.next;
            }
        out.println( "LinkedList ok with " + elementCount + " entries" );
        } // consistency

    /**
     * Get element from list.
     *
     * @param index 0 = retrieve first element, 1 = second element etc.
     *
     * @return the element at that index, null if the list is empty.
     * @throws ArrayIndexOutOfBoundsException if index does not reference an existing element.
     */
    public final synchronized E elementAt( int index ) throws ArrayIndexOutOfBoundsException
        {
        setCursor( index );
        return current.element;
        } // end elementAt

    /**
     * Generate an enumeration of the list.
     *
     * @return Enumeration that will cycle through all the list elements in order.
     */
    public final synchronized Enumeration<E> elements()
        {
        return new LinkedListEnumerator<>( this );
        } // end elements

    /**
     * Get the first element.
     *
     * @return the first element in the list, null if there is none.
     */
    public final synchronized E firstElement()
        {
        return ( head == null ) ? null : head.element;
        } // end firstElement

    /**
     * Get cursor position.
     *
     * @return -1 = empty, 0 = first element
     */
    public final synchronized int getCursor()
        {
        return cursor;
        } // end getCursor

    /**
     * Set list cursor to an existing element.
     *
     * @param index = 0 to point to the first element, = 1 to the second etc. You can't set the cursor when the list is
     *              empty.
     *
     * @throws ArrayIndexOutOfBoundsException if index does not reference an existing element.
     */
    @SuppressWarnings( { "UnnecessaryReturnStatement", "SillyAssignment" } )
    public final synchronized void setCursor( int index ) throws ArrayIndexOutOfBoundsException
        {
        if ( index < 0 || index >= elementCount )
            {
            throw new ArrayIndexOutOfBoundsException();
            }
        if ( index == cursor )
            {
            return;
            }
        // Chase the chain to find that element.
        // We can chase head forward, current back, current forward or tail back.
        // Figure out which would be fastest.
        // The most common case is moving one ahead or one back.  Handle those
        // cases specially.
        else if ( index < cursor )
            {
            if ( index == cursor - 1 )
                {
                current = current.prev;
                cursor = index;
                }
            else if ( index < cursor / 2 )
                {
                // chase head forward
                current = head;
                // chase forward from cursor, possibly zero steps.
                for ( cursor = 0; cursor < index; cursor++ )
                    {
                    current = current.next;
                    }
                // cursor will equal index
                }
            else
                {
                // chase current back
                for ( ; cursor > index; cursor-- )
                    {
                    current = current.prev;
                    }
                // cursor will equal index
                }
            }
        else if ( index == cursor + 1 )
            {
            current = current.next;
            cursor = index;
            }
        else if ( index < cursor + ( elementCount - cursor ) / 2 )
            {
            // chase forward from cursor, possibly zero steps.
            for ( ; cursor < index; cursor++ )
                {
                current = current.next;
                }
            // cursor will equal index
            }
        else
            {
            // chase tail back
            current = tail;
            // chase backward from cursor, possibly zero steps.
            for ( cursor = elementCount - 1; cursor > index; cursor-- )
                {
                current = current.prev;
                }
            // cursor will equal index
            }
        } // end setCursor

    /**
     * Get current element.
     *
     * @return element pointed to by the list cursor, null if the list is empty.
     */
    public final synchronized E getElement()
        {
        return ( current == null ) ? null : current.element;
        } // end getElement

    /**
     * Replace the current element. Change the link for the current element to point to a different object.
     *
     * @param obj the new object to replace the current element.
     *
     * @throws ArrayIndexOutOfBoundsException if the list is empty
     */
    public final synchronized void setElement( E obj ) throws ArrayIndexOutOfBoundsException
        {
        if ( current == null )
            {
            throw new ArrayIndexOutOfBoundsException();
            }
        current.element = obj;
        } // end setElement

    /**
     * Search the list for the given object.  A match is based on address equality not comparing fields.
     *
     * @param obj the element to search for.
     *
     * @return 0 = first element, 1 = second element etc., -1 = not found.
     */
    public final synchronized int indexOf( E obj )
        {
        // chase chain from one end to the other looking for it.
        // Perhaps this should be done with .equals instead of ==
        Link chase = head;
        for ( int i = 0; i < elementCount; i++ )
            {
            if ( chase.element == obj )
                {
                return i;
                }
            chase = chase.next;
            }
        // did not find it
        return -1;
        } // end indexOf

    /**
     * Insert an element just ahead of the current element. When done, the cursor points to the newly added element.
     *
     * @param obj element to add to the list.
     */
    public final synchronized void insertElement( E obj )
        {
        if ( current == null )
            {
            addElement( obj );
            }
        else
            {
            elementCount++;
            // cursor stays the same
            Link<E> succ = current;
            Link<E> pred = current.prev;
            current = new Link<>( obj, pred, succ );
            // succ can't be null.
            succ.prev = current;
            // pred would be null if there was only one element before this
            // insert.
            if ( pred == null )
                {
                head = current;
                }
            else
                {
                pred.next = current;
                }
            } // end else
        } // end insertElement

    /**
     * Insert an element AT the given index. Another way to look at this, is we are inserting just ahead of the element
     * at that the given index. When done, the cursor points to the newly added element, and the elements past it are
     * logically pushed down an index slot.
     *
     * @param obj   the element to add.
     * @param index where to insert the new element.  0 = at the head of the list.
     *
     * @throws ArrayIndexOutOfBoundsException if index does not reference an existing element.
     */
    public final synchronized void insertElementAt( E obj, int index ) throws ArrayIndexOutOfBoundsException
        {
        // we also allow an element to be inserted at the end of the list
        // even though that index would be out of bounds.
        if ( index == elementCount )
            {
            addElement( obj );
            }
        else
            {
            setCursor( index );
            insertElement( obj );
            }
        } // end insertElementAt

    /**
     * Is the List empty of elements?
     *
     * @return true if the list is empty.
     */
    public final synchronized boolean isEmpty()
        {
        return elementCount == 0;
        }

    /**
     * Get last element
     *
     * @return the last element in the list, null if the list is empty.
     */
    public final synchronized E lastElement()
        {
        return ( tail == null ) ? null : tail.element;
        } // end lastElement

    /**
     * Search the list for the given object.  A match is based on address equality, not comparing fields.  Search from
     * the tail back.
     *
     * @param obj the element to search for.
     *
     * @return 0 = first element, 1 = second element etc., -1 = not found.
     */
    public final synchronized int lastIndexOf( E obj )
        {
        // chase chain from one end to the other looking for it.
        Link chase = tail;
        for ( int i = elementCount - 1; i > 0; i-- )
            {
            if ( chase.element == obj )
                {
                return i;
                }
            chase = chase.prev;
            }
        // did not find it
        return -1;
        } // end lastIndexOf

    /**
     * Delete the current element. The succeeding element becomes the new current element. If there is no successor, the
     * predecessor becomes the current element. If the list either is or becomes empty, there is no current element.
     */
    public final synchronized void remove()
        {
        if ( current == null )
            {
            return;
            }
        elementCount--;
        Link<E> pred = current.prev;
        if ( pred == null )
            {
            head = current.next;
            }
        else
            {
            pred.next = current.next;
            }
        Link<E> succ = current.next;
        if ( succ == null )
            {
            tail = current.prev;
            current = pred;
            }
        else
            {
            succ.prev = current.prev;
            current = succ;
            }
        } // end remove

    /**
     * Remove all elements from the list. If there are no other references to the elements, this effectively destroys
     * them.
     */
    public final synchronized void removeAllElements()
        {
        head = null;
        tail = null;
        current = null;
        cursor = -1;
        elementCount = 0;
        }

    /**
     * Remove an element.
     *
     * @param index = 0 to remove the first element, = 1 to remove the second etc.
     *
     * @throws ArrayIndexOutOfBoundsException if index does not reference an existing element.
     */
    public final synchronized void removeElementAt( int index ) throws ArrayIndexOutOfBoundsException
        {
        setCursor( index );
        remove();
        }

    /**
     * Replace an element. Change the link for the indexed element to point to a different object.
     *
     * @param obj   the new object to replace the current element.
     * @param index the element to be replaced, 0 = the first element, 1 = the second etc.
     *
     * @throws ArrayIndexOutOfBoundsException if the index does not reference an existing object.
     */
    public final synchronized void setElementAt( E obj, int index ) throws ArrayIndexOutOfBoundsException
        {
        setCursor( index );
        setElement( obj );
        } // end setElement

    /**
     * How many elements are currently in the list?
     *
     * @return the number of elements in the list.
     */
    public final int size()
        {
        return elementCount;
        }
    } // end LinkedList class

/**
 * The LinkedList Class creates a Link object for each element to contain the forward and back References.
 */
class Link<E>
    {
    /**
     * Instance reference to the list item.
     */
    @SuppressWarnings( { "WeakerAccess" } )
    protected E element;

    /**
     * Instance reference to the next link node. Null if this is the last item on the list.
     */
    @SuppressWarnings( { "WeakerAccess" } )
    protected Link<E> next;

    /**
     * Instance reference to the previous link node. Null if this is the first item on the list.
     */
    @SuppressWarnings( { "WeakerAccess" } )
    protected Link<E> prev;

    /**
     * Link constructor.
     *
     * @param element the list item.
     * @param prev    reference to the previous link node on the list.
     * @param next    reference to the next link node on the list.
     */
    Link( E element, Link<E> prev, Link<E> next )
        {
        this.element = element;
        this.prev = prev;
        this.next = next;
        }
    } // end class Link

/**
 * Enumerator for counting through all the items on the list.
 */
final class LinkedListEnumerator<E> implements Enumeration<E>
    {
    /**
     * The list we are enumerating through.
     */
    private final LinkedList<E> linkedList;

    /**
     * Which item we are on in the enumeration.
     */
    private int count;

    /**
     * Constructor.
     *
     * @param l the list we wish to enumerate.
     */
    LinkedListEnumerator( LinkedList<E> l )
        {
        this.linkedList = l;
        this.count = 0;
        } // end constructor

    /**
     * Are there more elements in the this enumeration to process?
     *
     * @return true if there are more elements.
     */
    public final boolean hasMoreElements()
        {
        return count < linkedList.elementCount;
        } // hasMoreElements

    /**
     * Get the next element of the enumeration.
     *
     * @return the next list element.
     */
    public final E nextElement()
        {
        synchronized ( linkedList )
            {
            if ( count < linkedList.elementCount )
                {
                return linkedList.elementAt( count++ );
                }
            }
        throw new NoSuchElementException( "LinkedListEnumerator" );
        } // end nextElement
    } // end class LinkedListEnumerator
// -30-