package pqueue;

import container.*;
import java.util.NoSuchElementException;
import java.util.Comparator;

/** This implementation uses two adaptable heap priority queues.  The
 * second one has the same entries as the first, but in reverse order.
 */

public class TwoHeapAdaptablePriorityDeque extends HeapAdaptablePriorityQueue 
                                           implements AdaptablePriorityDeque {
 
  /* We're extending HeapAdaptablePriorityQueue, so the first pqueue is 
   * simply "this."  The second pqueue is stored in pqRev.
   *
   * Any changes must be made to both pqueues.  This is possible
   * because "twin" entries on the two pqueues always point to each
   * other.
   *
   * When we return an entry to the user, we always return the one on
   * "this" pqueue, not on pqRev.
   *
   * Many methods are simply inherited because it is fine to run them
   * only on "this," ignoring the extra information in pqRev:
   *    size(), isEmpty(), min(), toString() ...
   */

  protected HeapAdaptablePriorityQueue pqRev;  

  // ----- CONSTRUCTORS -----

  public TwoHeapAdaptablePriorityDeque() {
    this(new DefaultComparator());   // call another constructor for this class
  }

  public TwoHeapAdaptablePriorityDeque(Comparator c) {
    super(c);                // call constructor for parent class
    pqRev = new HeapAdaptablePriorityQueue(new ReverseComparator(c));
  }

  // ----- PUBLIC METHODS THAT OVERRIDE HeapAdaptablePriorityQueue METHODS -----

  public Entry insert(Object k, Object v) throws InvalidKeyException {

    /* Insert (k,v) on both priority queues.  We do this by explicitly
     * calling the superclass's insert() method, rather than duplicating
     * its code, which would be dangerous if the code changed in future.
     */

    Entry e    = super.insert(k,v);
    Entry eRev = pqRev.insert(k,v);

    /* However, the superclass didn't do quite the right thing, so now
     * we have to fix up its result.  We have to make e and eRev point
     * to each other, so that either one can find the other.  First we
     * have to "upgrade" them so that they have room for that extra
     * pointer.  (Yuck!)
     */

    TwinnedLocationAwareEntry twin1 = upgradeEntry(e, this);
    TwinnedLocationAwareEntry twin2 = upgradeEntry(eRev, pqRev);

    twin1.setTwin(twin2);
    twin2.setTwin(twin1);
    return twin1;

    /* Note that the above comments aren't Javadoc comments (they
     * don't start with "**").  That's because they concern this
     * method's implementation, not its interface (which is already
     * documented in PriorityQueue.java).  We don't have to publicize
     * how the data structure works inside.
     */
  }

  public Entry remove(Entry e) throws InvalidEntryException {
    FILL THIS IN
  }

  public Entry removeMin() throws EmptyPriorityQueueException {
    return remove(min());
  }

  public Object replaceKey(Entry e, Object k) throws InvalidEntryException, InvalidKeyException {
    FILL THIS IN
  }

  public Object replaceValue(Entry e, Object v) throws InvalidEntryException {
    FILL THIS IN
  }

  // ----- NEW METHODS THAT IMPLEMENT PriorityDeque -----

  public Entry max() throws EmptyPriorityQueueException {
    FILL THIS IN - CAREFUL!
  }

  public Entry removeMax() throws EmptyPriorityQueueException {
    return remove(max());
  }
 
  // ------ NESTED CLASS --------

  /** A comparator whose ordering is exactly the reverse of another comparator's. */
  public static class ReverseComparator implements Comparator {
    FILL THIS IN  
      (Hint: its constructor is called earlier in this file)
      (Hint: for inspiration, see the NullComparator example on the Homework 6 webage)
  }

  // ----- NESTED CLASS -----

  protected static class TwinnedLocationAwareEntry extends LocationAwareEntry {
    private TwinnedLocationAwareEntry twin;
    
    /* Given a LocationAwareEntry, this constructor creates a twinned
     * version that contains all the same data, but also has an extra
     * "twin" field that can be set and changed.  This twin field is
     * initially null.
     */
    public TwinnedLocationAwareEntry(LocationAwareEntry e) {
      super(e.key(), e.value(), e.location());
    }

    protected TwinnedLocationAwareEntry twin() { return twin; }

    protected void setTwin(TwinnedLocationAwareEntry e) { twin = e; }

    // key(), value(), and toString() are all inherited.
  }
  
  // ------ UTILITY METHODS FOR DEALING WITH TWINS --------

  /** Sneakily replace a LocationAwareEntry in a priority queue with a
   * TwinnedLocationAwareEntry that carries the same data. */

  private static TwinnedLocationAwareEntry upgradeEntry(Entry e, 
							HeapAdaptablePriorityQueue pq) {
    pq.checkEntry(e);
    LocationAwareEntry lae = (LocationAwareEntry)e;                       // old version
    TwinnedLocationAwareEntry tlae = new TwinnedLocationAwareEntry(lae);  // upgraded version
    pq.T.replace(lae.location(), tlae);  // replace lae with tlae in the heap's
                                         // CompleteBinaryTree, namely pq.T.
    return tlae;
  }
  
  /** Given an Entry in one priority queue, return its twin in 
   * the other priority queue.  Throws an exception if there's
   * no twin.
   */
  private Entry twin(Entry e) throws InvalidEntryException {
    if (e == null)
      throw new InvalidEntryException("null entry");
    else if (!(e instanceof TwinnedLocationAwareEntry))
      throw new InvalidEntryException("entry is not on a TwoHeapAdaptablePriorityDeque");
    else {
      return ((TwinnedLocationAwareEntry)e).twin();
    }
  }

  // -------- TEST METHOD ---------

  /** Try running this test method with an odd or even number of command-line arguments. */

  public static void main(String[] args) {
    AdaptablePriorityDeque pd = new TwoHeapAdaptablePriorityDeque();

    // The print statements below assume that the entries have a
    // toString() method.  They do (inherited from HeapPriorityQueue.MyEntry).

    int i;

    for (i=0; i < args.length; i++) {
      Entry e = pd.insert(args[i], new Integer(i));
      System.out.println("inserted " + e);
      pd.replaceValue(e, new Integer(3*i));
      System.out.println("tripled element to get " + e);
    }

    System.out.println();
    while (!pd.isEmpty()) {
      try {
	System.out.println("removing min from deque of size "+pd.size()+": "+pd.min()); 
	pd.remove(pd.min());
	System.out.println("removing max from deque of size "+pd.size()+": "+pd.max()); 
	pd.remove(pd.max());
      } catch (EmptyPriorityQueueException ex) {
	System.out.println("Caught EmptyPriorityQueueException while trying to remove max"
			   +"\n   (had odd number of elements, but tried to remove two at a time)");
      }
    }

    System.out.println();
    for (i=0; i < args.length; i++) 
      System.out.println("inserted " + pd.insert(new Integer(i), args[i]));
			 
    System.out.println();
    for (i=0; i < args.length; i++) {
      Entry e = pd.max();
      System.out.println("finding max and negating key to make it min: " + e);
      Integer key = (Integer)e.key();
      pd.replaceKey(e, new Integer(-key.intValue()));
    }

    System.out.println();
    for (i=0; i < args.length; i++) {
      Entry e = pd.min();
      System.out.println("finding min and negating key to make it max: " + e);
      Integer key = (Integer)e.key();
      pd.replaceKey(e, new Integer(-key.intValue()));
    }

    System.out.println();
    for (i=0; i < args.length; i++) {
      System.out.println("removing min: " + pd.min());
      pd.remove(pd.min());
    }
  }
}