Question
Use a B-tree to implement the set class from Figure 11.5 on page 551. A Header File //FILE: set.h (part of the namespace main_savitch_11) //TEMPLATE
Use a B-tree to implement the set class from Figure 11.5 on page 551.
A Header File
//FILE: set.h (part of the namespace main_savitch_11)
//TEMPLATE CLASS PROVIDED: set
//TYPEDEFS for the set
//set
//set
//strict weak ordering.
//CONSTRUCTOR for the set
//set( )
//Postcondition: The set is empty.
//MODIFICATION MEMBER FUNCTIONS for the set
//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
//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
//Assignments and the copy constructor may be used with set
//DYNAMIC MEMORY USAGE by the set
//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
namespace main_savitch_11 {
template
{
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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started