Source code: org/media/mn8/util/cron/BinaryHeap.java

   package org.media.mn8.util.cron;
   
   import java.util.Comparator;
   import java.util.NoSuchElementException;
   
   
   public final class BinaryHeap {
       private static final class MinComparator implements Comparator {
           public final int compare( final Object lhs, final Object rhs ) {
              return ( (Comparable)lhs ).compareTo( rhs );
          }
      }
  
  
      private static final class MaxComparator implements Comparator {
          public final int compare( final Object lhs, final Object rhs ) {
              return ( (Comparable)rhs ).compareTo( lhs );
          }
      }
  
  
      public static final Comparator MIN_COMPARATOR = new MinComparator();
      public static final Comparator MAX_COMPARATOR = new MaxComparator();
      private static final int DEFAULT_CAPACITY = 13;
      private static final Comparator DEFAULT_COMPARATOR = MIN_COMPARATOR;
      private int m_size;
      private Object[] m_elements;
      private Comparator m_comparator;
  
  
      public BinaryHeap() {
          this( DEFAULT_CAPACITY, DEFAULT_COMPARATOR );
      }
  
  
      public BinaryHeap( final int capacity, final Comparator comparator ) {
          //+1 as 0 is noop
          m_elements = new Object[ capacity + 1 ];
          m_comparator = comparator;
      }
  
  
      /**
       * Clear all elements from queue.
       */
      public void clear() {
          m_size = 0;
      }
  
      /**
       * Test if queue is empty.
       *
       * @return true if queue is empty else false.
       */
      public boolean isEmpty() {
          return ( 0 == m_size );
      }
  
  
      /**
       * Test if queue is full.
       *
       * @return true if queue is full else false.
       */
      public boolean isFull() {
          //+1 as element 0 is noop
          return ( m_elements.length == m_size + 1 );
      }
  
  
      /**
       * Returns the number of elements currently on the heap.
       *
       * @return the size of the heap.
       */
      public int size() {
          return m_size;
      }
  
      /**
       * Insert an element into queue.
       *
       * @param element the element to be inserted
       */
      public void insert( final Object element ) {
          if( isFull() ) {
              grow();
          }
          percolateUpHeap( element );
      }
  
  
      /**
       * Return element on top of heap but don't remove it.
       *
       * @return the element at top of heap
       * @throws NoSuchElementException if isEmpty() == true
       */
      public Object peek() throws NoSuchElementException {
         if( isEmpty() ) {
             throw new NoSuchElementException();
         } else {
             return m_elements[ 1 ];
         }
     }
 
 
     /**
      * Return element on top of heap and remove it.
      *
      * @return the element at top of heap
      * @throws NoSuchElementException if isEmpty() == true
      */
     public Object pop() throws NoSuchElementException {
         final Object result = peek();
         m_elements[ 1 ] = m_elements[ m_size-- ];
 
         //set the unused element to 'null' so that the garbage collector
         //can free the object if not used anywhere else.(remove reference)
         m_elements[ m_size + 1 ] = null;
 
         if( m_size != 0 ) {
             percolateDownHeap( 1 );
         }
         return result;
     }
 
 
     /**
      * Percolate element down heap from top.
      *
      * @param element the element
      */
     private void percolateDownHeap( final int index ) {
         final Object element = m_elements[ index ];
 
         int hole = index;
         int child = hole << 1;
 
         while( child <= m_size ) {
             //if we have a right child and that child can not be percolated
             //up then move onto other child
             if( child != m_size &&
                 m_comparator.compare( m_elements[ child + 1 ], m_elements[ child ] ) < 0 )
             {
                 child++;
             }
 
             //if we found resting place of bubble then terminate search
             if( m_comparator.compare( m_elements[ child ], element ) >= 0 ) {
                 break;
             }
 
             m_elements[ hole ] = m_elements[ child ];
             hole = child;
             child = hole << 1;
         }
 
         m_elements[ hole ] = element;
     }
 
 
     /**
      * Percolate element up heap from bottom.
      *
      * @param element the element
      */
     private void percolateUpHeap( final Object element ) {
         int hole = ++m_size;
         int next = hole >> 1;
 
         m_elements[ hole ] = element;
 
         while( hole > 1 &&
             m_comparator.compare( element, m_elements[ next ] ) < 0 )
         {
             m_elements[ hole ] = m_elements[ next ];
             hole = next;
             next = hole >> 1;
         }
 
         m_elements[ hole ] = element;
     }
 
 
     /**
      * Grows the heap by a factor of 2.
      */
     private void grow() {
         final Object[] elements = new Object[ m_elements.length * 2 ];
         System.arraycopy( m_elements, 0, elements, 0, m_elements.length );
         m_elements = elements;
     }
 
 
     /**
      * Create a string representing heap
      * and all elements in heap.
      *
      * @return the string representing heap
      */
     public String toString() {
         final StringBuffer sb = new StringBuffer();
         sb.append( "[ " );
         for( int i = 1; i < m_size + 1; i++ ) {
             if( i != 1 ) {
                 sb.append( ", " );
             }
             sb.append( m_elements[ i ] );
         }
         sb.append( " ]" );
         return sb.toString();
     }
 }