package class8_1_WhyNotTreeList;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * This class illustrates:
 *  * Advanced recursive techniques
 *  * Why we DON'T use Trees for list
 *
 *  It is based on the BinarySearchTree from
 *  class6_2_BinarySearchTree (which has bugs)
 *  and
 *  class6_2_BinarySearchTree_corrected (which fixes them)
 */
public class TreeList<E extends Comparable<E>> implements List<E> {
    public static void main(String[] args) {
        new TreeList().test();
    }

    private void test() {
        List<String> tree = new TreeList<String>();

        tree.add("Joe");
        tree.add("Nancy");
        tree.add("Andrew");
        tree.add("Mark");
        tree.add("Peter");
        tree.add("John");

        // Full tree:
        //   Andrew
        //  Joe
        //     John
        //    Mark
        //   Nancy
        //    Peter

        checkGet(tree, "Andrew", 0);
        checkGet(tree, "Joe", 1);
        checkGet(tree, "John", 2);
        checkGet(tree, "Mark", 3);
        checkGet(tree, "Nancy", 4);
        checkGet(tree, "Peter", 5);
    }

    private void checkGet(List<String> tree, String expected, int index) {
        System.out.println("DEBUG: Attempting to find "+expected+" at index "+index);
        String name;
        try {
            name = tree.get(index);
            if(name == null || !name.equals(expected)) {
                logToBothStreams("Warning: expected "+expected+", but got "+name+" at index "+index);
            } else {
                System.out.println("DEBUG: Succeeded at find: "+expected+" at index "+index);
            }
        } catch(ArrayIndexOutOfBoundsException e) {
            logToBothStreams("Warning: threw unexpected ArrayIndexOutOfBounds " +
                    "when trying to find "+expected+" at  index "+index);
        }
    }

    /**
     *     Print to both streams so the error stands out, and
     *     we know where it occurs relative to other errors.
     */
    private void logToBothStreams(String message) {
        System.out.println(message);
        System.err.println(message);
    }

    /**
     * Find an element by index
     * @param index the index of the desired element
     * @return the element found at index
     * @throws ArrayIndexOutOfBoundsException if the element is not found
     */
    @Override
    public E get(int index) throws ArrayIndexOutOfBoundsException {
        if(index < 0) {
            throw new ArrayIndexOutOfBoundsException("Index should not be negative, got "+index);
        }
        WrappedNode wn = new WrappedNode();
        wn.node = null;
        get(root, index, wn, 0);
//        alternativeGet(root, index, wn, 0);
        if(wn.node==null) { // This is valid, despite the warning!
            throw new ArrayIndexOutOfBoundsException("Index is too large");
        }
        return wn.node.value;
    }

    /**
     * Recursive get
     * @param n - the current node
     * @param goal - the goal index
     * @param wn - the wrapper for an "editable argument"
     * @param beforeUs -- the number of nodes before this sub-tree
     *                  that is, the number of nodes up to & including the parent.
     * @return the size of this sub-tree
     */
    private int get(Node n, int goal, WrappedNode wn, int beforeUs) {
        if(n==null) {
            return 0;
        }
        int size=beforeUs;
        size+=get(n.left,goal,wn,beforeUs);
        if(size==goal) {
            wn.node = n; // BUG FIX: not "this" as written on board -- generated compile error
        }
        size+=get(n.right,goal,wn,size+1);

        return size+1-beforeUs; // BUG FIX: Must return something!
    }

    /**
     * Alternative implementation (also works!)
     * This one is more efficient
     *   -- it stops once it finds the node.
     *
     * @param n - the current node
     * @param goal - the goal index
     * @param wn - the wrapper for an "editable argument"
     * @param beforeUs -- the number of nodes before this sub-tree
     *                  that is, the number of nodes up to & including the parent.
     * @return the size of this sub-tree
     */
    private int alternativeGet(Node n, int goal, WrappedNode wn, int beforeUs) {
        if(n==null) {
            return 0;
        }
//       System.out.println("DEBUG: Looking for index "+goal+" "+" at node with value "+n.value+" with "+beforeUs+" nodes before us.");
//       if(wn.node == null) {
//           System.out.println("DEBUG:    Wrapped node not yet set");
//       } else {
//           System.out.println("DEBUG:    Wrapped node contains: "+wn.node.value);
//       }

        int size=0;
        size+=get(n.left,goal,wn,beforeUs);
        if(size+beforeUs==goal) {
            wn.node = n; // BUG FIX: not "this" as written on board -- generated compile error
//           System.out.println("DEBUG:    Setting wrapped node to self, with value: "+n.value);
            size+=1; // count self so parents will know they are done.
        } else {
            size+=1; // count self
            size+=get(n.right,goal,wn,size+beforeUs);
        }
        return size;
    }


    private class WrappedNode {
        private Node node;
    }

    Node root;

    private class Node {
        Node left;
        Node right;
        E value;

        private Node(Node left, Node right, E value) {
            this.left = left;
            this.right = right;
            this.value = value;
        }
    }

    // EDIT: returned true (instead of void) to be compatible with List interface.
    public boolean add(E e) {
        if(root == null) {
            root = new Node(null, null, e);
        } else {
            add(e, root);
        }
        // EDIT: Print tree to debug.
        System.out.println("DEBUG: Printing tree after add:");
        print();
        // EDIT Return value as mentioned above.
        return true;
    }

    /**
     * @param e value to add
     * @param current the root of the sub-tree to add the node under
     *                current != null
     */
    private void add(E e, Node current) {
        if(e.compareTo(current.value) < 0 && current.left == null
                || e.compareTo(current.value) >=0 && current.right == null) {
            Node newNode = new Node(null, null, e);
            if(e.compareTo(current.value) < 0) {
                current.left = newNode;
            } else {
                current.right = newNode;
            }
        } else {
            // EDIT: Fix bug corrected in
            // class 6_2_BinarySearchTree_corrected
            if(e.compareTo(current.value) < 0) { // e < current
                add(e, current.left);
            } else {
                add(e, current.right);
            }
        }
    }

    public void oldAdd(E e) {
        Node newNode = new Node(null, null, e);

        if(root == null) {
            root = newNode;
        } else {
            Node current = root;
            Node prev = null;
            while(current != null) {
                if(e.compareTo(current.value) < 0) { // e < current
                    prev = current;
                    current = current.left;
                } else {
                    prev = current;
                    current = current.right;
                }
            }
            if(e.compareTo(prev.value) < 0) {
                prev.left = newNode;
            } else {
                prev.right = newNode;
            }
        }
    }

    public void print() {
        printTree(root, 0);
    }

    private void printTree(Node current, int depth) {
        if(current != null) {
            printTree(current.left,depth+1);
            for(int i=0;i<depth;i++) {
                System.out.print(" ");
            }
            System.out.println(current.value);
            printTree(current.right,depth+1);
        }
    }


    //===== unimplemented methods ================================================

    @Override
    public int size() {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public boolean isEmpty() {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public boolean contains(Object o) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public Iterator<E> iterator() {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public Object[] toArray() {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public <T> T[] toArray(T[] a) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public boolean remove(Object o) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public void clear() {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public E set(int index, E element) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public void add(int index, E element) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public E remove(int index) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public int indexOf(Object o) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public int lastIndexOf(Object o) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public ListIterator<E> listIterator() {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        throw new UnsupportedOperationException("Method not implemented");
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        throw new UnsupportedOperationException("Method not implemented");
    }
}