CPS 100, Spring 2001, Multiset2/Trees

This assignment is designed to give you practice with inheritance and trees. For extra credit you'll explore the relationship between tree-traversals (inorder, preorder, postorder) and tree construction.

Summary of What To Do

1. Implement a new MSApplicant abstract base class and child/sub classes MSPrinter and MSTotal.
2. Add a pure virtual function applyAll to the Multiset base class that uses an MSApplicant object (described more below). Implement the new member function for both the LinkedMultiset and TableMultiset and test this in a modified version of readwords.cpp that's given to you.
3. Implement a new class Tree that has a similar interface to your LinkedList class.
4. Implement a new sub-class of Multiset, TreeMultiset, that implements the multiset interface.
5. Time how long the different implementations of multisets take to process several files and explain the differences you find.

6. Extra Credit: experiment with different implementations of TreeMultiset::applyAll and reason about the implementations.

You will be given one new file for this assignment, a new implementation of readwords.cpp that can be found in ~ola/cps100/multiset2/readwords.cpp on the acpub system. You'll need to use the code you wrote for part 1 of the assignment. However, you should make a copy of your code for this new assignment. To do this you should create a directory cps100/multiset2. You should then copy all the files from your old directory to your new directory:

  cp ~/cps100/multiset ~/cps100/multiset2

1. The class MSApplicant

What to do

• msapplicant.h, stores the declaration for the base class MSApplicant.

• msprinter.h and msprinter.cpp, store the declaration and implementation, respectively, of an MSApplicant subclass named MSPrinter that prints all elements of a multiset.

• mstotal.h and mstotal.cpp, store the declaration and implementation, respectively, of an MSApplicant subclass named MSTotal that calculates the total number of elements in a multiset.

Details

Recall from last week's discussion section the class MSApplicant that serves as an interface/base class for classes that can be passed to a Multiset::applyAll function. For example, to print a multiset you won't have a print function as part of the Multiset class, you'd do something similar to the code below. The class MSPrinter is a subclass of MSApplicant. The function MSPrinter::applyOne would print one line of output as discussed in recitation section.

2. The applyAll functions

What to Do

Details

You should remove the prototypes for functions Multiset::print and Multiset::total since these will be replaced by using Multiset::applyAll and the MSApplicant subclasses MSPrinter and MSTotal you wrote in the first part of this assignment.

In all subclasses of Multiset (this includes LinkedMultiset and TableMultiset) implement applyAll and remove the implementations of total and print.

As we discussed in class and recitation, the applyAll should call MSApplicant::applyOne on each element in the multiset. This means, for example, that for the class LinkedMultiset you should be able to implement applyAll by changing one line of your print implementation. Instead of printing, call MSApplicant::applyOne:

Be sure to test both LinkedMultiset::applyAll and TableMultiset::applyAll in different compiles/runs of readwords.cpp.

3. Trees

What to Do

Use this class Tree to implement a new class TreeMultiset that uses binary search trees as the basis of the multiset. Use this class in readwords.cpp and compare timings with other Multiset implementations.

Details

Class Tree

Your Tree class should include member functions for

• Construction
• Size (# nodes in the tree)
• Adding a value to the tree
• Searching for a value in the tree
• Getting the root of the tree

These functions will be public as will a Tree::Node struct you write that's just like the Node struct in the class LinkedList, but in the tree class the pointers should be labelled as left and right rather than next and prev.

We've gone over code in class for searching for a value and for adding values to a search tree. These should be the basis for the member functions you write for adding and searching. The other functions (construction, size, returning root) are all one line functions (the constructor should use an initializer list). The root of the search tree should be set to NULL/0 when the tree is contructed.

You can write a test program to test this tree class (like the program testlink.cpp) but this isn't required. If you do write a test program, you should note this in your README, and submit it for extra credit.

Class TreeMultiset

You should write the interface to the class in treemultiset.h and the implementation in treemultiset.cpp. The class will be similar to LinkedMultiset but you'll need one (at least) helper function for implementing applyAll.

Here's the code for TreeMultiset::applyAll

The code for TreeMultiset::applyHelp should use a standard inorder tree traversal for visiting all nodes of the tree and calling applicant.applyOne for each node visited. If you do this and use a TreeMultiset in readwords.cpp to test the implementation you should get words printed in alphabetical order.

4. Extra Credit

The idea is for client code to create an empty multiset (say eSet), construct an MSCopy object using eSet, then pass the MSCopy object to the multiset to be copied.

Note that the set used to construct the MSCopy object is filled with values as a result of calling set.applyAll(copy) in the code above.

After implementing this class MSCopy you should develop a program similar to readwords.cpp but which you'll use for timing and testing the copying. Read words from a file and put them in a TreeMultiset. Then make a copy of the multiset using an MSCopy object. You'll then have two tasks:

• Write code, classes, and or applicants to test whether the copying works. To do this properly you should write a function/classes that determines if two multisets are equal. Two multisets a andw b are equal if each contains exactly the same strings and each string occurs the same number of times in both a and b.

• Time the copying part of the code for copying one TreeMultiset to another TreeMultiset (not the equal testing) using an inorder traversal for TreeMultiset::applyHelper and also time using a preorder traversal (swap two lines in the function TreeMultiset::applyHelper). Explain the differences in timings. Be sure to run the program on some text file that's large (but not too large) to get good timings.

Grading

Submit

  submit_cps100 multiset2 *.cpp *.h Makefile README

So that you submit all your .h and .cpp files, your README file, and a Makefile that compiles your program into an executable named readwords.

If submit_cps100 doesn't work, try ~ola/bin/submit100