/* Polymorphic stack data structure, using a list for stacks */


// declare "stackunderflow" to be a type of exception.
class stackunderflow extends Exception
{}

// basic polymorphic linked list class:
class cell<A>
{
    A head;
    cell<A> tail;
    cell(A h, cell<A> t) {head=h; tail=t;}
}


// polymorphic stack using a linked list
abstract class stack<Dtype>
{
    private int size = 0; // separate value to keep track of stack size
    private cell<Dtype> tos = null;  // top of the stack pointer
    
    void push(Dtype x) // push x on top of the stack
    {
	tos = new cell<Dtype>(x,tos);
	size++;
    }

    Dtype pop() throws stackunderflow
    {
        if (tos==null) throw new stackunderflow(); // throw exception
	cell<Dtype> top = tos;
	tos = tos.tail;
	size--;
	return top.head;
    }

    Dtype peek() throws stackunderflow
    {
       if (tos==null) throw new stackunderflow(); // throw exception
       return tos.head;
    }

    boolean isempty() { return (tos==null); }

  
    // The above methods are all "naturally polymorphic".  But suppose now
    // we want to find the "smallest" element stored in the stack.  We
    // need to be able to compare two elements to see one is "less than"
    // another.  Since we don't know what the type Dtype is, we can
    // only declare an abstract method that will be instantiate by 
    // subclasses:

    abstract boolean lessthan(Dtype a, Dtype b);
    
    Dtype smallest() throws stackunderflow
    {
	if (tos==null) throw new stackunderflow();
	Dtype answer = tos.head;
	cell<Dtype> current = tos.tail;
	while (current!=null)
	    { if (lessthan(current.head, answer)) answer = current.head; 
	      current = current.tail;
            }
	return answer;
    } //smallest
  

} //stack class


///////////////////////////////////////////////////
// concrete subclass for stack of strings

class sstack extends stack<String>
{
    boolean lessthan(String a, String b)
    { return (a.compareTo(b) < 0); }
}


// concrete subclass for stack of Integers. Remember that "Integer" is
// the object-version of int.  Only objects can participate in Java
// parameterized code.

class istack extends stack<Integer>
{
    boolean lessthan(Integer a, Integer b)
    {
	return a<b;
    }
}

// concrete subclass for stack of student objects, using the id number 
// to define <:

class stustack extends stack<student>
{
    boolean lessthan(student a, student b)
	{ return a.id < b.id; }
}


// test
public class polystack
{
  public static void main(String[] args)
  {
    try 
    {

      sstack ST = new sstack();
      ST.push("xyz");
      ST.push("abc");
      ST.push("nop");
      System.out.println(ST.smallest());

      istack IT = new istack();
      IT.push(3);
      System.out.println( IT.pop() );
      System.out.println( IT.pop() );  // should cause exception

    }
    catch (stackunderflow suf)
	{
	    System.out.println("can't do that with empty stack");
	}
    catch (Exception ee)
        { System.out.println("some other exception occurred"); }
  } //main
} //polystack