import java.util.NoSuchElementException;

public class TreePriorityQueue implements PriorityQueue
{
  private TreeNode root;

  public TreePriorityQueue()
  {
    root = null;
  }

  // postcondition: returns true if the priority queue is empty;
  //                otherwise returns false
  public boolean isEmpty()
  { return root == null;
  }

  // postcondition: obj has been added to the priority queue
  public void add(Object obj)
  { root = addHelper((Comparable)obj, root);
  }

  // postcondition: obj has been added to the subtree rooted at t;
  //                the updated tree is returned
  private TreeNode addHelper(Comparable obj, TreeNode t)
  { if(t == null)
    { return new TreeNode(new Item(obj));
    }
    else
    { Item it = (Item)t.getValue();
      Comparable data = it.getData();

      if(obj.compareTo(data) == 0)
        it.incrementCount();
      else if(obj.compareTo(data) < 0)
        t.setLeft(addHelper(obj, t.getLeft()));
      else
        t.setRight(addHelper(obj, t.getRight()));

      return t;
    }
  }

  // precondition:  the priority queue is not empty
  // postcondition: a data value of smallest priority has been
  //                removed and returned
  public Object removeMin()
  { if(root.getLeft() == null)
    { Item it = (Item)root.getValue();
      Object min = it.getData();
      it.decrementCount();
      if(it.getCount() == 0)
        root = root.getRight();
      return min;
    }
    else
    { TreeNode ptr = root.getLeft();
      TreeNode parent = root;
      while(ptr.getLeft() != null)
      { parent = ptr;
        ptr = ptr.getLeft();
      }
      Item it = (Item)ptr.getValue();
      Object min = it.getData();
      it.decrementCount();
      if(it.getCount() == 0)
        parent.setLeft(ptr.getRight());
      return min;
    }
  }

  // precondition:  the priority queue is not empty
  // postcondition: a data value of smallest priority is returned;
  //                the priority queue is unchanged
  public Object peekMin()
  { if(root == null)
      throw new NoSuchElementException();

    TreeNode ptr = root;

    while(ptr.getLeft() != null)
      ptr = ptr.getLeft();
    Item it = (Item)ptr.getValue();

    return it.getData();
  }

  // recursive method
  /*
  public Object peekMin()
  { if(root == null)
      throw new NoSuchElementException();

    return peekMinHelper(root);
  }

  private Object peekMinHelper(TreeNode node)
  {
    if(node.getLeft() == null)
      return ((Item)node.getValue()).getData();
    else
      return peekMinHelper(node.getLeft());
  }
  */

  public void display()
  {
    displayHelper(0, root);
  }

  private void displayHelper(int level, TreeNode t)
  {
    if(t != null)
    { displayHelper(level+1, t.getRight());
      for(int k = 0; k < level; k++)
        System.out.print("  ");
      System.out.println(t.getValue());
      displayHelper(level+1, t.getLeft());
    }
  }
}



