CISC 3130 Container-Relevant Language Features & Techniques

Topics

Exception handling
User-defined exception classes
Checked and unchecked exceptions
Nested and inner classes
Resizeable arrays/containers
Generic classes

Our Current `Vector` Class

Here is our current implementation of the Vector class:

class Vector {
	Vector(int capacity) {
		this.capacity = capacity;
		arr = new int[capacity];
	}
	Vector() {this(DEFAULT_CAPACITY);}

	int get(int index) {return arr[index];}

	void set(int index, int value) {arr[index] = value;}

	void add(int value) {
		arr[size] = value;
		size++;
	}

	int getCapacity() {return capacity;}
	int size() {return size;}

	public String toString() {
		String result = "{";
		for (int i = 0; i < size; i++)
			result += arr[i] + (i < size-1 ? ", " : "");
		result += "}";
		return result;
	}

	int [] arr;
	int capacity, size = 0;
	static final int DEFAULT_CAPACITY = 10;
}

I had mentioned in the previous lecture that this code was actually incorrect, and that we would correct the situation in this lecture. There are actually two error in our class:

While bounds-checking is being implicitly performed by the Java runtime on the physical (underlying) array there is no checking being done at the logical level
- Remember, the container elements lie in the range 0 … size-1. Elements outside of that range are not part of the container (even though they exist within the underlying container).
- Accessing an element outside the logical bounds of the vector should produce a similar sort of exception as accessing an element outside the bounds of an array
- As things stand in the above code, no error would result from access outside the bounds of the container as long as the access was within the bounds of the array
- We thus need to add our own bounds-checking logic
The underlying container (the built-in array) has a fixed size, and thus accepts a fixed number of elements. Beyond that point, one should not be able to append any additional elements.
- Attempting to add to a full container is known as container overflow
- In actuality, had one filled up the above Vector and then added an additional element, an ArrayIndexOutOfBoundsException WOULD occur
  - However, we'd like to have a bit more control over the exception thrown

Exception Handling

Bounds Checking

In general, if a bounds check fails, an exception should be thrown
We could simply perform a throw Exception, but we'd rather be consistent with how Java handles this situation.
- In addition, that would mean we would have to have a catch Exception e) in our try/catch block which is way too general a catch.
Bound-check failures occur in the context of arrays, Strings, and various other containers in Java
- array-based bound violations generate an ArrayIndexOutOfBoundsException
- String-based bound violations generate a StringIndexOutOfBoundsException
- Both of the above are subclasses of the general IndexOutOfBoundsException
- ArrayList does not have an ArrayListIndexOutOfBoundsException but rather throws the general IndexOutOfBoundsException
  - We won't concern ourselves with why at this point
- We might thus consider having a VectorIndexOutOfBoundsException, but will follow the ArrayList approach
  - One reason is that it's simpler to use an existing class than write a new one
  - Secondly, our Vector is closer in some sense to ArrayList than to
    - the built-in array: which is not a class (though it is an object)
    - String: which is not strictly a container in the Java universe
  - We will however, take the customized exception approach after our first exception-handling implementation, primarily to show how it's done (there are several techniques that can be illustrated in doing so).

Container Overflow

Again, we could simply throw an Exception or create our own exception class.
Instead we're going to follow Java's lead in terms of what it does with its containers
This is a bit of a challenge since just about all of Java's containers are resizeable and thus don't get full in the usual sense (unless we actually run out of memory, and that's a whole other situation).
However, there are a couple of fixed-size containers in the Java Container Framework (JCF) and they throw an IllegalStateException when they are full, so we'll do the same
- You would not be expected to figure this out (i.e., discover the existence of such containers, nor discover their use of this exception type).
- As an aside: the JCF is the set of classes and other entities in Java that provide and support use of containers; we will spend quite a bit of time going through it.

Vector Version 3: Exception Handling

class Vector {
	Vector(int capacity) {arr = new int[capacity];}
	Vector() {this(DEFAULT_CAPACITY);}

	int get(int index) {	
		if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
		return arr[index];
	}

	void set(int index, int value) {	
		if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
		arr[index] = value;
	}

	void add(int value) {
		if (size == getCapacity()) throw new IllegalStateException("Exceeded vector capacity of " + arr.length);
		arr[size++] = value;
	}

	int getCapacity() {return arr.length;}
	int size() {return size;}

	public String toString() {
		String result = "{";
		for (int i = 0; i < size; i++)
			result += arr[i] + (i < size-1 ? ", " : "");
		result += "}";
		return result;
	}

	int [] arr;
	int size = 0;
	static final int DEFAULT_CAPACITY = 10;
}

Notes

Note the logic to detect out of container range access in both the get and set methods
The IndexOutOfBoundsException constructor — like most exception class constructor — accepts a String containing some sort of descriptive message.
Overflow checking and the associated exception handling occurs in the add method … the only method that increases the size of the container.
Note the call to getCapacity in the overflow check in add. While we could have used arr.length, we choose to use the method instead for a couple of reasons:
- the method name is more expressive and more readily states what we're testing — the capacity.
- in general, it is considered better practice to use a method rather than an instance variable's value (even within the context of the class, despite the fact that the (normally private) instance variable is accessible)
- While we're relatively new at this game, we might not be shocked if we were told that at some point we might replace the array with some other underlying container, in which case the .length would no longer be applicable; however, we can always change the logic of getCapacity to reflect whatever we move to.

Here is the app:

public class VectorApp {
	public static void main(String [] args) {
		Vector v = new Vector();
		System.out.println("capacity: " + v.getCapacity());
		System.out.println("size: " + v.size());

		try {
			System.out.println(v.get(0));
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Successfully caught exception on get: " + e);
		}

		try {
			v.set(0, 999);
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Successfully caught exception on set: " + e);
		}

		for (int i = 0; i < v.getCapacity(); i++)
			v.add(i * 10);
		System.out.println(v);
		System.out.println("size: " + v.size());

		for (int i = 0; i < v.size(); i++)
			v.set(i, v.get(i)+1);
		System.out.println(v);
		System.out.println();

		try {
			v.add(999);
		} catch (IllegalStateException e) {
			System.out.println("Successfully caught exception on add: " + e);
		}
		System.out.println("capacity: " + v.getCapacity());
		System.out.println("size: " + v.size());
		System.out.println(v);
	}
}

Notes

As mentioned before, these apps are demos, not full-blown tests
- However, we would like to exhibit the exception handling semantics of the class, so our app logic begins to begins to take on a bit of a test flavor
Note the first try/catch block; the basic logic is:
- that we set ourselves up to perform an operation that will cause an exception to be thrown (the get(0) on the empty Vector)
- we enclose the exception-causing code in the try/catch
- in the catch portion, we print out the successful catch of the exception
- Had this been a proper test, we would have had code in the try portion — after the exception-cause statement, signalling the error that an exception was not thrown.
- We would also have similar tests on other out of range indexes (e.g., -1)
  - We have similar logic for set
  - Finally at the end of the app, after we have loaded up the container to capacity, we have similar exception checking logic, but this time we add an element and check for overflow

capacity: 10
size: 0
Successfully caught exception on get: java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
Successfully caught exception on set: java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
{0, 10, 20, 30, 40, 50, 60, 70, 80, 90}
size: 10
{1, 11, 21, 31, 41, 51, 61, 71, 81, 91}

Successfully caught exception on add: java.lang.IllegalStateException: Exceeded vector capacity of 10
capacity: 10
size: 10
{1, 11, 21, 31, 41, 51, 61, 71, 81, 91}

User-Defined Exception Classes

An exception class (i.e., a class that can be using a throw statement), must be a subclass (direct or otherwise) the Exception class.
Typically an exception class contains a constructor that invokes its parent's constructor using super
The constructor usually accepts a String, representing a descriptive message of the exception, which is passed up to the parent
The exception class can be defined as an standalone class (i.e., in its own .java file or as a nested class of the class for which it will be used to handle exceptions. We will illustrate both.

`RunTimeException` — Checked vs Unchecked Exceptions

When you open a file (for example when creating a Scanner object), there is is possibility that the file may not be found and a FileNotFoundException will be thrown
- If you recall, you must declare a throws FileNotFoundException (or simply throws Exception in this situation
Now, consider the array access code a[i], or the expression a / b
- the former can cause an ArrayIndexOutOfBoundsException to be thrown, and the latter can cause an ArithmeticException (with a 'zero divide' message).
- and yet no throws clause is required
Java categorizes exceptions into two distinct groups: checked and unchecked:
- checked exceptions are those that theoretically can be handled (recovered from). As such, the compiler requires the programmer to declare their potential occurrence within a method, so that callers of that method can decide whether they wish to add exception-handling code to the context in which they are calling the method
  - FileNotFoundExceptioa is a perfect example of this. The existence of the file is out of the control of the programmer, but if the file doesn't exist, the programmer can take steps to recover, by asking for the name of a different file, and this logic can be placed in a try/catch enclosing the opening of the file
- unchecked exceptions are usually the result of programming error: an index out of bounds or zero divide, for example, could be avoided by proper programming and subsequent testing.
  - Furthermore, the code that produces such errors is ubiquitous, i.e., everywhere. Imagine having to put a throws ArrayIndexOutOfBoundsException on every method that uses an array; or have a try/catch block around every expression containing a division.
Exception classes (i.e., subclasses of Exception are by default checked. To specify an exception class represents an unchecked exception (which again means that no throws clause is necessary), one make the class a subclass of RuntimeException
- RuntimeException is itself a subclass of Exception so the class in question is indeed an exception class
- being a subclas of RuntimeException makes the class an unchecked exception class
- RuntimeException is actually a quite good name for the 'class' of unchecked exceptions. Runtime errors are usually the result of programming errors (as opposed to something like a FileNotFoundException.
Both exceptions that can occur in Vector are the result of programming errors and or situations that cannot be recovered from:
- The index out of bounds is a result of the caller of get or set sending an invalid index. This is almost always the result of a programming error; furthermore it's probably unrecoverable or the bad index would not have been sent in the first place.
- Overflow is a result of the underlying container being too small; either:
  - a resizeable container should have been used (we'll get to that shortly) or
  - a larger Vector with a larger capacity should have been created (for dynamic fixed-size) or
  - the app can't accommodate what we are trying to do (in the case of a static fixed size — we would have to change the capacity in the code and rebuild the system).
As such, we will make our VectorException class an unchecked exception.

Vector Version 3.1: Exception Handling Using a User-Defined Exception Class

In those version, we define our own standalone exception class.

Again, this is primarily to show you some techniques that will prove useful later, and not just for exceptions
An exception class must be a subclass (direct or not) of the Exception class

Here is an exception class that we define; we will use it for both types of exceptions: out of bounds and overflow

class VectorException extends RuntimeException {
	VectorException(String message) {super(message);}
}

Notes

As discussed above, an exception class must be defined as a subclass of Exception, and in our case, we want it to be an unchecked as well, therefore were subclas it from RuntimeException.

Here is the Vector class:

class Vector {
	Vector(int capacity) {arr = new int[capacity];}
	Vector() {this(DEFAULT_CAPACITY);}

	int get(int index) {	
		if (index < 0 || index >= size) throw new VectorException("Index " + index + " out of bounds for length " + size);
		return arr[index];
	}

	void set(int index, int value) {	
		if (index < 0 || index >= size) throw new VectorException("Index " + index + " out of bounds for length " + size);
		arr[index] = value;
	}

	void add(int value) {
		if (size == getCapacity()) throw new VectorException("Exceeded vector capacity of " + arr.length);
		arr[size++] = value;
	}

	int getCapacity() {return arr.length;}
	int size() {return size;}

	public String toString() {
		String result = "{";
		for (int i = 0; i < size; i++)
			result += arr[i] + (i < size-1 ? ", " : "");
		result += "}";
		return result;
	}

	int [] arr;
	int size = 0;
	static final int DEFAULT_CAPACITY = 10;
}

Notes

Note the change in the exception being thrown

Here is the app:

public class VectorApp {
	public static void main(String [] args) {
		Vector v = new Vector();
		System.out.println("capacity: " + v.getCapacity());
		System.out.println("size: " + v.size());

		try {
			System.out.println(v.get(0));
		} catch (VectorException e) {
			System.out.println("Successfully caught exception on get: " + e);
		}

		try {
			v.set(0, 999);
		} catch (VectorException e) {
			System.out.println("Successfully caught exception on set: " + e);
		}

		for (int i = 0; i < v.getCapacity(); i++)
			v.add(i * 10);
		System.out.println(v);
		System.out.println("size: " + v.size());

		for (int i = 0; i < v.size(); i++)
			v.set(i, v.get(i)+1);
		System.out.println(v);
		System.out.println();

		try {
			v.add(999);
		} catch (VectorException e) {
			System.out.println("Successfully caught exception on add: " + e);
		}
		System.out.println("capacity: " + v.getCapacity());
		System.out.println("size: " + v.size());
		System.out.println(v);
	}
}

Notes

Note the change in the exception class being caught

The output:

capacity: 10
size: 0
Successfully caught exception on get: VectorException: Index 0 out of bounds for length 0
Successfully caught exception on set: VectorException: Index 0 out of bounds for length 0
{0, 10, 20, 30, 40, 50, 60, 70, 80, 90}
size: 10
{1, 11, 21, 31, 41, 51, 61, 71, 81, 91}

Successfully caught exception on add: VectorException: Exceeded vector capacity of 10
capacity: 10
size: 10
{1, 11, 21, 31, 41, 51, 61, 71, 81, 91}

Sidebar

Vector Version 3.2: A Nested/Inner Class for the Exception Class

In this version, we move the exception class into the corresponding container class. This is primarily for the purpose of encapsulation / data hiding. In practice, exception classes are not nested by defined as a top-level class (as in the previous version).

There are actually two types of inner class: static nested classes and non-static nested class, the latter also known as an
inner class.
- They differ syntactically by the static nest class having the static keyword in the class header (e.g. static class …)
- Semantically, they are quite different, but not in any way we need to deal with right now.
We will work with inner classes for now (when we actually use a nested class.
- In general, however, we will define our exception classes as top-level, unless otherwise specified

class Vector {
	class VectorException extends RuntimeException {
		VectorException(String message) {super(message);}
	}

	Vector(int capacity) {arr = new int[capacity];}
	Vector() {this(DEFAULT_CAPACITY);}

	int get(int index) {	
		if (index < 0 || index >= size) throw new VectorException("Index " + index + " out of bounds for length " + size);
		return arr[index];
	}

	void set(int index, int value) {	
		if (index < 0 || index >= size) throw new VectorException("Index " + index + " out of bounds for length " + size);
		arr[index] = value;
	}

	void add(int value) {
		if (size == getCapacity()) throw new VectorException("Exceeded vector capacity of " + arr.length);
		arr[size++] = value;
	}

	int getCapacity() {return arr.length;}
	int size() {return size;}

	public String toString() {
		String result = "{";
		for (int i = 0; i < size; i++)
			result += arr[i] + (i < size-1 ? ", " : "");
		result += "}";
		return result;
	}

	int [] arr;
	int size = 0;
	static final int DEFAULT_CAPACITY = 10;
}

Notes

Again, the absence of static in the nested class header means we are dealing with an inner (non-static nested) class
- The fully qualified name of the class is Vector$VectorException
  - The fully-qualified name of a class is its full name (in the absence of any imports or other naming-shortcuts)
    - This would include any package names, e.g. java.lang.String
    - In our case, we are working in the default package (i.e., the package you are in if there is no package statement at the top of your source file).
- The main advantage of doing this is when the nested class is only used by the outer class and thus no other code needs to see this class.
Other than the placement of the exception class, everything is the same

capacity: 10
size: 0
Successfully caught exception on get: Vector$VectorException: Index 0 out of bounds for length 0
Successfully caught exception on set: Vector$VectorException: Index 0 out of bounds for length 0
{0, 10, 20, 30, 40, 50, 60, 70, 80, 90}
size: 10
{1, 11, 21, 31, 41, 51, 61, 71, 81, 91}

Successfully caught exception on add: Vector$VectorException: Exceeded vector capacity of 10
capacity: 10
size: 10
{1, 11, 21, 31, 41, 51, 61, 71, 81, 91}

Notes

Note the name of the exception

Vector Version 4: A Resizeable Underlying Container

We now turn our attention to capacity/memory management of the underlying array, with the goal of having a resizeable underlying container. This would permit us to basically ignore capacity issues.

Sidebar

Memory Management

Arrays in Java are objects and are thus created using new (they are similar to classes in this respect; but different in that they cannot have methods)
As such, array variables are reference variables (again like variable for classes) and thus can 'point' to different array objects.
- This is in contrast to primitive types/variables, such as int, double, and boolean where the variables contain the actual value rather than a reference to an object
Note the array is not being resized; as we have said, arrays are, by definition, fixed in size
Rather, a new, larger array is created, the content of the original array are copied over to the new array and the reference variable redirected from the old array to the new.

Here is the core logic for resizing an array, assuming the array is referenced by the variable arr:

Create a new array with a larger capacity, typically, double the size of the original array
- Assign the reference returned by the new expression to some temporary reference variable; we'll call it temp
- the doubling of size if not arbitrary; we'll see later it's crucial ensuring this process is efficient
Copy the elements from the original array (referenced by arr) to the corresponding elements new array (referenced by temp)
Assign the reference to the new array i(in temp to arr)
- The original array object will, in all likelihood, become garbage

and here is the corresponding Java fragment:

int [] temp = new int[2*arr.length];
for (int i = 0; i < arr.length; i++)
	temp[i] = arr[i];
arr = temp;

Notes

Not much to say here; the fragment is a direct translation of the diagram into code
Note the loop goes up to arr.length, i.e., the old array objects length
As we mentioned above, the doubling is crucial to an efficient algorithm

Packaging the Resizing Logic into a Method

The Right Way

The Method

int [] resize(int [] arr) {
	int [] temp = new int[2*arr.length];
	for (int i = 0; i < arr.length; i++)
		temp[i] = arr[i];
	return temp;
}

The Invoking Code

int [] arr = new int[…];
…
// We realize we need a bigger array
arr = resize(arr);

The Wrong Way

The Method

void resize(int [] arr) {
	int [] temp = new int[2*arr.length];
	for (int i = 0; i < arr.length; i++)
		temp[i] = arr[i];
	arr = temp;
}

The Invoking Code

int [] arr = new int[…];
…
// We realize we need a bigger array
resize(arr);

Embedding Memory-Management into a Container Class

The above memory-managed logic is typically not done on 'standalone' arrays, but rather in the context of a container class and its underlying array.

Resizing logic is then embedded in the class — often as a private method — and handled completely by the class itself, i.e., totally invisible to the user.
In this context, the memory-management actually becomes a bit simpler and cleaner.

class Vector {
	Vector() {
		arr = new int[INITIAL_CAPACITY];
	}

	int get(int index) {	
		if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
		return arr[index];
	}

	void set(int index, int value) {	
		if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
		arr[index] = value;
	}

	void add(int value) {
		checkCapacity();
		arr[size++] = value;
	}

	int getCapacity() {return arr.length;}
	int size() {return size;}

	public String toString() {
		String result = "{";
		for (int i = 0; i < size; i++)
			result += arr[i] + (i < size-1 ? ", " : "");
		result += "}";
		return result;
	}

	private void checkCapacity() {
		if (size < getCapacity()) return;
		int [] temp = new int[2*getCapacity()];
		for (int i = 0; i < size; i++)
			temp[i] = arr[i];
		arr = temp;
	}

	int [] arr;
	int size = 0;
	static final int INITIAL_CAPACITY = 10;
}

Notes

We define an INITIAL_CAPACITY to start things off, but the container will resize itself as necessary
Once again, no capacity instance variable is required, we obtain the capacity from arr.length
All methods that increase the size of the container (in our case that would s only add)
Notice the elegance and efficiency of this scheme: checkCapacity compares size to the capacity of the container, and returns immediately if nothing need be done.
Again, checkCapacity is declared private as the memory/capacity management is solely the responsibility of the container.
And, as discussed before, we use the method getCapacity rather than arr.length for both increased readability as well as to 'protect' against any possibly change in the underlying container.

The app:

public class VectorApp {
	public static void main(String [] args) {
		basics();
		exceptions();
		capacityManagement();
	}

	static void basics() {
		System.out.println("=== Basic Functionality ===");
		System.out.println("--- Creating Vector and printing it and its initial stats ---");
		Vector v = new Vector();
		System.out.println(v + " (" + v.size() + "/" + v.getCapacity());
		System.out.println();

		System.out.println("--- Loading it up to capacity; add ---");
		for (int i = 0; i < v.getCapacity(); i++) {
			v.add(i * 10);
			System.out.println(v + " (" + v.size() + "/" + v.getCapacity() + ")");
		}
		System.out.println();

		System.out.println("--- Incrementing each element; get and set ---");
		for (int i = 0; i < v.size(); i++)
			v.set(i, v.get(i)+1);
		System.out.println(v);
		System.out.println();
	}

	static void exceptions() {
		System.out.println("=== Exceptions ===");
		Vector v = new Vector();
		try {
			System.out.println(v.get(0));
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Successfully caught exception on get: " + e);
		}

		try {
			v.set(0, 999);
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Successfully caught exception on set: " + e);
		}
		System.out.println();
	}

	static void capacityManagement() {
		System.out.println("=== Capacity Management ===");
		Vector v = new Vector();

		System.out.println("--- Creating Vector and loading it up with 1,000 elements ---");
		int oldCapacity = -1;
		for (int i = 0; i < 1000; i++) {
			v.add(i);
			if (v.getCapacity() != oldCapacity) 
				if (v.size() <= 10)
					System.out.println(v + " (" + v.size() + "/" + v.getCapacity() + ")");
				else
					System.out.println("{" + v.get(0) + ", " + v.get(1) + "..." + v.get(v.size()-2) + ", " + 
						v.get(v.size()-1) + "} (" + v.size() + "/" + v.getCapacity() + ") ... resized");  
			oldCapacity = v.getCapacity();
		}
		System.out.println("{" + v.get(0) + ", " + v.get(1) + "..." + v.get(v.size()-2) + ", " + 
			v.get(v.size()-1) + "} (" + v.size() + "/" + v.getCapacity() + ")");  
	}
}

Notes

The demo is again broken up into methods, but now for the purpose of separating out the various functional aspects I want to illustrate:
- the basics: adding, setting. getting, printing, accessing size and capacity
- exceptions: bounds checking
  - Notice because the manages the capacity for us, there's no more try/catch block for overflow (IllegalStateException)
- capacity management
I've added some more descriptive output
I'm printing out the vector a bit more, and when it adds to the 'story', I'm also printing out the size and capacity
We illustrate the resizing capability, by first filling up the array with a thousand elements, and printing the capacity whenever it changes
- Hopefully, the initial capacity is less than 1,000 so we can actually witness a resizing
To show the vector's 'growth' without constantly displaying hundreds of elements, I';ve added logic to 'ellipsize' the contents of the array

=== Basic Functionality ===
--- Creating Vector and printing it and its initial stats ---
{} (0/10

--- Loading it up to capacity; add ---
{0} (1/10)
{0, 10} (2/10)
{0, 10, 20} (3/10)
{0, 10, 20, 30} (4/10)
{0, 10, 20, 30, 40} (5/10)
{0, 10, 20, 30, 40, 50} (6/10)
{0, 10, 20, 30, 40, 50, 60} (7/10)
{0, 10, 20, 30, 40, 50, 60, 70} (8/10)
{0, 10, 20, 30, 40, 50, 60, 70, 80} (9/10)
{0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)

--- Incrementing each element; get and set ---
{1, 11, 21, 31, 41, 51, 61, 71, 81, 91}

=== Exceptions ===
Successfully caught exception on get: java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
Successfully caught exception on set: java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0

=== Capacity Management ===
--- Creating Vector and loading it up with 1,000 elements ---
{0} (1/10)
{0, 1...9, 10} (11/20) ... resized
{0, 1...19, 20} (21/40) ... resized
{0, 1...39, 40} (41/80) ... resized
{0, 1...79, 80} (81/160) ... resized
{0, 1...159, 160} (161/320) ... resized
{0, 1...319, 320} (321/640) ... resized
{0, 1...639, 640} (641/1280) ... resized
{0, 1...998, 999} (1000/1280)

Sidebar

Adding Another Constructor

Despite the container now being self-resizing, we often add an additional constructor that allows the user to specify the initial capacity of the container


Vector(int capacity) {arr = new int[capacity];}

This proves useful and efficient if the user has some advance knowledge of the size of the container
By allowing the user to provide an initial capacity, we can avoid the overhead of resizing
```
Vector v = new Vector(1000000);	// avoids a bunch of resizing
		
```

In fact, we will see that some containers in the JFC provide and initial capacity constructor and others don't; and this can actually tell us something about the nature of the container.

Generic Containers

We are headed towards our last improvement — a generic container, i.e., a container that permits arbitrary element types. We will make a couple of detours on the way, to both motivate it as well as introduce several other language features that are both useful and informative.

A `Vector` with `Integer` Element Type

We'll start by replacing the primitive int element type of the Vector with the corresponding Integer wrapper class.

As you may have learned in 3115, we want our containers to have a class element type (in particular Object, so we'll move a step in that direct and use Integer as it is a class, and it is also related to int (i.e., it is its wrapper class).
This has little to do with going towards generics other than the essentially irrelevant replacing of a primitive element type with a class.
The main change will be in the app below.

class Vector {
	Vector() {
		this.capacity = INITIAL_CAPACITY;
		arr = new Integer[capacity];
	}

	Integer get(int index) {	
		if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
		return arr[index];
	}

	void set(int index, Integer value) {	
		if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
		arr[index] = value;
	}

	void add(Integer value) {
		checkCapacity();
		arr[size++] = value;
	}

	int getCapacity() {return capacity;}
	int size() {return size;}

	public String toString() {
		String result = "{";
		for (int i = 0; i < size; i++)
			result += arr[i] + (i < size-1 ? ", " : "");
		result += "}";
		return result;
	}

	private void checkCapacity() {
		if (size < capacity) return;
		capacity *= 2;
		Integer [] temp = new Integer[capacity];
		for (int i = 0; i < size; i++)
			temp[i] = arr[i];
		arr = temp;
	}

	Integer [] arr;
	int capacity, size = 0;
	static final int INITIAL_CAPACITY = 10;
}

Notes

As mentioned above, nothing much new here: a change in the underlying array element type and the accompanying changes to the object creation, and associated parameters/return types.

The app is where we want to focus our attention:

public class VectorApp {
	public static void main(String [] args) {
		Vector v = new Vector();
		System.out.println("capacity: " + v.getCapacity());
		System.out.println("size: " + v.size());

		try {
			System.out.println(v.get(0));
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Successfully caught exception on get: " + e);
		}

		try {
			v.set(0, 999);
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Successfully caught exception on set: " + e);
		}

		for (int i = 1; i <= v.getCapacity(); i++)
			v.add(i * 10);
		System.out.println(v);
		System.out.println("size: " + v.size());

		for (int i = 0; i < v.size(); i++)
			v.set(i, v.get(i)+1);
		System.out.println(v);

		v.add(999);
		System.out.println("capacity: " + v.getCapacity());
		System.out.println("size: " + v.size());
		System.out.println(v);
		System.out.println();
	}
}

Notes

The highlighted items are all int-related literals or expressions,appearing in a context in which an Integer is expected.
Integer is a wrapper class for int it is not an int
- In particular, there is no + or * operator defined for Integer
  - Strictly speaking, we should be:
    - creating Integer objects to wrap any ints when adding to the Vector (whose element type is Integer
      - it would seem that to create an Integer from an int (say the int variable i), there would be an Integer constructor that accepts an int, and then one could write
        Integer integer = new Integer(i);
        however, for various technical reasons, that is not recommended; rather, there is a static method of Integer, valueOf, that accepts an int and returns a new Integer that wraps that int, and thus one would write:
        Integer integer = Integer.valueOf(i);
    - extracting int from any Integer objects when getting any element from the Vector and performing any arithmetic (or other int-based action on them.
      - this direction works as expected: there is a (instance) method of Integer, intValue that returns the (wrapped) value of the receiving Integer object as an int, e.g.:
        int i = Integer.intValue();

In other words, strictly speaking the correct version of the app should be:

public class VectorApp {
        public static void main(String [] args) {
                Vector v = new Vector();
                System.out.println("capacity: " + v.getCapacity());
                System.out.println("size: " + v.size());

                try {
                        System.out.println(v.get(0));
                } catch (IndexOutOfBoundsException e) {
                        System.out.println("Successfully caught exception on get: " + e);
                }

                try {
                        v.set(0, Integer.valueOf(999));
                } catch (IndexOutOfBoundsException e) {
                        System.out.println("Successfully caught exception on set: " + e);
                }

                for (int i = 1; i <= v.getCapacity(); i++)
                    v.add(Integer.valueOf(i * 10));
                System.out.println(v);
                System.out.println("size: " + v.size());

                for (int i = 0; i < v.size(); i++) 
                    v.set(i, Integer.valueOf(v.get(i).intValue()+1));
                System.out.println(v);

                v.add(Integer.valueOf(999));
                System.out.println("capacity: " + v.getCapacity());
                System.out.println("size: " + v.size());
                System.out.println(v);
                System.out.println();
        }
}

Notes

the code that extracts the vector element, adds 1 to it, and puts it back, i.e., v.set(i, new Integer(v.get(i).intValue()+1)) is a mouthful. Here is its equivalent, broken down for greater clarity and readability:
```
Integer integer = v.get(i);
int j = integer.intValue();
v.set(i, Integer.valueOf(j+1)); 
		
```

This is clearly quite cumbersome

and we will shortly see it gets even more complex when combined with the true element type of containers

Autoboxing

Autoboxing Tutorial

Java 5 introduced a new language feature; one that had been long awaited and addressed the above issue: autoboxing. The basic idea was to make the boundary between a primitive type and its wrapper class as transparent as possible. so that one could (almost) used int and Integer interchangeably.

To do that the compiler was enlisted to do much of the above cumbersome wrapping and unwrapping logic. The wrapping was called boxing, and the unrpapping unboxing.

any time a primitive type appears in a context requiring an object, the type is wrapped (by the compiler) into its wrapper class object


Vector v = new Vector();
v.add(3);		// compiler automatically inserts an Integer.valueOf
               //  so this internally becomes v.add(Integer.valueOf(3));

any time an object appears in a context requiring a primitive type, the object is unwrapped (by the compiler) to its corresponding primitive type


Vector v = new Vector();
…
int i = v.get(0);		// compiler automatically insert a '.intValue' 
                         //  so this becomes int i = v.get(0).intValue();

As one more example, here is our increment logic for the elemtns of the Vector in our app:


v.set(i, v.get(i)+1);

The first thing that happens in this expression is the i'th element of the v is retrieved, v.get(i)
- The retrieved object is an Integer since the Vector element type is Integer
- For the sake of this example, let's assume the object was wrapping the int value 5
The retrieved element then has 1 (v.get(i)+1) added to it
- This is an arithmetic expression requiring a primitive, however, the left operand is the Integer object we just retrieved, therefore the compiler unboxes the object, extracting the int value (5).
- 5 is added to 1 resulting in the int value 6.
The result of the addition is the 'value' operand of the set method, which is putting the new update value back into the same location of v. That value is supposed to be an Integer (i.e., object) but is the int (6) from the previous step
- The compiler therefore boxes the int into an Integer object (sing valieOf and that object then becomes the value that is stored into v by the set.

In summary, all the machinery of wrapping and unwrapping the primitive is still there, except it's supplied behind the scenes by the compiler and thus hidden from the programmer.
As a result our app did not have to be modified when we changed the element type from int to Integer

An `Vector` With `Object` Element Type

We now move to the general case of having Object as the element type

Object is chosen because all classes are descendants of Object, and an object of any class can be a Vector element.

class Vector {
	Vector() {
		this.capacity = INITIAL_CAPACITY;
		arr = new Object[capacity];
	}

	Object get(int index) {	
		if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
		return arr[index];
	}

	void set(int index, Object value) {	
		if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
		arr[index] = value;
	}

	void add(Object value) {
		checkCapacity();
		arr[size] = value;
		size++;
	}

	int getCapacity() {return capacity;}
	int size() {return size;}

	public String toString() {
		String result = "{";
		for (int i = 0; i < size; i++)
			result += arr[i] + (i < size-1 ? ", " : "");
		result += "}";
		return result;
	}

	private void checkCapacity() {
		if (size < capacity) return;
		capacity *= 2;
		Object [] temp = new Object[capacity];
		for (int i = 0; i < size; i++)
			temp[i] = arr[i];
		arr = temp;
	}

	Object [] arr;
	int capacity, size = 0;
	static final int INITIAL_CAPACITY = 10;
}

Notes

Same basic comments as before, no real change other than to the array element type, and the various parameter/return values corresponding to elements

The app is again where we will focus our attention:

public class VectorApp {
	public static void main(String [] args) {
		Vector v = new Vector();
		System.out.println("capacity: " + v.getCapacity());
		System.out.println("size: " + v.size());

		try {
			System.out.println(v.get(0));
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Successfully caught exception on get: " + e);
		}

		try {
			v.set(0, 999);
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Successfully caught exception on set: " + e);
		}

		for (int i = 1; i <= v.getCapacity(); i++)
			v.add(i * 10);
		System.out.println(v);
		System.out.println("size: " + v.size());

		for (int i = 0; i < v.size(); i++)
			v.set(i, ((Integer)v.get(i))+1);
		System.out.println(v);

		v.add(999);
		System.out.println("capacity: " + v.getCapacity());
		System.out.println("size: " + v.size());
		System.out.println(v);
		System.out.println();
	}
}

Notes

In the code v.get(i), now that the element type is Object all we can say when we extract an element is that it is an Object
- In particular, we do not know that it is an Integer (other than the fact that we know we have only added Integers to the Vector; this last fact will prove crucial in a bit)
- The compiler also does not know that the retrieved element is an Integer and thus cannot do any unboxing
  - The declared (i.e., compile-time) element type of the array is Object; it is only at runtime that the actual element is created (as an Integer)
    - That creation is done in the statement
```
v.add(i * 10);
								
```
      - once again, autoboxing plays a major role here. The add methods is expecting an object of type Object but is presented with an int (i * 10) and thus boxes the result of the expression the corresponding wrapper class (Integer) and it is this object that is added to the vector (i.e., the underlying array).
      - There is no problem inserting an Integer into an arrays of Object element type, as Integer is a subclass (indirectly possibly) of Object, i.e., it is a descendant of Object and thus is-a object of the suoerclass as well (i.e., an Integer object is-a Object object as well by virtue of the inheritance.

Upcasting and Downcasting

As explained above, the set (and the add) are not problematic; Integer objects are Object objects as well, can appear wherever an Object can, and thus can be made an element of an array with an Object element type.
- Assigning an object from lower down in the inheritance hierarchy (e.g. Integer) to a variable higher up in the hioerarcht (e.g. Object is called upcasting and is always legal and requires no special syntax..
  Thus inserting any type of object into a container with Object as element type is never a problem.
  - Which is why the containers of the JCF are have Object as their element type
The problem (as discussed in the first bullet) is retrieving an element from the container.
- In that situation, one wishes to 'restore' the particular identity (type, e.g. Integer) to the element so it can be used when assigning the reference to an object from a variable higher up in the hierarchy to a variable lower down.
  - While still viewed as an Object there are very few methods one can apply; in particular for our case, we cannot invoke the intValue method to extract the wrapped int
- What we are in essence doing is assigning a reference to an object (the element of the vector) from a variable higher up in the hierarchy (Objectto a variable lower down the hierarchy (Integer).
- This is known as downcasting and will only work is the object being referred to is 'compatible' with the lower variable
  - For our discussion, think of compatible as being an object of the class of the lower variable
  - and in general, one does know if something is compatible or not until runtime

Examples of Upcasting and Downcasting

Here is a hierarchy of shapes, a superclass, Shape and two subclasses, Circle and Square:

abstract class Shape {…}

class Circle extends Shape {…}

class Square extends Shape {…}

Now let's start working with some variables and objects of these classes.

1. Circle circle = new Circle();
2. Square square = new Square();

3. Shape shape1 = circle;		// ok, upcast — All Circles are Shapes by virtue of inheritance
4. Shape shape2 = square;		// ok, upcast — All Squares are Shapes

Notes

First off, we need to distinguish between types of the variables and objects
- circle: a reference to a Circle
- square: a reference to a Square
- shape1 / shape2: reference to a Shape
- the object of type Circle created in line 1
- the object of type Square created in line 2
Note the type of the reference variables are known statically (i.e., at code creation time, and thus at compile-time), while the objects are not created until runtime (as a result of executing the new operator).
- Since every reference variable typically contains a reference to an object, we speak of the static (or compile-time) type of the variable (i.e., it's declared type), vs the dynamic (runtime) type of the object it references.
- As such, after the above four line of code we have:
  - A variable of type reference to Circle (circle) containing a reference to a Circle object
  - A variable of type reference to Square (square) containing a reference to a Square object
  - A variable of type reference to Shape (shape1) containing a reference to a Circle object
  - A variable of type reference to Shape (shape2) containing a reference to a Square object
- The last two are a result of assigning the references from circle / square to shape1 / shape2 respectively
  - These two assignments are called upcasts as they are assigning a reference from a variables lower down the hierarchy up (a subclass) to a variable higher in the hierarchy (a superclass)
  - And upcasts are both legal and always successful, since the subclass is-a instance of its superclass as well
    - i.e., All Circles are Shapes and All Squares are Shapes

Now consider these sequences:

Circle circle = new Circle();	
Square square = circle;		// illegal --  no Circles are Squares

and

Square square = new Square();	
Circle circle = square;		// illegal --  no Squares are Circles

Notes

Both of the above assignments are illegal: the two classes are not related in the hierarchy in any meaningful way; i.e., neither is a subclass of the other.
It thus makes no sense to assign an object reference from one to the other (any more than it makes sense at the semantics level, i.e., turning a circle into a square or vice versa.
Again, no Circles are Squares and no Squares are Circles
Being illegal (and therefore of no use), these 'sidecasts' are not given any technical name

The above seems fairly straightforward. Now consider the following:

Shape shape = new Circle();						// this is a legal upcast … All Circles are Shapes
…
Circle circle = shape1;		// seems ok --  assigning a Circle object to a Circle variable
Square square = shape1;		// seems wrong --  assigning a Circle object to a Square variable

and

Shape shape = new Square();						// this is a legal upcast … All Circles are Shapes
…
Circle circle = shape;		// seems wrong --  assigning a Square object to a Circle variable
Square square = shape1;		// seems ok --  assigning a Square object to a Square variable

Notes

In each case, the assignment from shape is to a variable of a subclass (circle or square). Such an assignment is called a downcast (casting down the hierarchy)
The two fragments of code are identical other than the object created and assigned to shape
The … between the object creation and subsequent assignments is meant to signify that there may be a significant amount of code executed between the creation of the object and its assignment to circle and square
How is the compiler supposed to be able to distinguish between the legal and illegal assignments from shape to circle and square?
- In fact there is no way for the compiler to make that distinction, given that the object is not even created until runtime!

To emphasize that last point about the compiler not being able to distinguish a valid from invalid downcast and thus the check must be done at runtime, consider the following code:

Random r = new Random();
boolean b = r.nextBoolean();
Shape shape;
if (b)
	shape = new Circle();		// upcast
else
	shape = new Square();		// upcast
Circle circle = shape;	// ok? or not? downcast

Notes

Which object is initially assigned to shape depends on the value of the random variable which is not generated until runtime.
As a result, whether circle is assigned a reference to a Circle object (legal) or a reference to a Square object (illegal) cannot be determined until runtime
Through careful coding, you can often ensure that your downcasts will always work. But the compiler wants you to signal the fact that you know something potentially dangerous is happening, and therefore you must cast the downcast:
```
Shape shape = new Circle();
Circle circle = (Circle)shape;		// will pass compilation and succeed at runtime
Square square = (Square)shape;;		// will pass compilation but fail at runtime with a ClassCastException
```

Returning to our Random example

for final emphasis; the following code will sometimes work and sometimes fail with a ClassCastException:

Random r = new Random();
boolean b = r.nextBoolean();
Shape shape;
if (b)
	Shape = new Circle();
else
	Shape = new Square();
Circle circle = (Circle)shape;	// will sometimes succeed and sometimes fail at runtime

In summary, downcasts need to be checked at runtime, and if they fail, they throw a ClassCastException

The Need for Generic Containers

Having Object as the element type allows us to have any type of object in a container (because of upcasting). However, there is a price:

all retrievals requires a downcast to 'restore' the actual type of the element
- Note that we are not changing the type when we downcast; the object is and always was an Integer / Circle, Square (in our examples).
  - What is changing is the reference variable we are using to work with the object. The compiler only allows us to use the methods of the declared type of the reference variable.
    - In our case, the declared type of the elements of the underlying array are Object and thus while in the array, we can only use the methods of Object.
    - When we retrieve the element and downcast it by assigning it to an Integer variable, we can then call the methods of Integer using that variable. Similarly, when we downcast from a Shape to a Circle, we can then call the methods of Circle
We can add objects of different types to the same array (and thus container).
- While being able to do so sounds like a good thing, good programming almost always calls for arrays / containers to be homogeneous.
- Were we to mistakenly add a String object to a container meant for Integer, when we eventually retrieve the String and downcast it to use it as an Integer we will get a ClassCastException
```
Vector v = new Vector();
for (int i = 0; i < 10; i++)
	v.add(i);				// all good, autboxing and upcasting to the rescue
…
v.add("dog");				// oops .. but no error, upcast again String to Object
…
// Now go to go through the vector and add 1 to each element
for (int i = 0; i < v.size(); i++)
	v.set(i, ((Integer)v.get(i))+1);		// downcasting as required
				
```
  Notes
  - With the above code, the last item retrieved (the String) will fail the downcast and throw a ClassCastException

Vector Version 5 — A Generic Vector

We now introduce our final improvement on our container: the ability to specify and enforce a specific element type.

This is done through the introduction of a type parameter to the definition of the class (or other constructs as we shall eventually see).
The type parameter specifies the allowed element type for the container
A class with a type parameter is called a generic class

class Vector<E> {
	@SuppressWarnings("unchecked")
	Vector() {
		this.capacity = INITIAL_CAPACITY;
		arr = (E [])new Object[capacity];
	}

	E get(int index) {	
		if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
		return arr[index];
	}

	void set(int index, E value) {	
		if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
		arr[index] = value;
	}

	void add(E value) {
		checkCapacity();
		arr[size] = value;
		size++;
	}

	int getCapacity() {return capacity;}
	int size() {return size;}

	public String toString() {
		String result = "{";
		for (int i = 0; i < size; i++)
			result += arr[i] + (i < size-1 ? ", " : "");
		result += "}";
		return result;
	}

	private void checkCapacity() {
		if (size < capacity) return;
		capacity *= 2;
		@SuppressWarnings("unchecked")
		E [] temp = (E [])new Object[capacity];
		for (int i = 0; i < size; i++)
			temp[i] = arr[i];
		arr = temp;
	}

	E [] arr;
	int capacity, size = 0;
	static final int INITIAL_CAPACITY = 10;
}

Notes

The type parameter for a generic class is introduced in the class header following the class name
The usual conventions is to use a single upper-case letter, usually T (for type), or E (for element)m and occasionally a numeric suffix (e.g., T1) if there are more than one type (see the Pair example below).
The type parameter is then used throughout the class definition in the context that the element type would appear.
For technical reasons,Java does not permit the creation of a 'generic array', i.e., an array whose element type is a type parameter. However, this is a necessity as we need an array as our underlying container
- The workaround is to create an array of type Object, i.e., Object [] and then cast it to the generic array, i.e., E []
- This in turn causes the compiler to issue a warning, which in turn can be muted with the annotation
```
@SuppressWarnings("unchecked")
				
```
  - The annotation can be placed immediately before a declaration (as in checkCapacity, or in front of the surrounding method (as in the constructor).

And here is the app:

public class VectorApp {
	public static void main(String [] args) {
		basics();
		exceptions();
		capacityManagement();
		generics();
	}

	static void basics() {
		System.out.println("=== Basic Functionality ===");
		System.out.println("--- Creating Vector and printing it and its initial stats ---");
		Vector<Integer> v = new Vector<>();
		System.out.println(v + " (" + v.size() + "/" + v.getCapacity() + ")");
		System.out.println();

		System.out.println("--- Loading it up to capacity; add ---");
		for (int i = 0; i < v.getCapacity(); i++) {
			v.add(i * 10);
			System.out.println(v + " (" + v.size() + "/" + v.getCapacity() + ")");
		}
		System.out.println();

		System.out.println("--- Incrementing each element; get and set ---");
		for (int i = 0; i < v.size(); i++)
			v.set(i, v.get(i)+1);
		System.out.println(v);
		System.out.println();
	}

	static void exceptions() {
		System.out.println("=== Exceptions ===");
		Vector<String> v = new Vector<>();
		try {
			System.out.println(v.get(0));
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Successfully caught exception on get: " + e);
		}

		try {
			v.set(0, "");
		} catch (IndexOutOfBoundsException e) {
			System.out.println("Successfully caught exception on set: " + e);
		}
		System.out.println();
	}

	static void capacityManagement() {
		System.out.println("=== Capacity Management ===");
		Vector<Double> v = new Vector<>();

		System.out.println("--- Creating Vector and loading it up with 1,000 elements ---");
		int oldCapacity = -1;
		for (int i = 0; i < 1000; i++) {
			v.add((double)i);
			if (v.getCapacity() != oldCapacity) 
				if (v.size() <= 10)
					System.out.println(v + " (" + v.size() + "/" + v.getCapacity() + ")");
				else
					System.out.println("{" + v.get(0) + ", " + v.get(1) + "..." + v.get(v.size()-2) + ", " + 
						v.get(v.size()-1) + "} (" + v.size() + "/" + v.getCapacity() + ") ... resized");  
			oldCapacity = v.getCapacity();
		}
		System.out.println("{" + v.get(0) + ", " + v.get(1) + "..." + v.get(v.size()-2) + ", " + 
			v.get(v.size()-1) + "} (" + v.size() + "/" + v.getCapacity() + ")");  
	}

	static void generics() {
		System.out.println("--- Generics");
		System.out.println();

		System.out.println("--- A Vector of doubles");
		Vector<Double> vDouble = new Vector<>();
		for (int i = 0; i < 10; i++)
			vDouble.add((double)i);
		System.out.println(vDouble);
		System.out.println();

		System.out.println("--- A Vector of Strings");
		Vector<String> vString = new Vector<>();
		for (int i = 0; i < 7; i++)
			vString.add("Str" + i);
		System.out.println(vString);
		for (int i = 1; i < vString.size(); i++)
			System.out.println(vString.get(i).substring(1));
		System.out.println();

		System.out.println("--- A Vector of Vector<Integer>");
		Vector<Vector<Integer>> vvInteger = new Vector<>();
		for (int i = 0; i < 5; i++) {
			Vector<Integer> vInteger = new Vector<>();
			for (int j = 0; j < i; j++)
				vInteger.add(j);
			vvInteger.add(vInteger);
		}
		System.out.println(vvInteger);
	}
}

Notes

the diamond operator (<>) tells the compiler to perform type inference on the assignment of declaration, i.e., to look at the specified type argument on the left and use it to determine the proper value of the omitted type on the right.
The vectors in the exceptions AMD capacityManagement methods were modified to illustrate the generic facility, which is then expanded on in the newly introduced generics method.
- Neither of those methods really used anything 'integer', so it was trivial to change the Integer to String and Double
- The only exception was the use of the index variable in capacityManagement to load up the vector with the thousand elements. We could have simply assigned 0.0 to each element (we're not doing anything with them), but instead chose to simply cast the index variable to double
  - As a challenge, once it's a double autoboxing kicked in. But in Java, conversion of an int to double is legal, and implicit, so why couldn't we simply add the int value to the vector and let autoboxing do its magic there as well?

vectors within vectors: nested containers

=== Basic Functionality ===
--- Creating Vector and printing it and its initial stats ---
{} (0/10)

--- Loading it up to capacity; add ---
{0} (1/10)
{0, 10} (2/10)
{0, 10, 20} (3/10)
{0, 10, 20, 30} (4/10)
{0, 10, 20, 30, 40} (5/10)
{0, 10, 20, 30, 40, 50} (6/10)
{0, 10, 20, 30, 40, 50, 60} (7/10)
{0, 10, 20, 30, 40, 50, 60, 70} (8/10)
{0, 10, 20, 30, 40, 50, 60, 70, 80} (9/10)
{0, 10, 20, 30, 40, 50, 60, 70, 80, 90} (10/10)

--- Incrementing each element; get and set ---
{1, 11, 21, 31, 41, 51, 61, 71, 81, 91}

=== Exceptions ===
Successfully caught exception on get: java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0
Successfully caught exception on set: java.lang.IndexOutOfBoundsException: Index 0 out of bounds for length 0

=== Capacity Management ===
--- Creating Vector and loading it up with 1,000 elements ---
{0.0} (1/10)
{0.0, 1.0 ... 9.0, 10.0} (11/20) ... resized
{0.0, 1.0 ... 19.0, 20.0} (21/40) ... resized
{0.0, 1.0 ... 39.0, 40.0} (41/80) ... resized
{0.0, 1.0 ... 79.0, 80.0} (81/160) ... resized
{0.0, 1.0 ... 159.0, 160.0} (161/320) ... resized
{0.0, 1.0 ... 319.0, 320.0} (321/640) ... resized
{0.0, 1.0 ... 639.0, 640.0} (641/1280) ... resized
{0.0, 1.0 ... 998.0, 999.0} (1000/1280)
--- Generics

--- A Vector of doubles
{0.0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0}

--- A Vector of Strings
{Str0, Str1, Str2, Str3, Str4, Str5, Str6}
tr1
tr2
tr3
tr4
tr5
tr6

--- A Vector of Vector
{{}, {0}, {0, 1}, {0, 1, 2}, {0, 1, 2, 3}}

Underlying Concepts

compile-time nature of generics
type erasure
raw type
- Supplying a type to the type parameter of a generic class creates a
  parameterized type
```
HashSet<Integer> hs = new HashSet<>();
				
```
- Declaring a reference variable of a generic class without supplying a type creates a raw type of the generic class
```
	HashSet hs = new HashSet();
				
```
  - Raw types were introduced to allow for (pre-generic) legacy code to be compatible
  - However, working with raw types in current code is frowned upon, and often will generate warnings from the compiler

Some More Examples — Two Pair Classes

Homogeneous Pairs

class HomogeneousPair<T> {
	HomogeneousPair(T first, T second) {
		this.first = first;
		this.second = second;
	}

	void swap() {
		T t = first;
		first = second;
		second = t;
	}

	public String toString() {return "(" + first + ", " + second + ")";}

	T first, second;
}

Heterogeneous Pairs

class HeterogeneousPair<T1, T2> {
	HeterogeneousPair(T1 first, T2 second) {
		this.first = first;
		this.second = second;
	}

	public String toString() {return "(" + first + ", " + second + ")";}

	T1 first;
	T2 second;
}

Notes

swap method?

Using the Pair Classes

class PairsDemo {
	public static void main(String [] args) {
		HomogeneousPair<Integer> homPair1 = new HomogeneousPair<>(1, 2);
		System.out.println(homPair1);
		homPair1.swap();
		System.out.println(homPair1);
		System.out.println();

		HomogeneousPair<String> homPair2 = new HomogeneousPair<>("dog", "cat");
		System.out.println(homPair2);
		homPair2.swap();
		System.out.println(homPair2);
		System.out.println();

		HeterogeneousPair<Integer, String> hetPair2 = new HeterogeneousPair<>(1, "cat");
		System.out.println(hetPair2);
	}
}

(1, 2)
(2, 1)

(dog, cat)
(cat, dog)

(1, cat)

CISC 3130 Data Structures Container-Relevant Language Features & Techniques

Topics

Our Current Vector Class

Exception Handling

Bounds Checking

Container Overflow

Vector Version 3: Exception Handling

User-Defined Exception Classes

RunTimeException — Checked vs Unchecked Exceptions

Vector Version 3.1: Exception Handling Using a User-Defined Exception Class

Vector Version 3.2: A Nested/Inner Class for the Exception Class

Vector Version 4: A Resizeable Underlying Container

Memory Management

Packaging the Resizing Logic into a Method

The Right Way

The Method

The Invoking Code

The Wrong Way

The Method

The Invoking Code

Embedding Memory-Management into a Container Class

Adding Another Constructor

Generic Containers

A Vector with Integer Element Type

Autoboxing

An Vector With Object Element Type

Upcasting and Downcasting

Examples of Upcasting and Downcasting

The Need for Generic Containers

Vector Version 5 — A Generic Vector

Underlying Concepts

Some More Examples — Two Pair Classes

Homogeneous Pairs

Heterogeneous Pairs

Using the Pair Classes

CISC 3130
Data Structures
Container-Relevant Language Features & Techniques

Our Current `Vector` Class

`RunTimeException` — Checked vs Unchecked Exceptions

A `Vector` with `Integer` Element Type

An `Vector` With `Object` Element Type