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

B-Trees 551 FIGURE 11.5 Header File for the Set Template Class A Header File // 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 /IC++ 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 /I CONSTRUCTOR for the set class: // set( Postcondition: The set is empty IMODIFICATION MEMBER FUNCTIONS for the set class: // void clear( ) Postcondition: The set is empty bool insert(const Item& entry) /I 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 Ctt Standard Library set (see Appendix H) // size-t erase(const Item& target) /I 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) // boo1 empty) const /I 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. (continued)