home *** CD-ROM | disk | FTP | other *** search
/ Symantec Visual Cafe for Java 2.5 / symantec-visual-cafe-2.5-database-dev-edition.iso / Extras / OSpace / jgl.exe / jgl_2_0 / src / COM / objectspace / jgl / Heap.java < prev    next >
Encoding:
Java Source  |  1997-03-14  |  7.0 KB  |  181 lines
  1. // Copyright(c) 1996,1997 ObjectSpace, Inc.
  2. // Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.
  3.  
  4. package COM.objectspace.jgl;
  5.  
  6. /**
  7.  * The Heap class contains generic heap algorithms.
  8.  * <p>
  9.  * @see COM.objectspace.jgl.examples.HeapExamples
  10.  * @version 2.0.2
  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(log N), where N is the size of
  24.    * the heap. Space complexity is constant.
  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(log N), where N is
  37.    * the size of the heap. Space complexity is constant.
  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.    * Time complexity is 2*log(last-first) and space complexity is constant.
  66.    * @param first An iterator positioned at the first element of the sequence.
  67.    * @param last An iterator positioned immediately after the last element of the sequence.
  68.    */
  69.   public static void popHeap( BidirectionalIterator first, BidirectionalIterator last )
  70.     {
  71.     popHeap( first, last, new HashComparator() );
  72.     }
  73.  
  74.   /**
  75.    * Assuming that a sequence is organized as a heap, swap its first and last elements
  76.    * and then reorganize every element except for the last element to be a heap. The
  77.    * elements are organized according to a specified comparator.
  78.    * Time complexity is 2*log(last-first) and space complexity is constant.
  79.    * @param first An iterator positioned at the first element of the sequence.
  80.    * @param last An iterator positioned immediately after the last element of the sequence.
  81.    * @param comparator A binary predicate that returns true if its first operand is "less" than its second operand.
  82.    */
  83.   public static void popHeap( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator )
  84.     {
  85.     Object old = last.get( -1 );
  86.     last.put( -1, first.get() );
  87.     adjustHeap( first, 0, first.distance( last ) - 1, old, comparator );
  88.     }
  89.  
  90.   /**
  91.    * Arrange a sequence into a heap that is ordered according to the object's hash codes.
  92.    * The time complexity is linear and the space complexity is constant.
  93.    * @param first An iterator positioned at the first element of the sequence.
  94.    * @param last An iterator positioned immediately after the last element of the sequence.
  95.    */
  96.   public static void makeHeap( BidirectionalIterator first, BidirectionalIterator last )
  97.     {
  98.     makeHeap( first, last, new HashComparator() );
  99.     }
  100.  
  101.   /**
  102.    * Arrange a sequence into a heap that is ordered according to a comparator.
  103.    * The time complexity is linear and the space complexity is constant.
  104.    * @param first An iterator positioned at the first element of the sequence.
  105.    * @param last An iterator positioned immediately after the last element of the sequence.
  106.    * @param comparator A binary predicate that returns true if its first operand is "less" than its second operand.
  107.    */
  108.   public static void makeHeap( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator )
  109.     {
  110.     int len = first.distance( last );
  111.  
  112.     if ( len < 2)
  113.       return;
  114.  
  115.     int parent = ( len - 2 ) / 2;
  116.  
  117.     while ( true )
  118.       {
  119.       adjustHeap( first, parent, len, first.get( parent ), comparator );
  120.  
  121.       if ( parent == 0 )
  122.         return;
  123.  
  124.       parent--;
  125.       }
  126.     }
  127.  
  128.   /**
  129.    * Sort a heap according to the object's hash codes.
  130.    * Time complexity is N*log(N) and the space complexity is constant.
  131.    * @param first An iterator positioned at the first element of the heap.
  132.    * @param last An iterator positioned immediately after the last element of the heap.
  133.    */
  134.   public static void sortHeap( BidirectionalIterator first, BidirectionalIterator last )
  135.     {
  136.     sortHeap( first, last, new HashComparator() );
  137.     }
  138.  
  139.   /**
  140.    * Sort a heap according to a comparator.
  141.    * Time complexity is N*log(N) and the space complexity is constant.
  142.    * @param first An iterator positioned at the first element of the sequence.
  143.    * @param last An iterator positioned immediately after the last element of the sequence.
  144.    * @param comparator A binary predicate that returns true if its first operand is "less" than its second operand.
  145.    */
  146.   public static void sortHeap( BidirectionalIterator first, BidirectionalIterator last, BinaryPredicate comparator )
  147.     {
  148.     BidirectionalIterator lastx = (BidirectionalIterator) last.clone();
  149.  
  150.     while ( first.distance( lastx ) > 1 )
  151.       {
  152.       popHeap( first, lastx, comparator );
  153.       lastx.retreat();
  154.       }
  155.     }
  156.  
  157.   static void adjustHeap( BidirectionalIterator first, int holeIndex, int len, Object value, BinaryPredicate comparator )
  158.     {
  159.     int topIndex = holeIndex;
  160.     int secondChild = 2 * ( holeIndex + 1 );
  161.  
  162.     while ( secondChild < len )
  163.       {
  164.       if ( comparator.execute( first.get( secondChild ), first.get( secondChild - 1 ) ) )
  165.         --secondChild;
  166.  
  167.       first.put( holeIndex, first.get( secondChild ) );
  168.       holeIndex = secondChild;
  169.       secondChild = 2 * ( secondChild + 1 );
  170.       }
  171.  
  172.     if ( secondChild == len )
  173.       {
  174.       first.put( holeIndex, first.get( secondChild - 1 ) );
  175.       holeIndex = secondChild - 1;
  176.       }
  177.  
  178.     pushHeap( first, holeIndex, topIndex, value, comparator );
  179.     }
  180.   }
  181.