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.
Code/Book/Powerpoint
https://drive.google.com/file/d/1HQE_S18a7iRuGLurawaKCH1Y-ZqTqnyH/view?usp=sharing https://drive.google.com/file/d/159nDWBCpZXqZhYXuqKsNpUaW5s734SUn/view?usp=sharing https://drive.google.com/file/d/1wfYjza1N8D9nb26i8bb_ebE1cJVhCFZr/view?usp=sharing https://drive.google.com/file/d/10yCcjlt5e9S34whBZsj81uCye-JNIAki/view?usp=sharing
Code:
//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); ~set( ) { clear( ); } // MODIFICATION MEMBER FUNCTIONS void operator =(const set& source); void clear( ); bool insert(const Item& entry); std::size_t erase(const Item& target); // CONSTANT MEMBER FUNCTIONS std::size_t count(const Item& target) const; bool empty( ) const { return (data_count == 0); } // SUGGESTED FUNCTION FOR DEBUGGING void print(int indent) const; 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); void remove_biggest(Item& removed_entry); void fix_excess(std::size_t i); void fix_shortage(std::size_t i); set* b_tree_copy(const set* root_ptr); void b_tree_clear(set*& root_ptr); // NOTE: The implementor may want to have additional helper functions }; } //#include "set.template" // Include the implementation.
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; }
template bool set- ::loose_erase(const Item& target) {
}
template void set- ::remove_biggest(Item& removed_entry) {
}
template void set- ::fix_shortage(std::size_t i) {
} //bool loose_erase(const Item& target);
}
#endif
