/* DequeList<Item>  (linked-list based, iterable)
 * 
 * Methods
 * =======
 * boolean isEmpty()           : returns true if the deque is empty, false otherwise
 * int size()                  : returns the number of items in the deque
 * void pushLeft(Item item)    : pushes an item onto the left side of the deque
 * void pushRightt(Item item)  : pushes an item onto the right side of the deque
 * Item popLeft()              : pops the left-most item off the deque and returns it
 * Item popRight()             : pops the right-most item off the deque and returns it
 * Iterator iterator()         : returns a left-to-right iterator for the deque
 */

import java.util.Iterator;

public class DequeList<Item> implements Deque<Item>, Iterable<Item> {
    
    private class Node {
        Item item;
        Node left;
        Node right;
    }
   
    private Node leftEnd;
    private Node rightEnd;
    private int size;
    
    public boolean isEmpty() {
        return (size == 0);
    }
    
    public int size() {
        return size;
    }
    
    public void pushLeft(Item item) {
        Node node = new Node();
        node.item = item;
        if (this.isEmpty()) {
            leftEnd = node;
            rightEnd = node;
        }
        else {
            node.left = null;       // superfluous
            node.right = leftEnd;
            leftEnd.left = node;
            leftEnd = node;
        }
        size++;
    }
    
    public void pushRight(Item item) {
        Node node = new Node();
        node.item = item;
        if (this.isEmpty()) {
            leftEnd = node;
            rightEnd = node;
        }
        else {
            node.right = null;       // superfluous
            node.left = rightEnd;
            rightEnd.right = node;
            rightEnd = node;
        }
        size++;
    }
   
    public Item popLeft() {                // Three cases to consider:
        if (this.isEmpty()) {              // 0 nodes in the deque
            return null; 
        }
        else if (leftEnd == rightEnd) {    // 1 node in the deque
            Item item = leftEnd.item;
            leftEnd = null;
            rightEnd = null;
            size--;
            return item;               
        }
        else {                             // 2+ nodes in the deque
            Item item = leftEnd.item;
            leftEnd = leftEnd.right;
            leftEnd.left = null;
            size--;
            return item;
        }
    }
    
    public Item popRight() {               // Three cases to consider:
        if (this.isEmpty()) {              // 0 nodes in the deque
            return null; 
        }
        else if (leftEnd == rightEnd) {    // 1 node in the deque
            Item item = rightEnd.item;
            leftEnd = null;
            rightEnd = null;
            size--;
            return item;               
        }
        else {                             // 2+ nodes in the deque
            Item item = rightEnd.item;
            rightEnd = rightEnd.left;
            rightEnd.right = null;
            size--;
            return item;
        }
    }

    private class LeftToRightIterator implements Iterator<Item>{
        Node node = leftEnd;

        public boolean hasNext() {
            return (node != null);
        }

        public Item next() {
            Item itemToReturn = node.item;
            node = node.right;
            return itemToReturn;
        }
    }
    
    public Iterator<Item> iterator() {
        return new LeftToRightIterator();
    }

    /* FOR TESTING */
    public static void main(String[] args) {
        Deque<String> d = new DequeList<String>();
        d.pushLeft("a");
        d.pushLeft("b");
        d.pushRight("c");
        d.pushRight("d");
        
        System.out.println("deque elements after pushing a, b on left c, d on right in that order");
        for (String str : d) {
            System.out.print(str + " ");
        }
        System.out.println();
        
        d.popLeft();
        d.popRight();
        
        System.out.println("deque elements after popping two elements");
        for (String str : d) {
            System.out.print(str + " ");
        }
        System.out.println();
        
        System.out.println("deque now has size " + d.size());
        System.out.println("deque is " + (d.isEmpty() ? "" : "not ") + "empty");
    }
}