import java.lang.reflect.*;

//===================================================================
// HyperDimArray allows the dynamic creation and use of multi-dimensional
// arrays of objects. This class builds on java.lang.reflect.Array.
//===================================================================

public class HyperDimArray {

protected Object array;			// the n-dimensional array we manage
protected int[] dimensions;		// [] of length N
protected int lastDimIndex;		// N-1

//-------------------------------------------------------------------
// HyperDimArray Constructor
//-------------------------------------------------------------------
public HyperDimArray(Class type, int[] dimensions, boolean fill) {

	// allocate the array using the java.lang.reflect Array class
	array = Array.newInstance(type, dimensions);

	// if array needs to be initialized to contain default objects, do so
	if ( fill && ! type.isPrimitive() ) {
		fillArray(array, dimensions.length, type);
	}

	// note bookkeeping values
	this.dimensions		= dimensions;
	this.lastDimIndex	= this.dimensions.length -1;
}
//-------------------------------------------------------------------
// Recursively fill a multi-dimensional array with "blank" objects
//-------------------------------------------------------------------
protected Object fillArray(Object subArray, int dim, Class type) {

	if ( dim == 1 ) {
		// System.out.print("Dimension 1, filling ");
		// System.out.println(((Object[])subArray).length + " elements");

		for (int i=0; i < ((Object[])subArray).length; i++) {

			Object blank = null;
			try {
				blank = type.newInstance();
			} catch (InstantiationException ignored) {
				System.out.println("Array fill error: instantiation");
			} catch (IllegalAccessException ignored) {
				System.out.println("Array fill error: illegal access");
			}
			Array.set(subArray, i, blank);
		}
	} else {
		// System.out.print("Dimension "+ dim +" filling ");
		// System.out.println(((Object[])subArray).length + " subarrays");

		for (int i=0; i < ((Object[])subArray).length; i++) {

			Object subSubArray = Array.get(subArray, i);
			subSubArray = fillArray(subSubArray, dim-1, type);
			Array.set(subArray, i, subSubArray);
		}
	}
	return subArray;
}
//-------------------------------------------------------------------
// Descend through the dimensions until we locate the 1-D array that
// contains a certain element at coordinates (x,y,z,...).
// This array can then be used to retrieve the TYPED element.
//-------------------------------------------------------------------
public Object getLowestDimensionArray(int[] coordinates) {
Object subArray;

	subArray = array;
	for (int i=0; i < coordinates.length-1; i++) {
		subArray = Array.get(subArray, coordinates[i]);
	}
	return subArray;	// by now reduced to a 1-D array
}
//-------------------------------------------------------------------
// Generic n-dimensional array element retriever.
//-------------------------------------------------------------------
public Object get(int[] coordinates) {
Object lowestDimArray;

	lowestDimArray = getLowestDimensionArray(coordinates);
	return Array.get(lowestDimArray, coordinates[lastDimIndex]);
}
//-------------------------------------------------------------------
// Generic n-dimensional array element setter.
//-------------------------------------------------------------------
public void set(int[] coordinates, Object newValue) {
Object lowestDimArray;

	lowestDimArray = getLowestDimensionArray(coordinates);
	Array.set(lowestDimArray, coordinates[lastDimIndex], newValue);
}
//-------------------------------------------------------------------
// Handy characteristics query methods
//-------------------------------------------------------------------
public int[] getDimensions() {
	return dimensions;
}
public int dimensionality() {
	return dimensions.length;
}
public int size() {
int size = 1;
	for (int i=0; i < dimensions.length; i++) {
		size *= dimensions[i];
	}
	return size;
}
//-------------------------------------------------------------------
// main() consists of a suite of tests for class HyperDimArray.
// The tests exercise setting and getting elements in arrays of increasing
// dimensionality.
//-------------------------------------------------------------------
public static void main (String[] args) {
HyperDimArray hyperSpace;

int[] hyperDims1 = {10};	// a 1-D array of 10 elements
int[] hyperDims2 = {4,4};	// a 2-D array of 4*4 elements
int[] hyperDims3 = {3,3,3};	// a 3-D array of 3*3*3 elements
int[] hyperDims5 = {2,3,3,2,4};	// a 5-D array of 2*3*3*2*4 elements

//	hyperSpace = new HyperDimArray(java.awt.Point.class, hyperDims1, true);
//	testArray(hyperSpace);
//	hyperSpace = new HyperDimArray(java.awt.Point.class, hyperDims2, true);
//	testArray(hyperSpace);
//	hyperSpace = new HyperDimArray(java.awt.Point.class, hyperDims3, true);
//	testArray(hyperSpace);

	hyperSpace = new HyperDimArray(java.awt.Point.class, hyperDims5, true);
	testArray(hyperSpace);
}
//-------------------------------------------------------------------
// pick a random point within N-space, set it to some magic value,
// then go through all N-space elements to try and locate magic value.
// if not found or if found in different spot: FAIL test and halt.
//-------------------------------------------------------------------
protected static void testArray(HyperDimArray a) {
int[] arrayDims;
int[] hiddenCoords;
int[] foundCoords;
java.awt.Point x	 = null;
java.awt.Point magic = new java.awt.Point(13,1999);

	arrayDims = a.getDimensions();

	// stuff magic value "somewhere" in n-space
	hiddenCoords = randomLocation(arrayDims);
	System.out.println(
		"Hiding magic value in " + coords2Str(hiddenCoords));

	a.set(hiddenCoords, magic);

	// now go through all array elements until we find the magic element
	// when we find it, it has to be in the same randomly selected spot.
	foundCoords = new int[ a.dimensionality() ];
	for (int i=0; i < a.size(); i++) {

		// retrieve element from array
		x = (java.awt.Point) a.get(foundCoords);

		System.out.println("Element in "+ coords2Str(foundCoords) +" = "+ x);

		// if same as our magic element..
		if ( x.equals(magic) ) {
			System.out.println("Found el in "+ coords2Str(foundCoords));
			if ( ! equalCoords(foundCoords, hiddenCoords )) {
				System.out.println(
					"ERRROR: magic element found in wrong location!");
				System.exit(100);
			}
			break;
		}

		// otherwise, go to next array element
		foundCoords = nextLocation(foundCoords, arrayDims);
	}

	// if we went through entire array without finding the magic element,
	// we're in trouble.
	if ( ! x.equals(magic) ) {
		System.out.println("Element NOT found!");
		System.exit(100);
	}
}
//-------------------------------------------------------------------
// generate a random location in a given n-dimensional space
//-------------------------------------------------------------------
protected static int[] randomLocation(int[] space) {
int[] coords;

	coords = (int[]) space.clone();
	for (int i=0; i < space.length; i++) {
		coords[i] = (int) (space[i] * Math.random()) % space[i];
	}
	return coords;
}
//-------------------------------------------------------------------
// generate next location in a given n-dimensional space
// increments coordinate components in same right-to-left order as
// digits in an incrementing number. i.e 000, 001, 002, 010, 011, 012..
//-------------------------------------------------------------------
protected static int[] nextLocation(int[] current, int[] space) {
int[] coords;

	coords = (int[]) current.clone();

	for (int i=space.length-1; i>=0 ; i--) {
		coords[i] = (coords[i]+1) % space[i];
		if ( coords[i] != 0 ) {
			break;
		}
	}

	return coords;
}
//-------------------------------------------------------------------
// utility method to convert an array of ints (representing n-dimensional
// coordinates) into a string.
//-------------------------------------------------------------------
public static String coords2Str(int[] coords) {
StringBuffer x = new StringBuffer("(");

	for (int i=0; i < coords.length; i++) {
		x.append(coords[i]);
		if ( i != coords.length -1 ) {
			x.append(",");
		}
	}
	x.append(")");
	return x.toString();
}
//-------------------------------------------------------------------
// utility method to determine if two n-dimensional coordinates are equal
//-------------------------------------------------------------------
public static boolean equalCoords(int[] c1, int[] c2) {

	for (int i=0; i < c1.length; i++) {
		if ( c1[i] != c2[i] ) {
			return false;
		}
	}
	return true;
}
} // End of Class HyperDimArray