can i get some help with this, need to turn it in monday 27th.. for my final..

this was all we were given

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(Data Structures and Other Objects Using C++ 4th Edition by Michael Main, Walter Savitch) in your implementation. Write a driver code that will test each function in your B-Tree implementation.

//**********************************************

//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

//************************

//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;

}