1: // Created by Frank M. Carrano and Tim Henry.
2: // Copyright (c) 2013 __Pearson Education__. All rights reserved.
4: /** @file ArrayDictionary */
6: // PARTIALLY COMPLETE
8: template <class KeyType, class ItemType>
9: bool ArrayDictionary<KeyType, ItemType>::add(const KeyType& searchKey, const ItemType& newItem)
10: {
11: bool ableToInsert = (itemCount < maxItems);
12: if (ableToInsert)
13: {
14: // Make room for new entry by shifting all entries at
15: // positions >= newPosition toward the end of the array
16: // (no shift if newPosition == itemCount + 1). Performing
17: // a binary search doesn’t help here, because we need to
18: // shift the entries while looking for the insertion location.
19: int index = itemCount;
20:
21: // Short-circuit evaluation is important
22: while ( (index > 0) && (searchKey < items[index - 1].getKey()) )
23: {
24: items[index] = items[index - 1];
25: index--;
26: } // end while
27:
28: // Insert new entry
29: items[index] = Entry<KeyType, ItemType>(newItem, searchKey);
30: itemCount++; // Increase count of entries
31: } // end if
32:
33: return ableToInsert;
34: } // end add