/* QueueList<Item>  (linked-list based, iterable)
 * 
 * Methods
 * =======
 * boolean isEmpty()           : returns true if the queue is empty, false otherwise
 * int size()                  : returns the number of elements in the queue
 * void enqueue(Item item)     : adds item to the end of the queue
 * Item dequeue()              : removes the front-most item from the queue and returns it
 * Iterator iterator()         : returns a head-to-tail iterator for the queue
 */

import java.util.ConcurrentModificationException;
import java.util.Iterator;

public class QueueList<Item> implements Queue<Item>, Iterable<Item> {
    
    private class Node {
        Item item;
        Node next;
    }
   
    private Node first;
    private Node last; 
    private int size;
    private int modCount;
    
    public boolean isEmpty() {
        return (size == 0);
    }
    
    public int size() {
    	return size;
    }
    
    public void enqueue(Item item) {
        Node node = new Node();
        node.item = item;
        
        if (this.isEmpty()) 
            first = node;
        else  
            last.next = node;
        last = node;
        size++;
        modCount++;
    }
   
    public Item dequeue() {            // Three cases to consider:
        if (this.isEmpty()) {          // 0 nodes in the queue
            return null; 
        }
        else if (first == last) {      // 1 node in the queue
            Item item = first.item;
            first = null;
            last = null;
            size--;
            modCount++;
            return item;               
        }
        else {                         // 2+ nodes in the queue
            Item item = first.item;      
            first = first.next; 
            size--;
            modCount++;
            return item;  
        }
    }

    public Iterator<Item> iterator() {
        return new Iterator<Item>() {

           private Node node = first;
           private int savedModCount = modCount;

           public boolean hasNext() {
               if (modCount != savedModCount) throw new ConcurrentModificationException();
               return (node != null);
           }

           public Item next() {
               if (modCount != savedModCount) throw new ConcurrentModificationException();
               Item itemToReturn = node.item;
               node = node.next;
               return itemToReturn;
           }
        };
    }
}