package algs35;
import stdlib.*;
import java.util.HashMap;
import java.util.TreeSet;
/* ***********************************************************************
 *  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.
 *
 *************************************************************************/

public class XIndirectPQ {
  private final TreeSet<Element> pq = new TreeSet<>();
  private final HashMap<String,Element> st = new HashMap<>();

  private static class Element implements Comparable<Element> {
    public final String key;
    public final int priority;

    public Element(String key, int priority) {
      this.key       = key;
      this.priority  = priority;
    }
    public int compareTo(Element object) {
      Element e = object;
      if (priority != e.priority) return priority - e.priority;
      return key.compareTo(e.key);
    }
    public boolean equals(Object e) {
      if (e == null) return false;
      Element that = (Element) e;
      return (priority == that.priority && key.equals(that.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 = 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 = st.get(key);
    return e.priority;
  }

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

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

  // delete and return the minimum value, error if empty
  public String delMin() {
    Element min = 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 = pq.last();
    pq.remove(max);
    st.remove(max.key);
    return max.key;
  }


  // test client
  public static void main(String[] args) {
    XIndirectPQ pq = new XIndirectPQ();
    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())
      StdOut.println(pq.delMax());
  }

}