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

package COM.objectspace.jgl;

import java.util.Random;

/**
 * The Shuffling class contains generic shuffling algorithms.
 * <p>
 * @see COM.objectspace.jgl.examples.ShufflingExamples
 * @version 2.0.2
 * @author ObjectSpace, Inc.
 */

public final class Shuffling
  {
  static Random rand = new Random();

  private Shuffling()
    {
    }

  /**
   * Shuffle a sequence with uniform distribution by performing as many random swaps
   * as there are elements. Time complexity is linear and 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.
   */
  public static void randomShuffle( BidirectionalIterator first, BidirectionalIterator last )
    {
    if ( !(first.getContainer() instanceof Sequence) )
      throw new IllegalArgumentException( "iterator containers must be a Sequence" );

    if ( first.equals( last ) )
      return;

    BidirectionalIterator i = (BidirectionalIterator) first.clone();
    i.advance();
    int n = 2;

    while ( !i.equals( last ) )
      {
      BidirectionalIterator j = (BidirectionalIterator) first.clone();
      j.advance( Math.abs( rand.nextInt() ) % n );
      Swapping.iterSwap( i, j );
      i.advance();
      ++n;
      }
    }

  /**
   * Shuffle a random access container with uniform distribution by performing as many
   * random swaps as there are elements. Time complexity is linear and space complexity
   * is constant.
   * @param container The container.
   */
  public static void randomShuffle( Container container )
    {
    randomShuffle( (BidirectionalIterator) container.start(), (BidirectionalIterator) container.finish() );
    }
  }