import DAT.*;
import Exceptions.*;

public class StackCharBlock implements StackChar  {
	
	private char[] stack;
	private int bottom;

	/** : constructor for teh stack
	* @param c the size of the stack
	*/
	
	public StackCharBlock(int s){
	
	      stack = new char[s];
	      bottom = -1;
	}


 
                /**
	  *isEmpty(): return true if the stack is empty, false otherwise
	  * @return true if empty, false otherwise: 
                 */

	public boolean isEmpty(){
	     if(bottom == -1){
		return true;
	     }
	     else return false;
	}

   
	/**isFull(): return true if the stack is full, false otherwise 
               * @return true if the stack is full. false otherwise.
	*/   
	public boolean isFull(){
		
	     if(bottom == (stack.length-1) ){
		return true;
	     }
	     else return false;
	}
			

	/**4.push(c): push character c onto the top of the stack, or throw an Overflow exception if the stack is full 
               * @param c : the character to be put on the stack;
	* @throws Overflow : if the stack is too full
	*/   

	public void push(char c ) throws Overflow{
	
	      if( isFull() ){
		throw new Overflow("arrgh. its full!");
	      }
	      bottom++;
	      stack[bottom] = c;
	}


	/**5.peek(): return the character on top of the stack, or throw an Underflow exception if the stack is empty 
	* @return the value on the top of the stack
	* @throws Underflow if the stack is empty
	*
	*/                  

	public char peek() throws Underflow {

	      if( isEmpty() ){
	   	throw new Underflow("nothing in stack");
	      }
	 
	     return stack[bottom];
	}

	/** 6.pop():returns and removes the value on the top of the stack.such fun :)
	* @return the item on the top of the stack
	* @throws Underflow if there is nothing on the stack
	*/
	public char pop() throws Underflow {

	    char a;
	   
	    if(isEmpty() ){
		throw new Underflow("nothing to pop off stack");
	    }
	    else{
	   	
		a = stack[bottom];
		bottom--;
		return a;
	    }
	}
	
 }			
		


import Exceptions.*;

/** 
 * Block representation of a String queue. <br>
 * The queue is bounded and erodes with use.
 * @author Cara MacNish
 * @version Time-stamp: <98/03/23 15:23 cara>
 */
public class QueueStringBlock implements QueueString {

  /**
   * an array of queue items 
   */
  private String[] items;

  /**
   * index for the first item
   */
  private int first;

  /**
   * index for the last item
   */
  private int last;

  /**
   * initialise a new queue
   * @param size the size of the queue
   */
  public QueueStringBlock (int size) {
    items = new String[size];
    first = 0;
    last = -1;
  }

  /** 
   * test whether the queue is empty
   * @return true if the queue is empty, false otherwise
   */
  public boolean isEmpty () {return first == last + 1;}

  /**
   * test whether the queue is full
   * @return true if the queue is full, false otherwise
   */
  public boolean isFull () {return last == items.length - 1;}

  /**
   * add a new item to the queue
   * @param a the item to add
   * @exception Overflow if queue is full
   */
  public void enqueue (String a) throws Overflow {
    if (!isFull()) {
      last++;
      items[last] = a;
    }
    else throw new Overflow("enqueuing to full queue");
  }

  /**
   * examine the first item in the queue
   * @return the first item
   * @exception Underflow if the queue is empty
   */
  public String examine () throws Underflow {
    if (!isEmpty())  return items[first];
    else throw new Underflow("examining empty queue");
  }

  /**
   * remove the first item in the queue
   * @return the first item
   * @exception Underflow if the queue is empty
   */
  public String dequeue() throws Underflow {
    if (!isEmpty()) {
      String a = items[first];
      first++;
      return a;
    }				
    else throw new Underflow("dequeuing from empty queue");
  }							

  /**
   * string representation of the character queue
   * @return the string representation
   */
  public String toString () {
    String s="";
    for (int i=first; i<=last; i++)  s = s + items[i];
    return s;
  }
}


import DAT.*;




public class QueueStringBlockTest{

	
	public static void main(String[] args){

 		QueueStringBlock q;
	

		String person;
				
		System.out.println("wow.!.  here is a collection of prime ministers");

		q = new QueueStringBlock( 7 );

		q.enqueue("Fraser");
                q.enqueue("Hawke");
                q.enqueue("Keating");
                q.enqueue("Howard");
                System.out.println( q.dequeue() );
                System.out.println( q.dequeue() );
                System.out.println( q.dequeue() );
                q.enqueue("Beazley");
                q.enqueue("Kernot");
                person = q.examine();
                System.out.println("The Prime Minister is " + person);
	}
}	

		


import Exceptions.*;

/** 
 * Character queue interface. 
 * @author Cara MacNish
 * @version Time-stamp: <98/03/23 15:23 cara>
 */
public interface QueueString {

  /** 
   * test whether the queue is empty
   * @return true if the queue is empty, false otherwise
   */
  public boolean isEmpty ();

  /**
   * add a new item to the queue
   * @param a the item to add
   */
  public void enqueue (String a);

  /**
   * examine the first item in the queue
   * @return the first item
   * @exception Underflow if the queue is empty
   */
  public String examine () throws Underflow;

  /**
   * remove the first item in the queue
   * @return the first item
   * @exception Underflow if the queue is empty
   */
  public String dequeue() throws Underflow;
}

import DAT.*;
import Exceptions.*;

public class QueueCharCyclic implements QueueChar {

	
	char[] queue;

	int length;
	
	int first;
	int temp;
	/** the constructor for the object
	* @param size is the size of the new queue
	*
	*/

	public QueueCharCyclic(int size){
	
		queue = new char[size];
		length = 0;
		first = 0;
		temp =0;
	}

	/**  tests to see if the queue is full.
	* @return boolean true if the queue is full, false if its not.
	*
	*/

	public boolean isFull(){
	
		if(length >= queue.length){
			return true;
		}
		else return false;
	}

	/** test to see if the queue is empty
	* @return true if the queue is empty, false otherwise
	*/

	public boolean isEmpty(){
		return ( length == 0);
	}

	/** method for adding a char to the queue
	* @param c the char that is to be added to the queue
	* @throws Overflow if there is no more room on the queue
	*/

	public void enqueue(char c) throws Overflow {
		if( isFull() ){
			throw new Overflow("adding to a full queue");
		}
		
		temp = (first + length)%queue.length;
		queue[temp] = c;
		length++;

	}

	/** returns the value of the first item in the queue
	* @return the item at the start of the queue
	* @throws Underflow if there is nothing in the queue
	*/

	public char examine() throws Underflow{

		if( isEmpty() ){
			throw new Underflow("queue is empty");
		}

		return queue[first];
	}

	/** removes the item at the start of the queue
	* @return the value of the item that has been removed
	* @throws Underflow if the queue is empty
	*/

	public char dequeue() throws Underflow {
	
		if( isEmpty() ){
			throw new Underflow("Queue is empty");
		}
		
		temp = (first+1)%queue.length;

		length = length -1;
		char x = queue[first];
		first = temp;

		return x;
	}
}

		
	
public class test{

	public static void main(String args[] ){
		
		QueueCharCyclic p = new QueueCharCyclic(5);

		p.enqueue('c');
		p.enqueue('f');
		System.out.println( p.dequeue() );
		p.enqueue('a');
		p.enqueue('b');
		p.enqueue('j');
		System.out.println( p.dequeue() );
		p.enqueue('s');
		System.out.println(p.dequeue() );
		System.out.println(p.dequeue() );
		System.out.println(p.dequeue() );
		System.out.println(p.dequeue() );
		System.out.println(p.dequeue() );
		System.out.println(p.dequeue() );
		System.out.println("END of the test");
	}
	
}

import DAT.*;
import Exceptions.*;

public class QueueBlockCyclic implements Queue {

	
	Object[] queue;

	int length;
	
	int first;
	int temp;
	/** the constructor for a queue of objects
	* @param size is the size of the new queue
	*
	*/

	public QueueBlockCyclic(int size){
	
		queue = new Object[size];
		length = 0;
		first = 0;
		temp =0;
	}

	/**  tests to see if the queue is full.
	* @return boolean true if the queue is full, false if its not.
	*
	*/

	public boolean isFull(){
	
		if(length >= queue.length){
			return true;
		}
		else return false;
	}

	/** test to see if the queue is empty
	* @return true if the queue is empty, false otherwise
	*/

	public boolean isEmpty(){
		return ( length == 0);
	}

	/** method for adding an Object to the queue
	* @param c the char that is to be added to the queue
	* @throws Overflow if there is no more room on the queue
	*/

	public void enqueue(Object c) throws Overflow {
		if( isFull() ){
			throw new Overflow("adding to a full queue");
		}
		
		temp = (first + length)%queue.length;
		queue[temp] = c;
		length++;

	}

	/** returns the value of the first item in the queue
	* @return the item at the start of the queue
	* @throws Underflow if there is nothing in the queue
	*/

	public Object examine() throws Underflow{

		if( isEmpty() ){
			throw new Underflow("queue is empty");
		}

		return queue[first];
	}

	/** removes the item at the start of the queue
	* @return the value of the item that has been removed
	* @throws Underflow if the queue is empty
	*/

	public Object dequeue() throws Underflow {
	
		if( isEmpty() ){
			throw new Underflow("Queue is empty");
		}
		
		temp = (first+1)%queue.length;

		length = length -1;
		Object x = queue[first];
		first = temp;

		return x;
	}
}

		
	
import DAT.*;
import Exceptions.*;

public class LinkedList implements DAT.List {

	/** constructor
	*/

	public LinkedList(){
	}

	
	/** checks to see if the list is empty
	* @return boolean if file is empty
	*/
	public boolean isEmpty(){
	}

	/** checks to see if the window is before first
	* @return true if the window is before first 
	*/
	public boolean isBeforeFirst(){
	}
	
	/** check for window 
	* @return true if the window is after last
	*/
	public boolean isAfterLast(){

	}

	/** position the window before first
	* @param  w the window to be placed
	*/
	public void beforeFirst(Window w){
	
	}

	/** positions the window after the last element
	* @param w the window to be placed 
	*/
	public void afterLast(Window w){
		
	}
	
	/** position the window over the next element
	* @param w the window to be moved
	* @throws OutOfBounds exception
	*/
	public void next(Window w) throws OutOfBounds{
	
	}

	/** moves the window to the previous element
	* @param w the window to be moved
	* @throws OutOfBounds if the window is at before first
	*/ 
	public void previous(Window w) throws OutOfBounds {

	}

	/** inserts the element e after w
	* @param e the object to be inserted
	* @param w the window the element is to be inserted after
	* @throws outofbounds exception
	*/
	public void insertAfter(Object e,Window w) throws OutOfBounds {

	}

	/** inserts the object e before the window w 's postition
	* @param e the Object to be inserted
	* @param w the Window the link is to be inserted after
	* @throws outOfBounds if the window is beforeFirst
	*/
	public void insertBefore(Object e, Window w) throws OutOfBounds {
	
	}


	/** returns teh object in teh current window
	* @param w the window of the element to look at
	* @return the Object of the windows link
	* @throws Exception a general exception if there is nothing there or pointing at an empty link
	*/
	public Object examine(Window w) throws Exception {
	
	}

	/** replaces the links object with a new one
	* @param w the window to replace the element with
	* @param e the new object to replace it with
	* @throws Exception if there is a problem
	*/
	public void replace(Object e , Window w) throws Exception {

	}

	/** removes the element under w, returning the object and and puts w over the next element
	* @param w the window element to delete
	* @throws OutOfBOunds if teh element is before first or after last
	*/
	public Object delete(Window w) throws OutOfBounds {
	
	}

}
import DAT.*;
import Exceptions.*;

public class ListLinked implements DAT.List {

	private Link before;
	private Link after;
	
	


	/** constructor
	*/

	public ListLinked(){
		after = new Link(null, null);
		before = new Link(null, after);
	
	}

	
	/** checks to see if the list is empty
	* @return boolean if file is empty
	*/
	public boolean isEmpty(){
		if(before.successor == after){
			return true;
		}
		else return false;
	
	
	}

	/** checks to see if the window is before first
	* @param w the window to check
	* @return true if the window is before first 
	*/
	public boolean isBeforeFirst(WindowLinked w){
		return (w.link == before);

	}
	
	/** check for window 
	* @return true if the window is after last
	*/
	public boolean isAfterLast(WindowLinked w){
		return ( w.link == after);
	}

	/** position the window before first
	* @param  w the window to be placed
	*/
	public void beforeFirst(WindowLinked w){

		w.link = before;
	
	}

	/** positions the window after the last element
	* @param w the window to be placed 
	*/
	public void afterLast(WindowLinked w){
	
		w.link = after;	
	}
	
	/** position the window over the next element
	* @param w the window to be moved
	* @throws OutOfBounds exception
	*/
	public void next(WindowLinked w) throws OutOfBounds{
	
		if(w.link == after){
			throw new OutOfBounds("tried to access of end of list");
		}

		w.link = w.link.successor;

	}

	/** moves the window to the previous element
	* @param w the window to be moved
	* @throws OutOfBounds if the window is at before first
	*/ 
	public void previous(WindowLinked w) throws OutOfBounds {

		if(w.link == before){
			throw new OutOfBounds("tried to move previous at before first position");
		}

		Link old = w.link;
		w.link = before;
		while(w.link.successor != old){
			w.link = w.link.successor;
		}
	}

	/** inserts the element e after w
	* @param e the object to be inserted
	* @param w the window the element is to be inserted after
	* @throws outofbounds exception
	*/
	public void insertAfter(Object e,WindowLinked w) throws OutOfBounds {
		if(w.link == after ){
			throw new OutOfBounds("tried to insert after afterLast, die");
		}	
		Link old;
		old = w.link.successor;
		Link insert = new Link(e,old);
		w.link.successor = insert; 

	}

	/** inserts the object e before the window w 's postition
	* @param e the Object to be inserted
	* @param w the Window the link is to be inserted after
	* @throws outOfBounds if the window is beforeFirst
	*/
	public void insertBefore(Object e, WindowLinked w) throws OutOfBounds {

		if(w.link == before ){
			throw new OutOfBounds("tried to insert before first");
		}


		Link old = w.link;
		previous(w);
		Link insert = new Link(e,old);
		w.link.successor = insert;
		w.link = old;
	
	}


	/** returns teh object in teh current window
	* @param w the window of the element to look at
	* @return the Object of the windows link
	* @throws OutOfBounds a general exception if there is nothing there or pointing at an empty link
	*/
	public Object examine(WindowLinked w) throws OutOfBounds {
		if(w.link == after ||w.link == before){
			throw new OutOfBounds("nothing to examine here. tried to access" );
		}

		return w.link.item;
		
	
	}

	/** replaces the links object with a new one
	* @param w the window to replace the element with
	* @param e the new object to replace it with
	* @throws OutOfBounds if there is a problem
	*/
	public Object replace(Object e , WindowLinked w) throws OutOfBounds {

		if(w.link == before || w.link == after){
			throw new OutOfBounds("error.replacewentwrong:");
		}

		Object old = w.link.item;
		w.link.item = e;
		return old;

	}

	/** removes the element under w, returning the object and and puts w over the next element
	* @param w the window element to delete
	* @throws OutOfBOunds if teh element is before first or after last
	*/
	public Object delete(WindowLinked w) throws OutOfBounds {

		if(w.link == before || w.link == after ){
			throw new OutOfBounds("die die die");
		}

		Object oldItem = w.link.item;
		Object newItem = w.link.successor.item;
		w.link.successor = w.link.successor.successor;
		w.link.item = newItem;
		return oldItem;
		
	}

}
import DAT.*;
import ListLinked.*;

public class Test1 {

	public ListLinked li;

	public WindowLinked wi;

	public static void main(String[] args){
		
		li = new ListLinked();

		if(li.isEmpty() ) System.out.println("is empty");
		
		wi = new WindowLinked();

		li.beforeFirst(wi);
		
		li.insertAfter('a',wi);
		
		if(!li.isEmpty() ){
			System.out.println("isn't empty");
		}

		System.out.println("test " +list.examine(wi) );

		li.replace('b',wi);

		System.out.println("test2 "+ li.examine(wi) );

		li.delete(wi);

		System.out.println("end");

	}
}
import DAT.*;
import Exceptions.*;


public class MapLinked implements Map {
	
	private WindowLinked w;

	private ListLinked list;
	int count;

	public MapLinked(){
		count =0;
		list = new ListLinked();
		w = new WindowLinked();

		list.beforeFirst(w);
	}

	/** assigns an object for the dominant object
	* @param d the main object
	* @param c the object assigned with it
	*/
	public void assign(Object d,Object c){

		Pair insert = new Pair(d,c);
		
		if( isDefined(d) ){
			/* use the fact that the window won't have
			* been moved since the isDefined() call
			*/
			list.replace(insert,w);
			return;
		}		

		list.beforeFirst(w);		
		list.insertAfter(insert,w);
		count++;
	}
	
	/** deasign an object
	* @param a the dominante object that is removed
	* @return the image of the main object of the pair
	*/
	
	public Object deassign(Object a) throws ItemNotFound{
		Pair target;

		list.beforeFirst(w);
		if(!isDefined(a) ){
			throw new ItemNotFound("item not found");
		}
	
		//list.beforeFirst(w);	
		//while( !a.equals( ( (Pair)list.examine(w) ).item1 ) ){
		//	list.next(w);
		//}

		target = (Pair)list.delete(w);

		count--;

		return(target.item2);
	}
	
	/** returns the image of the object
	* @param d the object to check for the image of
	* @return the image object
	*/

	public Object image(Object d) throws ItemNotFound{

		list.beforeFirst(w);
		if( !isDefined(d) ){
			throw new ItemNotFound("item is not found");
		}
			
		while( !d.equals( ( (Pair)list.examine(w) ).item1 ) ){
			list.next(w);
		}
		
		return( ( (Pair)list.examine(w) ).item2 );
	}
	
	/** checks if the map is empty
	* @return true if empty, false otherwise
	*/
	public boolean isEmpty(){
		return( list.isEmpty() );
	}		
	
	/** check whether an object is defined
	* @param d the obejct to check for
	* @return true if it is defined, false if it can't be found
	*/
	public boolean isDefined( Object d){
		list.beforeFirst(w);
		boolean isDef = false;
		boolean notEnd = true;
		if(list.isEmpty() ){
			return false;
		}

		while(!isDef && notEnd){
			
			list.next(w);
			notEnd = !list.isAfterLast(w);
			if(notEnd){	
				isDef = d.equals( ( (Pair)list.examine(w) ).item1 );
			}
		}
		return isDef;
	}


}
import MapLinked;

public class Tester1 {
	
	public MapLinked map;

	public static void main(String args[] ){
	    MapLinked	map = new MapLinked();
		
		String str = "poppins";
		
		System.out.println( map.isEmpty() );
		map.assign("hero","Rommel");
		map.assign("religion","jesus");
		System.out.println( map.isEmpty() );

		System.out.println( map.image("hero") );
		map.assign("bob","jane");
		
		map.assign(str,"mary");
		
	    System.out.println( map.deassign(str) );
		
		

	}
}
import DAT.*;
import Exceptions.*;

public class OLBTest {

  public static void main(String[] args){
    Character a=new Character('a');
    Character b=new Character('b');
    OrderedList list1= new OrderedListBlock(10);
    OrderedList list2= new OrderedListBlock(10);
   
  
    list2.insert(a);
    list2.insert(new Character('b'));
    list2.insert(new Character('c'));
    list2.insert(new Character('d'));
    list2.insert(new Character('e'));
    list2.insert(new Character('f'));

    list1.insert(a);
    list1.insert(new Character('b'));
    list1.insert(new Character('c'));
    list1.insert(new Character('d'));
    list1.insert(new Character('e'));
    list1.insert(new Character('f'));
    list1.insert(new Character('g'));
    list1.insert(new Character('h'));
    list1.insert(new Character('i'));
    list1.insert(new Character('j'));

    System.out.println(list1.toString());
    System.out.println(list2.toString());
    System.out.println(list1.isSublist(list2));
    System.out.println(list1.getSublist(0,5));
    System.out.println(list2.getSublist(0,5));
    System.out.println(list1.getSize());
    System.out.println(list2.getSize());
    System.out.println(list1.equals(list2));
    System.out.println(list1.isSubset(list2));
    list2.delete(new Character('f'));
    System.out.println(list2.toString());
    System.out.println(list2.getSize());
    list2.insert(new Character('k'));
    System.out.println(list2.toString());

    
    
    //System.out.println(list1.isSubset(list2));
    //System.out.println(list2.getSublist(0,0));
    //System.out.println(list1.equals(list2));
    //list1.delete(b);
    //System.out.println(list1.toString());
    //list2.delete(b);
    //System.out.println(list2.getItem(0));
    //System.out.println(myList.getSize());
    // myList.insert(new Character('b'));
  }
}

public class OrderedListBlock implements OrderedList {

  /*
   * An array to hold the items in the ordered list. The items should
   * be stored contiguously from position 0.
   */
  private Object[] block;

  /*
   * A variable for storing the number of items in the ordered list.
   */
  private int count;

  public OrderedListBlock(int size){
	block = new Object[size];
	count = 0;
  }



   public boolean isEmpty(){
	return(count==0);
   }


   public boolean isFull(){
	return(count >= block.length);
   } 

   public boolean isInList(Object item){
	if(isEmpty() ){
		return false;
	}
	int loc = binarySearch(item,0,count);
	if(block[loc].toString() == item.toString() ){
		return true;
	}
	else{
		return false;
	}
   }

   /* do these items exist in any order in the list */
   public boolean isSubset(OrderedList items){
	Object test;
	int sizeOfItems = items.getSize();
	int i =0;
	boolean isSet = true;

	while(isSet && i<sizeOfItems){
	    test = items.getItem(i);
	    isSet = isInList(test);
	    i++;
	}
	return( isSet );

   }

   public boolean isSublist(OrderedList items){
	Object test;
	int i =0;
	int sizeOfList = items.getSize();
	int startIndex;

	if(sizeOfList == 0){
	    return false;
	}

	boolean isSubList = true;
	
	test = items.getItem(0);
		
	startIndex = binarySearch(test,0,count);

	for(i =0; i<sizeOfList && isSubList ;i++){
	    test = items.getItem(i);
	    isSubList = ( test.toString() == block[startIndex + i].toString() );
	}
	return isSubList;
   }


   public int getSize(){
	return count;
   }

   public Object getItem(int index) throws Overflow{
	if(index >= count){
		throw new Overflow(" index requested out of list: " + index);
	}
	else{
	  return(block[index]);
  	}
   }

   public OrderedList getSublist(int lowerBound, int upperBound) throws Overflow{
	if(lowerBound < 0 || upperBound >= count){
	    throw new Overflow("bounds for getSublist not set correctly");
	}
	
	int size = upperBound - lowerBound;
	int i;

	OrderedListBlock returnList = new OrderedListBlock(size);
    
	for(i = lowerBound;i<upperBound;i++){
	    returnList.insert(block[i]);
	}

	return(returnList);	
    }

    public void insert(Object item) throws Overflow{
	int i;
	if(isEmpty() ){
	    block[0] = item;
	    count++;
	    return;
	}
	if(isFull() ){
	    throw new Overflow(" inserting to full list");
	}
	    
	int tempIndex = binarySearch(item,0,count-1);

	if(block[tempIndex].toString() == item.toString() ){
	    return;
	}
	if(block[tempIndex].toString().compareTo(item.toString()) <0 ){
	    tempIndex++;
	}

	for(i = count;i > tempIndex; i--){
	    block[i] = block[i-1];
	}

	count++;
	block[tempIndex] = item;   
	
    }

    public void delete(Object item){
	int tempIndex;
	int i;

	tempIndex = binarySearch(item,0,count-1);
	
	if(block[tempIndex].toString() != item.toString() ){
	    return;
	}

	for(i = tempIndex; i < count-1;i++){
	    block[i] = block[i+1];
	}
	count--;

    }


	
    public boolean equals(OrderedList list){
	
	return(list.toString() == toString() );
    }

    public String toString(){
	int i;
	String objString = new String("");


	for(i=0;i<count;i++){
	    objString = objString + block[i].toString() + '\n' ;
	}

	return objString;

    }	


  /*
   * Carries out a recursive binary search for item d in the block 
   * between limits l and u. Returns the index of the item if found, 
   * otherwise returns the index of either the closest object below
   * the item or the closest object above the item. 
   */ 
  private int binarySearch (Object d, int l, int u) {
    if (l > u) throw new RuntimeException("Illegal call to binaryLocate.");
    if (l == u) return l;
    else {   
      int m = (l + u) / 2;   
      if (d.toString().compareTo(block[m].toString()) <= 0)   
        return binarySearch(d,l,m);   
      else return binarySearch(d,m+1,u);   
    }   
  }   

}

/**
 * An ordered list (or set) that allows logarithmic time searches for 
 * objects. Objects can also be retrieved according to their position
 * in the list, starting with position 0.
 * @author Cara MacNish
 */
public interface OrderedList {

  /**
   * test if the list is empty
   * @return true if the list is empty, false otherwise
   */
  public boolean isEmpty ();

  /**
   * test if the list is full
   * @return true if the list is full, false otherwise
   */
  public boolean isFull ();

  /**
   * look for an item in the ordered list
   * @param item the item to be found
   * @return true if the item is found (as judged by comparing string
   * representations), false otherwise
   */
  public boolean isInList (Object item);

  /**
   * look for a list of items in the ordered list
   * @param items the items to be found
   * @return true if the items are all found (the passed list is a 
   * "subset" of the list), false otherwise
   */
  public boolean isSubset (OrderedList items);

  /**
   * look for a list of consecutive items in the ordered list
   * @param items the items to be found
   * @return true if the items are all found consecutively (that is, in
   * the same order, with no other items in between, as this list), 
   * false otherwise
   */
  public boolean isSublist (OrderedList items);

  /**
   * get the size of the list
   * @return the size
   */ 
  public int getSize ();

  /**
   * get the item at some position in the list
   * @param position the index of the item to be retrieved
   * @return the item at that position
   * @exception Overflow if the position is not within the current list
   */
  public Object getItem (int position) throws Overflow;

  /**
   * get a list of the items between two positions in the list
   * @param lowerBound the index of the first item in the sublist
   * @param upperBound the index of the last item in the sublist
   * @return an ordered list consisting of all items between the bounds
   * (inclusive) in the same order
   * @exception Overflow if the bounds are not within the current list
   */
  public OrderedList getSublist (int lowerBound, int upperBound) throws Overflow;

  /**
   * insert an item in the list - if the item is already contained in 
   * the list no action should be taken 
   * @param item the item to insert
   * @exception Overflow if the item is not in the list, and the list is full
   */ 
  public void insert (Object item) throws Overflow;

  /** 
   * delete an item from the list - if the item is not in the list
   * no action should be taken
   * @param item the item to remove
   */
  public void delete (Object item);

  /**
   * checks whether the list is equal to the argument list 
   * @param list the list to compare
   * @return true if the lists have the same items (as judged by comparing
   * string representations of the items) in the same order
   */
  public boolean equals (OrderedList list);

  /** 
   * create a string representation of this list - this should be
   * constructed using the toString() method of each object in the
   * list (in order) separated by newline ("\n") characters
   * @return the string representation
   */
  public String toString ();

}

/**
 * Indicates an attempt to add to a full container class 
 * such as a stack or queue.
 * @author Cara MacNish
 * @version Time-stamp: <98/04/20 18:55 cara>
 */
public class Overflow extends RuntimeException {

  /**
   * Construct this exception object.
   * @param message the error message.
   */
  public Overflow( String message ) {
    super( message );
  }
}