/*             CSC 16 lab 10 : Polymorphic data structures

 (This lab is currently optional because Tuesday 11/22 is a conversion day)


     For this lab, make sure you study the "polylist.java" program
     I discussed in class, and is posted on the webpage.

     You are to extend the program in the following ways:

     1. Write calculator classes for Double and String.
        Now, for Strings, not all operations are meaningful.  For 
        for example, it doesn't make sense to multiply Strings.  However,
        if a class implements the calculator<String> interface, then
        it must still provide definitions for all the functions specified
	in the interface.  So you will just have to write something like:
	
	public String times(String x, String y) { return null; }
	
	And likewise for similar situations.  Note, however, that 
	although "one" doesn't exist for Strings, "zero" does, which is
	just the empty string "".  Use the compareTo function to determine
	the ordering of strings.

    2.  Earlier in the semester we wrote a "date" class - it's probably
        still in your directory.  Write a calculator for the date class,
	so we can have a linked list of dates.  For many of the operations
	such as "times", there is no reasonable cooresponding operation on
	the date class (unless you can think of one).  However, it is still
	possible to use the "before" and "sameday" operations of the date
	class so we can write, for example, a polymorphic function that
	can sort a linked list of days.  

    3.  A "queue" is a data structure that complements "stack".  Unlike
        a stack, elements are added to one end of the queue and removed
	from the other.  Like stacks a queue can also be implemented using
	linked lists.  The basic operations on queues are "enqueue" which
	inserts an element to the end of the queue, and "dequeue" which 
	removes an element at the front of the queue.  Look at the implemention
	of the "stack" class to get further hints as to how to do this.
	You'll still need to import the cell<A> class, and have a
	pointer in the queue<A> class that points to the first cell.
        You need to write a class that implements the
	following interface:
*/

interface queueinterface<A>
{
    public void enqueue(A x); // adds x to end of queue
    public A dequeue() throws Exception;       
                              // removes and returns front element,
                                 throw Exception if queue empty
    public A peek() throws Exception;          
                              // returns front element without deletion
    public boolean empty();   // determine if queue is null
    public int length();      // determine length of queue
    public boolean inqueue(A x, calculator<A> calc);
                              // determines if x is present in queue.
}

class queue<A> implements queueinterface<A>
{
    cell<A> front = null; //  pointer to first cell
    
    public A peek() throws Exception
    {
        if (front==null) throw new Exception("null queue");
	return front.head;
    }
    // ... (provide the rest of the implementation)
}// queue<A> class

/*
    4.  Some of the operations described above are naturally polymorphic,
        some not.  Identify another operations (among typical list operations
	we looked at in the past) that is also naturally polymorphic, 
        and implement it in the queue<A> class.

    5.  The calculator<A> interface contains several operations, but
        perhaps the list is not exhaustive.  Obviously, there's no
	minus or divide operations.  It's not difficult to add them in
	to the existing interfaces and classes.  But what other operations
	might be useful?  Identify such an operation, then:
	
	a. add the operation to the calculator<A> interface and all
	concrete calculator classes.

	b. Identify a polymorphic algorithm that makes use of the operation
	and implement it in the queue<A> class.

    6.  Your "main" method should test each operation and feature on 
        meaningful examples.

    7.  (optional) Modify the quicksort algorithm for linked lists (find
        program on webpage) to be polymorphic (right now it only sorts doubles)
*/