COP 3530
   Section U03
   Spring 2017



                           APPENDIX
                           ========




   The BinaryNode.java Class
   -------------------------


   import java.util.ArrayList;
   import java.util.Stack;
   import java.util.NoSuchElementException;


   public class BinaryNode<T> 
   {
    
      // Create a default binary node 
      public BinaryNode() 
      {
          this(null, null, null);
      }
    
      // create a node with given value and children
      public BinaryNode(T theElement, BinaryNode<T> lt, BinaryNode<T> rt)
      {
          element = theElement;
          left = lt;
          right = rt;
      }
    
        
      // return the element
      public T getElement()
      {
          return element;
      }
    
      // return the left child
      public BinaryNode<T> getLeft()
      {
          return left;
      }
    
      // return the right child
      public BinaryNode<T> getRight()
      {
          return right;
      }
        
    
      // print in post order
      public void printPostOrder()
      {
          if (left != null)
              left.printPostOrder();
          if (right != null)
              right.printPostOrder();
          System.out.println(element);
      }


    
        
      // the fields
      private T element;
      private BinaryNode<T> left;
      private BinaryNode<T> right;
  }

    
  The PriorityQueue.java Class
  ----------------------------


  import java.util.AbstractCollection;
  import java.util.Queue;
  import java.util.Comparator;
  import java.util.NoSuchElementException;
  import java.util.Collection;
  import java.util.Queue;
  import java.util.Iterator;


  public class PriorityQueue<T> extends AbstractCollection<T>
             implements Queue<T>
  {

      // the fields
      private int currentSize; // the number of elements in the heap
      private T[] array; // the heap array
      private Comparator<? super T> cmp;
      private static final int DEFAULT_CAPACITY = 100;

      /** Construct an empty PriorityQueue */
      public PriorityQueue()
      {
          currentSize = 0;
          cmp = null;
          array = (T[]) new Object[DEFAULT_CAPACITY + 1];
      }

      /* Construct an empty priority queue with a specific comparator */
      public PriorityQueue( Comparator <? super T> c)
      {
          currentSize = 0;
          cmp = c;
          array = (T[]) new Object[DEFAULT_CAPACITY + 1];
      }

      /* Construct a priority queue from another collection */
      public PriorityQueue(Collection<? extends T> coll)
      {
          cmp = null;
          currentSize = coll.size();
          array = (T[]) new Object[ (currentSize + 2) * 11/10];

          int i = 1;
          for ( T item: coll)
              array[i++] = item;
          buildHeap();
          for (int j = 0; j <= currentSize; j++)
              System.out.println(array[j]);
      }

      // return the current size
      public int size()
      {
          return currentSize;
      }

      // empty the priority queue
      public void clear()
      {
          currentSize = 0;
      }

      // construct an iterator
      public Iterator<T> iterator()
      {
          // ...
          return null;
      }

      // returns the smallest item in the priority queue
      // @throws NoSuchElementException if the queue is empty
      public T element()
      {
          if (isEmpty())
              throw new NoSuchElementException();
          return array[1];
      }

      // peek is required by the interface Queue
      // @returns the head or null if the queue is empty
      public T peek()
      {
          if (isEmpty())
              return null;
          return array[1];
      }

      // poll is required by the interface queue
      // remove the head of the list
      // @returns the smallest item in the priority queue
      //  @returns null if the queue is empty
      public T poll()
      {
          if (isEmpty())
              return null;
          T minItem = element();
          array[1] = array[currentSize--];
          percolateDown(1);

          return minItem;
      }

    
    
      // offer is required by the interface Queue
      // it is the same as add
      public boolean offer(T x)
      {
          return add(x);
      }

      // add an element to the priority queue
      // return true
      public boolean add( T x)
      {
          if (currentSize + 1 == array.length )
              doubleArray();
          // percolate up
          int hole = ++currentSize;
          array[0] = x;

          for (; compare(x, array[hole/2]) < 0; hole /= 2)
              array[hole] = array[hole/2];
          array[hole] = x;
          return true;
      }

      // removes the smallest item in the priority queue
      // @throws NoSuchElementException if empty
      public T remove()
      {
          T minItem = element();
          array[1] = array[currentSize--];
          percolateDown(1);

          return minItem;
      }

    
      // internal method to percolate down in the heap
      // @param hole is the index at which the percolate begins
      private void percolateDown( int hole)
      {
          int child;
          T tmp = array[hole];

          for (; hole * 2 <= currentSize; hole = child)
          {
              child = hole * 2;
              if (child != currentSize &&
                     compare(array[child+1], array[child]) < 0)
                  child++;
              if (compare(array[child], tmp) < 0)
                  array[hole] = array[child];
              else
                  break;
          }
          array[hole] = tmp;
      }

      // establish the heap property for an arbitrary arrangement of items
      private void buildHeap()
      {
          for (int i = currentSize / 2 ; i > 0; i--)

              percolateDown(i);
      }

      private void doubleArray()
      {
          // ...
      }
    
      // from figure 19.70
      private int compare(T lhs, T rhs)
      {
          if ( cmp == null)
              return ((Comparable) lhs).compareTo(rhs);
          else
              return cmp.compare(lhs,rhs);
      }

      // return true if it is empty and false otherwise
      public boolean isEmpty()
      {
          return currentSize == 0;
      }

  }

  Figure 1
  --------

                        Mark
                 /                \
                /                  \
             David                 Ursula 
            /     \              /       \
           /       \            /         \
       Bill       John        Rita        Zelda
      /   \       /  \        /   \       /
     /     \     /    \      /     \     /
   Alex  Carol Elaine Luke  Pepito Tom  Wendy