Keywords: current

Next: 2.1.7.2 Spaghetti References (akin Up: 2.1.7 Extended Mutable Lists Previous: 2.1.7 Extended Mutable Lists

### 2.1.7.1 Formulating Traditional Linked Lists as Objects

The quasi-list representation of mutable sequences includes an extra level of object nesting in the representation of list tails beyond what is present in the conventional ``singly-linked list'' representations that are widely used in procedural programming. A major disadvantage of this data representation is the extra memory required to hold the extra object allocated for each node. The basic singly-linked list representation avoids this extra overhead; it relies on the exactly same data representation as the ``lists as containers'' representation given in Section 2.1.5 with one critical modification: the `first` and `rest` fields of `Cons` objects are mutable. The following Java code implements the `MutSeq` interface using conventional singly-linked lists rather than quasi-lists.

    class MutList implements MutSeq {

      /* fields */
      static final Empty EMPTY = new Empty();  // singleton empty list

      List value;

      /* constructors */
      MutList() { value = EMPTY; }
      private MutList(List v) { value = v; }

      /* visible methods */
      Seq empty() { return new MutList(); }
      Seq cons(Object newElt) { return new MutList(value.cons(newElt)); }

      Object first() { return value.first(); }
      // returns the element s[0]

      Object rest() { return MutList(value.rest()); }
      // returns a MutList containing elements s[1],...,s[n-1]

      Object eltAt(int i) { return value.eltAt(i); }
      // returns the element s[i]

      boolean isEmpty() { return value.isEmpty(); }
      //  yields the number of elements in the sequence

      void insert(Object o) { value = value.cons(o); }
      // returns new MutList with elts o, s[0], s[1], ..., s[n]

      void setFirst(Object o) { value = value.setFirst(o); }

      void setEltAt(int i, final Object val) {  // changes s[i] to val

        class UpdateEltAt implements MutSeqVisitor {
          /* fields */
          int index;       // index of element to be updated

          /* constructor */
          UpdateEltAt(int i) { index = i; }

          /* visit methods */
          Object forEmpty(MutSeq host) { throw
            new IllegalArgumentException("out-of-bounds index in UpdateEltAt");
          }
          Object forCons(MutSeq host) {
            if (index == 0) {
    	  host.setFirst(val);
    	  return null;
            }
            else host.rest().execute(new UpdateEltAt(i-1));
        }
        value = execute(new UpdateEltAt(i));
      }

      void remove() { value = value.rest; }
      // removes s[0] from the sequence

      Object execute(SeqVisitor v) { return value.execute(v); }
      // apply visitor v to value and return result; value is UNCHANGED

      Object execute(MutSeqVisitor v) {
        // apply visitor v to this; value may CHANGE
        if (value == EMPTY) then return v.forEmpty(this)
        else return v.forCons(this);
      }

      private static abstract class List implements Seq {
        abstract void setFirst(Object o};
        abstract List cons(Object o};
        abstract Object first();
        abstract Seq rest();
        abstract boolean isEmpty();
      }
      private class Empty extends List {
        public void setFirst(Object o) {
          throw new IllegalArgumentException(setFirst() applied to empty list");
        }
        public List cons(Object o} { new Cons(o,MutList.this); }
        public Object first() {
          throw new IllegalArgumentException("first() applied to empty list");
        }
        public Seq rest(); ???

          throw new IllegalArgumentException("rest() applied to empty list");
        }
        public int length() { return 0; }
      }
      private static class Cons extends List { ... }
    }

Note that we have defined the `List` classes as inner classes to hide them from clients of `MutList`. This feature distinguishes our representation of basic linked lists from the traditional representation used in procedural languages. By embedding the `Node` class hierarchy inside the definition of the `MutList` class, we have completely hidden the fact that we are using a conventional linked list representation! To client code, `MutList` is semantically indistinguishable from `QuasiList`!

What have we gained? First, the `MutList` class is a more efficient implementation of the `MutSeq` interface corresponding to quasi-lists because it allocates only one object for each list node instead of two. Second, we can easily expand the `MutList` class to include constant-time methods for adding and element to the end of a list and appending to lists. The extended class maintains a reference to the subsequnce containing last element The following `ExtMutList` class provides these new methods. Since the implementation relies on maintaining references to both the first and last nodes of the list (`value` and `last`, the changes to `MutList` required to create `ExtMutList` are non-trivial.

    class ExtMutList implements ExtMutSeq {

      /* fields */
      static final Empty EMPTY = new Empty();  // singleton empty list

      List value;

      /* constructors */
      MutList() { value = EMPTY; }
      private MutList(List v) { value = v; }

      /* visible methods */
      Seq empty() { return new MutList(); }
      Seq cons(Object newElt) { return new MutList(value.cons(newElt)); }

      Object first() { return value.first(); }
      // returns the element s[0]

      Object rest() { return MutList(value.rest()); }
      // returns a MutList containing elements s[1],...,s[n-1] where n=length(this)

      Object eltAt(int i) { return value.eltAt(i); }
      // returns the element s[i]

      int length() { return value.length(); }
      //  yields the number of elements in the sequence

      void insert(Object o) { value = value.cons(o); }
      // returns new MutList with elts o, s[0], s[1], ..., s[n]

      void setFirst(Object o) { value = value.setFirst(o); }

      void setEltAt(int i, final Object val) {  // changes s[i] to val

        class UpdateEltAt implements MutSeqVisitor {
          /* fields */
          int index;       // index of element to be updated

          /* constructor */
          UpdateEltAt(int i) { index = i; }

          /* visit methods */
          Object forEmpty(MutSeq host) { throw
            new IllegalArgumentException("out-of-bounds index in UpdateEltAt");
          }
          Object forCons(MutSeq host) {
            if (index == 0) {
    	  host.setFirst(val);
    	  return null;
            }
            else host.rest().execute(new UpdateEltAt(i-1));
        }
        value = execute(new UpdateEltAt(i));
      }

      void remove() { value = value.rest; }
      // removes s[0] from the sequence

      Object execute(SeqVisitor v) { return value.execute(v); }
      // apply visitor v to value and return result; value is UNCHANGED

      Object execute(MutSeqVisitor v) {
        // apply visitor v to this; value may CHANGE
        if (value == EMPTY) then return v.forEmpty(this)
        else return v.forCons(this);
      }

      private static abstract class List implements Seq {
        abstract void setFirst(Object o};
        abstract List cons(Object o};
        abstract Object first();
        abstract Seq rest();
        abstract int length();
      }
      private class Empty extends List {
        public void setFirst(Object o) {
          throw new IllegalArgumentException(setFirst() applied to empty list");
        }
        public List cons(Object o} { new Cons(o,MutList.this); }
        public Object first() {
          throw new IllegalArgumentException("first() applied to empty list");
        }
        public Seq rest();

          throw new IllegalArgumentException("rest() applied to empty list");
        }
        public int length() { return 0; }
      }
      private static class Cons extends List { ... }
    }

    interface ExtMutSeq extends MutSeq {
      void insertRear(Object e);
      void mutAppend(ExtMutSeq t);
    }

    class ExtMutList extends MutList implements ExtMutSeq {

      /* fields */
      Node value;
      Node last;

      /* relies on default constructor that calls super() */

      /* visible methods */
      Object first() { return value.first(); }
      Seq rest() { return value.rest(); }

      Object eltAt(int i) { return value.eltAt(i); }
      // returns the element s[i]

      int length() { return value.length(); }
      //  yields the number of elements in the sequence

      void insert(Object o) { value = value.cons(o); } /* last ?? */
      // returns new ExtMutList with elts o, s[0], s[1], ..., s[n]

      void setFirst(Object o) { value = value.setFirst(o); }

      void setEltAt(int i, final Object val) {  // changes s[i] to val

        class UpdateEltAt implements MutSeqVisitor {
          /* fields */
          int index;       // index of element to be updated

          /* constructor */
          UpdateEltAt(int i) { index = i; }

          /* visit methods */
          Object forEmpty(MutSeq host) { throw
            new IllegalArgumentException("out-of-bounds index in UpdateEltAt");
          }
          Object forCons(MutSeq host) {
            if (index == 0) {
    	  host.setFirst(val);
    	  return null;
            }
            else host.rest().execute(new UpdateEltAt(i-1));
        }
        value = execute(new UpdateEltAt(i));
      }

      void remove() { value = value.rest; }
      // removes s[0] from the sequence

      Object execute(SeqVisitor v) { return value.execute(v); }
      // apply visitor v to value and return result; value is UNCHANGED

      Object execute(MutSeqVisitor v) {
        // apply visitor v to this; value may CHANGE
        if (value == EMPTY) then return v.forEmpty(this)
        else return v.forCons(this);
      }

      private static abstract class Node {
        abstract void setFirst(Object o};
        abstract void cons(Object o};
        abstract Object first();
        abstract Node next();
        abstract Object eltAt(int i);
        abstract int length();
      }
      private static class Empty extends Node { ... }
      private static class Cons extends Node { ... }
    }

Next: 2.1.7.2 Spaghetti References (akin Up: 2.1.7 Extended Mutable Lists Previous: 2.1.7 Extended Mutable Lists