Can anyone finish this for me? Thank you so much.

Complete the implementation of B-Tree using the class set as shown in the attached C++ and header files. You should closely follow the pseudo code/algorithm described in the book in your implementation. Write a driver code that will test each function in your B-Tree implementation.

I can post links to the book and code if needed. The template class has missing code, and the source.cpp. I believe the set.h is fine.

//SOURCE.CPP

#include #include "set.h"

using namespace std; using namespace main_savitch_11;

int main() { set s; set* ds = new set < double >;

return 0; }

//SET.H

// FILE: set.h (part of the namespace main_savitch_11) // TEMPLATE CLASS PROVIDED: set // (a container template class for a set of items) // // TYPEDEFS for the set class: // set::value_type // set::value_type is the data type of the items in the set. It may be // any of the C++ built-in types (int, char, etc.), or a class with a // default constructor, a copy constructor, an assignment operator, and a // less-than operator forming a strict weak ordering. // // CONSTRUCTOR for the set class: // set( ) // Postcondition: The set is empty. // // MODIFICATION MEMBER FUNCTIONS for the set class: // void clear( ) // Postcondition: The set is empty. // // bool insert(const Item& entry) // Postcondition: If an equal entry was already in the set, the set is // unchanged and the return value is false. Otherwise, entry was added // to the set and the return value is true. This is slightly different than // the C++ Standard Library set (see Appendix H). // // size_t erase(const Item& target) // Postcondition: If target was in the set, then it has been removed from // the set and the return value is 1. Otherwise the set is unchanged and the // return value is zero. // // CONSTANT MEMBER FUNCTIONS for the Set class: // size_t count(const Item& target) const // Postcondition: Returns the number of items equal to the target // (either 0 or 1 for a set). // // bool empty( ) const // Postcondition: Returns true if the set is empty; otherwise returns false. // // VALUE SEMANTICS for the set class: // Assignments and the copy constructor may be used with set objects. // // DYNAMIC MEMORY USAGE by the set class: // If there is insufficient dynamic memory, then the following functions throw // bad_alloc: // The constructors, insert, and the assignment operator.

#ifndef MAIN_SAVITCH_SET_H #define MAIN_SAVITCH_SET_H #include // Provides size_t

namespace main_savitch_11 { template class set { public: // TYPEDEFS typedef Item value_type;

// CONSTRUCTORS and DESTRUCTOR set(); set(const set& source); //THIS NEEDS TO BE FIXED ~set() { clear(); }

// MODIFICATION MEMBER FUNCTIONS void operator =(const set& source); void clear(); bool insert(const Item& entry); std::size_t erase(const Item& target); //THIS NEEDS TO BE FIXED

// CONSTANT MEMBER FUNCTIONS std::size_t count(const Item& target) const; //THIS NEEDS TO BE FIXED bool empty() const { return (data_count == 0); }

// SUGGESTED FUNCTION FOR DEBUGGING void print(int indent) const; //THIS NEEDS TO BE FIXED

private: // MEMBER CONSTANTS static const std::size_t MINIMUM = 2; static const std::size_t MAXIMUM = 2 * MINIMUM;

// MEMBER VARIABLES std::size_t data_count; Item data[MAXIMUM + 1]; std::size_t child_count; set *subset[MAXIMUM + 2];

// HELPER MEMBER FUNCTIONS bool is_leaf() const { return (child_count == 0); } bool loose_insert(const Item& entry); std::size_t get_index(const Item& entry); bool loose_erase(const Item& target); //NEEDS CODE void remove_biggest(Item& removed_entry); //NEEDS CODE void fix_excess(std::size_t i); void fix_shortage(std::size_t i); //NEEDS CODE set* b_tree_copy(const set* root_ptr); //THIS NEEDS TO BE FIXED void b_tree_clear(set*& root_ptr); // NOTE: The implementor may want to have additional helper functions }; }

#include "set.template"

#endif

//SET.TEMPLATE

//#include "set.template" // Include the implementation. #include "stdafx" #include #include "set.h"

using name space std; namespace main_savitch_11 {

template set::set() { data_count = 0; child_count = 0; for (auto& p : subset) { p = nullptr; } }

template set::set(const set& source) { //data_count = source.data_count; //child_count = source.child_count; //for (int i = 0; i < data_count; i++) { // data[i] = source.data[i]; //} this = b_tree_copy(&source); }

template set* b_tree_copy(const set* root_ptr) { if (root_ptr == nullptr) { return nullptr; } set* set_ptr = new set; set_ptr->data_count = root_ptr->data_count; set_ptr->child_count = root_ptr->child_count; for (int i = 0; i < data_count; i++) { set_ptr->data[i] = root_ptr->data[i]; } for (int i = 0; i < set_ptr->child_count; i++) { set_ptr->subset[i] = b_tree_copy(root_ptr->subset[i]); } return set_ptr; }

template void set::clear() { for (auto& v : data) { v = Item(); } for (auto& p : subset) { b_tree_clear(p); } data_count = 0; child_count = 0; }

template void set::b_tree_clear(set*& root_ptr) { if (root_ptr != nullptr) { for (auto& v : root_ptr->data) { v = Item(); } for (int i = 0; i < root_ptr->child_count; i++) { b_tree_clear(root_ptr->subset[i]); } delete root_ptr; root_ptr = nullptr; } }

template void set::operator=(const set& source) { if (this == &source) { return; } clear(); this = b_tree_copy(&source); }

template std::size_t count(const Item& target) const { std::size_t i = get_index(target); if (i < data_count && !(target < data[i]) { return 1; } if (child_count == 0) { return 0; } return subset[i]->count(target); }

template std::size_t set::get_index(const Item& entry) { for (std::size_t i = 0; i < data_count; i++) { if (!(data[i] < entry)) { return i; } } return data_count; }

template bool set::loose_insert(const Item& entry) { std::size_t i = get_index(entry);

if (i < data_count && !(entry < data[i]) { return false; }

if (child_count == 0) { for (std::size_t ix = data_count - 1; ix >= i; ix--) { data[ix + 1] = data[ix]; } data[i] = entry; data_count++; return true; }

bool b = subset[i]->loose_insert(entry);

if (subset[i]->data_count == MAXIMUM + 1) { fix_excess(i); } }

template void set::fix_excess(std::size_t i) { for (std::size_t ix = child_count - 1; ix > i; ix--) { subset[ix + 1] = subset[ix]; }

subset[i + 1] = new set; child_count++;

for (std::size_t ix = MINIMUM + 1; ix < MAXIMUM + 2; ix++) { subset[i + 1]->subset[ix - MINIMUM - 1] = subset[i]->subset[ix]; } for (std::size_t ix = MINIMUM + 1; ix < MAXIMUM + 1; ix++) { subset[i + 1]->data[ix - MINIMUM - 1] = subset[i]->data[ix]; }

subset[i]->data_count = MINIMUM; subset[i + 1]->data_count = MINIMUM; subset[i]->child_count = MINIMUM + 1; subset[i + 1]->child_count = MINIMUM + 1;

for (std::size_t ix = data_count - 1; ix >= i; ix--) { data[ix + 1] = data[ix]; }

data_count++; data[i] = subset[i]->data[MINIMUM]; }

template bool set::insert(const Item& entry) { if (!loose_insert(entry)) { return false; } if (data_count > MAXIMUM) { set* pset = new set; pset->subset[0] = this; pset->child_count = 1; this = pset; fix_excess(0); } return true; }

//THESE 3 need to be finished

template bool set::loose_erase(const Item& target) {

//CODE HERE

}

template void set::remove_biggest(Item& removed_entry) {

CODE HERE

}

template void set::fix_shortage(std::size_t i) {

//CODE HERE

}

}