import java.util.Vector;
import java.util.NoSuchElementException;

/*
 * An implementation of a Priority Queue built using Vector.  Uses the
 * Vector ability to increase capacity automatically; see
 * java.util.Vector
 */

public abstract class PriorityQueue {

  private Vector elements;         // elements of the priority queue
  final int INITIALCAPACITY = 10;  // initial capacity

  // Create a new priority queue; size doubles whenever it gets full
  public PriorityQueue () {
    elements = new Vector(INITIALCAPACITY, 0);
  }

  // Override this method to determine how items are ordered
  // return true iff Object a is before Object b
  abstract public boolean before (Object a, Object b);

  // Insert an element into the priority queue
  public void insert (Object item) {
    elements.addElement(item);
  }

  // Check if the priority queue is empty
  public boolean isEmpty () {
    return elements.isEmpty();
  }

  // Return the minimum element in the priority queue
  // throw NoSuchElementException if queue is empty
  public Object peek () {
    if (isEmpty()) throw new NoSuchElementException("PriorityQueue");
    Object min = elements.elementAt(0);
    for (int i = 1; i < elements.size(); i++)
      if (before(elements.elementAt(i), min))
        min = elements.elementAt(i);
    return min;
  }

  // Delete the minimum element from the priority queue and return it
  public Object get () {
    Object item = this.peek();
    elements.removeElement(item);
    return item;
  }

  // Clear the priority queue
  public void clear () {
    elements.removeAllElements();
  }

  // return the current size of the priority queue
  public int size () {
    return elements.size();
  }

  // return a string representation of the priority queue  
  // useful for debugging
  public String toString() {
    return elements.toString();
  }
}