In this post, we feature a comprehensive article which explains the Problem with creating Generic Arrays. The Java programming language added generics in September of 2004 in the Java 5.0 “Tiger” release. The system of generics or type parameterization, extends Java’s existing type system while providing type safety.
1. Introduction
Java has the Collections Framework, providing a library of generic data structures for use in Java software
development. The Collections Framework lacks on one data structure—an array. Yet the Java Collections
Framework has a type parameterized ArrayList.java and Vector.java data structures. Both data
structures use a dynamic array of one-dimension that utilizes an underlying array of java.lang.Object.
Java provides a built-in array that is an object that is included in the language specification since Java 1.0
from 1995. As an object, the built-in array is declared and instantiated in the Java code to a particulate type.
The built-in array is a container of objects that is a fixed number and length of possibly many dimensions.
Yet compile-time type safety using generics is not fully realized. Especially with the built-in array object.
2. Generic Arrays
The problem is when generics are used with the built-in array entity in Java. Consider the following Java class, TestArray1.java which declares two generic arrays around a single generic type parameter E. The Java class source code is:
class TestArray1 {
public E[] array = new E[10];
}//end class TestArray1
The source code for TestArray1.java is declarative only, the arrays are not used. Two use cases of a generic
array are written: one for the generic array as a class attribute, and the other using a generic array in a static
(i.e., non-instance) method of the class.
2.1 Generic Error when Compiled
When compiled the following error is reported by the compiler:
Error: TestArray1.java.
Line 3 At 22: generic array creation
public E[] array = new E[10];
^
There is one kind of error reported: generic array creation. This error corresponds directly to a use case of generic arrays.
Covariance
In Java, arrays are covariant, or use type specialization of general towards specific types, such as a Collection to a Set. However, generic type parameters are not covariant. Goetz explains, “The Collections classes use an ugly trick to get around this problem…” [Goet 2019]
Thus to use the built-in array with Java generics, or the generic type parameter E, the array must be of type java.lang.Object which is the great-great super-type in Java. Everything is an java.lang.Object, this is the ugly trick.
Object Array
Yet the drawback for using an Object array is the imperative for generics⎼to bind a data structure or variable to a specific type. A data structure of type Object can mix and match any type, and requires a type cast to convert to the original type. In this generics in Java are not useful⎼and this is the core problem.
The solution or answer to the problem is simple⎼a Java array class that is generic. Such a class is not in the Java collections framework, thus create it.
3. Java Array Class
The Java Array class is like the other data structures in the Java collections framework, it is a data structure. The implementation originally written is for simplicity, and does not implement any specific interfaces or extend any super-classes. The goal is to get a functional and useful array as a class Array.java to build upon. The skeleton of the generic type parameter Array.java class is:
class Array {
Array(final int... dim);
void init(final E elem);
void init(final E[] elem);
E get(final int...idx);
void add(final E elem, final int... idx);
}
Essentially you have a means to construct an array of any rank, and then any size for the dimensions
The array then has a method init() to initialize the array to a default or sentinel initial value. Lastly the array has the two primary methods, one to add() an element, and one to get() an element at a specific location within the array. The basic functionality of instantiate or create, initialize the overall array, and access an element.
3.1 Array Class Attributes
The Java array class has several attributes that define an instance of an Array.java class. The attributes of the generic type parameter Array.java class are:
class Array {
int size;
int dim[];
int rank;
Object data[];
E elem;
}
The Array.java class attributes are the data as a built-in array of Object, the boundaries of the array, such as size, rank, dimensions. Lastly, there is the elem, the initialization element.
3.2 Rank and Dimension with Varargs
The Java programming language added variable number or parameters or arguments, named Java variable arguments, or more simply varargs in Java 5.0 “Tiger” release in September 2004. This particular feature allows a constructor or method to take a varying number of parameters, and thus generalize parameters without duplicating a constructor or method simply for the number of parameters.
The generalization of the Array class uses a this specific Java feature: varargs, or variable arguments for creation and access of the elements in the Array.java class. This allows any rank (the number of dimensions) and also for each any number dimension for any non-negative integer.
Varargs also allows a rank to be general, so there is (at least theoretically…) no least upper bound on the rank of the Array.java class. Thus varargs allow for an overall generalization in defining and using a generic Array.java class.
Constructor using Varargs
The source code for the Array.java constructor illustrates using varargs for the dimensions to create a generic array object using the Array.java class. The rank and dimensions are generalized, so any rank of array is possible with any dimensional bounds. The source code for the Array.java constructor is:
Array(final int... dims) {
this.rank = dims.length;
this.dim = new int[rank];
int size = 1;
//compute size of 1-dim internal array
for (int x = 0; x < dims.length; x++) {
size = size * dims[x];
dim[x] = dims[x];
}//end for
//create internal "flat" array
this.data = new Object[size];
this.size = size;
}//end constructor
The varargs is the varying parameters passed as a primitive int as an array of integers in the variable dims. From dims the rank, dimensions for the boundaries of the array, and the overall internal “flat” array are calculated and created. Without the varargs, a constructor for each rank for different dimensions would be required. With a finite number of constructors for rank, the Array.java generic array class would be limited and not as general with varargs.
Accessor with Varargs
Accessing an element in the generic array is via the get and set methods. These are the access or accessor methods. Unlike the properties getter and setter methods, for the generic array class the dimension index specifies the element.
Using varargs, this generalizes the access methods for any rank or dimension to access an element. The dimensional index is checked against the boundaries and rank of the generic array for access.
Read Accessor Get
The getter method is the read accessor, it reads or copies a value from the array. The source code for the Array.java the get accessor method is:
E get(final int... idx) {
return (E) this.data[this.getIndex(idx)];
}//end get
Write Accessor Set
The setter method is the write accessor, it writes or copies a value into the array. The source code for the Array.java set accessor method is:
void set(final E elem, final int... idx) {
this.data[this.getIndex(idx)] = elem;
}//end set
For simplicity, the auxiliary method, getIndex() does the actual “heavy lifting” of computing the single dimension index, and checking the boundaries of the array index.
Auxiliary Methods to Help
Three auxiliary methods or helper methods do the actual processing in the generic Array.java class. One method, getIndex() computes a single index from the multiple index dimensions, and the two other methods isValidDim() and isValidIndex() validate that the index calculated, or given does not exceed the boundaries of the array. The interface source code for the auxiliary methods is:
class Array {
int getIndex(final int... idx);
boolean isValidDim(final int... idx);
boolean isValidIndex(final int idx);
}//end class Array
Heavy Lifting Getting an Element Index
The getIndex() method is the core function of the Array.java class. The getIndex() method calculates the index into the internal one-dimensional linear or “flat” array of an element. From compiler theory (and this alludes to the theory, but a more in-depth explanation is beyond the scope of explanation) an array is either indexed by row-major or column-major for an index. [Aho 2007]
For the Array.java class, it is immaterial, so long as the function is consistent for a given index for the dimension boundaries of the array instance. The source code for the getIndex() method is:
int getIndex(final int... idx){
isValidDims(idx);
int index = 0;
for(int x = 0; x < idx.length; x++) {
int i = idx[x];
for(int y = x + 1; y < idx.length; y++) {
i = i * dim[y];
}//end for
index = index + i;
}//end for
return index;
}//end getIndex
The source code for the getIndex() method validates the dimensions of an index before actually calculating the one dimensional index into the internal linear array.
Validation of an Index
There are two methods to validate an index. One is to validate a multiple dimensional index, and the other is to validate a single index. The source code to validate a single dimensional index is:
void isValidIndex(final int idx){
if(idx = this.size) throw new RuntimeException("Index Overflow Error!");
}//end isValidIndex
The isValidIndex() simply checks that the index is mathematically within the range of zero to the overall size of the internal array. If the index is not within the range, a runtime, unchecked exception is thrown. The source code to validate a multiple dimension index is:
void isValidDims(final int... idx) {
if(idx.length != this.dim.length) throw new RuntimeException("Rank Error");
for(int x = 0; x = dim[x]) throw new RuntimeException(“Index Overflow Error");
if(idx[x] < 0) throw new RuntimeException(“Index Underflow Error”);
}//end for
}//end isValidDims
The isValidDims() simply traverses each dimension parameter, and checks that the rank for the index is the same as the rank parameter of the array. If the rank of the array and the index are not equal, a runtime, unchecked exception RuntimeException is thrown.
3.3 Other Non-Varargs Methods
The other methods are non-varargs, that either take no parameters as a getter accessor method, or take a single parameter. The two categories of methods are:
- Query the array parameters
- Unique array functionality
Query the Array
The query the array parameters accesses the parameters of the array, as a getter access method, or with a parameter. The array is queries for rank, overall size, the upper dimensions, and the dimension at a specific index within the rank. The interface for the query the array methods of the Array.java class are:
class Array {
int getDim(final int dim);
int[] getDims();
int getRank();
int size();
}//end class Array
Unique Array Class Functionality
The unique array class functionality are a constructor and two methods that provide unique functionality. The two methods are to access and convert to a linear array of the Array class instance. The other functionality is a constructor that allows the instance of the Array class to be copied or replicated. The functionality for the Array.java class is:
class Array {
Array(final Array array);
E getAt(final int idx);
Object[] toArray();
}
Accessor as Linear Array
The getAt() method allows an array element to be accessed as if the Array class instance were a “flat” linear array of one dimension. The integer index is checked for validity, and the element is returned at a valid location with the internal one dimension array. The source code to access as a linear array is:
E getAt(final int index) {
this.isValidIndex(index);
return (E) this.data[index];
}//end getAt
Conversion to Linear Object Array
The toArray() method converts the Array class instance, or rather accesses the internal one dimensional array and returns it as an array of Object. The toArray() method returns a shallow copy of the internal linear array, not a deep copy. The getter accessor source code to access the linear Object array is:
Object[] toArray() {
return this.data;
}//end toArray
Copy Constructor
The copy constructor allows an Array class instance to be duplicated but as a “deep” copy of an existing Array class instance. The array copied and the copy are of the same type parameter, dimensions, rank, and of course the elements. The source code of the copy constructor is:
Array(final Array orig) {
this.rank = orig.rank;
this.dim = orig.dim;
this.size = orig.size;
this.elem = (E) orig.elem;
this.data = new Object[this.size];
System.arraycopy(orig.data, 0, this.data, 0, this.size);
}//end constructor copy
The System.arraycopy() copies the original and creates a new Object array for the deep copy. The various Array class instance parameters are copied into the deep copy.
4. Using the Generic Array Class
Using the Java generic array Array.java is illustrated in source code by two examples of use:
- Bubble sort algorithm
- Multiplication table
Both examples illustrate by demonstration the use of the generic array class methods to create, initialize, access, query, and implement functionality around an array, but not using the built-in Java array. The source code illustrates and the output from the source code fragment is given.
4.1 Bubble Sort
The bubble sort is a basic, simple sorting algorithm, but is perfect to illustrate the use of the Array.java generic array class. The bubble sort is implemented using the generic Java array as:
Array list = new Array(9).init(new Integer[]{3,5,7,4,8,0,2,1,6});
System.out.println(Arrays.toString(list.toArray()));
boolean swapFlag = true;
while(swapFlag) {
swapFlag = false;
for(int x=0;x 0) {
Integer temp = list.get(x);
list.set( list.get(x+1), x);
list.set( temp, (x+1));
swapFlag = true;
}//end if
}//end for
}//end while
System.out.println(Arrays.toString(list.toArray()));
When run, the output from the bubble sort using the generic Java array is:
[3, 5, 7, 4, 8, 0, 2, 1, 6]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
4.2 Multiplication Table
A basic, illustrative application of the Java generic array is to create a simple multiplication table of the integer from 1 to 10. This requires a two dimensional array of integers. After creating the multiplication table, the mathematical properties of identity and commutativity are verified. The source code for this use of the generic Java array is:
Array multiplyTable = new Array(10,10).init(0);
for(int x=0;x<multiplyTable.getDim(0);x++){
for(int y=0;y<multiplyTable.getDim(1);y++){
multiplyTable.set(x*y, x,y);
}//end for
}//end for
//check 1*n = n
for(int x=0;x<multiplyTable.getDim(0);x++){
if(multiplyTable.get(1,x) != x)
throw new RuntimeException("Identity property doesn't hold!”);
if(multiplyTable.get(x,1) != x)
throw new RuntimeException("Identity property doesn't hold!”);
}//end for
//check m*n = n*m
for(int x=0;x<multiplyTable.getDim(0);x++){
for(int y=0;y<multiplyTable.getDim(1);y++){
if(multiplyTable.get(x,y) != multiplyTable.get(y,x) )
throw new RuntimeException("Commutative property doesn't hold!");
}//end for
}//end for
There is no output, because the identity and commutative mathematical properties for multiplication are true, and thus valid. But this illustrates the use of a two dimensional generic array. For other higher dimensions, other applications are possible.
5. Conclusion
The original problem demonstrated the problem with a type parameterized, or generic array using the built-in array entity. Using the same code fragment, but substituting the generic array Array.java, the source code is:
class TestArray2 {
public Array array = new Array(10);
}//end class TestArray2
When compiled there are no reported errors. The data structure Array.java achieves a solution to the original problem.
The type parameterization or generics in Java allows for type-safe classes, but there are trade-offs in the design of the generic type parameterization system. Thus generics in Java has some flaws relating to the built-in Java array entity. The Java Collections Framework unfortunately does not remedy the problem by providing an array data structure.
The solution is within the Java language and generic type parameterization. Simply design a generic Array class as a first-class object written in Java. On the surface, it seems a redundant, duplication of an existing Java entity—the array.
This is not replication; designing a Java Array class creates a generic, type-safe data structure that is a useful replacement for the built-in Java array entity. The trade-off is that without operator overloading, the syntax is less explicit about array access and operations, but is consistent with invoking methods on an object instance.
6. References
- [Aho 2007] Aho, Alfred V., Lam, Monica S., Sethi, Ravi, and Ullman, Jeffrey D. Compilers: Principles, Techniques, and Tools, 2nd edition. Pearson Education, Inc., New York, New York, 2007, pp. 381 – 382.
- [Goet 2019] Goetz, Brian. “Java theory and practice: Generics gotchas,” January 25, 2005. https://www.ibm.com/developerworks/java/library/j-jtp01255/index.html, Accessed September 28, 2019.
7. Download the Source Code
You can download the full source code of this article here: The Problem with Creating Generic Arrays
