|
CS210 - Algorithms and Data Structures I Department of Computer Science National University of Ireland, Maynooth |
|
|
CS210 - Algorithms and Data Structures I Department of Computer Science National University of Ireland, Maynooth |
T Naughton, NUIM
Back to CS210 home
Laboratory Sheet 8
ADTs (incl. searching & sorting) In this lab you will continue to design and write code for abstract data types. Answer Problem 8.1. You might find Sun's Java API reference pages useful. Specifications of the Object/Integer/String classes and the Comparable interface can be found here (click on the java.lang package and scroll down the list). Also see definitions of built-in array sorting and searching methods (click on the java.util package and choose the Arrays class).
An array-based set class
We will continue to develop an array-based set class. Build on your solution to Lab Sheet 7. Here is one possible solution (MyLittleArraySetVer2) to Lab Sheet 7. It has the following test program MyLittleArraySetVer2Tester and it prints the following sample output.
Our set class currently has the following functionality: it can create an empty set, create a set with one element, check if an element is in the set, return the cardinality of the set, and check if a set is empty.
The first improvement we will make will be to allow sets of more than one element to be created. This would mean defining a new constructor that takes an array of elements as an argument (a conversion constructor). We also need a constructor that takes an existing set (a copy constructor). As a reminder, here are examples of the three types of constructors (for the String class) in action.
String a, b, c;
char data[] = {'a', 'b', 'c'};
// default constructor
a = new String(); // a is an empty string
// conversion constructor
b = new String(data); // b is "abc"
// copy constructor
c = new String(b); // c is "abc"
// combining conversion & copy constructors
c = new String(new String("bbb")); // c is "bbb"
When the conversion constructor of our set class is passed an array, it will have to remove the duplicates from the array before storing it as a set. This is because we cannot trust the client (the user program) to pass us a suitable array. (This is a very prudent practice!) It might therfore be a good idea to order this array (i.e. ensure that the array is sorted). This will speed up the removal of duplicates (as seen in lectures). If we then also ensure that the internal representation of the set elements is also ordered we can improve our searching algorithm. Instead of a sequential search of O(n) we could employ a O(log n) binary search (as seen in lectures).
As can be seen from Sun's definition of the Object class, Objects can only test for equality (with equals()). What we need are objects for whom a relative order can be determined. The Comparable interface defines a compareTo() method that allows us to determine if one object is "less than" another. Luckily, many Object classes implement this interface. So, from now on, we will store Comparable objects in our set. Algorithms for sorting and searching arrays of Comparable objects can be found at Sun's Java API reference web pages (see web address above).
A method is also required to extract the array elements from a set. This will be used by the copy constructor and also by the union, intersection, and set subtraction operators. This method (let's call it toArray()) returns a copy of the array of references to the objects within its set. It is important to return a copy of the array of references (a newly created array of the same length that has the same references), rather than a copy of the reference to the array (a newly created reference that points to the same array). We should not trust the client and so should not give out references to our private data. If one really needed to do such a thing (to avoid spending resources for a copying operation), this method should be made private, so that only clients of the same class (or derived from this class) could get access to the private reference.
Here is the skeleton code for such an array-based set class MyLittleArraySetVer3.
Problem 8.1 Complete the ADT by writing code for the unfinished methods. Test your ADT by running the following test program MyLittleArraySetVer3Tester. Your program should print something like this sample output.