// From the software distribution accompanying the textbook // "A Practical Introduction to Data Structures and Algorithm Analysis, // Third Edition (C++)" by Clifford A. Shaffer. // Source code Copyright (C) 2007-2011 by Clifford A. Shaffer. #include "dictionary.h" #include "KVpair.h" #include "salist.h" // Dictionary implemented with a sorted array-based list template class SALdict : public Dictionary { private: SAList* list; public: SALdict(int size=defaultSize) // Constructor { list = new SAList(size); } ~SALdict() { delete list; } // Destructor void clear() { list->clear(); } // Reinitialize // Insert an element: Keep elements sorted void insert(const Key&k, const E& e) { KVpair temp(k, e); list->insert(temp); } // Use sequential search to find the element to remove E remove(const Key& k) { E temp = find(k); if (temp != NULL) list->remove(); return temp; } E removeAny() { // Remove the last element Assert(size() != 0, "Dictionary is empty"); list->moveToEnd(); list->prev(); KVpair e = list->remove(); return e.value(); } // Find "K" using binary search E find(const Key& k) const { int l = -1; int r = list->length(); while (l+1 != r) { // Stop when l and r meet int i = (l+r)/2; // Check middle of remaining subarray list->moveToPos(i); KVpair temp = list->getValue(); if (k < temp.key()) r = i; // In left if (k == temp.key()) return temp.value(); // Found it if (k > temp.key()) l = i; // In right } return NULL; // "k" does not appear in dictionary } int size() // Return list size { return list->length(); } };