print-all-words-using-iterator
In this lab, you will implement 3 functions that use iterators to answer questions about prefix trees. The functions you need to implement are as follows:
- void print_all_words_with_iterator(const PrefixTree& pt): prints all of the words in the given prefix tree
- int rank_word_with_iterator(string word, const PrefixTree& pt): returns the rank of the given word in the prefix tree (1 if it’s the first word, 2 if it’s the second, etc.); return -1 if word is not in the tree
- void print_common_words_with_iterators(const PrefixTree& lhs, const PrefixTree& rhs): prints all of the words that are in both of the given trees
You have been provided with an implementation of a PrefixTree that features an iterator (but no printAllWords member function). You can create the iterator with the begin() and end() member functions of PrefixTree: begin() starts with the first word in the tree alphabetically, and end() is an empty string after the last word in the tree. This iterator is an output iterator: it can output a single string when dereferenced, and it will move to the next string in sorted order when incremented, but it cannot be used to modify the PrefixTree. The PrefixTreeIterator only supports the prefix increment operator (++it), not the postfix increment operator (it++).
You have also been provided with a driver file to help you get started. You should submit the driver file with implementations of the 3 functions above filled in. The new driver will call print_all_words_with_iterator when you type “list” at the prompt, rank_word_with_iterator when you type “rank [word]”, and print_common_words_with_iterator when you type “compare [tree]”. The tree should be typed either the same way that it gets printed by “print” or as a comma-separated list of words in parentheses (no spaces!). The driver also supports the command “input [tree]” which clears the words in the current tree and replaces it with the given tree.
Files:
Example test cases:
input (bE(D,E,sT),caT)
list
rank best
rank worst
compare (b(a(R,T),EsT),ca(RT,T),doG)
Expected output for list (print_all_words_with_iterator):
be
bed
bee
best
cat
Expected output for rank best (rank_word_with_iterator): best is rank 4 alphabetically
Expected output for rank worst: worst has been not added
Expected output for compare (print_common_words_with_iterators):
be
best
cat
