import java.util.Random;

public class InputGenerator {

/**

* An input returning a list of randomly generated values of size n

* @param n The size of the input

* @return the list of randomly generated values

*/

public static NumberList generateRandomInput(int n){

NumberList randomList = new NumberList();

Random rand = new Random();

for(int i = 0; i < n; i++){

randomList.add(rand.nextInt(n-1)+1);

}

return randomList;

}

public static NumberList generateBestCase(int n){

NumberList bestList = new NumberList();

for(int i = 0; i < n; i++){

bestList.add(i+1);

}

return bestList;

}

public static NumberList generateWorstCaseSelection(int n){

NumberList worstList = new NumberList();

for(int i = 0; i < n; i++){

worstList.add(n-i);

}

return worstList;

}

public static NumberList generateWorstCaseMerge(int n){

NumberList worstList = generateBestCase(n);

return splitAndMerge(worstList);

}

private static NumberList splitAndMerge(NumberList list){

if(list.size() == 1){

return list;

}else if (list.size() == 2){

list.add(list.remove(0));

return list;

}else{

NumberList left = new NumberList();

NumberList right = new NumberList();

int size = list.size();

for(int i = 0; i < size; i++){

if(i%2 == 0){

left.add(list.remove(0));

}else{

right.add(list.remove(0));

}

}

splitAndMerge(left);

splitAndMerge(right);

list.addAll(left);

list.addAll(right);

return list;

}

}

}