ArrayIntList

Table of contents

1. Letter Inventory
2. Collections
3. Class invariants
4. Pre/post conditions
5. Exceptions

Letter Inventory

Natural language processing (NLP) is an interdisciplinary area of computer science focused on programming computers to work with natural languages used by humans everyday. Since all data in computers are ultimately represented as numbers, a key challenge in NLP is vectorization: the process of turning a natural language text into a meaningful numeric representation.

A letter inventory is a data type that represents a character-by-character count vectorization for letters in the English alphabet. Each letter inventory keeps track of how many a’s, how many b’s, etc. are contained in a given string. For example, the letter inventory for the string “Washington State” corresponds to [aaeghinnosstttw]. The case of the letter is ignored, so ‘s’ and ‘S’ are exactly the same.

Letter Inventory

We can use letter inventories to autocorrect text as the user types!

Collections

Letter inventories are a specific type of collection. A collection is an object that stores elements (data). Almost every problem that we’ll solve in this course involves defining algorithms that use collections to store and manipulate data.

To help us learn how to design a letter inventory, we’ll study how Java implements a popular collection type called ArrayList by building a simplified ArrayIntList class. An ArrayIntList can be used to store a list (ordered sequence) of integer data.

// An ArrayIntList stores a list of integers
public class ArrayIntList {
    private int[] elementData;
    private int size;

    // Constructs an empty list
    public ArrayIntList() {
        elementData = new int[10];
        size = 0;
    }

    // Appends the given value to the end of the list
    public void add(int value) {
        elementData[size] = value;
        size += 1;
    }
}

Internally, the ArrayIntList class maintains two fields: an int[] elementData representing the list of integers and an int size representing the current number of elements in the list.

Class invariants

So what’s the difference between an ArrayIntList and a raw int[]? Lists disagree with two key features of arrays.

1. Array elements can be stored at any index.
2. Array size is fixed and cannot be changed after construction.

These two features are part of what make arrays so useful as building blocks for programs. But they also inconvenience client programmers in two ways.

1. Since array elements can be stored at any index, there can be empty indices between elements.
2. Since array size is fixed, full arrays cannot store any more elements. (A larger array needs to be constructed, and all of the elements need to be copied over.)

Lists help clients store ordered sequences of elements without having to worry about these inconveniences. Our study of ArrayIntList will primarily focus on the first point about the location of array elements. Unlike int[], ArrayIntList enforces a class invariant (a relationship that must always hold) between the values in elementData and the size field.

ArrayIntList class invariant

The i-th item in the list is always stored at elementData[i].

• Before any public method call, the class invariant must hold for external correctness.
• In the implementation, the class invariant can be temporarily broken so long as it is later restored.
• After any public method call, the class invariant must hold for external correctness.

Pre/post conditions

A getter method for ArrayIntList elements can be written in a few lines.

// Returns the integer at the given index in the list
public int get(int index) {
    return elementData[index];
}

To tell the client about these errors, we’ll introduce a documentation format called pre/post conditions.

Preconditions

Conditions that the client needs to follow in order for the method to behave as intended.

Postconditions

The intended behavior of a method assuming preconditions hold.

// pre : 0 <= index < size()
// post: Returns the integer at the given index in the list
public int get(int index) {
    return elementData[index];
}

While these comments are helpful for the client, it would be better to add validation checks in the code to prevent unintended behavior from occurring when the preconditions are not met. Here are two approaches.

Returning a dummy value

We can return a specific dummy value to notify the client. For example, some implementations of indexOf (returns the index of a given value in a list) return -1 if the value is not contained in the list. Since the client knows that the only valid indices that should be returned from indexOf are in the range 0 <= index < size(), -1 signifies a false result. If implemented this way, this behavior should be clearly documented!

Throwing an exception

The implementer can report a problem to the client by throwing an exception. Most of the time, we prefer this approach.

Exceptions

We can check preconditions by adding an if statement. In order to stop the program within the if statement, throw an exception.

// pre : 0 <= index < size() (throws IllegalArgumentException if not)
// post: Returns the integer at the given index in the list
public int get(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException();
    }
    return elementData[index];
}

In this example, we chose to throw new IllegalArgumentException(). There are many different types of exceptions, each of which informs the client of a different problem. Don’t worry about which one to use: for the purpose of this course, we’ll walk you through the exceptions that need to be thrown when they become relevant.

Note that we also documented this exception by adding it to our method comment.