LAB 6 - Constructing Arrays with Java Generics

Goal

Using Java Generics, implement an array container with the following functionalities:

isEmpty returns true if there are no elements in the array.
getSize returns the number of elements in the array.
add adds x into the array if it is not already present. Returns a Boolean indicating if the operation was successful.
remove removes x from the array if it was present, and does nothing otherwise. Returns a Boolean indicating if the operation was successful. contains returns true if and only if x is in the array.
iterator returns an object that implements the standard java.util.Iterator interface.

Here is the rough outline of the implementation:

					  import java.util.NoSuchElementException;
					  public class ArrayContainer<AnyType>
					  {
					   		 public ArrayContainer( )  {... }
							 public boolean isEmpty( ) {.... }
							 public int getSize( ) { .... }
							 public boolean add( AnyType x ) { ... }
							 public boolean remove( AnyType x ) { ....}
							 public boolean contains( AnyType x ) { ....}
							 private class ArrayIterator implements java.util.Iterator<AnyType>
							 {
							  		 public boolean hasNext( ) { ....}
									 public AnyType next( ) {.... }
									 public void remove( ) {
									 		if( !okToRemove )
											 	  throw new IllegalStateException( );
											okToRemove = false;
											ArrayContainer.this.remove( items[ --current ] );
									}
									private int current = 0;
									private boolean okToRemove = false;
							}
							public java.util.Iterator<AnyType> iterator( ){ .... }
							private void doubleArray( ){ ....}
							private AnyType[] items;
							private int  size;
					}

How to implement an array inside a container

How would you implement ArrayContainer<AnyType>? The ArrayContainer class is supposed to manage an array of AnyType, so you might expect the constructor for ArrayContainer<AnyType> to create an array of AnyType:

				 class ArrayContainer<AnyType> {
				 	   private AnyType[] items;
				 	   public ArrayContainer() {
				 	   		  items = new AnyType[DEFAULT_SIZE]; // illegal
				 	   }
				 }

But this code does not work -- you cannot instantiate an array of a type represented by a type parameter. The compiler doesn't know what type AnyType really represents, so it cannot instantiate an array of AnyType. The Collections classes use an ugly trick to get around this problem, one that generates an unchecked conversion warning when the Collections classes are compiled. The constructor for the a implementation of ArrayContainer looks likes this:

				  class ArrayContainer<AnyType> {
				  		private AnyType[] items;
				  		public ArrayList() {
				  			  items = (AnyType[]) new Object[DEFAULT_SIZE]; 
				  		}
				  }

Why does this code not generate an ArrayStoreException when items is accessed? After all, you can't assign an array of Object to an array of String. Well, because generics are implemented by erasure, the type of items is actually Object[], because Object is the erasure of AnyType. This means that the class is really expecting AnyType to be an array of Object anyway, but the compiler does extra type checking to ensure that it contains only objects of type AnyType. So this approach will work, but it's ugly, and not really something to emulate An alternate approach would have been to declare items as an array of Object, and cast it to AnyType[] everywhere it is used. You would still get unchecked conversion warnings (as you do with the previous approach), but it would have made some unstated assumptions (such as the fact that items should not escape the implementation of ArrayContainer) more clear.

LAB 6 - Constructing Arrays with Java Generics

Goal

How to implement an array inside a container

Links