PET: Partial Evaluation-based Test Case Generator for Bytecode

package net.datastructures;
import java.util.Comparator;

/** Realization of a priority queue by means of a heap.  The heap is
  * built upon a vector-based complete binary tree.
  *
  @author Roberto Tamassia, Michael Goodrich, Eric Zamore
  */
public class HeapPriorityQueue implements PriorityQueue 
  protected CompleteBinaryTree T;
  protected Comparator comp;
  /** Inner class for heap entries. */
  protected static class  MyEntry implements Entry {
    protected Object key, value;
    public MyEntry(Object k, Object v) { key = k; value = v; }
    public Object key() { return key; }
    public Object value() { return value; }
    public String toString() { return "(" + key  + "," + value + ")"}
  }
  /** Inner class for a comparator that uses the natural ordering of keys. */
  protected static class DefaultComparator implements Comparator {
    public DefaultComparator() { /* default constructor */ }
    public int compare(Object a, Object bthrows ClassCastException 
      return ((Comparablea).compareTo(b)// use the natural order for a
    }
  }
  /** Creates an empty heap with the default comparator. */ 
  public HeapPriorityQueue() {  
    T = new VectorCompleteBinaryTree()// use a vector-based tree
    comp = new DefaultComparator();     // use the default comparator
  }
  /** Creates an empty heap with the given comparator. */
  public HeapPriorityQueue(Comparator c) {
    T = new VectorCompleteBinaryTree();
    comp = c;
  }
  /** Sets the comparator used for comparing items in the heap. 
   @throws IllegalStateException if priority queue is not empty */
  public void setComparator(Comparator cthrows IllegalStateException {
    if(!isEmpty())  // this is only allowed if the priority queue is empty
      throw new IllegalStateException("Priority queue is not empty");
    comp = c;
  }
  /** Returns the size of the heap. */
  public int size() { return T.size()
  /** Returns whether the heap is empty. */
  public boolean isEmpty() { return T.size() == 0}
  /** Returns but does not remove an entry with minimum key. */
  public Entry min() throws EmptyPriorityQueueException {
    if (isEmpty()) 
      throw new EmptyPriorityQueueException("Priority queue is empty");
    return entry(T.root());
  }
  /** Inserts a key-value pair and return the entry created. */
  public Entry insert(Object k, Object xthrows InvalidKeyException {
    checkKey(k);  // may throw an InvalidKeyException
    Entry entry = new MyEntry(k,x);
    upHeap(T.add(entry));
    return entry;
  }
  /** Removes and returns an entry with minimum key. */
  public Entry removeMin() throws EmptyPriorityQueueException {
    if (isEmpty()) 
      throw new EmptyPriorityQueueException("Priority queue is empty");
    Entry min = entry(T.root());
    if (size() == 1)
      T.remove();
    else {
      T.replace(T.root(), T.remove());
      downHeap(T.root());
    }
    return min;
  }
  /** Returns the entry stored at a heap node. */
  protected Entry entry (Position p) { 
    return (Entryp.element()
  }
  /** Returns the key stored at a heap node. */
  protected Object key (Position p) {
    return ((Entryp.element()).key()
  }
  /** Determines whether a given key is valid. */
  protected void checkKey(Object keythrows InvalidKeyException {
    try {
      comp.compare(key,key);
    }
    catch(Exception e) {
      throw new InvalidKeyException("Invalid key");
    }
  }
   /** Performs up-heap bubbling. */
  protected void upHeap(Position v) {
    Position u;
    while (!T.isRoot(v)) {
      u = T.parent(v);
      if (comp.compare(key(u), key(v)) <= 0break;
      swapElements(u, v);
      v = u;
    }
  }
  /** Performs down-heap bubbling. */
  protected void downHeap(Position r) {
    while (T.isInternal(r)) {
      Position s;    // the position of the smaller child
      if (!T.hasRight(r))
  s = T.left(r);
      else if (comp.compare(key(T.left(r)), key(T.right(r))) <=0)
  s = T.left(r);
      else
  s = T.right(r);
      if (comp.compare(key(s), key(r)) 0) {
  swapElements(r, s);
  r = s;
      }
      else 
  break;
    }
  }
  /** Swaps the elements of the two positions. */
  protected void swapElements(Position x, Position y) {
    Object temp = x.element();
    T.replace(x, y.element());
    T.replace(y, temp);
  }
  /** Text visualization for debugging purposes */
  public String toString() {
    return T.toString();
  }
}

The Java2Html library is used for displaying source code.