notes13

In Java, a package is a collection of classes and Java interfaces, and possibly subpackages, that trust each other. Packages have three benefits.

1. Packages can contain hidden classes that are used by the package but are not visible or accessible outside the package.
2. Classes in packages can have fields and methods that are visible by all classes inside the package, but not outside.
3. Different packages can have classes with the same name. For example, java.awt.Frame and photo.Frame.

Here are two examples of packages.

1. java.io is a package of I/O-related classes in the standard Java libraries.
2. Homework 4 uses "list", a package containing the classes DList and DListNode. You will be adding two additional classes to the list package.

Package names are hierarchical. java.awt.image.Model refers to the class Model inside the package image inside the package awt inside the package java.

java.lang.System.out.println("My fingers are tired.");

import java.io.File;  // Can now refer to File class, not just java.io.File.
import java.io.*;     // Can now refer to everything in java.io.

java.awt.Frame.add(photo.Frame.canvas);

javac -cp ".:~jrs/classes:libraries.jar" *.java

/* list/SList.java */                |  /* list/SListNode.java */
                                     |
package list;                        |  package list;
                                     |
public class SList {                 |  class SListNode {
  SListNode head;                    |    Object item;
  int size;                          |    SListNode next;
}                                    |  }

javac -g list/SList.java
java list.SList

In java.util there is a standard Java interface for iterating over sequences of objects.

public interface Iterator {
  boolean hasNext();
  Object next();
  void remove();                          // The remove() method is optional.
}

Part of Project 1 is to write a class RunIterator that implements an Iterator for your RunLengthEncoding class. Its purpose is to provide an interface by which other classes can read the runs in your run-length encoding, one by one.

An Iterator is like a bookmark. Just as you can have many bookmarks in a book, you can have many Iterators iterating over the same data structure, each one independent of the others. One Iterator can advance without disturbing other Iterators that are iterating over the same data structure.

The first time next() is called on a newly constructed Iterator, it returns the first item in the sequence. Each subsequent time next() is called, it returns the next item in the sequence. After the Iterator has returned every item in the sequence, every subsequent call to next() throws an exception and halts with an error message. (I find this annoying; I would prefer an interface in which next() returns null. The Java library designers disagree.)

To help you avoid triggering an exception, hasNext() returns true if the Iterator has more items to return, or false if it has already returned every item in the sequence. It is usually considered good practice to check hasNext() before calling next(). (In the next lecture we'll learn how to catch exceptions; that will give us an alternative way to prevent our program from crashing when next() throws an exception.)

There is usually no way to reset an Iterator back to the beginning of the sequence. Instead, you construct a new Iterator.

Most data structures that support Iterators "implement" another interface in java.util called "Iterable".

public interface Iterable {
  Iterator iterator();
}

It is customary for applications that want to iterate over a data structure DS to call DS.iterate(), which constructs and returns a DSIterator whose fields are initialized so it is ready to return the first item in DS.

A benefit of creating an Iterable class with its own Iterator is that Java has a simple built-in loop syntax, a second kind of "for each" loop, that iterates over the items in a data structure. Suppose we design an SList that implements Iterator. The following loop (which can appear in any class) iterates through the items in an SList l.

  for (Object o : l) {
    System.out.println(o);
  }

This loop is equivalent to

  for (Iterator i = l.iterator(); i.hasNext(); ) {
    Object o = i.next();
    System.out.println(o);
  }

To make all this more concrete, here is a complete implementation of an SListIterator class and a partial implementation of SList, both in the "list" package.

/* list/SListIterator.java */

package list;
import java.util.*;

public class SListIterator implements Iterator {
  SListNode n;

  public SListIterator(SList l) {
    n = l.head;
  }

  public boolean hasNext() {
    return n != null;
  }

  public Object next() {
    if (n == null) {
      /* We'll learn about throwing exceptions in the next lecture. */
      throw new NoSuchElementException();                       // In java.util
    }
    Object i = n.item;
    n = n.next;
    return i;
  }

  public void remove() {
    /* Doing it the lazy way.  Remove this, motherf! */
    throw new UnsupportedOperationException("Nice try, bozo."); // In java.lang
  }
}

/* list/SList.java */

package list;
import java.util.*;

public class SList implements Iterable {
  SListNode head;
  int size;

  public Iterator iterator() {
    return new SListIterator(this);
  }

  [other methods here]
}

Observe that an Iterator may mess up or even crash the program if the structure it is iterating over changes. For example, if the node "n" that an SListIterator references is removed from the list, the SListIterator will not be able to find the rest of the nodes.

An Iterator doesn't have to iterate over a data structure. For example, you can implement an Iterator subclass called Primes that returns each successive prime number as an Integer object.