package se.chalmers.dat255.sleepfighter.challenge.sort;

import java.util.BitSet;
import java.util.Random;

import se.chalmers.dat255.sleepfighter.utils.collect.PrimitiveArrays;
import se.chalmers.dat255.sleepfighter.utils.math.IntMath;
import se.chalmers.dat255.sleepfighter.utils.math.RandomMath;

/**
 * ClusteredGaussianListGenerator is an implementation of NumberListGenerator
 * provides a list of numbers that have clusters with low standard deviation (stdDev),
 * and high stdDev as a whole.
 *
 * We want a list that looks like for example:
 * [131, 135, 136, 315, 317, 328, 931, 935, 941].
 * There is nothing special about the numbers in themselves,
 * other than that the whole set has a large stdDev while
 * the tripples form clusters with low stdDev internally.
 *
 * In order to accomplish this, we first randomize a list
 * with outerSize which make up the higher numbers like: x00
 * where x is a randomized digit. This value is standard-distributed from 1-9.
 *
 * After, we do for each number in the higher/outer numbers
 * a new list of innerSize which is calculated as higher[i] + randGaussian(innerRange)
 * where innerRange is some random generated range within [1, 99] if say numDigits == 3.
 *
 * @author Centril<twingoow@gmail.com> / Mazdak Farrokhzad.
 * @version 1.0
 * @since Oct 1, 2013
 */
public class ClusteredGaussianListGenerator implements NumberListGenerator {
	private static final double INNER_STANDARD_DEVIATIONS = 2.0;
	private static final int MAX_GAUSS_ITERATIONS = 100;

	private int numDigits = 3;

	@Override
	public void setNumDigits( int digits ) {
		if ( this.numDigits < 2 ) {
			throw new IllegalArgumentException( "n(digits) must be > 1, but " + digits + " was provided" );
		}

		this.numDigits = digits;
	}

	@Override
	public int getNumDigits() {
		return this.numDigits;
	}

	/**
	 * {@inheritDoc}<br/>
	 * Implementation note: the size must have integer factors: <code>size = a * b, where a, b ∈  Z+</code>
	 */
	@Override
	public int[] generateList( Random rng, int size ) {
		// outer = index 0, inner = index 1.
		int[] sizes = computeSizes( size );
		int[] numbers = new int[sizes[0] * sizes[1]];
		int outerMultiplier = com.google.common.math.IntMath.pow( 10, this.numDigits - 1 );
		int innerMax = outerMultiplier - 1;

		// Fill outer array first.
		int[] outer = new int[sizes[0]];
		for ( int i = 0; i < sizes[0]; ++i ) {
			outer[i] = RandomMath.nextRandomRanged( rng, 1, 9 ) * outerMultiplier;
		}

		// Fill inner array for each outer array.
		for ( int i = 0; i < sizes[0]; ++i ) {
			// Calculate bounds [min, max].
			int[] innerBounds = new int[] { RandomMath.nextRandomNon10( rng, 1, innerMax ), RandomMath.nextRandomNon10( rng, 1, innerMax ) };
			int diff = innerBounds[1] - innerBounds[0];
			if ( diff < 0 ) {
				// Wrong order, swap!
				PrimitiveArrays.swap( innerBounds, 0, 1 );
				diff = -diff;
			}
			if ( diff < sizes[1] ) {
				// Difference is too small, make sure we got room!
				innerBounds[0] = Math.max( 1, innerBounds[0] - sizes[1] );
				innerBounds[1] = innerBounds[0] + sizes[1];

				diff = innerBounds[1] - innerBounds[0];
			}

			BitSet bits = new BitSet( diff );
			boolean filledModulo10 = false;

			// Now do the filling.
			int[] inner = new int[sizes[1]];
			for ( int j = 0; j < sizes[1]; ++j ) {
				inner[j] = RandomMath.nextGaussianNon10( rng, innerBounds[0], innerBounds[1], MAX_GAUSS_ITERATIONS, INNER_STANDARD_DEVIATIONS );

				// Protect against same numbers all the time, can we do away with this loop? not O(n) but still...
				boolean hasDuplicate = false;
				for ( int k = 0; k < j; ++k ) {
					if ( inner[k] == inner[j] ) {
						hasDuplicate = true;
					}
				}

				if ( hasDuplicate ) {
					if ( !filledModulo10 ) {
						// Set all numbers that end with 0 in BitSet, we don't want them!
						// This assumes that neither innerBounds[0, 1] are modulo 10.
						for ( int l = ((innerBounds[0] / 10) + 1) * 10; l <= innerBounds[1]; l += 10 ) {
							bits.set( l - innerBounds[0] );
						}

						filledModulo10 = true;
					}

					// Find first false bit.
					// This beats the idea of randomness, but avoiding duplicates is more important!
					inner[j] = bits.nextClearBit( 0 ) + innerBounds[0];
				}

				bits.set( inner[j] - innerBounds[0] );

				numbers[sizes[1] * i + j] = outer[i] + inner[j];
			}
		}

		return numbers;
	}

	/* --------------------------------
	 * Private interface.
	 * --------------------------------
	 */

	/**
	 * Computes outer & inner sizes.
	 *
	 * @param size the size to break down.
	 * @return the sizes.
	 */
	private int[] computeSizes( int size ) {
		if ( size < 1 ) {
			throw new IllegalArgumentException( "Only integers > 0 are allowed" );
		}

		int[] sizes = IntMath.findClosestFactors( size );

		if ( sizes == null ) {
			throw new IllegalArgumentException( "There is no 2-factor solution for the size: " + size );
		}

		return sizes;
	}
}

package se.chalmers.dat255.sleepfighter.utils.math;

import java.util.Random;

/**
 * RandomMath provides utility methods for dealing with random numbers.
 *
 * @author Centril<twingoow@gmail.com> / Mazdak Farrokhzad.
 * @version 1.0
 * @since Sep 30, 2013
 */
public class RandomMath {
	/**
	 * Calculates the first random number in range [min, max] that is not modulo 10.
	 *
	 * @param rng the random number generator.
	 * @param min the minimum number, inclusive.
	 * @param max the maximum number, inclusive.
	 * @return the randomly generated number.
	 */
	public static int nextRandomNon10( Random rng, int min, int max )  {
		int r;
		while ( (r = nextRandomRanged( rng, min, max )) % 10 == 0 );
		return r;
	}

	/**
	 * Calculates random number in range [min, max]
	 *
	 * @param rng the random number generator.
	 * @param min the minimum number, inclusive.
	 * @param max the maximum number, inclusive.
	 * @return the randomly generated number.
	 */
	public static int nextRandomRanged( Random rng, int min, int max ) {
		// Maybe use nextGaussian here instead?
		return min + (int) (rng.nextDouble() * ((max - min) + 1));
	}

	/**
	 * <p>Returns a random generated gaussian / normal distributed<br/>
	 * number with given mean and standard deviation.</p>
	 *
	 * <p>99.7% of all numbers lie within the 3rd standard deviation, see:<br/>
	 * http://en.wikipedia.org/wiki/68-95-99.7_rule</p>
	 *
	 * @see http://en.wikipedia.org/wiki/68-95-99.7_rule
	 * @param rng the random number generator.
	 * @param mean the mean to distribute around.
	 * @param stdDev the standard deviation, which in layman terms can be put as how much the curve is stretched.
	 * @return the randomly generated number.
	 */
	public static double nextGaussian( Random rng, double mean, double stdDev ) {
		return mean + rng.nextGaussian() * stdDev;
	}

	/**
	 * <p>Returns a random generated pseudo-gaussian / normal<br/>
	 * distributed number in a given range [min, max].<br/>
	 * It is not gaussian in the sense that it has a range<br/>
	 * whereas gaussian distributions are unbounded.</p>
	 *
	 * @param rng the random number generator.
	 * @param min the minimum value, inclusive.
	 * @param max the maximum value, inclusive.
	 * @param maxIterations the hard limit of iterations to run before ending loop, used as a safety measure.
	 * @param deviations how many standard deviations to use.
	 * @return the random number.
	 */
	public static int nextGaussianRanged( Random rng, int min, int max, int maxIterations, double deviations ) {
		// See http://stackoverflow.com/questions/1303368/how-to-generate-normally-distributed-random-from-an-integer-range?rq=1
        int r = 0;
        for ( int i = 0; (i < maxIterations) && ((r = (int) nextGaussian( rng, min + (max - min) / 2.0, (max - min) / 2.0 / deviations )) > max || r < min); ++i );
        return r;
	}

	/**
	 * Like {@link #nextGaussianRanged(Random, int, int, int)} but excluding numbers modulo 10.
	 *
	 * @param rng the random number generator.
	 * @param min the minimum value, inclusive.
	 * @param max the maximum value, inclusive.
	 * @param maxIterations the hard limit of iterations to run before ending loop, used as a safety measure.
	 * @param deviations how many standard deviations to use.
	 * @return the random number.
	 */
	public static int nextGaussianNon10( Random rng, int min, int max, int maxIterations, double deviations ) {
		int r;
		while ( (r = nextGaussianRanged( rng, min, max, maxIterations, deviations )) % 10 == 0 );
		return r;
	}
}