/**
 * Implementation of a stack based on an array.
 */
public class ArraySearchableStack<E> implements SearchableStack<E> {
  
  private E[] as;
  private int top = 0;
  private int maxSize;
  
  /**
   * Constructor. 
   */

  public ArraySearchableStack(int size) {
    as = (E[]) new Object[size];
    maxSize = size;
  }
  
  /**
   * Push an element.
   * @param e The object to be pushed.
   */
  public void push(E e) {
    as[top] = e;
    top = top + 1;
  }
  
  /**
   * Pop an object.
   */
  public E pop() {
    top = top - 1;
    return as[top];
  }
  
  /**
   * Check whether empty.
   */
  public boolean isEmpty() {
    return top == 0; 
  }
  
  /**
   * Check whether full.
   */
  public boolean isFull() {
    return top == maxSize;
  }
  
  /**
   * Return the current size.
   */
  public int size() {
    return top; 
  }
  
  /**
   * Check whether there is a match of the object in
   * the searchable stack.
   * @param e The object you are looking for a match of.
   */
  public boolean search( E o ) {

    SearchableStack<E> s = new ArraySearchableStack(top);
    while(!isEmpty()) {
      
      E next = pop();       
      s.push( next );
      if( o.equals(next)) {
        while(!s.isEmpty()) {
          push(s.pop());
        }
        return true;
      } 
    }
    
    while(!s.isEmpty()) {
      push(s.pop());
    }  
    return false;
  }

  /**
   * Find, remove and return a matching element.
   * While searching a match shift any non-matching
   * Objects to a storage space.
   * @param E The object you are looking for a match of.
   */
  public E find(E e) { 
    
    SearchableStack<E> s = new ArraySearchableStack(top);
    E next = this.pop();
    while(!e.equals(next)) {
      s.push(next);
      next = this.pop();        
    }
    while(!s.isEmpty()) {
      push(s.pop());
    }      
    return e;
  }
  
  /** 
   * Return a string representation of the stack.
   */
  public String toString( ) {
    
    SearchableStack<E> s = new ArraySearchableStack(top);
    String myContents = "";

    while( !this.isEmpty() ) {

      E next = this.pop();        
      myContents = myContents + next.toString() + "\n";
      s.push(next);  
    }
    
    while(!s.isEmpty()) {
      push(s.pop());
    }      
    return myContents;
  }
}