2.1.6 Mutable Wrappers

The simplest form of mutable sequence is a ``box'' (``wrapper'') containing an immutable sequence. In such an formulation of mutable sequences, only the contents of the wrapper object change. The values stored in the field(s) of a wrapper object are immutable. The following abstract class defines a wrapper class for immutable sequences that can be subclassed for any implementation of the Seq interface.

abstract class SeqBox implements Seq {

  /** contents of SeqBox: elts[0],elts[1],...,elts[n-1] */
  protected Seq elts;  

  public T first() { return elts.first(); }
  public Seq rest() { return elts.rest(); }
  public Seq eltAt(int i) { return elts.eltAt(i); }
  public boolean isEmpty() { return elts.isEmpty(); } 
  public Object apply(SeqVisitor v) { return elts.apply(v); }
  public String toString("ListBox" + elts);

  /* mutators */

  /** updates the first element of this to be val */
  public void setFirst(T val) { 
    if (elts.isEmpty()) throw new 
      NoSuchElementException("setFirst(" + val + 
        ") invoked on the empty sequence " + this);
    else elts = elts.rest.cons(val); 
  }

  /** updates element with index i to be val */
  public void setEltAt(final int i, final T val) { 
    elts = (Seq) elts.apply(new SeqVisitor() { // ANONYMOUS INNER CLASS
      int index = i;
      public Object forEmpty(Seq host) { throw new 
        NoSuchElementException("setEltAt(" + i + ", " + val + 
        ") invoked on the empty sequence " + this);
      }
      public Object forCons(Seq host) {
	if (index == 0) return elts.rest().cons(val);
        else {
	  index--;
	  return elts.rest().apply(this).cons(elts.first());
        }
      }
    });
  }
	                   
  /** inserts val in front of s[0] in this */
  public void insertFront(T val) { elts = elts.cons(val); }

  /** removes the first element (with index 0) from this */
  public void removeFront() { elts = elts.rest; }
}

The insertFront method modifies the list it is invoked on, so there is no need for it to return a value and its return type is set to void. Mutator methods often have the return type void because they embody commands that modify objects rather than functions that compute new values based on the value of this.

As with immutable sequences, there are two basic implementation schemes for mutable sequences: linked and contiguous. We will focus our attention on linked representations which are more interesting and versatile that their contiguous counterparts. As you might expect, mutation significantly complicates the implementation of linked representations.

The following ListBox class defines a mutable wrapper class for the List representation of immutable sequences. The easiest way to implement mutable sequences is to define a container class with a field that is an immutable sequence. Then we can update the mutable sequence by modifying the contents of the field in the container object. For example, suppose we have a class List that defines a list representation for immutable sequences of some type T, e.g., the List class sketched above. A simple container class with an elements field of type List is the following:

class ListBox extends SeqBox {

  ListBox() { elts = new Empty.only; }
  ListBox(T val) { elts = new Cons(val, Empty.only); }

  public Seq empty() { return new ListBox(); }
  public Seq cons(T val) { return new ListBox(elts.cons(val)); }
}

A major limitation of the wrapper class formulation of mutable sequences is that the visitor interface can only define functional operations that do not modify this. The efficient operations for this form of mutable lists correspond to the efficient operations on the underlying List class: adding and removing elements at the front of the list. Mutable lists in which elements can only added or removed at the front are called stacks or LIFO lists (LIFO abbreviates "last in, first out").

Finger Exercise Define a class ArrayBox that implements the SeqBox interface using an array of type T for some specific type T. Use DrJava to test your class.