home *** CD-ROM | disk | FTP | other *** search
/ ActiveX Programming Unleashed CD / AXU.iso / jgl_1_1 / jgl_1_1.exe / src / Heap.java < prev    next >
Encoding:
Java Source  |  1996-09-10  |  6.8 KB  |  180 lines
  1. // Copyright(c) 1996 ObjectSpace, Inc.
  2. // Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.
  3.  
  4. package jgl;
  5.  
  6. /**
  7.  * The Heap class contains generic heap algorithms.
  8.  * <p>
  9.  * @see jgl.examples.HeapExamples
  10.  * @version 1.1
  11.  * @author ObjectSpace, Inc.
  12.  */
  13.  
  14. public class Heap
  15.   {
  16.   private Heap()
  17.     {
  18.     }
  19.   
  20.   /**
  21.    * Assuming that a sequence is already organized as a heap, insert the element that
  22.    * is immediately after the sequence into the heap. The elements are organized
  23.    * according to their hash code. The time complexity is O(logN), where N is the size of 
  24.    * the heap.
  25.    * @param first An iterator positioned at the first element of the sequence.
  26.    * @param last An iterator positioned immediately after the last element of the sequence.
  27.    */
  28.   public static void pushHeap( BidirectionalIterator first, BidirectionalIterator last )
  29.     {
  30.     pushHeap( first, last, new HashComparator() );
  31.     }
  32.  
  33.   /**
  34.    * Assuming that a sequence is already organized as a heap, insert the element that
  35.    * is immediately after the sequence into the heap. The elements are organized
  36.    * according to a specified comparator. The time complexity is O(logN), where N is 
  37.    * the size of the heap.
  38.    * @param first An iterator positioned at the first element of the sequence.
  39.    * @param last An iterator positioned immediately after the last element of the sequence.
  40.    * @param comparator A binary predicate that returns true if its first operand is "less" than its second operand.
  41.    */
  42.   public static void pushHeap( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator )
  43.     {
  44.     pushHeap( first, first.distance( last ) - 1, 0, last.get( -1 ), comparator );
  45.     }
  46.  
  47.   static void pushHeap( BidirectionalIterator first, int holeIndex, int topIndex, Object value, BinaryPredicate comparator )
  48.     {
  49.     int parent = ( holeIndex - 1 ) / 2;
  50.  
  51.     while( holeIndex > topIndex && comparator.execute( first.get( parent ), value ) )
  52.       {
  53.       first.put( holeIndex, first.get( parent ) );
  54.       holeIndex = parent;
  55.       parent = ( holeIndex - 1 ) / 2;
  56.       }
  57.  
  58.     first.put( holeIndex, value );
  59.     }
  60.  
  61.   /**
  62.    * Assuming that a sequence is organized as a heap, swap its first and last elements
  63.    * and then reorganize every element except for the last element to be a heap. The 
  64.    * elements are organized according to their hash code. 
  65.    * @param first An iterator positioned at the first element of the sequence.
  66.    * @param last An iterator positioned immediately after the last element of the sequence.
  67.    */
  68.   public static void popHeap( BidirectionalIterator first, BidirectionalIterator last )
  69.     {
  70.     popHeap( first, last, new HashComparator() );
  71.     }
  72.  
  73.   /**
  74.    * Assuming that a sequence is organized as a heap, swap its first and last elements
  75.    * and then reorganize every element except for the last element to be a heap. The 
  76.    * elements are organized according to a specified comparator. 
  77.    * @param first An iterator positioned at the first element of the sequence.
  78.    * @param last An iterator positioned immediately after the last element of the sequence.
  79.    * @param comparator A binary predicate that returns true if its first operand is "less" than its second operand.
  80.    */
  81.   public static void popHeap( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator )
  82.     {
  83.     Object old = last.get( -1 );
  84.     last.put( -1, first.get() );
  85.     adjustHeap( first, 0, first.distance( last ) - 1, old, comparator );
  86.     }
  87.  
  88.   static void adjustHeap( BidirectionalIterator first, int holeIndex, int len, Object value, BinaryPredicate comparator )
  89.     {
  90.     int topIndex = holeIndex;
  91.     int secondChild = 2 * holeIndex + 2;
  92.  
  93.     while( secondChild < len )
  94.       {
  95.       if( comparator.execute( first.get( secondChild ), first.get( secondChild - 1 ) ) )
  96.         secondChild--;
  97.  
  98.       first.put( holeIndex, first.get( secondChild ) );
  99.       holeIndex = secondChild;
  100.       secondChild = 2 * ( secondChild + 1 );
  101.       }
  102.  
  103.     if( secondChild == len )
  104.       {
  105.       first.put( holeIndex, first.get( secondChild - 1 ) );
  106.       holeIndex = secondChild - 1;
  107.       }
  108.  
  109.     pushHeap( first, holeIndex, topIndex, value, comparator );
  110.     }
  111.  
  112.   /**
  113.    * Arrange a sequence into a heap that is ordered according to the object's hash codes.
  114.    * The time complexity is linear and the space complexity is constant.
  115.    * @param first An iterator positioned at the first element of the sequence.
  116.    * @param last An iterator positioned immediately after the last element of the sequence.
  117.    */
  118.   public static void makeHeap( BidirectionalIterator first, BidirectionalIterator last )
  119.     {
  120.     makeHeap( first, last, new HashComparator() );
  121.     }
  122.  
  123.   /**
  124.    * Arrange a sequence into a heap that is ordered according to a comparator.
  125.    * The time complexity is linear and the space complexity is constant.
  126.    * @param first An iterator positioned at the first element of the sequence.
  127.    * @param last An iterator positioned immediately after the last element of the sequence.
  128.    * @param comparator A binary predicate that returns true if its first operand is "less" than its second operand.
  129.    */
  130.   public static void makeHeap( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator )
  131.     {
  132.     int len = first.distance( last );
  133.  
  134.     if( len < 2)
  135.       return;
  136.  
  137.     int parent = ( len - 2 ) / 2;
  138.  
  139.     while( true )
  140.       {
  141.       adjustHeap( first, parent, len, first.get( parent ), comparator );
  142.  
  143.       if( parent == 0 )
  144.         return;
  145.  
  146.       parent--;
  147.       }
  148.     }
  149.  
  150.   /**
  151.    * Sort a heap according to the object's hash codes.
  152.    * The time complexity is linear and the space complexity is constant.
  153.    * @param first An iterator positioned at the first element of the heap.
  154.    * @param last An iterator positioned immediately after the last element of the heap.
  155.    */
  156.   public static void sortHeap( BidirectionalIterator first, BidirectionalIterator last )
  157.     {
  158.     sortHeap( first, last, new HashComparator() );
  159.     }
  160.  
  161.   /**
  162.    * Sort a heap according to a comparator.
  163.    * The time complexity is linear and the space complexity is constant.
  164.    * @param first An iterator positioned at the first element of the sequence.
  165.    * @param last An iterator positioned immediately after the last element of the sequence.
  166.    * @param comparator A binary predicate that returns true if its first operand is "less" than its second operand.
  167.    */
  168.   public static void sortHeap( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator )
  169.     {
  170.     BidirectionalIterator lastx = (BidirectionalIterator) last.clone();
  171.  
  172.     while( first.distance( lastx ) > 1 )
  173.       {
  174.       popHeap( first, lastx, comparator );
  175.       lastx.retreat();
  176.       }
  177.     }
  178.   }
  179.  
  180.