PriorityQueue.java

Go to the documentation of this file.

package aud;
 
import java.util.Comparator;
 
import aud.adt.AbstractPriorityQueue;
 
public class PriorityQueue<T> extends AbstractPriorityQueue<T> {
 
  // TODO define unit test for PriorityQueue
  // TODO Is it better to "outsource" the mapping? (public upheap, downheap)?
 
  private static final int MINENTRIES=64;
 
  Vector<T>          heap_;
 
  HashMap<T,Integer> position_;
 
  public PriorityQueue(int n,Comparator<T> cmp) {
    super(cmp);
    heap_=new Vector<T>();
    heap_.reserve(n);
    position_=new HashMap<T,Integer>(n);
  }
  public PriorityQueue(Comparator<T> cmp) { this(MINENTRIES,cmp); }
 
  public PriorityQueue(int n) { this(n,null); }
  public PriorityQueue() { this(MINENTRIES,null); }
 
  @Override public T front() {
    return heap_.front(); // may throw
  }
 
  @Override public boolean is_empty() {
    return heap_.empty();
  }
 
  public boolean contains(T x) { return position_.contains(x); }
 
  public int size() { return heap_.size(); }
 
  @Override public T pop() {
    T root=heap_.front(); // may throw
    position_.remove(root);
 
    if (heap_.size()>1) {
      position_.insert((heap_.data_[0]=heap_.back()),0);
      heap_.pop_back();
      downheap(0);
    }
    else
      heap_.pop_back();
 
    return root;
  }
 
  int getParent(int k) { return ((k+1)/2)-1; }
  int getLeftChild(int k) { return ((k+1)*2)-1; }
  boolean less(int i,int j) {
    return super.less(heap_.at(i),heap_.at(j));
  }
  boolean leq(int i,int j) {
    if (less(i,j))  return true;
    else            return !less(j,i); // symmetric test fails for equality
  }
  boolean less(T x,int k) {
    return super.less(x,heap_.at(k));
  }
  void move(int from,int to) {
    T x=heap_.data_[from];
    heap_.data_[to]=x;
    position_.insert(x,to);
  }
  void set(int k,T x) {
    heap_.data_[k]=x;
    position_.insert(x,k);
  }
 
  void downheap(int k) {
    T x=heap_.data_[k];
    int j=getLeftChild(k);
 
    while (j<heap_.size()) {
      if (j<heap_.size()-1 && less(j+1,j)) j=j+1;
      if (less(x,j)) break;
      move(j,k);
      k=j;
      j=getLeftChild(k);
    }
    set(k,x);
  }
 
  @Override public void push(T x) {
    if (contains(x))
      throw new RuntimeException(x.toString()+" already contained in PQ");
 
    int k=heap_.size();
    heap_.push_back(x);
    position_.insert(x,k);
    upheap(k);
  }
 
  void upheap(int k) {
    if (k>0) {
      T x=heap_.data_[k];
      int p;
      while (k>0 && less(x,p=getParent(k))) {
        move(p,k);
        k=p;
      }
      set(k,x);
    }
  }
 
  public void raise(T x) {
    assert(position_.contains(x));
    int k=position_.find(x);
 
    assert(k==0 || less(getParent(k),k));   // priority was raised!
 
    downheap(k);
  }
 
  public void lower(T x) {
    assert(position_.contains(x));
    int k=position_.find(x);
 
    // Assert that priority was lowered!
    assert(getLeftChild(k)  >=heap_.size() || less(k,getLeftChild(k)));
    assert(getLeftChild(k)+1>=heap_.size() || less(k,getLeftChild(k)+1));
 
    upheap(k);
  }
 
  @Override public String toString() {
    return position_.toString();
  }
 
  public void checkConsistency() {
    System.err.println("size="+heap_.size());
    // check mapping between heap_ and position_
    if (heap_.size()!=position_.size())
      throw new RuntimeException("size mismatch");
    for (int i=0;i<heap_.size();++i)
      if (position_.find(heap_.at(i))==null || position_.find(heap_.at(i))!=i)
        throw new RuntimeException("invalid mapping for key='"+heap_.at(i)+"'");
 
    // check heap property
    for (int i=0;i<heap_.size();++i) {
      if (i>0) {
        int p=getParent(i);
        if (!leq(p,i))
          throw new RuntimeException("heap property violated (parent");
      }
      int left=getLeftChild(i);
      if (left<heap_.size()) {
        if (!leq(i,left))
          throw new RuntimeException("heap property violated (left)");
 
        int right=left+1;
        if (right<heap_.size()) {
          if (!leq(i,right))
            throw new RuntimeException("heap property violated (right)");
        }
      }
    }
  }
 
  public static void main(String[] args) {
 
    {
      // use as a "standard" priority queue
 
      PriorityQueue<Integer> pq=new PriorityQueue<Integer>();
 
      pq.push(2); System.out.println(pq);
      pq.push(4); System.out.println(pq);
      pq.push(3); System.out.println(pq);
      pq.push(1); System.out.println(pq);
 
      System.out.println(pq.pop());
      System.out.println(pq);
 
      System.out.println(pq.pop());
      System.out.println(pq);
    }
    {
      // now the following provides a mapping from entries to priorities
      final HashMap<String,Integer> priority=new HashMap<String,Integer>();
      priority.insert("a",1);
      priority.insert("b",2);
      priority.insert("c",3);
      priority.insert("d",4);
 
      PriorityQueue<String> pq=
        new PriorityQueue<String>
        (new Comparator<String>() {
          @Override public int compare(String a,String b) {
            return priority.find(a)-priority.find(b);
          }
        });
 
      // first we do the same as above
 
      pq.push("b"); System.out.println(pq);
      pq.push("d"); System.out.println(pq);
      pq.push("c"); System.out.println(pq);
      pq.push("a"); System.out.println(pq);
 
      System.out.println(pq.pop());
      System.out.println(pq);
 
      System.out.println(pq.pop());
      System.out.println(pq);
 
      // restore what we had before
      pq.push("b"); System.out.println(pq);
      pq.push("a"); System.out.println(pq);
 
      // now we gonna change the priority mapping and update pq
 
      System.out.println("front="+pq.front());
      priority.insert("a",5); // RAISE priority ...
      System.out.println("new prioities: "+priority);
      pq.raise("a");         // ... and update pq
      System.out.println("front="+pq.front());
      priority.insert("c",0); // LOWER priority ...
      System.out.println("new prioities: "+priority);
      pq.lower("c");         // ... and update pq
      System.out.println("front="+pq.front());
    }
  }
 
}