// class SortableQueue for CPS 151
import java.util.NoSuchElementException;
import java.util.Random;

public class SortableQueue extends IntQueue {
    protected int size;
    
    // default constructor
    public SortableQueue() {
        clear();
    }
    
    // constructor to load the queue with random values
    public SortableQueue(int howMany) {
        this(); // do the default construction first
        Random rand = new Random();
        
        for(int j = 1; j <= howMany; j++)
            add(rand.nextInt(1000));
    }
    
    public void add(int elem) {
        super.add(elem);
        size++;
    }
    
    public void remove(){
        // TODO
    }
    
    public void clear() {
        super.clear();
        size = 0;
    }
    
    public boolean isSorted() {
        //TODO

        // stub right now
        return true;    // all pairs check out
    }
    
    // Split "this" Sortable Queue into two Queues L1 and L2 of
    // roughly equal sizes.
    // Pre: L1 and L2 should be empty and 
    //      "this" queue should have > 1 nodes when this method is called,
    //      otherwise an exception is thrown
    // Post: "this" queue will become empty on successful completion
    //      of this method
    public void split(SortableQueue L1, SortableQueue L2) 
            throws IllegalStateException {

        // check the preconditions
        if (!L1.empty() || !L2.empty())
            throw new IllegalStateException("Cannot split into non-empty list");
        if (size <= 1)
            throw new IllegalStateException("List too short for split");

        // TODO: NOW DO THE ACTUAL SPLITTING

    } // end split
    
    public void merge(SortableQueue L1, SortableQueue L2)
            throws IllegalStateException {

        // check the preconditions
        // "this" list should be empty
        if (!empty())
            throw new IllegalStateException("cannot merge into nonempty list");
        if (!L1.isSorted() || !L2.isSorted())
            throw new IllegalStateException("cannot merge unsorted list(s)");

        // TODO: NOW DO THE ACTUAL MERGING (SEE HOW IT IS DONE FOR ARRAYS)
        
        
    } // end merge

    public int removeMin() {
	if (empty())
	    throw new IllegalStateException("removeMin() called on empty queue");
	// add code to locate the minimum value in a node and remove that value from the linked queue

	return 0;	// stub, replace by return of the minimum value
    } // end removeMin
} // end class SortableQueue


    class Node {
        public int data;
        public Node next;
	public Node(int elem) {
		data = elem;
		next = null;
	}
    }

// class IntQueue for CPS 151

class IntQueue {
    // instance variables
    protected Node first;
    protected Node last;

    // default constructor
    public IntQueue() {
        clear();
    }

    public boolean empty() {
        return first == null;
    }

    public void add(int elem) {
        if (first == null) {	// the list is empty and last is also null
            first = last = new Node(elem);
        } 
        else {
            last = last.next = new Node(elem);
        }
    } // end add

    // removes the first value in the Queue, 
    // throws NoSuchElementException if Queue empty
    public void remove() {
        if (first == null) {
            throw new NoSuchElementException("Remove() called on Empty List");
        }
        first = first.next;
        // has the list become empty?
        if (first == null) {
            last = null;
        }
    } // end remove

    // returns the first value in the Queue, 
    // throws NoSuchElementException if Queue empty
    public int peek() throws NoSuchElementException {
        if (first == null) {
            throw new NoSuchElementException("Peek() called on Empty List");
        }
        return first.data;
    }
    
    public void clear() {
        first = null;
        last = null;
    }
    
    public String toString() {
        if (empty())
            return "[]";
        
        String result = "[";
        Node current = first;
        
        result += current.data;
        current = current.next;
        
        while (current != null) {
            result += ", " + current.data;
            current = current.next;
        } // end loop
        
        return result + "]";
    }
} // end class IntQueue