class ArrayDictionary
1: // Created by Frank M. Carrano and Timothy M. Henry.
2: // Copyright (c) 2017 Pearson Education, Hoboken, New Jersey.
4: // Listing 18-3.
6: /** An array-based implementation of the ADT dictionary
7: that organizes its entries 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"
17: #include "PrecondViolatedExcept.h"
19: template <class KeyType, class ValueType>
20: class ArrayDictionary : public DictionaryInterface<KeyType, ValueType>
21: {
22: private:
23: static const int DEFAULT_CAPACITY = 21; // Small capacity to test for a full dictionary
24: std::unique_ptr<Entry<KeyType, ValueType>[]> entries; // Array of dictionary entries
25: int entryCount; // Current count of dictionary entries
26: int maxEntries; // Maximum capacity of the dictionary
27:
28: void destroyDictionary();
29: int findEntryIndex(int firstIndex, int lastIndex, const KeyType& searchKey) const;
30:
31: public:
32: ArrayDictionary();
33: ArrayDictionary(int maxNumberOfEntries);
34: ArrayDictionary(const ArrayDictionary<KeyType, ValueType>& dictionary);
35: virtual ~ArrayDictionary();
36:
37: bool isEmpty() const;
38: int getNumberOfEntries() const;
39:
40: bool add(const KeyType& searchKey, const ValueType& newValue) throw(PrecondViolatedExcept);
41: bool remove(const KeyType& searchKey);
42: void clear();
43:
44: ValueType getValue(const KeyType& searchKey) const throw(NotFoundException);
45: bool contains(const KeyType& searchKey) const;
46:
47: /** Traverses the entries in this dictionary in sorted search-key order
48: and calls a given client function once for the value in each entry. */
49: void traverse(void visit(ValueType&)) const;
50: }; // end ArrayDictionary
52: #include "ArrayDictionary.cpp"
53: #endif