Set
is used, firstly to illustrate the concept
of abstract data types, and then to illustrate how a great variety of
data structures may be used to give different implementations of this
one simple concept of a Set.
A set is defined as a collection of elements which has no concept of an element occurring a multiple number of times, and no concept of the elements having any order. So the only operations on a set are to add a new item, delete an existing item, and test whether a particular item is a member of the set. To keep things simple, we said there would be no operations that would result in "error" conditions. So deleting an item from a set in which that item is a not a member is a possible operation which just leaves the set unchanged, and adding an item to a set where it is already a member is a possible operation and leaves the set unchanged. Also to keep things simple we dealt only with sets of integers.
IntSet1
but introduces a toString
method (used in all subsequent examples) which is more versatile
than a print
method.
copy
method to the code for IntSet5
.
Uses inheritance to build on existing code
rather than rewriting code from scratch.
union
and an
intersection
method. Also has a static method
fromString
which converts the string representation
of a set to a set object.
union
and intersection
implemented
efficiently i.e. directly handling the arrays of both sets being
combined to form a new set.
IntSet4
, but constructive rather than
destructive. Also includes union
, intersection
and fromString
methods.
add
, delete
and member
,
plus toString
. Includes nested class Cell
for linked list cells.
copy
method to IntSet11
by inheritance.
Copy method uses iteration.
copy
method to IntSet11
by inheritance.
Copy method uses recursion.
copy
method to IntSet11
by inheritance.
Copy method uses iteration with "stack and reverse" technique.
copy
method to IntSet11
by inheritance.
Copy method uses iteration with stacking but no reversing - acceptable
in this case, since the order doesn't matter with sets.
For sets, the front-end class in most cases provides a main
method (when you run a Java program, the main
method is
where execution starts) which gives a very simple text-based program
allowing the user to issue commands to manipulate a set. The program
is not meant to be a good example of application design. It is
designed to be as simple as possible in order that you should not be
distracted by it. The idea is that there is a single set which is
manipulated by commands typed in by the user. Initially the set
is empty. The command p
prints a representation of the
set. The command a
followed by a number on the same
line adds that number to the set (if you use p
again after
that, you can see the change). The command d
followed by
a number deletes the number from the set. The command m
followed by a number causes a message to be printed saying whether
the number is in the set. For simplicity, adding a number to the set
when it is already there, or deleting one which isn't there causes no
change (rather than, for example, some sort of error condition). The
command q
causes the set manipulation program to halt.
Below are listed the various forms of the program used:
UseIntSets1
, doesn't have a separate class
for sets. The code for manipulating the array and count
used to represent a set is put into separate methods for each
operation, but in the same class as the "front-end" main
method.
UseIntSets
programs have the
sets represented by a separate class, and the add
,
delete
and member
operations
represented by the public methods of the class. Here the sets
are represented by objects of class IntSet1
.
UseIntSets2
but sets represented by IntSet2
objects. This means that there is no explicit call to a print
method in sets to print them, instead the toString
method
is called implicitly. All subsequent UseIntSets
programs
will print text representation of sets using toString
.
UseIntSets4
is that it causes sets to be represented by the
IntSets3
class rather than the IntSets2
class.
UseIntSets4
is that it causes sets to be represented by the
IntSets4
class rather than the IntSets2
class.
UseIntSets4
is that it causes sets to be represented by the
IntSets5
class rather than the IntSets2
class.
u
) to the set manipulation
program. Isuing this command causes the current set to return to the
set before the last change. This is done by using IntSet6
to represent sets, so that a copy of a set can be made before it is
changed.
UseIntSets8
is that it causes sets to be represented by the
IntSets11a
class rather than the IntSets6
class.
UseIntSets8
is that it causes sets to be represented by the
IntSets11b
class rather than the IntSets6
class.
UseIntSets8
is that it causes sets to be represented by the
IntSets11c
class rather than the IntSets6
class.
UseIntSets8
is that it causes sets to be represented by the
IntSets11d
class rather than the IntSets6
class.
UseIntSets8
. However, sets are represented by the
constructive IntSet7
, and instead of the old set being
copied, a reference is made to it for use if the "undo" command is
given, while the reference to the current set is re-assigned to the
result of the constructive method.
UseIntSets4
is that it causes sets to be represented by the
IntSets11
class rather than the IntSets2
class.
UseIntSets4
is that it causes sets to be represented by the
IntSets12
class rather than the IntSets2
class.
UseIntSets4
is that it causes sets to be represented by the
IntSets13
class rather than the IntSets2
class, and it has a command t
which enables the tree
representation of the set to be viewed.
UseIntSets4
is that it causes sets to be represented by the
IntSets14
class rather than the IntSets2
class.
UseIntSets4
is that it causes sets to be represented by the
IntSets14a
class rather than the IntSets2
class.
UseIntSets4
is that it causes sets to be represented by the
IntSets15
class rather than the IntSets2
class.
UseIntSets4
is that it causes sets to be represented by the
IntSets16
class rather than the IntSets2
class.
UseIntSets15
is that
it has a command t
which enables the tree
representation of the set to be viewed.
UseIntSets9
is that it causes sets to be represented by the
IntSets17
class rather than the IntSets7
class.
UseIntSets9
is that it causes sets to be represented by the
IntSets17a
class rather than the IntSets7
class.
UseIntSets9
is that it causes sets to be represented by the
IntSets18
class rather than the IntSets7
class, and it has a command t
which enables the tree
representation of the set to be viewed.