// 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. // Implementation for a dictionary based on Skiplists #include "book.h" #include "skiplist.h" // Warning: This test driver has horrible memory leaks. // Everytime the program does a remove to "it", the next time "it" // gets used, that previous Int object gets clobbered. int main() { SkipList sl; Int* it; cout << "Size: " << sl.size() << "\n"; sl.insert(100, new Int(100)); sl.print(); cout << "Size: " << sl.size() << "\n"; it = sl.remove(10); sl.print(); cout << "Size: " << sl.size() << "\n"; sl.clear(); cout << "Size: " << sl.size() << "\n"; sl.insert(15, new Int(15)); cout << "Size: " << sl.size() << "\n"; if ((it = sl.find(20)) != NULL) cout << "Found " << it << endl; else cout << "No key 20\n"; if ((it = sl.find(15)) != NULL) cout << "Found " << it << endl; else cout << "No key 15\n"; sl.print(); if ((it = sl.remove(20)) != NULL) cout << "Removed " << it << endl; else cout << "No key 20\n"; cout << "Now, insert 20\n"; sl.insert(20, new Int(20)); sl.print(); if ((it = sl.remove(20)) != NULL) cout << "Removed " << it << endl; else cout << "No key 20\n"; sl.print(); sl.insert(700, new Int(700)); cout << "Size: " << sl.size() << "\n"; sl.insert(350, new Int(350)); sl.insert(201, new Int(201)); sl.insert(170, new Int(170)); sl.insert(151, new Int(151)); sl.insert(190, new Int(190)); sl.insert(1000, new Int(1000)); sl.insert(900, new Int(900)); sl.insert(950, new Int(950)); sl.insert(10, new Int(10)); sl.print(); if ((it = sl.find(1000)) != NULL) cout << "Found " << it << endl; else cout << "No key 1000\n"; if ((it = sl.find(999)) != NULL) cout << "Found " << it << endl; else cout << "No key 999\n"; if ((it = sl.find(20)) != NULL) cout << "Found " << it << endl; else cout << "No key 20\n"; cout << "Now do some delete tests.\n"; if ((it = sl.remove(15)) != NULL) cout << "Removed " << it << endl; else cout << "No key 15\n"; sl.print(); if ((it = sl.remove(151)) != NULL) cout << "Removed " << it << endl; else cout << "No key 151\n"; sl.print(); if ((it = sl.remove(151)) != NULL) cout << "Removed " << it << endl; else cout << "No key 151\n"; if ((it = sl.remove(700)) != NULL) cout << "Removed " << it << endl; else cout << "No key 700\n"; sl.print(); sl.clear(); sl.print(); cout << "Size: " << sl.size() << "\n"; cout << "Finally, test iterator\n"; sl.insert(3500, new Int(3500)); sl.insert(2010, new Int(2010)); sl.insert(1700, new Int(1700)); sl.insert(1510, new Int(1510)); sl.insert(1900, new Int(1900)); sl.insert(10000, new Int(10000)); sl.insert(9000, new Int(9000)); sl.insert(9500, new Int(9500)); sl.insert(100, new Int(100)); sl.print(); // while (sl.size() > 0) // cout << sl.removeAny() << " "; // cout << "\n"; return 0; }