Home » Java » Core Java » The Problem With Creating Generic Arrays

About William Gilreath

I am a software development engineer, computer scientist, mathematician, and writer. I am a senior machine learning engineer at VMware, Inc. https://www.wfgilreath.xyz

The Problem With Creating Generic Arrays

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:

  1. Query the array parameters
  2. 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:

  1. Bubble sort algorithm
  2. 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.

7. Download the Source Code

Download
You can download the full source code of this article here: The Problem with Creating Generic Arrays

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

 

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

 

and many more ....

 

Receive Java & Developer job alerts in your Area

I have read and agree to the terms & conditions

 

Subscribe
Notify of
guest

This site uses Akismet to reduce spam. Learn how your comment data is processed.

0 Comments
Inline Feedbacks
View all comments