Section 14

Data structures and abstract data types
Programming Exercise

Data structures and abstract data types

In the second part of the course we will depart from Java basics and focus on data structures and the algorithms that manipulate them. Keep in mind that an algorithm is a more general description of a procedure that could be implemented in any sufficiently powerful programming language. Furthermore, the specification of a data structure includes how information is organized (how it is given structure) and the allowed operations on the data structure. This specification is called an abstract data type, known as abstract because the specification is separate from any specific implementation (say, in Java or another programming language).

However, since this course is primarily focused on Java, and since Java provides object-oriented programming tools that help us implement abstract data types, we will often present you an abstract data type definition in the form of a Java interface. Consider the Bag interface from the lecture notes:

public interface Bag {
    boolean add(Object item);
    boolean remove(Object item);
    boolean contains(Object item);
    int numItems();
    Object grab();
    Object[] toArray();
}

Answer the following questions.

If we were to write a blueprint class called MyBag that defined all the methods in the Bag interface, how would we indicate that any MyBag object adheres to the abstract definition of a Bag? ¹
In the Bag interface, there is no getItem() method for accessing a specific item in the bag. Instead, there is a method called grab() which accesses a random item in the bag. Why does this make sense, given the characteristics of a bag? ²

In lecture we presented an implementation of the Bag abstract data type in the ArrayBag class. Download Bag.java (the interface) and ArrayBag.java (an implementation of the interface) now and open them in VSCode. Then answer the following questions.

What are the fields of the ArrayBag class, and why did we include them in our definition? ³
In lecture, we looked at the ArrayBag class’ implementation of the add() method; it returns true if it is able to add the item to the bag, and false if it cannot add the item when the bag is full. Draw a diagram of the fields of an ArrayBag object as the add() method is called on it for the first time. Show the addition of the string "don't blink". ⁴
Create an instance of ArrayBag, add "don't blink", and show the proper method of retrieving the string from the ArrayBag using the grab() method. Use the most specific type for the variable that catches the return value of grab(). (The grab() method should return "don't blink", since it will be the only item in the bag — we know this will be a string.) ⁵
Consider the ArrayBag method containsAll(). Why does it make sense to have the method take a parameter of type Bag and not ArrayBag? ⁶
Our Bag interface has a method toArray(). The toArray() method returns an array containing the current contents of the bag. This allows clients of any Bag-implementing class to iterate over the items in the bag. Find the method in the ArrayBag class. What does the method do, and why? ⁷

Programming Exercise

Each week, one of the S-111 teaching fellows must take the unit tests home and enter the final grades into a spreadsheet. Since there are about 30 unit tests, and entering grades is a monotonous task, each teaching fellow would like to avoid doing this as much as possible. A particularly clever teaching fellow suggested that, in order to keep it fair, one name would be drawn out of a bag at random each week, and that name would determine the teaching fellow who would be given the task of entering the grades.

You will write a class TFChooser that uses an ArrayBag to store the names of the four teaching fellows. The TFChooser class will provide us with a way to fairly delegate the grading task. The class should contain the following features: ⁸
- a constructor that takes an array of strings containing the names of teaching fellows and constructs a TFChooser that could select any of those names after the object is constructed
- an add method that takes a string (the name of the teaching fellow) and stores the teaching fellow’s name, such that the teaching fellow could be chosen to enter the grades thereafter
- an excuse method that takes a string (the name of the teaching fellow) and excuses the specified teaching fellow from being selected to enter the grades
- a choose method that selects a teaching fellow at random to perform the monotonous grading task
Let’s assume that there are four teaching fellows for S-111, and their names are the following:
- "David Chung"
- "Jodi Yu"
- "Yu Chung"
- "Dadi Jovid the Third"
Due to a highly unlikely and unfortunate series of values returned from Math.random(), Yu was chosen to enter the grades six times in a row. Yu protested the fairness of your TFChooser class and demanded that the class implement a chooseAll method that returns an array of strings containing a random permutation of names from the ArrayBag. This way, Yu will not have to worry about being selected until every other teaching fellow has been selected. Implement the chooseAll() method. ⁹

We would include the implements Bag clause in the header for MyBag. ↩
Given the “bag” analogy, it would not be possible to pick out a specific item from the bag since the items are not ordered (and therefore the items do not have a position). ↩
The ArrayBag class has an object array and a numItems integer. The Object array called items serves as a storage area for items in the bag, and the numItems integer allows us to keep track of how many items are in the bag. ↩
We start with the following “empty” ArrayBag on the heap. Depicted here also is a reference (arrB) to the bag on the stack.

After confirming that the parameter is not null, the add method checks to see if numItems == items.length. This is false, since items.length is 50 and numItems is 0. We access items[numItems] and set it equal to the reference to the string:

Then we do numItems++ and return true.

↩
We have to do a cast to get this to work:
```
ArrayBag bag = new ArrayBag();
bag.add("don't blink");
String s = (String)bag.grab();
```
However, this will only work if we know grab could only return a string! In this case, it is okay, since we know we only added strings. In general, however, it is very dangerous to downcast something (from Object to a more specific type). ↩
We might want containsAll() to work as generally as possible. For instance, we might want to compare two different objects that both implement the Bag interface. This also reflects the fact that it is possible to determine whether two bags contain the same items using only the methods in the Bag interface. ↩
The method creates a new array and copies the values of the elements from the array in the called ArrayBag object. The wrong way to implement this method is as follows:
```
public Object[] toArray() {
    return items;
}
```
If we do this, a reference to the internal array of the ArrayBag is returned. If the client code modifies the array, then it is also modifying the array inside the ArrayBag, and can cause the object to enter an invalid state. For example, we could remove items from the array, after which the numItems field in the ArrayBag we took the reference from would not match the actual number of items in the array. ↩
TFChooser.java ↩

Here’s one approach (remember that this method is inside TFChooser):

public String[] chooseAll() {
    ArrayBag alreadyChosen = new ArrayBag();
    String[] randNames = new String[names.numItems()];

    for (int i = 0; i < randNames.length; i++) {
        String tf = null;
        do {
            tf = (String)names.grab();
        } while (alreadyChosen.contains(tf));

        randNames[i] = tf;
        alreadyChosen.add(tf);
    }

    return randNames;
}

However, it is possible (unlikely, but possible) that this method will never return (how?). The following method must return, and will produce a uniformly random result (this algorithm is called the Fisher-Yates shuffle):

public String[] chooseAll() {
    Object[] bagItems = this.names.toArray();
    for (int src = 0; src < bagItems.length; src++) {
        double r = Math.random();
        int dest = (int)(r * (bagItems.length - src) + src);

        Object temp = bagItems[dest];
        bagItems[dest] = bagItems[src];
        bagItems[src] = temp;
    }

    return (String[])bagItems;
}

There is also another version that is must return and is probably the most intuitive:

public String[] chooseAll(){
    String[] randNames = new String[names.numItems()];

    int numItems = names.numItems();
    //get names at random and remove them from the bag
    for(int i = 0; i < numItems; i++){
        String tf = (String)names.grab();
        randNames[i] = tf;
        names.remove(tf);
    }

    //add the names back into the bag
    for(int i = 0; i < randNames.length; i++){
        names.add(randNames[i]);    
    }

    return randNames;

}

↩

Last updated on July 17, 2025.