Lab: 13 - Generics

Assigned

Friday, 22 September 2023

(1/2 point) Start this lab session by sharing something (most interesting or helpful and Java methods) you learned from the readings or on your own (about Java) this week.
Add the answers to your lab report. At least three ideas per student. 

OVERVIEW

In many Java applications that store large amounts of information about large numbers of persons, organizations, commodities, or other entities, it is useful to associate the data structure that contains all of the information about one such entity with a much smaller object called a key or an identifier. Each key uniquely identifies the data structure that is associated with it (which is typically called the value of the key). A key can be used as a shorthand way to refer to the value associated with it, as a search key for recovering the value from a large database, or as a sorting key for putting a collection of such values into some useful order without having actually to copy or rearrange the values themselves. (Typically it is much faster to sort the keys than to sort the values associated with them.)

In today’s lab, we’ll define a generic type for key-value pairs, which are objects that record the associations of values with keys.

Note: In this lab, getting the types correct can be a bit of a challenge. Use the Eclipse IDE to help with casting objects, but read the messages and understand what it is doing for you.

Part 1: Key-Value Pairs

1. Open Eclipse, create a new project called generics and in that project create a new package called kvpairs for the classes we develop in this lab.

2. Let’s use the name KeyValuePair for the generic class that we want to define. Because we want the implementation of this class to be the same no matter what classes the keys and the values actually belong to, we’ll use two type parameters in its declaration. Recall that the list of type parameters begins with a less-than sign and ends with a greater-than sign and that adjacent type parameters are separated by commas.

In Eclipse, use the “New Class” wizard to create the KeyValuePair. The wizard will open an editor containing the boilerplate for the class definition. Add a list of type parameters to the signature of the class.

1. Each KeyValuePair should store its key and its value in private fields. Add declarations for these fields.

2. Define a constructor for KeyValuePair that takes the key and the value as arguments and puts them in the appropriate fields of the newly created KeyValuePair.

3. Provide an accessor method for each of the fields. We’ll assume that KeyValuePair objects, once created, are immutable, and so we won’t provide mutators.

4. (1 point) Since, by default, the KeyValuePair is derived from java.lang.Object, it inherits the methods that that class supports, including equals and hashCode. Note: we will learn more about hash codes later in the term. For now, look up what the method returns and make use of that information while enjoying the benefits of information-hiding. For equals and hashCode, define new methods with the same names inside the class definition and prefix the definition of each method with the annotation @Override, signalling to the compiler that the replacement is intentional. Define hashCode as a function of the hash codes of key-value pairs (e.g., key hash code + value hash code ). Note that the equals method accepts an Object as its parameter.

5. Override the toString method.

Test your new methods to make sure that they give the results you expected. Note that equals and hashCode are connected by an invariant: If alpha.equals(beta) is true, then the same int value must be returned by alpha.hashCode() and beta.hashCode().

To test the methods, create objects of keyValuePair where keys are strings and values are some numeric type e.g., Integer or Double. Then, print out their keys and values. Test whether any two objects are equal. Confirm that if two equal objects provide the same hash code. Experiment with keyValuePairs of different types. Try a student ID (Integer) and student name (a String) and then a student ID (Integer) and their GPA (Double). What advantages do you see in using generics?

Part 2: Lists of Key-Value Pairs

Lists promise to maintain elements in a particular sequence. There are two types of List:

1. ArrayList allows randomly accessing elements.
2. LinkedList provides sequential access.

The java.util package provides generic classes called ArrayList and LinkedList in which one can store any number of objects and access them, as in Scheme. But Java’s ArrayList and LinkedList elements are actually Objects, and they have internal states in a way that Scheme lists don’t.

For instance, there’s no cons function. To create a list ls with one element (the number 42, for instance) in Java, one would execute the statements

//Code to create an ArrayList and add an element in the list
List<Integer> arrayList = new ArrayList<Integer>();
arrayList.add(42);

//Code to create a LinkedList and add an element to the end of the list
List<Integer> linkedList = new LinkedList<Integer>();
linkedList.add(42); 

Unlike cons in Scheme, add changes the state of the list; in the example, the constructor gives you an empty list, and then the call to add changes arrayList or linkedList from an empty list into a list containing one element.

The intent of using the Interface is that if you decide you want to change your implementation, all you need to do is change it at the point of creation. So, you will typically make an object of a concrete class, upcast it to the corresponding interface, and then use the interface throughout the rest of your code. Note: This approach will not work if you want to use specific functionality (methods) listed in the concrete class but not in the Interface.

Note that, in this example, the compiler autoboxes the int 42, wrapping it in an Integer object so that it matches the type specified for values in the list.

Now for the exercise: In your client program for the KeyValuePair class, create two lists, an ArrayList and a Linkedlist, of at least five key-value pairs. For the first list, the keys are Strings and the associated values are the lengths of those Strings; and choose a different specification for the second list. The key-value pairs don’t have to be arranged in any particular order.

One of the methods provided in List is the iterator. This method returns an object of some class that implements the Iterator interface and can be used for traversing the list. The Iterator interface specifies that instances of a class that implements the interface must provide two important methods: next, which takes no arguments and returns a new element from the underlying list each time it is invoked, and hasNext, which takes no arguments and determines whether there are any elements of the underlying list that have not yet been returned by next.

Thus one common pattern for traversing a List<Integer> object called ls and processing each of its elements in some way looks like this:

    Iterator<Integer> traverser = ls.iterator();
    while (traverser.hasNext()) { 
         Integer element = traverser.next(); 
         // process element in some way
     } 

(2 1/2 points)The exercise, then, is to

• write a method in your client program that takes a List and prints the values of the list using an Iterator.
• write a method in your client program that takes a List and prints the values of the list using the enhance for loop.
• write a method that takes a List and a key and performs a linear search of the list. If any of the keys in the key-value pairs, stored in the list, is equal to the key supplied return the value associated with that key. If none of the keys match, return null.
• Test your linear method (failure or success cases as appropriate).

Lab Submission

You will submit your files via Gradescope by the end of the week. Please submit the source files, lab report, and driver App (do not submit your .class files).

I strongly recommend that each student keep a copy of the lab. Therefore, don’t forget to share the files/folder with your lab partner!

Remember: Write your code anticipating errors and print user-friendly error messages, all your public methods should be well documented (use Javadoc comments). Please include comments or organize your code and report in a way that will help the grader to find the answer to the exercises or posted questions.