Chapter 15

Collections

Pre-built Classes for Storing Data!

Subsections of Collections

Don't Reinvent the Wheel

Early Wheel Early Wheel1

Even though programming is a relatively new profession, the explosion of programmers and code in recent years has given us a unique opportunity to learn from others. Code sharing websites such as GitHub and StackOverflow contain great examples of how to do both simple and complex tasks in code, usually complete the detailed explanations of how each program functions.

So, as developers today, it is often important to remember the mantra “don’t reinvent the wheel” when writing our programs. While it may be tempting to build everything ourselves, many times the language comes with packages or modules with exactly what we need.

In other cases we may find third party packages/modules online. If we are careful about where we find that code, we can even find a version that is better written than we could do ourselves!

Licensing & Plagiarism

When using code found online, there are several important things to keep in mind

Licensing

Most, but not all, code available online includes a license that describes how the code or software may be used. As a developer, it is your responsibility to read, understand, and abide by the terms of the license you find. For example, some licenses may allow you to use the code in any way you want, even in a paid application, while other licenses require you to make your code open source if you choose to use their code.

By way of example, the CC-curricula often uses a testing extension called Hamcrest. These packages are covered by the BSD-3-Clause open source license.

Plagiarism

Additionally, even when using code that is licensed, there is still the matter of plagiarism. It is always a good idea to cite any sources of code that you didn’t write yourself, no matter how small. In this course, and in most classes in academia, you should always check with your instructor or read the syllabus before using code you didn’t write.


  1. File:Roue primitive.png. (2019, January 8). Wikimedia Commons, the free media repository. Retrieved 17:50, November 26, 2019 from https://commons.wikimedia.org/w/index.php?title=File:Roue_primitive.png&oldid=333994349↩︎

Language Libraries

YouTube Video

Video Materials

In this module, we won’t be going quite as far as looking online for code that performs a particular task. Instead, we’re going to explore some of the more important features available as part of our chosen programming language. In many instances, the developers of the programming language have taken the time to include some of the most important and commonly used pieces of code directly as part of the language itself.

Library

Most programming languages include a wide range of features as part of a library of code that can be used in any applications. In this way, applications built with these programming languages can share many of the same features, making it easy for a developer to move between applications easily.

To think about this another way, consider a modern automobile. Most of them include the same parts - an engine, transmission, battery, alternator, starter, and more. If each car was built in a different way using different types of parts, it would be very difficult for any mechanic to be able to fix more than just a few cars. By using standard parts, even if they are a little different in each model, it becomes much easier to repair and maintain those vehicles.

Subsections of Language Libraries

Common Features

Each programming language chooses many different features to include in the library for that language. Thankfully, there are a few common features that most languages seem to include:

  • Strings: we’ve already learned about how to use and manipulate strings in our programs. Most of those methods and classes for dealing with strings come directly from the language’s library
  • File I/0: similarly, opening, reading, and writing to files is also included in the library for most languages
  • Lists: a more flexible and general form of an array, a list is a data structure that can expand to hold many items. In addition, most implementations of a list include several helpful methods for sorting, searching, and manipulating the list in many different ways.
  • Maps: in programming, a map, sometimes called a dictionary, is a data structure that associates a key with a value. For example, an object representing a student could be stored in a map, using the student’s unique student ID as the key. This allows us to quickly search for and find a value based on its associated key.
  • Tuples: a tuple is a special data type that associates multiple values into a single variable. It is very similar to a class that only contains attributes, getters. Some languages, such as Python, include this directly as a feature of the language, while other languages, such as Java, require a bit of work to use tuples directly. Tuples are typically implemented as immutable data types, values are set at instantiation and may not change.
  • Network I/O: most programming languages also include features to communicate via a network or the Internet.

Of course, this is just a short list of the items that might be included in each programming language’s library. In this module, we’ll explore several of these in the language we are learning.

Chapter 4.J

Java Collections

Collections in Java

Subsections of Java Collections

Documentation

Java includes an extensive library of classes that can be included in any Java program. These classes are included as part of the Java Development Kit, or JDK, which includes the Java compiler that we use to build our programs.

Thankfully, the developers of the Java programming language have also written an extensive online manual that explains all of the features of the Java library in detail. Many developers refer to this manual as the Java API, or sometimes simply the documentation for the Java programming language.

To explore the Java API, we can start on this webpage. That link goes directly to the Java API for Java version 8, but it is very easy to find the manual for other versions of Java as well. There is a more technical version of the documentation found here if we’d like to dive even deeper.

On the home page of the Java API, we’ll see several items. To the left is a list of all the classes included in the Java library, so we can quickly explore and find the exact class we are looking for. If we’d like to browse, the panel to the right lists an overview of all of the packages included in the Java library. A package is a set of classes that are all related somehow, giving us a nice layer of organization to our code.

Here are some Java packages that we may want to explore as we continue to develop more advanced programs using Java:

  • java.io—classes for handling input and output and working with the file system.
  • java.lang—classes that are integral to the Java programming language, such as the core data types and exceptions
  • java.math—classes for dealing with arbitrarily large or precise numbers
  • java.net—classes for building networked applications
  • java.nio.file—classes for interfacing with the file system
  • java.time—classes for dealing with dates and times
  • java.util—collection classes and some miscellaneous utilities

In this module, we’ll mostly explore a few of the collection classes in the java.util package.

Collections

The Java API contains several different classes specifically designed to store data. All together, we usually refer to these classes as the collections framework since they are used to store a “collection” of data.

The Java collections framework contains implementations for several different data structures, which are classes used to store and manipulate data in specific ways. We’ll learn more about how each of these implementations works and differs in a later course, but in this course, we’ll quickly describe a few of the most common ones. Specifically, we’ll discuss these two data structures:

  • Lists
  • Maps

We’ll also learn how to build our own Tuple objects in Java, since Java doesn’t include tuples in the language or the Java API library directly, but they are very useful objects to have in our programs.

Generics

As we’ve already learned, the Java programming language requires us to declare the type of each variable we are using before we can even compile the code. However, this can make it very difficult to enforce type-safety when working with collections, since each collection could only guarantee that an item was a subclass of Object, the base class for all classes in Java.

Java 5 added support for generics, a method of programming that allows us to be a bit more flexible in the way we handle types. In short, when developing a collection, we can specify that each item in the collection must be an object compatible with a given, but unknown type. Then, when we use that collection in our code, we can specify the specific type we intend to store in the collection, and the Java compiler will be able to automatically enforce those type rules as if we originally wrote the collection class to only store items of that type.

For example, Java uses a class List<E> to represent a list that stores elements of some class E. We don’t know what that class is at first, but we can still write our List class as if it is a specific type.

Then, when we instantiate a List object in our code, we can provide a type of item we’d like to store, such as String. So, we’d now have a class List<String> which represents a list of strings. This allows the Java compiler to make sure that we are only storing strings in the list. In addition, it allows us to automatically treat each item retrieved from the list as a string, without any additional conversion required.

We’ll see how to do this in code on the next page.

To learn more about how Java handles Generics, check out Lesson: Generics in the Java Tutorials from Oracle.

Primitives vs. Objects

One last thing that we must discuss related to Java and collections is the difference between primitive data types and objects. As we’ve already learned in this course, Java contains several primitive data types, such as int, double, boolean, and more. However, if we wish to store items of these primitive types in our collections, we’ll quickly run into a problem. This is because the primitive data types aren’t actually objects, and because of that, they don’t follow the rules needed to allows generics to work.

Thankfully, Java has a quick and easy workaround. Java includes classes Integer, Double, and Boolean to represent objects that store a single value of the corresponding primitive data type. In addition, Java will automatically convert data between the two in some situations, using a process called autoboxing and unboxing. You can find more on the Autoboxing and Unboxing Java Tutorial from Oracle. We’ll see how this works on the next page as well

List

First, let’s explore the simplest of these collections, the list. A list is defined as an ordered collection or sequence of elements, meaning that the order in which the elements were added to the list is preserved, but that order can be updated through the use of sorting algorithms.

Lists are similar to arrays in many ways. The biggest difference in Java is that arrays must be declared with a static size that cannot be changed, whereas a list can hold any number of elements, even without knowing the number of elements it will contain ahead of time.

In Java, the collections framework provides an abstract class List<E> that defines the operations a list should be able to perform. So, as we saw in an earlier module, we can store our lists in the datatype List, but we cannot instantiate that class directly because it is abstract.

There are many classes in the Java collections framework that extend the List abstract class. The two most important are the ArrayList and LinkedList classes. Thankfully, since they both inherit from the List class, we can use them interchangeably.

Why Multiple List Implementations?

Java provides multiple versions of the list classes for one important reason: performance. Each version of the list class can perform the same operations and provide the same results, but because each one handles the underlying storage of data differently, the time it takes to perform those operations can vary widely.

To truly understand the difference requires a much deeper understanding of computer science than we are going to gain in this course alone. However, even novice programmers can empirically explore the difference to see which data structure is best for their program.

The key is to build a simple program that uses one of the list classes, performing the operations our actual program might perform. After doing a large number of those operations (say, over one million of them), we can record the amount of time that program took to complete. Then, we can repeat that same process for each different list class. The version that ran the quickest is probably the best choice for our needs.

Creating a List

To use lists in our program, we’ll need to start by importing the appropriate libraries at the top of our file:

import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;

To create a list, we can simply instantiate it just like any other object. However, since the Java lists use generics, we must also provide the type of data we’d like to store in the list inside of angle brackets <> as well.

For example, to create an ArrayList that stores whole numbers, or int values, we would do the following:

List<Integer> intList = new ArrayList<Integer>();

Notice that we have to use the Integer type instead of int, because these lists can only store objects, not primitive data types.

Similarly, to create a LinkedList that stores String objects, we could do this:

List<String> stringList = new LinkedList<String>();

That’s all there is to it!

List Operations

The List class in Java defines several operations that each list class must be able to perform. The full list can be found on the List page of the Java API documentation. Here are a few of the most important ones:

  • add(e)—adds element e to the end of the list
  • add(index, e)—adds element e to the specified index position in the list. All elements at that position and after are shifted toward the end of the list.
  • contains(o)—returns true if the object is contained in the list
  • get(index)—gets the element in the list at the specified index position
  • indexOf(o)—returns the first index that this object can be found in the list, or -1 if it is not found
  • isEmpty()—returns true if the list contains 0 elements
  • remove(index)—removes the element at the specified index position in the list
  • remove(o)—removes the first occurrence of the given object from the list, if one exists.
  • set(index, element)—replaces the element at index position in the list with the given element.
  • size()—returns the number of elements in the list
  • toArray()—returns an array containing all elements in this list in order

Iterating

What if we want to iterate through a list? Thankfully, we can use an enhanced for loop to do this, in the same way that we can iterate through an array:

List<Integer> intList = new ArrayList<Integer>();
intList.add(5);
intList.add(3);
intList.add(7);
intList.add(2);
intList.add(4);

for(int x: intList){
  System.out.println(x);
}

Sorting

To sort a list in Java, we can use the Collections.sort() method on the list itself. First, we’ll need to import the Collections class at the top of the file:

import java.util.Collections;

Then, we can use the sort() method in our code. This will sort the list in ascending order by default, but we can provide an optional parameter to sort in descending order as well:

List<Integer> intList = new ArrayList<Integer>();
intList.add(5);
intList.add(3);
intList.add(7);
intList.add(2);
intList.add(4);

// sort in ascending order
Collections.sort(intList);

// sort in descending order
Collections.sort(intList, Collections.reverseOrder());
List or an Array?

Consider a list when:

  • the number of elements cannot be known at instantiation
  • you want to access the elements using integer indexes, and you want the indexes to run contiguously from 0
  • you want to be able to control the order of the elements (by sorting etc)
  • the size of the collection can vary over the life of the program

Select an array when:

  • the number of elements can be known at instantiation, or an upper limit used
  • you want to be able to have “empty” elements in the collection
  • the size of the collection cannot vary over the life of the program

Example

To explore how to use a list in a real program, let’s look at a quick example program. Here’s a short problem statement:

Write a program that will accept a single integer as input, either from the terminal or by reading a file provided as the first command-line argument. If no command-line argument is provided, assume that input should be read from the terminal. If there are any errors opening a file provided as an argument or parsing the input, simply print “Invalid Input!” and terminate the program. If the provided integer is less than 3, it should also print “Invalid Input!”.

Using the integer provided as input, the program should generate a list of numbers representing the Fibonacci sequence containing that many entries.

Before printing the list, the program should perform two additional operations on the list. First, if the integer provided as input is contained in the list, it should be removed. Secondly, the list should be presented in descending order, with the largest value first.

The program should print the list to the terminal, with each entry separated by a space.

The program should be implemented as two functions - a main() function that handles reading input, and a makeList() function that accepts a single integer as a parameter and returns the completed list of integers.

Fibonacci Sequence

The Fibonacci sequence is produced by adding the two previous numbers together to generate a new number. Traditionally, the first two Fibonacci numbers are 0 and 1. So, the next number is 0 + 1 = 1, and the number following that is 1 + 1 = 2. The sequence continues indefinitely.

Formally, the Fibonacci sequence is defined as:

$$F_0 = 0$$ $$F_1 = 1$$ $$F_n = F_{n-1} + F_{n-2}$$

You can find more information about the Fibonacci Sequence on Wikipedia.

For example, if the input provided is 8, the program would begin by generating the first eight Fibonacci numbers, starting with 0 and 1:

[0, 1, 1, 2, 3, 5, 8, 13]

Then, since 8 is contained in the list, it should be removed:

[0, 1, 1, 2, 3, 5, 13]

Finally, the list should be sorted in descending order, so the final list returned will be:

[13, 5, 3, 2, 1, 1, 0]

main Function

So, let’s build the program. We can start with this simple skeleton:

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.lang.ArrayIndexOutOfBoundsException;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Collections;

public class ListExample{
  
  public static void main(String[] args){
    Scanner scanner;
    try{
      scanner = new Scanner(new File(args[0]));
    }catch(FileNotFoundException e){
      System.out.println("Invalid Input!");
      return;
    }catch(ArrayIndexOutOfBoundsException e){
      //no argument provided, read from terminal
      scanner = new Scanner(System.in);
    }
    
    try(
      Scanner reader = scanner
    ){
    
      int count = Integer.parseInt(reader.nextLine());
      if(count < 3){
        System.out.println("Invalid Input!");
        return;
      }
      
      List<Integer> list = makeList(count);
      
      for(int x : list){
        System.out.print(x + " ");
      }
      System.out.println();
      
    }catch(Exception e){
      System.out.println("Invalid Input!");
      return;
    }
  }
  
  public static List<Integer> makeList(int x){

    // MORE CODE GOES HERE
  
  }
}

This program contains a simple main() method that will handle reading and parsing the input from either the terminal or a file provided as a command-line argument. It will also verify that the input is an integer, and it is a value that is at least 3 or greater. If will then call the makeList() function using the input as a parameter to create the list. Finally, it will print the result using a simple enhanced for loop to iterate through the list and print each element followed by a space. We also must remember to print a newline at the end. Pretty nifty, right?

So, all we need to worry about implementing is the makeList() function.

makeList Function

YouTube Video

Video Materials

Let’s dive into the makeList() function. First, we’ll need to create a list. However, as we saw earlier, there are two different types of list we can use. For this example, let’s just use an ArrayList of Integers, but we could just as easily use a LinkedList as well. So, the code would be as follows:

public static List<Integer> makeList(int x){
  List<Integer> list = new ArrayList<Integer>();

}

Then, we’ll need to add the first two items to the list, representing the first two Fibonacci numbers:

public static List<Integer> makeList(int x){
  List<Integer> list = new ArrayList<Integer>();
  list.add(0);
  list.add(1);
}

Following that, we’ll use a simple for loop to generate the next few numbers. We can either have separate variables to represent the previous values, or we can just read them directly from the list using the get() method:

public static List<Integer> makeList(int x){
  List<Integer> list = new ArrayList<Integer>();
  list.add(0);
  list.add(1);
  for(int i = 2; i < x; i++){
    int newNumber = list.get(i-1) + list.get(i-2);
    list.add(newNumber);
  }
}

Once we’ve generated our list, we need to make sure x is not in the list. If so, we can just remove it. However, remember that there are two methods for removing an item from the list. If we just provide an int as an argument, it will call the version that removes the element at that index in the list. Instead, we’ll need to cast that int as an Integer so that it removes the element with the value equal to x. Thankfully, if we use the remove() method on an item that isn’t in the list, it won’t do anything.

public static List<Integer> makeList(int x){
  List<Integer> list = new ArrayList<Integer>();
  list.add(0);
  list.add(1);
  for(int i = 2; i < x; i++){
    int newNumber = list.get(i-1) + list.get(i-2);
    list.add(newNumber);
  }
  list.remove((Integer)x);
}

Finally, we can use the Collections.sort() method to sort the list. We’ll need to remember to include the optional parameter to sort in descending order. Once we’ve sorted the list, we can return it.

public static List<Integer> makeList(int x){
  List<Integer> list = new ArrayList<Integer>();
  list.add(0);
  list.add(1);
  for(int i = 2; i < x; i++){
    int newNumber = list.get(i-1) + list.get(i-2);
    list.add(newNumber);
  }
  list.remove((Integer)x);
  Collections.sort(list, Collections.reverseOrder());
  return list;
}

That’s all there is to it! See if you can complete the code in ListExample.java to the left, then use the two assessments below to check your program.

Subsections of List

Maps

Next, let’s explore another important collection, the map. Some programming languages, such as Python, refer to this collection as a dictionary as well.

A map is a collection that associates, or maps, a key to a value. To store something in a map, we must provide a unique key for each value. If we provide a key that is already in use, the value stored by that key is overwritten. Then, to retrieve a value, we simply provide the key that is associated with that value.

This is very similar to how arrays work, where each element in the array can be accessed using an array index. The biggest difference is that keys in a map can be any value, not just an integer, and likewise the values can be any type of value.

In Java, the collections framework provides an abstract class Map<K, V> that defines the operations a list should be able to perform. So, as we saw in an earlier module, we can store our maps in the datatype Map, but we cannot instantiate that class directly because it is abstract.

There are many classes in the Java collections framework that extend the Map abstract class. The most commonly used version is the HashMap and LinkedList class.

Creating a Map

To use a map in our program, we’ll need to start by importing the appropriate libraries at the top of our file:

import java.util.Map;
import java.util.HashMap;

To create a map, we can simply instantiate it just like any other object. However, since the Java maps use generics, we must also provide the data types for both the keys and values inside of angle brackets <> as well.

For example, to create a HashMap that associates String keys with Double values, we would do the following:

Map<String, Double> aMap = new HashMap<String, Double>();

Notice that we have to use the Double type instead of double, because these maps can only store objects, not primitive data types, just like Lists.

That’s all there is to it!

Map Operations

The Map class in Java defines several operations that each map class must be able to perform. The full list can be found on the Map page of the Java API documentation. Here are a few of the most important ones:

  • put(k, v)—associate the value v with the key k in the map
  • get(k)—return the value associated with the key k in the map
  • size()—returns the number of key and value associations in the map
  • containsKey(k)—returns true if the map contains an associated value for the given key k
  • containsValue(v)—returns true if one or more keys in the map are associated with the given value v

Iterating

What if we want to iterate through a map? That is a bit tricky, but it can be done. To do this, we’ll use an enhanced for loop, which will use the special Map.Entry class to represent each entry. The code for doing this is shown here:

Map<String, String> mapIter = new HashMap<String, String>();
mapIter.put("One", "Uno");
mapIter.put("Two", "Dos");
mapIter.put("Three", "Tres");
mapIter.put("Four", "Quatro");

for(Map.Entry<String, String> entry : mapIter.entrySet()){
  System.out.println("Key: " + entry.getKey());
  System.out.prinltn("Value: " + entry.getValue());
}

However, in most cases, it doesn’t make much sense to iterate through a map, since that isn’t what it is designed for. Instead, we may want to consider using some sort of a list instead.

Map or List?

Consider a map when:

  • you want to use something other and integers as the index (key)
  • you don’t care about the order the elements are yielded (provided) by iteration

Example

To explore how to use a map in a real program, let’s look at a quick example program. Here’s a short problem statement:

Write a program that will read multiple lines of input, either from the terminal or by reading a file provided as the first command-line argument. If no command-line argument is provided, assume that input should be read from the terminal. If there are any errors opening a file provided as an argument or parsing the input, simply print “Invalid Input!” and terminate the program.

The program will store a map that associates lines of input with random integers.

When a line of input is read, the program will check to see if that line has already been used as a key in the map. If so, it will return the value associated with that key.

If the map does not contain an entry for that key, the program should generate a new random integer and store it in the map, using the input line as the key.

The program should be implemented as two functions - a main() function that handles reading input, and a getOutput() function that accepts a string as a parameter and returns the associated number for that string. It should also use a global variable to store the map.

For example, let’s say the program receives the following input:

cat
dog
horse
dog
cat

One possible output could be:

12334512345
239487234
234234
239487234
12334512345

Notice that the lines of output correspond with the lines of input, such that the program returns the same value each time it reads the word cat.

main Function

So, let’s build the program. We can start with this simple skeleton:

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.lang.ArrayIndexOutOfBoundsException;
import java.util.Map;
import java.util.HashMap;
import java.util.Random;

public class MapExample{
  
  public static Map<String, Integer> map;
  public static Random random;
  
  public static void main(String[] args){
    Scanner scanner;
    try{
      scanner = new Scanner(new File(args[0]));
    }catch(FileNotFoundException e){
      System.out.println("Invalid Input!");
      return;
    }catch(ArrayIndexOutOfBoundsException e){
      //no argument provided, read from terminal
      scanner = new Scanner(System.in);
    }
    
    try(
      Scanner reader = scanner
    ){
    
      while(reader.hasNext()){
        String inp = reader.nextLine();
        int output = getOutput(inp);
        System.out.println(output);
      }
      
    }catch(Exception e){
      System.out.println("Invalid Input!");
      return;
    }
  }
  
  public static int getOutput(String inp){

    // MORE CODE GOES HERE
  
  }
}

This program contains a simple main() function that will handle reading and parsing the input from either the terminal or a file provided as a command-line argument. When it reads a line of input, it will use the getOutput() function to get the associated output for that input, and then print it to the terminal.

The program also includes a global static field to store the map. We also do the same for a Random object to generate random numbers. In that way, we can use the same objects in both functions without having to pass them around as arguments.

So, all we need to worry about implementing is the getOutput() function.

getOutput Function

YouTube Video

Video Materials

Let’s dive into the getOutput() function. First, we’ll need to see if the map and random objects have been initialized. We can do that by checking to see if they are equal to null. If so, we’ll initialize them:

public static int getOutput(String inp){
  if(map == null){
    map = new HashMap<String, Integer>();
  }
  if(random == null){
    random = new Random();
  }
}

Then, we’ll need to see if the map contains a value for the string provided as input. If so, we can just return that value:

public static int getOutput(String inp){
  if(map == null){
    map = new HashMap<String, Integer>();
  }
  if(random == null){
    random = new Random();
  }
  if(map.containsKey(inp)){
    return map.get(inp);
  }
}

However, if the map does not contain a value for that key, we must generate a new one, store it in the map, then return it:

public static int getOutput(String inp){
  if(map == null){
    map = new HashMap<String, Integer>();
  }
  if(random == null){
    random = new Random();
  }
  if(map.containsKey(inp)){
    return map.get(inp);
  }else{
    int newNumber = random.nextInt();
    map.put(inp, newNumber);
    return newNumber;
  }
}

That’s all there is to it! See if you can complete the code in MapExample.java to the left, then use the two assessments below to check your program.

Subsections of Maps

Tuples

The last data structure we will explore is the tuple. A tuple in mathematics is defined as a “finite ordered list” of items. So, it is a list of items that is not infinite, and the ordering of the items in that list matters.

Some languages, such as Python, provide support for tuples directly in the language itself or as part of the standard library. Java, however, does not provide native support for a data structure that is exactly like a tuple. Nearly every language implements the tuple as an immutable data type.

Instead, we’ll learn how to construct our own tuple, and see how it could be used in a couple of useful contexts.

Creating a Tuple

To create a tuple in Java, we must first create a class to store the data. This is a simple class that usually includes two or more public fields to store the data. For example, we could create a tuple that will store two integers like this:

public class IntTuple{
  private final int FIRST;
  private final int SECOND;
  
  public IntTuple(int one, int two){
    this.FIRST = one;
    this.SECOND = two;
  }
  public int getFIRST(){
      return this.FIRST;
  }
  public int getSECOND(){
      return this.SECOND;
  }

}

This is a very simple class that stores two integers as fields first and second, and also includes a constructor to help populate those two values. The data is made immutable by declaring the instance variables private final, assigning to them in the constructor, and only providing getters1.

We may also want to add a couple of features to our tuple class. First, we can implement the toString() method to provide a string representation of this item. This is helpful anytime we need to print some debugging output:

@Override
public String toString(){
  return String.format("(%d, %d)", this.FIRST, this.SECOND);
}

In addition, we may want to implement an equals() method. That method is also included as part of every object in Java, and it is used to determine if two objects are equal to each other. By default, it will simply check to see if they are exactly the same instance of the object. For tuples, we might want to simply check and see if they store the same values, regardless of whether they are the same instance. So, to implement that method, we could include the following code:

@Override
public boolean equals(Object obj){
  //check of obj is null
  if(obj == null){
    return false;
  }

  // check if they are the same instance
  if(this == obj){
    return true;
  }
  
  // check if obj is same type
  if(!(obj instanceof IntTuple)){
    return false;
  }
  
  // cast to same type
  IntTuple tuple = (IntTuple)obj;
  
  // check if all fields are the same
  return tuple.getFIRST() == this.FIRST && tuple.getSECOND() == this.SECOND;
}

First, notice that the equals() method accepts a Java Object as input. This is because we can provide any object as input. So, our equals() method must handle any type of object, so it has to include extra code to check the type of the object as well as the values it contains.

Next, notice that we are very careful to first check that the parameter provide is not null before using it. Again, we have no guarantee that the value we are provided has even been initialized, so we must make sure it is before continuing.

Finally, if we’ve determined that the object provided is indeed a valid IntTuple instance, we can cast it to that type and check the values of each field to see if they match.

Using a Tuple

One of the most useful ways to use a tuple is when we need to store associated values in a data structure, or if we want to return multiple values from a function.

The classic example for tuples is representing coordinates in space, such as a two-dimensional game. In this way, we could create a list of tuples to represent items in the game, and we can even return both the x and y coordinates of an item in a single tuple.

Example

To really explore how we could use a tuple in our code, let’s build a simple program. Here’s a problem statement:

Write a program that will read multiple lines of input from the terminal.

The program should implement a simple search game. Players will guess coordinates on a 10x10 grid, trying to find a hidden item. So, input will take the form of two integers, separated by a space. If the program is unable to parse an input for any reason, it should print “Invalid Input!” and terminate the program.

When a player makes a guess, the program should respond with one of the four cardinal directions: “North”, “South”, “East”, “West”, indicating the direction of the hidden item from the guess. For simplicity, the program will only respond “North” or “South” if the player’s guess is not on the same row, or x coordinate, as the location, and “East” or “West” only if the player’s guess is on the same row as the location. If the player guesses correctly, simply print “Found!” and terminate the program. If the player repeats a guess, the program should print “Repeat!” instead of a cardinal direction.

The hidden location should be randomly generated and stored in an instance of the IntTuple class defined above as a global variable, and the program should maintain a global list of IntTuples representing the locations already guessed.

The program should be implemented as two functions: main() that handles reading input and printing output, and a makeGuess() function that accepts two integers, x and y as parameters, and responds with a string representing the result of that guess.

Let’s see if we can build this program using our IntTuple class as defined above.

main Function

First, let’s look at the main function. Once again, we’ll start with skeleton code that is very similar to the other examples in this chapter:

import java.util.Scanner;
import java.io.File;
import java.io.FileNotFoundException;
import java.lang.ArrayIndexOutOfBoundsException;
import java.util.Random;
import java.util.List;
import java.util.LinkedList;

public class TupleExample{
  
  public static List<IntTuple> guesses;
  public static Random random;
  public static IntTuple location;
  
  public static void main(String[] args){
    try{
      Scanner reader = new Scanner(System.in);
      while(reader.hasNext()){
        String[] inp = reader.nextLine().split(" ");
        int x = Integer.parseInt(inp[0]);
        int y = Integer.parseInt(inp[1]);
        String out = makeGuess(x, y);
        System.out.println(out);
        if(out.equals("Found!")){
          return;
        }
      }
      
    }catch(Exception e){
      System.out.println("Invalid Input!");
      return;
    }
  }
  
  public static String makeGuess(int x, int y){

    // MORE CODE GOES HERE
  
  }
}

At the top of the class, we have included three static fields to store our list of previous guesses, an IntTuple of the correct location, and a random number generator.

In this code, we are simply reading a line of input, splitting it into two tokens, and then parsing each token to an integer to get the x and y values of the guess. After that, we can call the makeGuess() function with those values, and print the result. Finally, we must check to see if the result is "Found!". If so, we can terminate the program using the return keyword.

makeGuess Function

YouTube Video

Video Materials

Now that we have our main() function written, let’s work on the makeGuess() function. As we saw on the previous page, we must first make sure our list storing the guesses has been initialized, as well as our random number generator:

public static String makeGuess(int x, int y){
  if(guesses == null){
    guesses = new LinkedList<IntTuple>();
  }
  if(random == null){
    random = new Random();
  }
}

In this example, we are using the LinkedList class as our list. Again, the choice really doesn’t matter at this point, but there are some performance considerations that we could discuss in a future course.

In addition, we must make sure our random location has been established. So, we’ll do that in the code as well:

public static String makeGuess(int x, int y){
  if(guesses == null){
    guesses = new LinkedList<IntTuple>();
  }
  if(random == null){
    random = new Random();
  }
  if(location == null){
    location = new IntTuple(random.nextInt(10), random.nextInt(10));
  }
}

Here, we are using the nextInt() method of Random to generate a number between 0 and 9, inclusive.

Now we must handle producing the output. First, we need to create a new IntTuple for the guess, and then check and see if the guess is correct, or if it has already been guessed:

public static String makeGuess(int x, int y){
  if(guesses == null){
    guesses = new LinkedList<IntTuple>();
  }
  if(random == null){
    random = new Random();
  }
  if(location == null){
    location = new IntTuple(random.nextInt(10), random.nextInt(10));
  }
  IntTuple guess = new IntTuple(x, y);
  if(guess.equals(location)){
    return "Found!";
  }
  if(guesses.contains(guess)){
    return "Repeat!";
  }
}

Here, we are using that important equals() method we created earlier to determine if two tuples contain the same values. In addition, it is important to remember that the contains() method of a list also uses the equals() method when determining if the list contains a particular item. In fact, most Java libraries always use the equals() method of an object to determine if two objects are equal, so it is important to implement that method in our tuple class.

If we find out that the guess is not the hidden location, then we should store it in our list of guesses:

public static String makeGuess(int x, int y){
  if(guesses == null){
    guesses = new LinkedList<IntTuple>();
  }
  if(random == null){
    random = new Random();
  }
  if(location == null){
    location = new IntTuple(random.nextInt(10), random.nextInt(10));
  }
  IntTuple guess = new IntTuple(x, y);
  if(guess.equals(location)){
    return "Found!";
  }
  if(guesses.contains(guess)){
    return "Repeat!";
  }
  guesses.add(guess);
}

Finally, we can handle printing the hints for cases where the guess is not on the same row:

public static String makeGuess(int x, int y){
  if(guesses == null){
    guesses = new LinkedList<IntTuple>();
  }
  if(random == null){
    random = new Random();
  }
  if(location == null){
    location = new IntTuple(random.nextInt(10), random.nextInt(10));
  }
  IntTuple guess = new IntTuple(x, y);
  if(guess.equals(location)){
    return "Found!";
  }
  if(guesses.contains(guess)){
    return "Repeat!";
  }
  guesses.add(guess);
  if(guess.getFIRST() > location.getFIRST()){
    return "North";
  }
  if(guess.getFIRST() < location.getFIRST()){
    return "South";
  }
}

Below that, we can assume that the guess is on the same row, so we’ll have to handle the cases where the guess is east or west of the location:

public static String makeGuess(int x, int y){
  if(guesses == null){
    guesses = new LinkedList<IntTuple>();
  }
  if(random == null){
    random = new Random();
  }
  if(location == null){
    location = new IntTuple(random.nextInt(10), random.nextInt(10));
  }
  IntTuple guess = new IntTuple(x, y);
  if(guess.equals(location)){
    return "Found!";
  }
  if(guesses.contains(guess)){
    return "Repeat!";
  }
  guesses.add(guess);
  if(guess.getFIRST() > location.getFIRST()){
    return "North";
  }
  if(guess.getFIRST() < location.getFIRST()){
    return "South";
  }
  if(guess.getSECOND() > location.getSECOND()){
    return "West";
  }else{
    return "East";
  }
}

There we go! That method will handle producing the output for any guess provided by the user. See if you can complete the code in IntTuple.java and TupleExample.java to the left, then use the two assessments below to check your program.


  1. It is technically sufficient to declare them as final, the private and getter only is admittedly overkill. ↩︎

Subsections of Tuples

Documenting Code

As we continue to write larger and more complex programs, it is important to remember that we can include comments and documentation in our code. Comments are lines of text in our program’s source code that are ignored by the compiler or interpreter, allowing us to add information to the program beyond the code itself.

These help explain our code to anyone who might read it, but can even be useful to help us remember exactly how it works or what it does, especially if we end up coming back to a program written a long time ago that we do not remember very well.

Single Line Comments

As we’ve seen before, we can add single-line comments to our Java programs using two forward slashes // before a line in our source file:

// this is a comment
int x = 5;

// this is also a comment
boolean b = true;

Multiple Line Comments

Java also includes the ability to add a comment that spans multiple lines, without requiring each line to be prefixed with forward slashes. Instead, we can use a forward slash followed by an asterisk /* to start a comment, and then an asterisk followed by a forward slash to end it */, as shown below:

int x = 5;

/* This is a multi line comment
it can span multiple lines

and even blank lines */

int y = 10;

Documentation

Finally, Java also includes a secondary type of comment that spans multiple lines, specifically for creating documentation. Instead of a single asterisk, we use a double asterisk after the forward slash at the beginning /**, but the ending is the same as before */.

In addition, these comments typically include an asterisk at the beginning of each line, aligned with the first asterisk of the start of the comment. Thankfully, most code editors will do this for us automatically, including Codio!

These comments are specifically designed to provide information about classes and methods in our code. Here’s a quick example, using the IntTuple class developed earlier in this module:

/**
 * Represents a tuple containing two integer values. 
 * 
 * @author Test Student
 * @version 1.0
 * @since 2019-01-01
 */
public class IntTuple{
  
  public int first;
  public int second;
  
  /**
   * Constructs a new IntTuple object.
   * 
   * @param one     the first element in the tuple
   * @param two     the second element in the tuple
   */
  public IntTuple(int one, int two){
    this.first = one;
    this.second = two;
  }
}

Once we’ve written this documentation in our code, Java includes a special tool called Javadoc that will generate HTML files that describe what our code does. In fact, the Java API files, such as the one for Scanner, are generated using this tool!

For more information about writing comments for the Javadoc tool, as well as some great examples, consult the documentation.

Summary

In this module, we explored some of the useful features included in our chosen programming language. These features give us a small taste of all the handy and exciting things we can do in our programs.

In addition, we saw a method for effectively documenting our code. Even if it isn’t required, it is still a very good habit to get into.

This module is really intended to be a great capstone for this course. At this point, we have learned most of the basics of what we can do in our chosen programming language. From here, it is all about exploring different data structures, algorithms, and libraries we can use in our code.

In addition, we can learn about the frameworks and design patterns used in state-of-the-art software today, as well as the methods used by software engineers to develop software solutions to real-world problems.

Let’s all go out and try to build some cool software!