class TreeDictionary
1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: // Listing 18-4.
6: /** A binary search tree implementation of the ADT dictionary
7: that organizes its data items in sorted search-key order.
8: Search keys in the dictionary are unique.
9: @file TreeDictionary.h */
10:
11: #ifndef _TREE_DICTIONARY
12: #define _TREE_DICTIONARY
14: #include "DictionaryInterface.h"
15: #include "BinarySearchTree.h"
16: #include "Entry.h"
17: #include "NotFoundException.h"
19: template <class KeyType, class ItemType>
20: class TreeDictionary : public DictionaryInterface<KeyType, ItemType>
21: {
22: private:
23: // Binary search tree of dictionary entries
24: BinarySearchTree<Entry<KeyType, ItemType> > itemTree;
25:
26: void traversalHelper(Entry<KeyType, ItemType>& theEntry);
27:
28: public:
29: TreeDictionary();
30: TreeDictionary(const TreeDictionary<KeyType, ItemType>& dict);
31: virtual ~TreeDictionary();
32:
33: // The declarations of the public methods appear here and are the
34: // same as given in Listing 18-3 for the class ArrayDictionary.
35:
36: bool isEmpty() const;
37: int getNumberOfItems() const;
38: bool add(const KeyType& searchKey, const ItemType& newItem);
39: bool remove(const KeyType& searchKey);
40: void clear();
41: ItemType getItem(const KeyType& searchKey) const throw (NotFoundException);
42: bool contains(const KeyType& searchKey) const;
43:
44: /** Traverses the items in this dictionary in sorted search-key order
45: and calls a given client function once for each item. */
46: void traverse(void visit(ItemType&)) const;
47: }; // end TreeDictionary
49: #include "TreeDictionary.cpp"
50: #endif