package sorts;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
/**
* Utility class to generate arrays for testing sorting algorithms.
* !!!!!!!!!!! DO NOT MODIFY THIS FILE !!!!!!!!!
*/
public class ArrayGenerator {
private static Random rand = new Random();
public static int[] generateRandomArray(int size) {
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = rand.nextInt();
}
return arr;
}
// Generates an array sorted in order with a fraction of elements swapped.
public static int[] generateInOrderArray(int size, double perturbation) {
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = i;
}
int swaps = (int) (size * perturbation);
for (int i = 0; i < swaps; i++) {
int a = rand.nextInt(size);
int b = rand.nextInt(size);
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
return arr;
}
// Generates a descending array then perturbs it.
public static int[] generateOutOfOrderArray(int size, double perturbation) {
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = size - i;
}
int swaps = (int) (size * perturbation);
for (int i = 0; i < swaps; i++) {
int a = rand.nextInt(size);
int b = rand.nextInt(size);
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
return arr;
}
// Generates an array where each element is (random % mod) + offset.
public static int[] generateModuloArray(int size, int mod, int offset) {
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = rand.nextInt(mod) + offset;
}
return arr;
}
/**
* Generates an array of size n with values in the range [a, b] (inclusive),
* such that approximately clumpFraction (a number between 0 and 1) of the array
* is chosen between c and d (inclusive), and the remaining entries are chosen
* uniformly from [a, b] excluding the clump set.
*/
public static int[] generateClumpedArrayCustom(int size, int a, int b, double clumpFraction, int c, int d) {
// Determine the number of clumped values (rounding to nearest integer).
int clumpCount = (int) Math.round(size * clumpFraction);
int nonClumpCount = size - clumpCount;
int[] arr = new int[size];
// Fill the clumped portion with random numbers in [c, d].
for (int i = 0; i < clumpCount; i++) {
arr[i] = rand.nextInt(d - c + 1) + c;
}
// For the non-clumped portion, we need to choose numbers uniformly from [a, b]
// excluding the interval [c, d].
// Compute the number of allowed values below c and above d.
int lowerRangeLength = c - a; // valid values: a .. c-1
int upperRangeLength = b - d; // valid values: d+1 .. b
int allowedLength = lowerRangeLength + upperRangeLength;
if (allowedLength <= 0) {
throw new IllegalArgumentException("Invalid ranges: there are no values outside the clumped interval.");
}
// Fill the remaining part with values outside [c, d].
for (int i = clumpCount; i < size; i++) {
int r = rand.nextInt(allowedLength);
if (r < lowerRangeLength) {
// Choose from [a, c-1]
arr[i] = a + r;
} else {
// Choose from [d+1, b]
arr[i] = d + 1 + (r - lowerRangeLength);
}
}
// Shuffle the array to mix the clumped and non-clumped values.
for (int i = size - 1; i > 0; i--) {
int j = rand.nextInt(i + 1);
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
return arr;
}
/**
* Generates an array of size n with values in the range [a, b] (inclusive),
* such that approximately clumpFraction (a number between 0 and 1) of the array
* is chosen from a subset of k distinct random values (the clump set),
* and the remaining entries are chosen uniformly from [a, b] excluding the clump set.
*
* @param n the size of the array to generate.
* @param a the lower bound (inclusive) for values.
* @param b the upper bound (inclusive) for values.
* @param clumpFraction the fraction of entries that should be chosen from the clump set.
* @param k the number of distinct clump values.
* @return the generated array.
* @throws IllegalArgumentException if n <= 0, a > b, k > (b - a + 1), or clumpFraction is not between 0 and 1.
*/
public static int[] generateArrayWithClumpSubset(int n, int a, int b, double clumpFraction, int k) {
if (n <= 0)
throw new IllegalArgumentException("n must be positive");
if (a > b)
throw new IllegalArgumentException("a must be <= b");
int range = b - a + 1;
if (k > range)
throw new IllegalArgumentException("k cannot exceed the total number of distinct values in [a, b]");
if (clumpFraction < 0 || clumpFraction > 1)
throw new IllegalArgumentException("clumpFraction must be between 0 and 1");
Random rand = new Random();
int[] arr = new int[n];
// Determine the number of positions to force from the clump subset.
int clumpCount = (int) Math.round(n * clumpFraction);
// 1. Generate the clump subset of k distinct random values in [a, b].
Set<Integer> clumpSet = new HashSet<>();
while (clumpSet.size() < k) {
int val = rand.nextInt(range) + a;
clumpSet.add(val);
}
// Convert to a list for easier random access.
List<Integer> clumpList = new ArrayList<>(clumpSet);
// 2. Decide which positions in the array will come from the clump subset.
// Create an array of indices [0..n-1] and shuffle it.
int[] indices = new int[n];
for (int i = 0; i < n; i++) {
indices[i] = i;
}
for (int i = n - 1; i > 0; i--) {
int j = rand.nextInt(i + 1);
int tmp = indices[i];
indices[i] = indices[j];
indices[j] = tmp;
}
// Mark the first clumpCount indices as clump positions.
Set<Integer> clumpPositions = new HashSet<>();
for (int i = 0; i < clumpCount; i++) {
clumpPositions.add(indices[i]);
}
// 3. Fill the array.
for (int i = 0; i < n; i++) {
if (clumpPositions.contains(i)) {
// For clump positions, assign a value chosen uniformly from the clump set.
int randomIndex = rand.nextInt(clumpList.size());
arr[i] = clumpList.get(randomIndex);
} else {
// For non-clump positions, choose a value uniformly from [a, b] that is not in the clump set.
int candidate;
do {
candidate = rand.nextInt(range) + a;
} while (clumpSet.contains(candidate));
arr[i] = candidate;
}
}
return arr;
}
}