List. When we implemented
sets using linked lists, the type for the actual cells of the linked list
was included within the class for sets. But now we are considering an
implementation using a type that has already been made available through
the class List. So we are in fact implementing one
abstract data type (Set, but in line with the previous
implementations we shall use the name IntSet19) in terms
of another one (List) which in turn is implemented by a
data structure. So, for example, the set {5,9,7,2}
is implemented by the list [5,9,7,2] which in
turn is implemented by a chain of cells storing these numbers. If
s is a variable of type IntSet19 this can
be illustrated diagrammatically as:
The code for IntSet19, implementing sets using the
abstract data type List is:
class IntSet19
{
// Constructive Set class,
// implemented using unordered ADT Lists
private List list;
public IntSet19()
{
list = List.empty();
}
private IntSet19(List l)
{
list = l;
}
public IntSet19 delete(int n)
{
List list1 = delete(n,list);
return new IntSet19(list1);
}
private static List delete(int n,List l)
{
if(l.isEmpty())
return List.empty();
else if(l.head()==n)
return l.tail();
else
return delete(n,l.tail()).cons(l.head());
}
public IntSet19 add(int n)
{
List ptr;
for(ptr=list; !ptr.isEmpty()&&ptr.head()!=n; ptr=ptr.tail());
if(ptr.isEmpty())
{
List list1 = list.cons(n);
return new IntSet19(list1);
}
else
return this;
}
public boolean member(int n)
{
List ptr;
for(ptr=list; !ptr.isEmpty()&&ptr.head()!=n; ptr=ptr.tail());
return (!ptr.isEmpty());
}
public String toString()
{
String str="{";
if(!list.isEmpty())
{
str+=list.head();
for(List ptr=list.tail(); !ptr.isEmpty(); ptr=ptr.tail())
str+=","+ptr.head();
}
return str+"}";
}
}
It is very similar to the code which implemented sets constructively
but directly using linked lists we gave
previously. However, an empty set is
represented by an empty List, produced using the call
List.empty() rather than by null. The call
List.empty() produces a List object whose
llist field is null, so an empty set is
represented by an object whose list field refers to
an object whose llist field is null. In
general an object representing a set has a private field called
list which refers to a List object which in
turn has a private field called llist which refers to
a Cell object.
Apart from this, where the representation which directly uses linked lists
calls on the first field of a Cell object, the
representation using Lists calls on the head
method of a List object. Similarly, where the representation
which directly uses linked lists calls on the next field of a
Cell object, the representation using Lists calls
on the tail method of a List object. Where a
new Cell whose first field is set to
n and whose next field is set to l
is created by new Cell(n,l), a new List whose
head is n and whose tail is l is created by
l.cons(n).
Tree which matches
the tree structure used previously
to represent sets. As with our abstract data type
List the abstract data type Tree we give
below has only constructive methods. Therefore it acts as a way to
protect against the temptation to implement some operation destructively
which could have unexpected side-effects due to shared data not being
taken into account.
Here is the code for Tree:
class Tree
{
private Cell tree;
public static Tree empty()
{
return new Tree(null);
}
private Tree(Cell l)
{
tree=l;
}
public int item()
{
return tree.item;
}
public Tree left()
{
return new Tree(tree.left);
}
public Tree right()
{
return new Tree(tree.right);
}
public static Tree make(int n,Tree l,Tree r)
{
return new Tree(new Cell(n, l.tree,r.tree));
}
public boolean isEmpty()
{
return tree==null;
}
private static class Cell
{
int item;
Cell left,right;
Cell(int n,Cell l,Cell r)
{
item=n;
left=l;
right=r;
}
}
}
In this case, the names of the methods left,
right and item are the same as the names
of the fields of Cell objects. This does not cause
a problem because it is always clear which is meant: they mean the
field only when attached to a reference to a Cell object
which can only occur within the class Tree.
Also there is no direct equivalent to the List method
cons which is called on a List object and
returns an object representing the list of that List
object with an extra element (given as the argument to cons)
joined to its front. Instead there is a method in class Tree
which we have called make which is static so
it isn't called on any Tree object. Instead it is called
attached to the class name Tree, and takes as its arguments
three values, an integer (when we are dealing with trees of integers)
and two trees and returns the tree object made up by putting these
values together, so Tree.make(n,l,r) returns the tree whose
node value in n, whose left subtree is l and
whose right subtree is r.
We can represent sets using the abstract data type Tree.
Just as the code for the representation using the abstract data type
List closely resembled the code for representing sets
with construtive methods using linked lists, so the code the
representation using the abstract data type Tree closely
resembles the code for representing sets with constructive methods using
linked tree structures:
class IntSet20
{
// Constructive Set class, sets stored as ordered ADT trees
private Tree tree;
public IntSet20()
{
tree=Tree.empty();
}
private IntSet20(Tree t)
{
tree=t;
}
public IntSet20 delete(int n)
{
return new IntSet20(delete(n,tree));
}
private static Tree delete(int n,Tree t)
{
if(t.isEmpty())
return Tree.empty();
else if(n<t.item())
return Tree.make(t.item(),delete(n,t.left()),t.right());
else if(n>t.item())
return Tree.make(t.item(),t.left(),delete(n,t.right()));
else if(t.left().isEmpty())
return t.right();
else if(t.right().isEmpty())
return t.left();
else
{
int m=rightmost(t.left());
Tree newleft=removeRightmost(t.left());
return Tree.make(m,newleft,t.right());
}
}
private static int rightmost(Tree t)
{
if(t.right().isEmpty())
return t.item();
else
return rightmost(t.right());
}
private static Tree removeRightmost(Tree t)
{
if(t.right().isEmpty())
return t.left();
else
return Tree.make(t.item(),t.left(),removeRightmost(t.right()));
}
public IntSet20 add(int n)
{
return new IntSet20(add(n,tree));
}
private static Tree add(int n, Tree t)
{
if(t.isEmpty())
return Tree.make(n,Tree.empty(),Tree.empty());
else if(n==t.item())
return t;
else if(n<t.item())
return Tree.make(t.item(),add(n,t.left()),t.right());
else
return Tree.make(t.item(),t.left(),add(n,t.right()));
}
public boolean member(int n)
{
return member(n,tree);
}
private static boolean member(int n,Tree t)
{
if(t.isEmpty())
return false;
else if(t.item()==n)
return true;
else if(n<t.item())
return member(n,t.left());
else
return member(n,t.right());
}
public String toString()
{
return "{"+toString(tree)+"}";
}
private static String toString(Tree tree)
{
if(tree.isEmpty())
return "";
else if(tree.left().isEmpty()&&tree.right().isEmpty())
return ""+tree.item();
else if(tree.left().isEmpty())
return tree.item()+","+toString(tree.right());
else if(tree.right().isEmpty())
return toString(tree.left())+","+tree.item();
else
return toString(tree.left())+","+tree.item()+","+toString(tree.right());
}
}
Last modified: 3 October 2001