import java.util.*;
/**
 * Implementation of a stack based on an ArrayList.
 */
public class ArrayListSearchableStack<E> implements SearchableStack<E> {
  
  private ArrayList<E> as;
  private int top = 0;
  
  /**
   * Constructor. 
   */

  public ArrayListSearchableStack() {
    as = new ArrayList<E>();
  }
  
  /**
   * Push an element.
   * @param e The object to be pushed.
   */
  public void push(E e) {
    as.add(top, e);
    top = top + 1;
  }
  
  /**
   * Pop an object.
   * @return the top element in the stack
   */
  public E pop() {
    top = top - 1;
    return as.remove(top);
  }
  
  /**
   * Check whether empty.
   * @return whether empty
   */
  public boolean isEmpty() {
    return top == 0; 
  }
  
  /**
   * Check whether full.
   * @return whether full
   */
  public boolean isFull() {
    return false;
  }
  
  /**
   * Return the current size.
   * @return the size
   */
  public int size() {
    return top; 
  }
  
  /**
   * Check whether a matching element is contained.
   * @return whether a matcing element is stored.
   */
  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.
   * @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.
   * @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;
  }
}