home *** CD-ROM | disk | FTP | other *** search
/ ActiveX Programming Unleashed CD / AXU.iso / jgl_1_1 / jgl_1_1.exe / src / Rotating.java < prev    next >
Encoding:
Java Source  |  1996-09-10  |  4.8 KB  |  145 lines
  1. // Copyright(c) 1996 ObjectSpace, Inc.
  2. // Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.
  3.  
  4. package jgl;
  5.  
  6. /**
  7.  * The Rotating class contains generic rotating algorithms.
  8.  * <p>
  9.  * @see jgl.examples.RotatingExamples
  10.  * @version 1.1
  11.  * @author ObjectSpace, Inc.
  12.  */
  13.  
  14. public final class Rotating
  15.   {
  16.   private Rotating()
  17.     {
  18.     }
  19.  
  20.   /**
  21.    * Rotate a sequence to the left. After the operation, the element that used to be 
  22.    * located by the first iterator is positioned immediately before the position
  23.    * indicated by the second iterator. The time complexity is linear and the space 
  24.    * complexity is constant.
  25.    * @param first An iterator positioned at the first element in the sequence.
  26.    * @param middle An iterator positioned immediately after the target location of the first element in the sequence.
  27.    * @param last An iterator positioned at the last element in the sequence.
  28.    */
  29.   public static void rotate( ForwardIterator first, ForwardIterator middle, ForwardIterator last )
  30.     {
  31.     if ( !(first.getContainer() instanceof Sequence) )
  32.       throw new IllegalArgumentException( "iterator containers must be a Sequence" );
  33.  
  34.     if( first.equals( middle ) || middle.equals( last ) )
  35.       return;
  36.  
  37.     if( first instanceof RandomAccessIterator )
  38.       rotateRandomAccess( (RandomAccessIterator) first, (RandomAccessIterator) middle, (RandomAccessIterator) last );
  39.     else if( first instanceof BidirectionalIterator )
  40.       rotateBidirectional( (BidirectionalIterator) first, (BidirectionalIterator) middle, (BidirectionalIterator) last );
  41.     else
  42.       rotateForward( first, middle, last );
  43.     }
  44.  
  45.   /**
  46.    * Perform the same operations as rotate(), except that that the result is placed
  47.    * into a separate sequence. The time complexity is linear and the space complexity is 
  48.    * constant.
  49.    * @param first An iterator positioned at the first element in the input sequence.
  50.    * @param middle An iterator positioned immediately after the target location of the first element in the input sequence.
  51.    * @param last An iterator positioned at the last element in the input sequence.
  52.    * @param result An iterator positioned at the first element in the output sequence.
  53.    * @return An iterator positioned immediately after the last element in the output sequence.
  54.    */
  55.   public static OutputIterator rotateCopy( ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result )
  56.     {
  57.     return Copying.copy( first, middle, Copying.copy( middle, last, result ) );
  58.     }
  59.  
  60.   static void rotateBidirectional( BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last )
  61.     {
  62.     Reversing.reverse( first, middle );
  63.     Reversing.reverse( middle, last );
  64.     Reversing.reverse( first, last );
  65.     }
  66.  
  67.   static void rotateForward( ForwardIterator first, ForwardIterator middle, ForwardIterator last )
  68.     {
  69.     ForwardIterator firstx = (ForwardIterator) first.clone();
  70.     ForwardIterator middlex = (ForwardIterator) middle.clone();
  71.     ForwardIterator i = (ForwardIterator) middle.clone();
  72.  
  73.     while( true )
  74.       {
  75.       Swapping.iterSwap( firstx, i );
  76.       firstx.advance();
  77.       i.advance();
  78.  
  79.       if( firstx.equals( middlex ) )
  80.         {
  81.         if( i.equals( last ) )
  82.           return;
  83.  
  84.         middlex = (ForwardIterator)i.clone();
  85.         }
  86.       else if( i.equals( last ) )
  87.         {
  88.         i = (ForwardIterator)middlex.clone();
  89.         }
  90.       }
  91.     }
  92.  
  93.   static void rotateRandomAccess( RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last )
  94.     {
  95.     int n = gcd( first.distance( last ), first.distance( middle ) );
  96.  
  97.     while( n-- != 0 )
  98.       {
  99.       RandomAccessIterator i = (RandomAccessIterator) first.clone();
  100.       i.advance( n );
  101.       cycle( first, last, i, first.distance( middle ) );
  102.       }
  103.     }
  104.  
  105.   static int gcd( int m, int n )
  106.     {
  107.     while( n != 0 )
  108.       {
  109.       int t = m % n;
  110.       m = n;
  111.       n = t;
  112.       }
  113.  
  114.     return m;
  115.     }
  116.  
  117.   static void cycle( RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator initial, int shift )
  118.     {
  119.     Object value = initial.get();
  120.     RandomAccessIterator ptr1 = (RandomAccessIterator) initial.clone();
  121.     RandomAccessIterator ptr2 = (RandomAccessIterator) ptr1.clone();
  122.     ptr2.advance( shift );
  123.  
  124.     while( !ptr2.equals( initial ) )
  125.       {
  126.       ptr1.put( ptr2.get() );
  127.       ptr1 = (RandomAccessIterator) ptr2.clone();
  128.  
  129.       if( ptr2.distance( last ) > shift )
  130.         {
  131.         ptr2.advance( shift );
  132.         }
  133.       else
  134.         {
  135.         int delta = shift - ptr2.distance( last );
  136.         ptr2 = (RandomAccessIterator) first.clone();
  137.         ptr2.advance( delta );
  138.         }
  139.       }
  140.  
  141.     ptr1.put( value );
  142.     }
  143.   }
  144.  
  145.