1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: /** @file HashedDictionary.cpp */
6: // Separate chaining resolves collisions
8: // PARTIALLY COMPLETE
10: template <class KeyType, class ItemType>
11: bool HashedDictionary<KeyType, ItemType>::add(const KeyType& searchKey, const ItemType& newItem)
12: {
13: // Create entry to add to dictionary
14: HashedEntry<KeyType, ItemType>* entryToAddPtr =
15: new HashedEntry<KeyType, ItemType>(newItem, searchKey);
16:
17: // Compute the hashed index into the array
18: int itemHashIndex = getHashIndex(searchKey);
19:
20: // Add the entry to the chain at itemHashIndex
21: if (hashTable[itemHashIndex] == nullptr)
22: {
23: hashTable[itemHashIndex] = entryToAddPtr;
24: }
25: else
26: {
27: entryToAddPtr->setNext(hashTable[itemHashIndex]);
28: hashTable[itemHashIndex] = entryToAddPtr;
29: } // end if
30:
31: return true;
32: } // end add
34: template <class KeyType, class ItemType>
35: bool HashedDictionary<KeyType, ItemType>::remove(const KeyType& searchKey)
36: {
37: bool itemFound = false;
38:
39: // Compute the hashed index into the array
40: int itemHashIndex = getHashIndex(searchKey);
41: if (hashTable[itemHashIndex] != nullptr)
42: {
43: // Special case - first node has target
44: if (searchKey == hashTable[itemHashIndex]->getKey())
45: {
46: HashedEntry<KeyType, ItemType>* entryToRemovePtr =
47: hashTable[itemHashIndex];
48: hashTable[itemHashIndex] = hashTable[itemHashIndex]->getNext();
49: delete entryToRemovePtr;
50: entryToRemovePtr = nullptr; // For safety
51: itemFound = true;
52: }
53: else // Search the rest of the chain
54: {
55: HashedEntry<KeyType, ItemType>* prevPtr = hashTable[itemHashIndex];
56: HashedEntry<KeyType, ItemType>* curPtr = prevPtr->getNext();
57: while ((curPtr != nullptr) && !itemFound )
58: {
59: // Found item in chain so remove that node
60: if (searchKey == curPtr->getKey())
61: {
62: prevPtr->setNext(curPtr->getNext());
63: delete curPtr;
64: curPtr = nullptr; // For safety
65: itemFound = true;
66: }
67: else // Look at next entry in chain
68: {
69: prevPtr = curPtr;
70: curPtr = curPtr->getNext();
71: } // end if
72: } // end while
73: } // end if
74: } // end if
75:
76: return itemFound;
77: } // end remove