/*
 * @(#)SwapSortAlgorithm.java	1.0 95/06/26 Jason Harrison
 *
 * Copyright (c) 1995 University of British Columbia
 *
 * Permission to use, copy, modify, and distribute this software
 * and its documentation for NON-COMMERCIAL purposes and without
 * fee is hereby granted provided that this copyright notice
 * appears in all copies. Please refer to the file "copyright.html"
 * for further important copyright and licensing information.
 *
 * UBC MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
 * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
 * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
 * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. UBC SHALL NOT BE LIABLE FOR
 * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
 * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
 */

/**
 * A swap sort demonstration algorithm
 *
 *  We know how the data was constructed and can use this to our advantage.
 *  THIS IS NOT A SORT!  DO NOT USE THIS ROUTINE FOR REAL APPLICATIONS.
 *  IT IS ONLY A DEMONSTRATION OF HOW LONG IT TAKES JAVA TO SWAP N ELEMENTS.
 *  
 *  EQUIVALENT CODE:
 *     for (int i = 0; i < a.length; i++ ) {
 *         a[i] = i;
 *     }
 *
 * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
 *
 * @author Jason Harrison@cs.ubc.ca
 * @version 	1.0, 26 Jun 1995
 *
 */
class SwapSortAlgorithm extends SortAlgorithm {
    void sort(int a[]) throws Exception {
	int max = a[0];

        /* 
         *  Originally the SortItem class created arrays without duplicates
         *  and thus every item had a single correct location in the final
         *  sorted array.  With duplicates there are many correct final
         *  locations and we cannot just swap an item into the final spot.
         *
         *  So fill the array the old way, shuffle it and then continue with
         *  the old algorithm.  (This the old is SortItem::scramble())
         *  Even then this doesn't always work due to floating point 
         *  limitations.
         */

        /*
         *  The array a holds values from 0 to max where a.length = max / f.
         *  Here we find max.
         */
	for (int i = 1; i < a.length; i++) {
            if (max < a[i]) {
                max = a[i];
	    }
	}

        /*
         *  Now find f, the scaling factor for drawing the contents of
         *  the array a.  The correct value for a[j] is j / f.
         */
	double f = ((double) a.length - 1.0) / (double) max;

        /* 
         *  Fill the array with random numbers from 0..a.length-1
         */
        
        for (int i = a.length; --i >= 0;) {
            a[i] = (int)(i / f);
        }

        /* 
         *  Shuffle the array
         */
	for (int i = a.length; --i >= 0;) {
	    int j = (int)(i * Math.random());
	    int t = a[i];
	    a[i] = a[j];
	    a[j] = t;
	}

        pause();

        /*
         *  Now sort the array.
         *  Each time through the loop we remove a value, find it's correct
         *  position in the array, and place it there.  The displaced 
         *  value becomes the next value to place.
         */
	int T = a[0];
        int S = a[1];
	for (int i = 0; i < a.length; i++) {
	    if (stopRequested) {
		return;
            }
	    S = a[(int) (T * f)];
            /* 
             *  If the item we're trying to move is supposed to where the
             *  next item goes we'll get stuck in a fixed point.
             *  Pick a new starting point.
             */
            if( T == S) {
                T = a[(int) (Math.random() * a.length)];
                S = a[(int) (T * f)];
            }
	    a[(int) (T * f)] = T;
	    T = S;
	    pause((int) (S * f), (int) (T * f));

        }
    }
}