class ArrayDictionary
1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: // Listing 18-3.
6: /** An array-based 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 ArrayDictionary.h */
10:
11: #ifndef _ARRAY_DICTIONARY
12: #define _ARRAY_DICTIONARY
14: #include "DictionaryInterface.h"
15: #include "Entry.h"
16: #include "NotFoundException.h"
18: template <class KeyType, class ItemType>
19: class ArrayDictionary : public DictionaryInterface<KeyType, ItemType>
20: {
21: private:
22: static const int DEFAULT_CAPACITY = 21; // Small capacity to test for
23: // a full dictionary
24: Entry<KeyType, ItemType>* items; // Array of dictionary entries
25: int itemCount; // Current count of dictionary items
26: int maxItems; // Maximum capacity of the dictionary
27: void destroyDictionary();
28: int findEntryIndex(int firstIndex, int lastIndex,
29: const KeyType& searchKey) const;
30: public:
31: ArrayDictionary();
32: ArrayDictionary(int maxNumberOfEntries);
33: ArrayDictionary(const ArrayDictionary<KeyType, ItemType>& dict);
34:
35: virtual ~ArrayDictionary();
36:
37: bool isEmpty() const;
38: int getNumberOfItems() const;
39: bool add(const KeyType& searchKey, const ItemType& newItem);
40: bool remove(const KeyType& searchKey);
41: void clear();
42: ItemType getItem(const KeyType& searchKey) const throw (NotFoundException);
43: bool contains(const KeyType& searchKey) const;
44:
45: /** Traverses the items in this dictionary in sorted search-key order
46: and calls a given client function once for each item. */
47: void traverse(void visit(ItemType&)) const;
48: }; // end ArrayDictionary
50: #include "ArrayDictionary.cpp"
51: #endif