home *** CD-ROM | disk | FTP | other *** search
/ ActiveX Programming Unleashed CD / AXU.iso / jgl_1_1 / jgl_1_1.exe / src / Shuffling.java < prev    next >
Encoding:
Java Source  |  1996-09-10  |  1.8 KB  |  64 lines
  1. // Copyright(c) 1996 ObjectSpace, Inc.
  2. // Portions Copyright(c) 1995, 1996 Hewlett-Packard Company.
  3.  
  4. package jgl;
  5.  
  6. import java.util.Random;
  7.  
  8. /**
  9.  * The Shuffling class contains generic shuffling algorithms.
  10.  * <p>
  11.  * @see jgl.examples.ShufflingExamples
  12.  * @version 1.1
  13.  * @author ObjectSpace, Inc.
  14.  */
  15.  
  16. public final class Shuffling
  17.   {
  18.   static Random rand = new Random();
  19.  
  20.   private Shuffling()
  21.     {
  22.     }
  23.  
  24.   /**
  25.    * Shuffle a sequence with uniform distribution by performing as many random swaps
  26.    * as there are elements. Time complexity is linear and space complexity is constant.
  27.    * @param first An iterator positioned at the first element of the sequence.
  28.    * @param last An iterator positioned immediately after the last element of the sequence.
  29.    */
  30.   public static void randomShuffle( BidirectionalIterator first, BidirectionalIterator last )
  31.     {
  32.     if ( !(first.getContainer() instanceof Sequence) )
  33.       throw new IllegalArgumentException( "iterator containers must be a Sequence" );
  34.  
  35.     if( first.equals( last ) )
  36.       return;
  37.  
  38.     BidirectionalIterator i = (BidirectionalIterator) first.clone();
  39.     i.advance();
  40.     int n = 2;
  41.  
  42.     while( !i.equals( last ) )
  43.       {
  44.       BidirectionalIterator j = (BidirectionalIterator) first.clone();
  45.       j.advance( Math.abs( rand.nextInt() ) % n );
  46.       Swapping.iterSwap( i, j );
  47.       i.advance();
  48.       ++n;
  49.       }
  50.     }
  51.  
  52.   /**
  53.    * Shuffle a random access container with uniform distribution by performing as many 
  54.    * random swaps as there are elements. Time complexity is linear and space complexity 
  55.    * is constant.
  56.    * @param container The container.
  57.    */
  58.   public static void randomShuffle( Container container )
  59.     {
  60.     randomShuffle( (BidirectionalIterator) container.start(), (BidirectionalIterator) container.finish() );
  61.     }
  62.   }
  63.  
  64.