IndirectPQ.java

Below is the syntax highlighted version of IndirectPQ.java from §3.5 Searching Applications.

/*************************************************************************
 *  Compilation:  javac IndirectPQ.java
 *  Execution:    java IndirectPQ
 *  
 *  Indirect priority queue implementation with Java's TreeSet and
 *  HashMap. It assumes the priorities are integers and the values
 *  are strings, although it is easily modifiable for Comparable
 *  priorities and Object values.
 * 
 *  % java IndirectPQ
 *  this
 *  is
 *  a
 *  test 
 *
 *  Remarks
 *  -------
 *  All operations are efficient, but it could be improved by using
 *  a binary heap instead of the red-black tree.
 *
 *************************************************************************/

import java.util.HashMap;
import java.util.TreeSet;

public class IndirectPQ {
    private TreeSet pq = new TreeSet();
    private HashMap st = new HashMap();

    private class Element implements Comparable {
        private String key;
        private int priority;

        public Element(String key, int priority) {
            this.key       = key;
            this.priority  = priority;
        }
        public int compareTo(Object object) {
            Element e = (Element) object;
            if (priority != e.priority) return priority - e.priority;
            return key.compareTo(e.key);
        }
        public boolean equals(Element e) {
            if (e == null) return false;
            return (priority == e.priority && key.equals(e.key));
        }
    }


    public boolean isEmpty() { return pq.isEmpty(); }
    public int size()        { return pq.size();    }

    // insert a key with a given priority (changing the priority if the key is present)
    public void put(String key, int priority) {
        delete(key);
        Element e = new Element(key, priority);
        st.put(key, e);
        pq.add(e);
    }

    // does the key exist?
    public boolean exists(String key) {
        return (st.get(key) != null);
    }

    // delete key
    void delete(String key) {
        Element e = (Element) st.get(key);
        if (e != null) {  
            pq.remove(e);
            st.remove(key);
        }
    }

    // return the priority of a given key
    int get(String key) {
        Element e = (Element) st.get(key);
        return e.priority;
    }

    // return minimum priority, error if empty
    public int min() {
        Element min = (Element) pq.first();
        return min.priority;
    }

    // return minimum priority, error if empty
    public int max() {
        Element max = (Element) pq.last();
        return max.priority;
    }

    // delete and return the minimum value, error if empty
    public String delMin() {
        Element min = (Element) pq.first();
        pq.remove(min);
        st.remove(min.key);
        return min.key;
    }

    // delete and return the maximum value, error if empty
    public String delMax() {
        Element max = (Element) pq.last();
        pq.remove(max);
        st.remove(max.key);
        return max.key;
    }


    // test client
    public static void main(String[] args) {
        IndirectPQ pq = new IndirectPQ();
        pq.put("test", 31);
        pq.put("is",   55);
        pq.put("this", 25);
        pq.put("not",  65);
        pq.put("a",    36);
        pq.put("this", 61);      // changes the key
        pq.delete("not");

        while (!pq.isEmpty())
            System.out.println(pq.delMax());
    }

}