import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

/*
 * This is a Utility class that provides the capability of flattening arbitrarily nested
 * arrays of integers.
 * The code operates by recursively processing nested arrays.
 * For ease of use, the nested arrays are represented as nested lists.
 */

public class Flattener {

	/**
	 * Recursively flattens a nested list of integers.
	 * Only Integers and lists are accepted as part of the input.
	 *
	 *
	 * @param input The nested list of integers to flatten
	 * @return A flat list of integers
	 * @exception IllegalArgumentException is thrown if the input tree contains anything else but integers or lists
	 * @exception NullPointerException is thrown if the input is null, or contains nulls
	 */
	public static List<Integer> flatten(List<?> input) {
		//Do not accept null input
		Objects.requireNonNull(input, "The input list must not be null");
		List<Integer> flat = new ArrayList<>();

		//Process the list
		for (Object element : input) {
			if (element instanceof Integer) {
				//integers are directly added to the flat list
				flat.add((Integer)element);
			} else if (element instanceof List) {
				//lists are recursively flattened before adding all elements to the flat list
				flat.addAll(Flattener.flatten((List<?>)element));
			} else {
				//The element does not have one of the expected data types of integer or list
				// => signal an exception
				throw new IllegalArgumentException("Unsupported data type found: " + element.getClass().getName());
			}
		}
		return flat;
	}

	public static void main(String[] args) {
		//Try the flattening function out on different inputs for test purposes
		List<List<Object>> inputs = Arrays.asList(
				Arrays.asList(),
				Arrays.asList(Arrays.asList(Arrays.asList())),
				Arrays.asList(Arrays.asList(1,2,Arrays.asList(3)),4),
				Arrays.asList(1,2, Arrays.asList(3,4), 5, Arrays.asList(Arrays.asList(6,7,8), Arrays.asList(9), Arrays.asList()))
		);

		inputs.forEach(input -> System.out.println("flatten(" + input + ") = " + Flattener.flatten(input)));

//		This is the actual output just for reference:
//			flatten([]) = []
//			flatten([[[]]]) = []
//			flatten([[1, 2, [3]], 4]) = [1, 2, 3, 4]
//			flatten([1, 2, [3, 4], 5, [[6, 7, 8], [9], []]]) = [1, 2, 3, 4, 5, 6, 7, 8, 9]

	}

}