// 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. // This is an outline for a B+ tree implementation. Primarily, // this code tests the syntax for the outline. It is not a working, // concrete implementation. #include "book.h" #include "dictionary.h" #include "BPnode.h" template class BPTree : public Dictionary { private: BPNode* root; int reccount; E findhelp(BPNode* root, const Key k) const; BPNode* inserthelp(BPNode* root, const Key& k, const E& e); bool removehelp(BPNode* root, const Key& k); // Stub for a binary search on the key array int binaryle(Key keys[], int cnt, const Key k) const { return 0; } public: BPTree() { root = NULL; reccount = 0; } ~BPTree() {}; void clear() { root = NULL; reccount = 0; } // Memory leak void insert(const Key& k, const E& e) { // Insert node root = inserthelp(root, k, e); reccount++; } E remove(const Key& k) { E temp = findhelp(root, k); if (temp != NULL) { if (removehelp(root, k) && (root->numrecs() == 1)) // Collapse root if (!root->isLeaf()) root = ((BPInternal*)root)->pointers(0); reccount--; } return temp; } E removeAny() { return NULL; } E find(const Key& k) const { return findhelp(root, k); } int size() { return reccount; } }; template E BPTree::findhelp(BPNode* rt, const Key k) const { int currec = binaryle(rt->keys(), rt->numrecs(), k); if (rt->isLeaf()) if ((((BPLeaf*)rt)->keys())[currec] == k) return ((BPLeaf*)rt)->recs(currec); else return NULL; else return findhelp(((BPInternal*)rt)-> pointers(currec), k); } template BPNode* BPTree::inserthelp(BPNode* rt, const Key& k, const E& e) { if (rt->isLeaf()) // At leaf node: insert here return ((BPLeaf*)rt)->add(k, e); // Add to internal node int currec = binaryle(rt->keys(), rt->numrecs(), k); BPNode* temp = inserthelp( ((BPInternal*)root)->pointers(currec), k, e); if (temp != ((BPInternal*)rt)->pointers(currec)) return ((BPInternal*)rt)-> add(k, (BPInternal*)temp); else return rt; } /** Delete a record with the given key value, and return true if the root underflows */ template bool BPTree::removehelp(BPNode* rt, const Key& k) { int currec = binaryle(rt->keys(), rt->numrecs(), k); if (rt->isLeaf()) if (((BPLeaf*)rt)->keys()[currec] == k) return ((BPLeaf*)rt)->del(currec); else return false; else // Process internal node if (removehelp(((BPInternal*)rt)-> pointers(currec), k)) // Child will merge if necessary return ((BPInternal*)rt)->underflow(currec); else return false; } int main(int argc, char** argv) { BPTreedum; }