5 Array-Based Structures

Version 4.3¹

Handouts:

• Part A: Drake: (1) Card (2) Deck (3) ArrayStack (4) ArrayQueue (5) ArrayList classes.
• Part B: Drake: (1) ArrayIterator (2) GoFish (3) GoFishHand classes

Read Chapter 5, "Array-Based Structures." Principal points to understand:

1. How array-based structures can be made to vary in size (shrink and stretch).
2. How array-based structures can implement stacks and queues.
3. The List interface and its array-based implementation.
4. What are Iterators, and how are they implemented.
5. How are the interfaces and classes of the Java Collections Framework related to those presented in this text?

Part A: Pages 119–139

Most abstract data types (ADTs) have at least two implementations, one using arrays and one using linked structures. This week, we look at the array-based implementations of some ADTs that we have previously studied, as well as some new ADTs.

5.1 Shrinking and Stretching Arrays

Arrays are fixed-length objects: once an array is allocated, its size (length, number of elements) cannot be changed. (Note: this does not mean that array-type variables cannot store references to various different sizes of array of the same type. The length of an array is not part of its data type.)

Working around this, we can still "shrink" and "expand" arrays in a certain sense.

The Card and Deck classes, pp. 120 ff.

• How do we make the Deck shrink? Does the array really shrink?

Expanding arrays, the basic idea: create a new, larger array and copy the contents of the old array into it. Details in the next section.

Discuss exercises, p. 126: #5.1–5.4.

5.2 Implementing Stacks and Queues

The ArrayStack Class, pp. 127–129

Basic diagram: a stack containing elements (bottom to top) w, x, y, z:

PNG image of an array-based stack

The size field is the index of what will become the new top if a push is performed. The actual top of stack, if any, is at data[size - 1] .

Sketch what happens as we push and pop elements.

Discuss code; walk through a few examples.

The ArrayQueue Class

Basic diagram: a queue containing A (at the front), B, C, D:

PNG image of an array-based queue

The front element, if the queue is non-empty, is data[front] .

Preliminary statement: The rear element, if the queue is non-empty, is at data[front + size - 1] ; front + size is the index of what will become the new rear if another element is enqueued. (This is a preliminary statement of where the rear is, which we will qualify below.)

Sketch what happens as we enqueue and dequeue elements.

What happens as more and more elements are dequeued, so that front approaches the highest array subscript?

PNG image of an array-based queue

What are the elements, from front to rear?

Now we qualify the preliminary statement about the location of the rear of the queue:

The rear element, if the queue is non-empty, is at data[(front + size - 1) % N] , where N is the array length of data; the next element enqueued goes in at data[(front + size) % N] . (In the sketches above, N = 10, which would not happen in the implementation because N would always be a power of 2l.) So we might think of "rear" as a virtual field = (front + size) % N and indicating the point for insertion of the next element.

Discuss code.

Discuss exercises: p. 133, # 5.7, 5.8 (?), 5.9–5.12.

5.3 The List Interface

A List is a sequence of elements which allows access at both ends and at all positions in between. Thus, it is more general than Stack and Queue, which allow access only at one or both ends.

The List Interface, p. 134

Note: the term 'list' is more flexible in its meaning than the terms 'stack' and 'queue'. Stack and queue have a well-defined, universally understood set of operations. Lists, on the other hand—there are many possible variations in what one can mean by list, and what a list can do. For example:

• An add method that inserts at the beginning
• An add method with a position argument
• An insert method which is the opposite of remove —shoves elements aside to make space for the inserted element
• Elements might be numbered from 1 rather than 0.
• An immutable list type—rather than add and remove, we create new modified lists

The ArrayList Class, pp. 135–137

PNG image of an array-based list

• Methods on the first two pages are either trivial or seen before in the ArrayStack and ArrayQueue classes.
  • So skip unless there are questions.
• The "interesting" methods are contains, toString, and remove, p. 137.
• Discuss how the second remove element could be simplified.
  • Find the index of the object to be removed.
  • Then call the remove(int) method.
  • Would this work with generics? What if E = Integer ? Conflict with int due to autoboxing??
• How would you define a method to insert at a given index, rather than only at the last position?

Discuss exercises: pp. 138–139, #5.16, 5.17, 5.19–5.22.

Part B: Pages 139–154

5.4 Iterators

What Is an Iterator

• The author states: Iterators are useful for traversing a list—that is, "visiting" each element. The iterator generalizes a common type of procedure.

• That is, it abstract the pattern:

  for each element e in data structure D:
    do something with e
  

• For data structures based on an array A this becomes:

  for i = 0 to size - 1:
    do something with A[i]
  

• Give examples of this pattern? ...
• "Such a method would have to appear in the ArrayList class, because it directly accesses the fields data and size." (p. 139)
• But is this necessary? Couldn't we use the methods get and size?

• Iterators can do three things:

  1. Tell if there are more elements not yet visited.
  2. Tell what is the next element (if any).

  3. Remove the element last visited (the "current") element.

     • Cannot insert an element!
     • Cannot replace an element!

• Comment: An iterator is an object that encapsulates the state of an iteration, such as the for loops above, over a collection of elements. This state consists of:

  • The collection (e.g., an array) (i.e., which collection are we in?)
  • The index of the current element (i.e., where are we in this collection?)

Interfaces

• The Iterator interface (java.util.Iterator<E>).

  • View it on the Java API documentation site.

• The Iterable interface (java.lang.Iterable<T>).

  • Ditto
  • Single method, iterator() returns an Iterator<T>.

  • Connection with enhanced for statement:

    for (E e: collection) {
      statements ...
    }
    

    is allowed for any collection type implementing Iterable (also for Iterator?). Replace E with the actual element type.

  • Example: at the top of p. 141:

    int sum = 0;
    for (int n: numbers) {
      sum += n;
    }
    

  • This "expands to" (i.e., is compiled the same as):

    int sum = 0;
    Iterator iter = numbers.iterator();
    while (iter.hasNext()) {
      n = iter.next();
      sum += n;
    }
    

    except that the variable iter is actually "nameless", i.e., it will not conflict with any named variable.

Some Classes Implementing Iterator

• The java.util.Scanner class
  • hasNext
  • next
  • Also other methods, such as nextInt, not part of the Iterator interface.

  • So we could do

    for (String token : myscanner) 
        ...
    

• The ArrayIterator class implements Iterator

  • Diagram, Fig. 5-34 on p. 141, shows interesting system structure.
  • Code (ArrayIterator.java, handout), Fig. 5-36, p. 142.
  • It keeps track of the "current element" indirectly, by keeping track of the "previous" element. What would be involved in replacing "previous" with "current"? With "next"? When does the term "current" actually make sense?

• Discussion: the ArrayIterator has a (contains a reference to an) ArrayList. Would it be possible for it to have, rather, the array encapsulated by the ArrayList? Would this be desirable?

An Application

The game of Go Fish.

• Rules, p. 143.
• GoFish class (represents a game with two players: human and computer).
• Diagram, Fig. 5-38 on p. 143, shows now very interesting interrelated objects. Diagrams are now becoming useful! Distinguish the "is-a" from the "has-a" relationships in this diagram.

• GoFish.java code listing (pp. 144–148, handout):

  • The play method:

    while loops with empty bodies
      while (...) {
    }
    

    could also be written as:

    while (...)
      ;
    

    where ";" is the empty statement that does nothing.
  • playerTurn method returns boolean bonusTurn—if true, the player gets to go again, used in the while loops of the play methods.
  • computerTurn method likewise returns boolean bonusTurn

  • Could you improve the computer's strategy, which is to ask for a random rank?

• GoFishHand.java code listing (pp. 148–149, handout):

  • Subclass of ArrayList.
  • The give method uses iterator to give all cards of a given rank to the other player.

  • The meldSets method uses iterator collect the "complete" sets of all four cards of the same rank.

    • Why?

Disputation

(1) I'm not convinced that Iterators are so useful here, or in general. Can we try rewriting the give or meldSets method of GoFishHand without using Iterators?

Pseudocode for replacing the iterator loop in give:

i = 0
while i < size:
  card = get(i)
  if card's rank == rank:
    remove(i)
    add card to taker hand
    foundAny = true
  else:
    i++

That doesn't seem more complicated than with the iterator, does it?

If we counted downwards from size−1 to 0, it would be even simpler:

for i = size - 1 down to 0:
  card = get(i)
  if card's rank == rank:
    remove(i)
    add card to taker hand
    foundAny = true

In other words, we can easily do it directly, without the iterator. So why use an iterator?

(2) In general, what we can do with iterators is fairly limited: with each element, we get to observe it (next() method), and we get to delete it (remove() method). What if we wanted to replace it with a different element, or duplicate it, or add a new element?

• We just have to use the collection directly.

(3) It seems that the real usefulness of iterators is when we want people to be able to traverse a collection without knowing the collection's structure. That is, we let them observe (next()) and remove() each element, one after another, in some order, but without implying that the elements are really ordered that way in the collection. That is, we treat the collection in a somewhat abstract way as a collection, rather than a sequence.

• So why not define a fold method?

What I'm saying here probably doesn't make a whole lot of sense when the only iterable collections we've seen are lists. But there are also trees and hash tables, for example.

Okay, sketch a tree and explain what this means.

Iterator exercises

(Maybe discuss) page 150–151: #5.24, 5.25, maybe 5.26 and 5.27

5.5 The Java Collections Framework

• The List, Stack, and Queue data types are very commonly used, and so Java makes them available in its standard library.

  • This set of interfaces and classes is called the "Java Collections Framework" (JCF) The JCF also includes other types of collection classes and interfaces, such as trees and hash tables.
  • Most of the JCF is in the java.util package.
  • Diagram, Fig. 5-49 p. 151, shows some of the interfaces we've covered and their array-based implementations.
  • Look at the API documentation on Sun's Java web site.
  • Point out that all this documentation was generated from Javadoc comments

  • Demonstrate how to run javadoc:

    $ javadoc [packagenames] [sourcefilenames]
    

    See man javadoc for more.

• While we're on the subject of Java tools:

  • jar is an file archiving utility. If you download the source files from Drake's web site, use jar to unpack the archive.

  • Usage:

    $ jar [cxv] [f ARCHIVE] [FILE...]
    

    • c creates archive file
    • x extracts from archive file
    • v verbose (prints each file name)
    • f ARCHIVE identifies the archive file
    • Run man jar for other options

  • Examples:

    • jar cvf drake.jar drake

      creates an archive file 'drake.jar' containing the 'drake' directory and all of its contents

    • jar xvf drake.jar

      extracts all files from 'drake.jar'

  • tar is similar to jar but not associated with Java. Use z to compress with gzip or j to compress with bzip2.

    $ tar cvzf drake.tar.gz drake
    $ tar cvjf drake.tar.bz2 drake
    

Abstract Classes

• Abstract classes are somewhat like interfaces: they may declare abstract methods, which they do not define.
• Unlike an interface, an abstract class may also declare fields and define non-abstract methods.
• Like an interface, an abstract class cannot be instantiated; we can only create instances of subclasses that are non-abstract.
• Define an abstract class if you want a type that has some methods and/or fields defined, and specifies that there are other methods, but leaves their definitions to its subclasses.

• Example: abstract class Stack, Fig. 5-50 p. 153, is not very useful in practice, but does illustrate the point.

  • Look at the declaration for abstract methods pop and push.
• Look at the API documentation for the abstract class AbstractList for a better sense of how abstract classes might be useful. This class provides definitions for many list operations (methods), but assumes the existence of get, set, and size methods. Based on this infrastructure, which is defined only in its subclasses, the AbstractList class defines numerous methods including clear, addAll, equals, and indexOf.

• Note that get and size are declared abstract; set and remove are not, but are described as "optional operations" (bizarre)! The AbstractList class defines methods set and remove, but all they do is throw an exception. Subclasses can provide more meaningful definitions, but are not required to.

  • Maybe not so bizarre after all. In an "immutable" list class, you would certainly choose to not implement these.

Exercises and Problems

(Possibly)

• Discuss exercises, p. 152, maybe 5.28 and 5.29. Just discuss, not program.
• Problems, p. 154–155, #5.35: Deck class based on an ArrayList. Also discuss how easy or hard it would be to do the same for stack and queue classes.
• Projects, p. 155, #5.36: just discuss the proposed abstract ArrayBasedStructure class.

Footnotes