001package algs35;
002import stdlib.*;
003import java.util.HashMap;
004import java.util.TreeSet;
005/* ***********************************************************************
006 *  Compilation:  javac IndirectPQ.java
007 *  Execution:    java IndirectPQ
008 *
009 *  Indirect priority queue implementation with Java's TreeSet and
010 *  HashMap. It assumes the priorities are integers and the values
011 *  are strings, although it is easily modifiable for Comparable
012 *  priorities and Object values.
013 *
014 *  % java IndirectPQ
015 *  this
016 *  is
017 *  a
018 *  test
019 *
020 *  Remarks
021 *  -------
022 *  All operations are efficient, but it could be improved by using
023 *  a binary heap instead of the red-black tree.
024 *
025 *************************************************************************/
026
027public class XIndirectPQ {
028        private final TreeSet<Element> pq = new TreeSet<>();
029        private final HashMap<String,Element> st = new HashMap<>();
030
031        private static class Element implements Comparable<Element> {
032                public final String key;
033                public final int priority;
034
035                public Element(String key, int priority) {
036                        this.key       = key;
037                        this.priority  = priority;
038                }
039                public int compareTo(Element object) {
040                        Element e = object;
041                        if (priority != e.priority) return priority - e.priority;
042                        return key.compareTo(e.key);
043                }
044                public boolean equals(Object e) {
045                        if (e == null) return false;
046                        Element that = (Element) e;
047                        return (priority == that.priority && key.equals(that.key));
048                }
049        }
050
051
052        public boolean isEmpty() { return pq.isEmpty(); }
053        public int size()        { return pq.size();    }
054
055        // insert a key with a given priority (changing the priority if the key is present)
056        public void put(String key, int priority) {
057                delete(key);
058                Element e = new Element(key, priority);
059                st.put(key, e);
060                pq.add(e);
061        }
062
063        // does the key exist?
064        public boolean exists(String key) {
065                return (st.get(key) != null);
066        }
067
068        // delete key
069        void delete(String key) {
070                Element e = st.get(key);
071                if (e != null) {
072                        pq.remove(e);
073                        st.remove(key);
074                }
075        }
076
077        // return the priority of a given key
078        int get(String key) {
079                Element e = st.get(key);
080                return e.priority;
081        }
082
083        // return minimum priority, error if empty
084        public int min() {
085                Element min = pq.first();
086                return min.priority;
087        }
088
089        // return minimum priority, error if empty
090        public int max() {
091                Element max = pq.last();
092                return max.priority;
093        }
094
095        // delete and return the minimum value, error if empty
096        public String delMin() {
097                Element min = pq.first();
098                pq.remove(min);
099                st.remove(min.key);
100                return min.key;
101        }
102
103        // delete and return the maximum value, error if empty
104        public String delMax() {
105                Element max = pq.last();
106                pq.remove(max);
107                st.remove(max.key);
108                return max.key;
109        }
110
111
112        // test client
113        public static void main(String[] args) {
114                XIndirectPQ pq = new XIndirectPQ();
115                pq.put("test", 31);
116                pq.put("is",   55);
117                pq.put("this", 25);
118                pq.put("not",  65);
119                pq.put("a",    36);
120                pq.put("this", 61);      // changes the key
121                pq.delete("not");
122
123                while (!pq.isEmpty())
124                        StdOut.println(pq.delMax());
125        }
126
127}