/**
 * Priority queue in which the SMALLEST entry is preferentially taken,
   with display() amplified to "pretty-print".

  @author   Timothy Rolfe
  <pre>
   job description structure:
      timeRqd   --- basis for the priority queue (take shortest time)
      otherInfo --- standing in for other information about the job

   Priority queue:  minheap of job descriptions
  </pre>
 */
// Priority queue implementation as a minHeap
public class MinHeap
{
// Negative time is not allowed --- placeholder for heap[0]
   static final JobEntry NEG_TIME = new JobEntry(-1, "");

// No need for a constructor:  all initialized to zeroes.

   public boolean isEmpty ( )
   {  return n == 0;  }    // Not exactly rocket science!

   public void enqueue ( JobEntry job)  // Make an entry into the minheap
   {  if ( heap == null )  // I.e., very first enqueue
         newSize (1);      // Realistically, this should be greater
      n++;
      if ( n > size )
         newSize (size*2);
      heap[n] = job;
      upHeap(n);
   }

   public JobEntry dequeue ( )          // Remove an entry from the minheap
   {  JobEntry rtnVal = heap[1];

      if (n < 1) return null;        // I.e., attempt to dequeue on empty

      heap[1] = heap[n--];           // The last shall be first
      downHeap(1);                   // --- but not for long

      return rtnVal;                    // Return item that had been on top
   }
/**
 * Determine the line position on display as a complete binary tree
 */
   void places(int k)
   {  if ( k == 1 )
      {  usedDisplay = 0;
         if ( sizeDisplay < n )
         {  linePos = new int [n+1]; sizeDisplay = n; }
      }
      if ( k <= n )
      {  places(k*2);
         linePos[k] = usedDisplay;
         usedDisplay += 2;
         places(k*2+1);
      }
   }

/**
 * Somewhat prettified display:  Subheap roots are directly
 * above their respective subheaps.  Good for up to about 40
 * heap entries before line-wrap causes a problem.
 */
   public void display ()
   {  int idx,
          endIt = 2,
          usedDisplay = 0;

   // In-order traversal, setting into linePos where each of
   // the heap entries will print on its line.
      places(1); // Pass the subscript of the root.

      for (idx = 1; idx <= n; idx++)
      {  String current;

         if (idx == endIt) // Go to new line
         {  System.out.println ();
            usedDisplay = 0;      // Restart positions used
            endIt <<= 1;   // Next power of two.
         }
      // ?Need to space over?
         for ( ; usedDisplay < linePos[idx] ; usedDisplay++ )
            System.out.print (" ");

         current = heap[idx].otherInfo;
         System.out.print ( (current.length() < 2 ? " " : "")
            + current);
         usedDisplay += 2;
      }
      System.out.println ();
   }

   protected void newSize(int m)        // Change size to m
   {  JobEntry[] r = new JobEntry [m+1];// New heap, correcting for [0]
      int        lim = size < m ? size : m; // i.e., min(size,m)

   // Parameter order:  src, srcStart, dest, destStart, length
      if ( heap != null )     // On the first call, there IS no heap array
         System.arraycopy (heap, 1, r, 1, lim);
      r[0] = NEG_TIME;                  // Set in the sentinel value

      heap = r;                         // Connect heap to the new space
      size = m;
   }

   protected void upHeap(int child)     // Correct the heap from child upwards
   {  int parent = child/2;
      JobEntry hold = heap[child];

   // NOTE:  This code depends on the sentinel value in heap[0]
      while ( hold.compareTo(heap[parent]) < 0 )
      {  heap[child] = heap[parent];
         child = parent;
         parent = child/2;
      }
      heap[child] = hold;
   }

   protected void downHeap(int parent)   // Correct the heap from parent downwards
   {  JobEntry hold = heap[parent];
      int child = 2*parent;

      while (child <= n)     // I.e, while still in the active heap
      {  if ( child < n && heap[child].compareTo(heap[child+1]) > 0 )
            child++;
         if ( !(heap[child].compareTo(hold) < 0))// if NOT out of place
            break;
         heap[parent] = heap[child];
         parent = child;
         child = 2*parent;
      }
      heap[parent] = hold;
   }

   protected JobEntry[] heap = null;// Dynamic array
   protected int        n = 0,      // # queued entries (logical size)
                        size = 0;   // Actual allocation (physical size)

// display()/places() variables that need to retain their values.
   int     linePos[] = null,        // line positions
           sizeDisplay = 0,         // size of linePos
           usedDisplay;             // currently used positions
}