ActiveX Programming Unleashed CD/AXU.iso/jgl_1_1/jgl_1_1.exe/src/Sorting.java

Java Source | 1996-09-10 | 5.7 KB | 197 lines

// Copyright(c) 1996 ObjectSpace, Inc.
// Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.

package jgl;

/**
 * The Sorting class contains generic sorting algorithms.
 * <p>
 * @see jgl.examples.SortingExamples
 * @version 1.1
 * @author ObjectSpace, Inc.
 */

public final class Sorting
  {
  static final int stlThreshold = 16;
  Sequence base;
  BinaryPredicate comparator;

  private Sorting()
    {
    }

  /**
   * Sort the elements in a sequence according to their hash code. The object with the
   * smallest hash code is placed first. The time complexity is O(NlogN) and the space
   * complexity is constant.
   * @param first An iterator positioned at the first element of the sequence.
   * @param last An iterator positioned immediately after the last element of the sequence.
   * @exception java.lang.IllegalArgumentException is thrown if the iterators do not have
   * Sequence containers -or- if there containers are different.
   */
  public static void sort( ForwardIterator first, ForwardIterator last )
    {
    sort( first, last, new HashComparator() );
    }

  /**
   * Sort the elements in a sequence using a comparator. The time complexity is O(NlogN)
   * and the space complexity is constant.
   * @param first An iterator positioned at the first element of the sequence.
   * @param last An iterator positioned immediately after the last element of the sequence.
   * @param comparator A binary function that returns true if its first operand should be positioned before its second operand.
   * @exception java.lang.IllegalArgumentException is thrown if the iterators do not have
   * Sequence containers.
   */
  public static void sort( ForwardIterator first, ForwardIterator last, BinaryPredicate comparator )
    {
    new Sorting( first, last, comparator );
    }

  /**
   * Sort the elements in a Sequence container according to their hash code. The
   * object with the smallest hash code is placed first. The time complexity is O(NlogN)
   * and the space complexity is constant.
   * @param container A Sequence container.
   */
  public static void sort( Sequence container )
    {
    sort( container.start(), container.finish(), new HashComparator() );
    }

  /**
   * Sort the elements in a random access container using a comparator. The time
   * complexity is O(NlogN) and the space complexity is constant.
   * @param container A random access container.
   * @param comparator A BinaryFunction that returns true if its first operand should be positioned before its second operand.
   */
  public static void sort( Sequence container, BinaryPredicate comparator )
    {
    sort( container.start(), container.finish(), comparator );
    }

  private Sorting( ForwardIterator first, ForwardIterator last, BinaryPredicate comparit )
    {
    if ( ( !(first.getContainer() instanceof Sequence) ) ||
         ( !(last.getContainer() instanceof Sequence) ) )
      throw new IllegalArgumentException( "iterator containers must be a Sequence" );

    base = (Sequence) first.getContainer();
    comparator = comparit;

    // calculate first and last index into the sequence.
    int start = (base.start()).distance( first );
    int finish = (base.start()).distance( last );

    quickSortLoop( start, finish );
    finalInsertionSort( start, finish );
    }

  void finalInsertionSort( int first, int last )
    {
    if( last - first > stlThreshold )
      {
      int limit = first + stlThreshold;

      for( int i = first + 1; i < limit; i++ )
        linearInsert( first, i );

      for( int i = limit; i < last; i++ )
        unguardedLinearInsert( i, base.at( i ) );
      }
    else
      {
      for( int i = first + 1; i < last; i++ )
        linearInsert( first, i );
      }
    }

  void unguardedLinearInsert( int last, Object value )
    {
    int next = last - 1;

    while( comparator.execute( value, base.at( next ) ) )
      base.put( last--, base.at( next-- ) );

    base.put( last, value );
    }

  void linearInsert( int first, int last )
    {
    Object value = base.at( last );

    if( comparator.execute( value, base.at( first ) ) )
      {
      for( int i = last; i > first; i-- )
        base.put( i, base.at( i - 1 ) );

      base.put( first, value );
      }
    else
      {
      unguardedLinearInsert( last, value );
      }
    }

  void quickSortLoop( int first, int last )
    {
    while( last - first > stlThreshold )
      {
      Object pivot;
      Object a = base.at( first );
      Object b = base.at( first + (last - first ) / 2 );
      Object c = base.at( last - 1 );

      if( comparator.execute( a, b ) )
        {
        if( comparator.execute( b, c ) )
          pivot = b;
        else if( comparator.execute( a, c ) )
          pivot = c;
        else
          pivot = a;
        }
      else if( comparator.execute( a, c ) )
        pivot = a;
      else if( comparator.execute( b, c ) )
        pivot = c;
      else
        pivot = b;

      int cut = first;
      int lastx = last;

      while( true )
        {
        while( comparator.execute( base.at( cut ), pivot ) )
          ++cut;

        --lastx;

        while( comparator.execute( pivot, base.at( lastx ) ) )
          --lastx;

        if( cut >= lastx )
          break;

        Object tmp = base.at( cut );
        base.put( cut++, base.at( lastx ) );
        base.put( lastx, tmp );
        }

      if( cut - first >= last - cut )
        {
        quickSortLoop( cut, last );
        last = cut;
        }
      else
        {
        quickSortLoop( first, cut );
        first = cut;
        }
      }
    }
  }