Building Java Programs

Lab: Implementing a Collection Class

Except where otherwise noted, the contents of this document are Copyright 2019 Stuart Reges and Marty Stepp.

Lab goals

Goals for this problem set:

• learn how to implement our own basic collection class
• practice coding with unfilled arrays
• implement accessor and mutator methods on an object's state

ArrayIntList

In this chapter, we implement a collection called ArrayIntList.

• Similar to an ArrayList of int values.
• Stores its data in an integer array.

unfilled array: The array is larger than the data it stores.

• This gives extra space to add more elements without immediately resizing.
• The extra "0" slots should not be exposed or accessible by the client of this class.

ArrayIntList.java

Here is the code for ArrayIntList as written in this chapter:

• ArrayIntList.java

The class uses the following data fields (refer to them in your exercise solutions):

public class ArrayIntList {
    private int[] elementData;   // list of integers
    private int size;            // current number of elements in the list
    
    ...
}

Exercise : arrayIntListMystery

Suppose the following method is added to the ArrayIntList class:

public void mystery() {
    int n = 0;
    for (int i = 0; i < size; i++) {
        n += elementData[i] * i;
    }
    elementData[size] = n;
    size++;
}

What is the output of the following client code?

ArrayIntList list = new ArrayIntList();
list.add(14); list.add(3); list.add(6); list.add(2);
list.mystery();
System.out.println("list = " + list);
System.out.println("size = " + list.size());

• line 1: list = [14, 3, 6, 2, 21]
• line 2: size = 5

Exercise : isPairwiseSorted

Write a method isPairwiseSorted to be added to the ArrayIntList class. The method returns true if each successive pair of numbers in the list is in nondecreasing order.

For example, if a variable called list stores [3, 8, 2, 5, 19, 24, -3, 0, 4, 4, 8, 205, 42], then the call of list.isPairwiseSorted() should return true because the successive pairs of this list are all sorted: (3, 8), (2, 5), (19, 24), (-3, 0), (4, 4), (8, 205). The extra value 42 at the end had no effect on the result because it is not part of a pair.

If the list had instead stored [7, 42, 308, 409, 19, 17, 2], then the method should return false because the pair (19, 17) is not in sorted order. If a list is so short that it has no pairs, then it is considered to be pairwise sorted.

Exercise : runningTotal

Write a method runningTotal to be added to the ArrayIntList class. The method returns a new ArrayIntList that contains a running total of the original list. In other words, the ith value in the new list should store the sum of elements 0 through i of the original list.

For example, given a variable list that stores [2, 3, 5, 4, 7, 15, 20, 7], the call of list.runningTotal() should return a new list [2, 5, 10, 14, 21, 36, 56, 63].

Note that your method is creating a new list to be returned, not modifying the current list itself. The original list should not be changed by the method. The new list returned should have the same capacity as the original.

Recall: Removing from an ArrayIntList

When removing a value from an ArrayIntList, the surrounding values must be shifted left to fill the gap left by it.

Example: calling list.remove(2); to remove the value at index 2 from the list below.

index   0   1   2   3   4   5   6   7   8   9
      +---+---+---+---+---+---+---+---+---+---+
      | 4 | 7 | 5 | 1 | 6 | 3 | 0 | 8 | 0 | 0 |
      +---+---+---+---+---+---+---+---+---+---+
size = 8           /   /   /   /   /
                  /   /   /   /   /
                 /   /   /   /   /
                v   v   v   v   v
      +---+---+---+---+---+---+---+---+---+---+
      | 4 | 7 | 1 | 6 | 3 | 0 | 8 | 0 | 0 | 0 |
      +---+---+---+---+---+---+---+---+---+---+
size = 7

The opposite is true when inserting a new element (subsequent elements must be shifted right).

Exercise : removeFront

Write a method removeFront to be added to the ArrayIntList class. Your method takes an integer n as a parameter and that removes the first n values from a list of integers.

For example, if a variable called list stores [8, 17, 9, 24, 42, 3, 8], the call of list.removeFront(4); should remove the first 4 elements, causing the list's contents to become [42, 3, 8]. You may assume that the parameter value passed is between 0 and the size of the list inclusive.

Exercise : removeAll

Write a method removeAll to be added to the ArrayIntList class. Your method accepts an integer value as a parameter and that removes all occurrences of the given value from the list.

For example, if the variable named list stores [14, 5, -1, 7, 14, 7, 7, 29, 3, 7], the call of list.removeAll(7); should modify the list to store [14, 5, -1, 14, 29, 3].

Exercise : stretch

Write a method stretch to be added to the ArrayIntList class. Your method takes an integer n as a parameter and replaces each integer in the list with n copies of that integer.

For example, if a variable called list stores [18, 7, 4, 24, 11] and we make the call of list.stretch(3);, the list should be changed to store [18, 18, 18, 7, 7, 7, 4, 4, 4, 24, 24, 24, 11, 11, 11]. If n is zero or negative, the list should become empty.

Note that you may need to increase the capacity of the list's internal array to have enough space to fit all of the necessary element values.

Exercise : longestSortedSequence

Write a method longestSortedSequence to be added to the ArrayIntList class. Your method returns the length of the longest sorted (nondecreasing) subsequence within the list of integers.

For example, if a variable called list stores [1, 3, 5, 2, 9, 7, -3, 0, 42, 308, 17], then the call of list.longestSortedSequence() would return 4 because it is the length of the longest sorted sequence within this list (the sequence -3, 0, 42, 308 that begins at index 6).

If the list is empty, your method should return 0. For a nonempty list the method will always return a value of at least 1 because any individual element constitutes a sorted sequence.