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 { ... }
}