import java.util.AbstractList;
import java.util.Iterator;
import java.util.Random;

import java.util.NoSuchElementException;

/**
  * A singly linked null-terminated list implementation.
  */
class LinkedList<E> extends AbstractList<E> {
    private Node<E> head = null;
    private Node<E> tail = null;
    private int size = 0;

    /**
     * In-place O(NlgN) shuffle.
     */
    public void shuffle(Random random) {
        head = shuffle(0, size(), head, random);
        tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
    }

    /**
     * Shuffles the specified sublist starting from the lo's index
     * and ending right before the hi's index. Requires you to
     * pass a reference to the element at the lo index, so that
     * the method wouldn't have to search for that element by itself.
     * @return head element of the shuffled null-terminated sublist.
     */
    private Node<E> shuffle(int lo, int hi,
            Node<E> loElement, Random random) {
        if (hi - lo == 1) {
            // null-terminate a single-element list
            loElement.next = null;
            return loElement;
        }
        int mid = (lo + hi) >>> 1;
        Node<E> midElement = loElement;
        for (int i = lo; i < mid; i++) {
            midElement = midElement.next;
        }

        loElement = shuffle(lo, mid, loElement, random);
        midElement = shuffle(mid, hi, midElement, random);
        return mergeShuffledLists(
            lo, loElement,
            mid, midElement, 
            hi, random
        );
    }
    
    /**
     * Merges two shuffled halves of the list into a single one
     * in a way that the resulting list is uniformly shuffled
     * (given that the specified sublists are uniformly shuffled).
     * @return  head element of the merged null-terminated list.
     */
    private Node<E> mergeShuffledLists(
            int iLeftSublist, Node<E> leftSublistIter,
            int iRightSublist, Node<E> rightSublistIter,
            int hi, Random random) {
        int mid = iRightSublist;
        double sublistSize = hi - iLeftSublist;
        // initialize with dummy node to avoid both copy-paste code,
        // when initializing newHead with the initial value,
        // and excessive not-null checks inside the loop
        Node<E> newHead = new Node<>(null, null);
        Node<E> newListIter = newHead;
    
        while (leftSublistIter != null || rightSublistIter != null) {
            double decision = random.nextDouble();
            if (rightSublistIter == null
                    || decision < (mid - iLeftSublist) / sublistSize) {
                newListIter.next = leftSublistIter;
                leftSublistIter = leftSublistIter.next;
                iLeftSublist++;
            } else {
                newListIter.next = rightSublistIter;
                rightSublistIter = rightSublistIter.next;
                iRightSublist++;
            }
            newListIter = newListIter.next;
        }
        // null-terminate reassembled list
        newListIter.next = null;
        // skip the dummy node
        return newHead.next;
    }
    
    @SuppressWarnings("unchecked")
    /**
     * Linear time shuffle that uses O(N) extra memory
     */
    public void linearShuffle(Random random) {
        if (size() > 1) {
            Object[] nodes = new Object[size()];
            shuffle(nodes, random);
            head = (Node<E>) nodes[0];
            tail = head;
            for (int i = 1; i < nodes.length; i++) {
               tail.next = (Node<E>) nodes[i];
               tail = tail.next;
            }
        }
    }
    
    /**
     * Uniformly shuffles the array using the specified {@code random}
     * instance.
     */
    private static void shuffle(Object[] array, Random random) {
        final int n = array.length;
        for (int i = 0; i < n - 1; i++) {
            swap(array, i, i + random.nextInt(n - i - 1) + 1);
        }
    }
    
    /**
     * Swaps the elements at the specified indices of the {@code array}.
     * @throws  IndexOutOfBoundsException if either of the specified
     *          indices is out of range.
     */
    public static void swap(Object[] array, int i, int j) {
        if (!rangeCheck(array, i) || !rangeCheck(array, j)) {
            throw new IndexOutOfBoundsException(String.format(
                "Got: i = %d, j = %d meanwhile = len(array) = %d",
                i, j, array.length
            ));
        }
        Object swap = array[i];
        array[i] = array[j];
        array[j] = swap;
    }
    
    @Override
    /**
      * Returns the element at the specified position in the list.
      * This method runs at O(N) time since it has to go from
      * the head of the list to the target element.
      */
    public E get(int index) {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException(String.format(
                "Got: index = %d, size = %d", index, size()
            ));
        }
        int iCurrent = 0;
        Node<E> current = head;
        while (iCurrent != index) {
            current = current.next;
            iCurrent++;
        }
        return current.value;
    }
    
    /**
     * Checks, if the specified index belongs to the array.
     * @return  {@code false} in case the index is out of range
     *          or the {@code array} argument is null.
     */
    private static boolean rangeCheck(Object[] array, int index) {
        if (array == null) {
            return false;
        }
        if (index < 0 || index >= array.length) {
            return false;
        }
        return true;
    }

    @Override
    /**
      * Appends the specified element to the end of the list.
      * @return {@code true} in case the collection changed
      *         as a result of the call.
      */
    public boolean add(E value) {
        assert (head == null) == (tail == null);

        if (value == null) {
            throw new NullPointerException(
                "Null elements are not allowed"
            );
        }

        if (head == null) {
            head = new Node<>(value, null);
            tail = head;
        } else {
            tail.next = new Node<>(value, null);
            tail = tail.next;
        }
        size++;
        return true;
    }

    @Override
    /**
      * Inserts a new element at the specified position.
      */
    public void add(int index, E value) {
        assert (head == null) == (tail == null);

        if (value == null) {
            throw new NullPointerException(
                "Null elements are not allowed"
            );
        }
        if (index < 0 || index > size()) {
            throw new IndexOutOfBoundsException(String.format(
                "Got: index = %d, size = %d", index, size()
            ));
        }
        
        if (index == 0) {
            head = new Node<>(value, head);
            if (tail == null) {
                tail = head;
            }
        } else {
            int iCurrent = 0;
            Node<E> current = head;
            while (iCurrent < index - 1) {
                current = current.next;
                iCurrent++;
            }
            current.next = new Node<>(value, current.next);
            if (index == size()) {
                tail = current.next;
            }
        }
        size++;
    }

    @Override
    /**
      * Returns the size of the array.
      * The implementation is based on just keeping a {@code size}
      * variable which is being updated after every list mutation.
      * Thus the returned value does not depend on whether the
      * list is null-terminated or not.
      */
    public int size() {
        return size;
    }

    @Override
    /**
      * Clears the list.
      */
    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    /**
      * Removes the element with the specified index from the list
      */
    public E remove(int index) {
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException(String.format(
                    "Got: index = %d, size = %d", index, size()
            ));
        }
        E value = null;
        if (index == 0) {
            value = head.value;
            head = head.next;
            if (head == null) {
                tail = null;
            }
        } else {
            int iCurrent = 0;
            Node<E> current = head;
            while (iCurrent < index - 1) {
                current = current.next;
                iCurrent++;
            }
            value = current.next.value;
            current.next = current.next.next;
            if (index == size() - 1) {
                tail = current;
            }
        }
        size--;
        return value;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public E set(int index, E value) {
        if (value == null) {
            throw new NullPointerException(
                "Null elements are not allowed"
            );
        }
        if (index < 0 || index >= size()) {
            throw new IndexOutOfBoundsException(String.format(
                "Got: index = %d, size = %d", index, size
            ));
        }

        int iCurrent = 0;
        Node<E> current = head;
        while (iCurrent < index) {
            current = current.next;
            iCurrent++;
        }
        E previousValue = current.value;
        current.value = value;
        return previousValue;
    }

    @Override
    public Iterator<E> iterator() {
        return new LinkedListIterator(head);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[ ");
        for (E element : this) {
            sb.append(String.format("%s ", element));
        }
        sb.append("]");
        return sb.toString();
    }

    private static class Node<T> {
        private T value;
        private Node<T> next = null;

        public Node(T value, Node<T> next) {
            this.value = value;
            this.next = next;
        }
    }

    /**
      * An iterator that sequentially returns the elements in order.
      * Works in a null-termination manner, so you must
      * make sure that the list is null-terminated.
      */
    private class LinkedListIterator implements Iterator<E> {
        private Node<E> current;

        private Node<E> beforePrevious = null;
        private int iBeforePrevious = -2;
        private boolean removeCalled = false;

        public LinkedListIterator(Node<E> head) {
            current = head;
        }
        
        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public E next() {
            if (current == null) {
                throw new NoSuchElementException("The list is empty");
            }
            E value = current.value;
            iBeforePrevious++;
            if (iBeforePrevious > 0) {
                beforePrevious = current;
            } else if (iBeforePrevious == 0) {
                beforePrevious = head;
            }
            current = current.next;
            return value;
        }
        
        @Override
        public void remove() {
            if (!removeCalled) {
                if (iBeforePrevious >= 0) {
                    beforePrevious.next = beforePrevious.next.next;
                    size--;
                } else if (iBeforePrevious == -1) {
                    head = current;
                    size--;
                } else {
                    throw new IllegalStateException(
                        "next() has not yet been called"
                    );
                }
            } else {
                throw new IllegalStateException(
                    "remove() has already been called once after"
                    + "the next() call."
                );
            }
        }
    }

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        System.out.println(list);
        list.shuffle(new Random());
        System.out.println(list);
    }
}