The goal of this assignment is to reinforce the B-tree data structure in C++. Specifically, the assignment is to do problem 3 on page 582 of the text. You will need a test program.

*********************************************

Header File for the Set Template Class

*********************************************

// 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); } private: // MEMBER CONSTANTS static const std::size_t MINIMUM = 200; 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); 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);

}; } #include "set.template" // Include the implementation. #endif

3 Use a B-tree to implement the set class from Figure 11.5 on page 551. Follow the programming tips from page 569-570 3 Use a B-tree to implement the set class from Figure 11.5 on page 551. Follow the programming tips from page 569-570