Algorithms and Data Structures 2005: Sets code

In the Algorithms and Data Structures course, the simple abstract data type 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.

Set implementations

Here is a guide to the various implementations of sets:

IntSet1 Set stored as unordered partly filled array of integers ("array and count" technique).
IntSet2 As IntSet1 but introduces a toString method (used in all subsequent examples) which is more versatile than a print method.
IntSet3 Set stored as ordered partly filled array of integers. Makes addition and deletion of elements more complex, but enables membership test to be done by the more efficient binary search algorithm.
IntSet4 Set stored as an array of booleans. Shows a completely different way of representing sets of integers. More efficient, but means integers can only come from a limited range.
IntSet5 Set stored as an ordered fully-filled array of integers. More efficient in terms of space, but less efficient in terms of time, as a whole new array must be created every time an element is added or deleted.
IntSet6 Adds a copy method to the code for IntSet5. Uses inheritance to build on existing code rather than rewriting code from scratch.
IntSet7 A constructive implementation of sets using fully-filled arrays of integers. Instead of the add and delete methods changing the set they are called on, they return a new set with the required change while leaving the old set unchanged.
IntSet8 A constructive implementation of sets using arrays of integers, with the addition of a union and an intersection method. Also has a static method fromString which converts the string representation of a set to a set object.
IntSet9 A constructive implementation of sets using arrays of integers, including union and intersection implemented efficiently i.e. directly handling the arrays of both sets being combined to form a new set.
IntSet10 A constructive implementation of sets using arrays of booleans. Same technique as IntSet4, but constructive rather than destructive. Also includes union, intersection and fromString methods.
IntSet11 Set stored as an unordered linked list, destructive implementation using iteration. Only basic operations: add, delete and member, plus toString. Includes nested class Cell for linked list cells.
IntSet11a Adds copy method to IntSet11 by inheritance. Copy method uses iteration.
IntSet11b Adds copy method to IntSet11 by inheritance. Copy method uses recursion.
IntSet11c Adds copy method to IntSet11 by inheritance. Copy method uses iteration with "stack and reverse" technique.
IntSet11d Adds 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.
IntSet12 Set stored as an ordered linked list, destructive implementation using iteration.
IntSet13 Set stored as an ordered binary tree, destructive implementation using iteration.
IntSet14 Set stored as an ordered linked list, destructive implementation. Methods implemented using recursion rather than iteration.
IntSet14a Set stored as unordered linked list, destructive implementation using recursion.
IntSet15 Set stored as an ordered linked list with dummy first cell, destructive implementation. Methods implemented using recursion.
IntSet16 Set stored as an ordered tree, destructive implementation. Methods implemented using recursion.
IntSet17 Set stored as unordered linked list, constructive implementation using recursion for deletion.
IntSet17a Set stored as unordered linked list, constructive implementation using iteration for deletion.
IntSet18 Set stored as ordered trees, constructive implementation using recursion.

"Front-end" or "driver" classes

The important thing in this course is the code which implements algorithms and data structures. However, in order that this code can be run and tested it is necessary to have a framework which makes use of it. Therefore classes have been introduced which provide such a "front-end". These classes need to interact with the human user and therefore involve use of some of Java's complicated input/output code. Please note that it is not required for this course that you study these front-end classes or understand how they work. Please, in fact, forget them, they are not important.

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 This first version doesn't use a separate class to store sets as objects. Sets are represented as an array and count pair, but the code manipulating it is mixed up with the code providing the "front-end".
UseIntSets2 As with 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.
UseIntSets3 This and all subsequent 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.
UseIntSets4 As 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.
UseIntSets5 The only difference between this and UseIntSets4 is that it causes sets to be represented by the IntSets3 class rather than the IntSets2 class.
UseIntSets6 The only difference between this and UseIntSets4 is that it causes sets to be represented by the IntSets4 class rather than the IntSets2 class.
UseIntSets7 The only difference between this and UseIntSets4 is that it causes sets to be represented by the IntSets5 class rather than the IntSets2 class.
UseIntSets8 Adds an "undo" command (type 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.
UseIntSets8a The only difference between this and UseIntSets8 is that it causes sets to be represented by the IntSets11a class rather than the IntSets6 class.
UseIntSets8b The only difference between this and UseIntSets8 is that it causes sets to be represented by the IntSets11b class rather than the IntSets6 class.
UseIntSets8c The only difference between this and UseIntSets8 is that it causes sets to be represented by the IntSets11c class rather than the IntSets6 class.
UseIntSets8d The only difference between this and UseIntSets8 is that it causes sets to be represented by the IntSets11d class rather than the IntSets6 class.
UseIntSets9 A set maintenance program with an "undo" just like 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.
UseIntSets10 The only difference between this and UseIntSets4 is that it causes sets to be represented by the IntSets11 class rather than the IntSets2 class.
UseIntSets11 The only difference between this and UseIntSets4 is that it causes sets to be represented by the IntSets12 class rather than the IntSets2 class.
UseIntSets12 The difference between this and 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.
UseIntSets13 The only difference between this and UseIntSets4 is that it causes sets to be represented by the IntSets14 class rather than the IntSets2 class.
UseIntSets13a The only difference between this and UseIntSets4 is that it causes sets to be represented by the IntSets14a class rather than the IntSets2 class.
UseIntSets14 The only difference between this and UseIntSets4 is that it causes sets to be represented by the IntSets15 class rather than the IntSets2 class.
UseIntSets15 The only difference between this and UseIntSets4 is that it causes sets to be represented by the IntSets16 class rather than the IntSets2 class.
UseIntSets15a The difference between this and UseIntSets15 is that it has a command t which enables the tree representation of the set to be viewed.
UseIntSets16 The only difference between this and UseIntSets9 is that it causes sets to be represented by the IntSets17 class rather than the IntSets7 class.
UseIntSets16a The only difference between this and UseIntSets9 is that it causes sets to be represented by the IntSets17a class rather than the IntSets7 class.
UseIntSets17 The difference between this and 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.

Matthew Huntbach

Last modified: 13 April 2005