// FILE: bag6.template
// -------------------------------------------------------------------------
// This is a partial implementation of the bag template class from Section
// 10.5 of "Data Structures and Other Objects Using C++". The parts marked
// with ***STUDENT WORK*** are left as a project for data structures
// students. Some additional discussion of this project is available at
// http://www.cs.colorado.edu/~main/projects/chap10a.html
// -------------------------------------------------------------------------
// TEMPLATE CLASS IMPLEMENTED: bag<Item> (see bag6.h for documentation)
// INVARIANT of the ADT:
// root_ptr is the root pointer of a binary search tree that contains the
// bag's items.
#include <cassert>
#include <cstdlib>
namespace main_savitch_10
{
template <class Item>
void bst_remove_max(binary_tree_node<Item>*& root_ptr, Item& removed)
// Precondition: root_ptr is a root pointer of a non-empty binary
// search tree.
// Postcondition: The largest item in the binary search tree has been
// removed, and root_ptr now points to the root of the new (smaller)
// binary search tree. The reference parameter, removed, has been set
// to a copy of the removed item.
{
/***STUDENT WORK***
** This recursive function should be implemented by the student, as
** discussed on page 507 of the second edition of the textbook.
** The base case occurs when there is no right child of the
** root_ptr node. In this case, the root_ptr should be moved down
** to its left child and then the original root node must be
** deleted. There is also a recursive case, when the root does
** have a right child. In this case, a recursive call can be made
** using root_ptr->right( ) as the first parameter. Please notice
** in bintree.h, the return value from root_ptr->right( ) has been
** changed from the first printing of the book. The new version of
** the right() function has the prototype:
** binary_tree_node<Item>*&
** The & symbol in the return type means that the return value is
** a reference to the actual right pointer in the node. Any changes
** made to this pointer in the recursive call will directly change
** the right pointer in the root_ptr's node.
*/
}
template <class Item>
bool bst_remove(binary_tree_node<Item>*& root_ptr, const Item& target)
// Precondition: root_ptr is a root pointer of a binary search tree
// or may be NULL for an empty tree).
// Postcondition: If target was in the tree, then one copy of target
// has been removed, and root_ptr now points to the root of the new
// (smaller) binary search tree. In this case the function returns true.
// If target was not in the tree, then the tree is unchanged (and the
// function returns false).
{
binary_tree_node<Item> *oldroot_ptr;
if (root_ptr == NULL)
{ // Empty tree
return false;
}
if (target < root_ptr->data( ))
{ // Continue looking in the left subtree
// Note: Any change made to root_ptr->left by this recursive
// call will change the actual left pointer (because the return
// value from the left() member function is a reference to the
// actual left pointer.
return bst_remove(root_ptr->left( ), target);
}
if (target > root_ptr->data( ))
{ // Continue looking in the right subtree
// Note: Any change made to root_ptr->right by this recursive
// call will change the actual right pointer (because the return
// value from the right() member function is a reference to the
// actual right pointer.
return bst_remove(root_ptr->right( ), target);
}
if (root_ptr->left( ) == NULL)
{ // Target was found and there is no left subtree, so we can
// remove this node, making the right child be the new root.
oldroot_ptr = root_ptr;
root_ptr = root_ptr->right( );
delete oldroot_ptr;
return true;
}
// If code reaches this point, then we must remove the target from
// the current node. We'll actually replace this target with the
// maximum item in our left subtree.
// Note: Any change made to root_ptr->left by bst_remove_max
// will change the actual left pointer (because the return
// value from the left() member function is a reference to the
// actual left pointer.
bst_remove_max(root_ptr->left( ), root_ptr->data( ));
return true;
}
template <class Item>
typename bag<Item>::size_type bst_remove_all
(binary_tree_node<Item>*& root_ptr, const Item& target)
// Precondition: root_ptr is a root pointer of a binary search tree
// or may be NULL for an empty tree).
// Postcondition: All copies of target have been removed from the tree
// has been removed, and root_ptr now points to the root of the new
// (smaller) binary search tree. The return value tells how many copies
// of the target were removed.
{
/** STUDENT WORK
** Note: This implementation is similar to bst_remove, except that
** all occurrences of the target must be removed, and the return
** value is the number of copies that were removed.
*/
binary_tree_node<Item> *oldroot_ptr;
if (root_ptr == NULL)
{ // Empty tree
/* STUDENT WORK */
}
if (target < root_ptr->data( ))
{ // Continue looking in the left subtree
/* STUDENT WORK */
}
if (target > root_ptr->data( ))
{ // Continue looking in the right subtree
/* STUDENT WORK */
}
if (root_ptr->left( ) == NULL)
{ // Target was found and there is no left subtree, so we can
// remove this node, making the right child be the new root.
oldroot_ptr = root_ptr;
root_ptr = root_ptr->right( );
delete oldroot_ptr;
return 1;
}
// If code reaches this point, then we must remove the target from
// the current node. We'll actually replace this target with the
// maximum item in our left subtree. We then continue
// searching for more copies of the target to remove.
// This continued search must start at the current root (since
// the maximum element that we moved up from our left subtree
// might also be a copy of the target).
/* STUDENT WORK */
}
template <class Item>
bag<Item>::bag(const bag<Item>& source)
// Library facilities used: bintree.h
{
root_ptr = tree_copy(source.root_ptr);
}
template <class Item>
bag<Item>::~bag( )
// Header file used: bintree.h
{
tree_clear(root_ptr);
}
template <class Item>
typename bag<Item>::size_type bag<Item>::size( ) const
// Header file used: bintree.h
{
return tree_size(root_ptr);
}
template <class Item>
void bag<Item>::insert(const Item& entry)
// Header file used: bintree.h
{
binary_tree_node<Item> *cursor;
if (root_ptr == NULL)
{ // Add the first node of the binary search tree:
root_ptr = new binary_tree_node<Item>(entry);
return;
}
else
{ // Move down the tree and add a new leaf:
cursor = root_ptr;
/* STUDENT WORK */
}
}
template <class Item>
typename bag<Item>::size_type bag<Item>::count(const Item& target) const
{
size_type answer = 0;
binary_tree_node<Item> *cursor;
cursor = root_ptr;
/* STUDENT WORK */
return answer;
}
template <class Item>
typename bag<Item>::size_type bag<Item>::erase(const Item& target)
{
return bst_remove_all(root_ptr, target);
}
template <class Item>
bool bag<Item>::erase_one(const Item& target)
{
return bst_remove(root_ptr, target);
}
template <class Item>
void bag<Item>::operator =(const bag<Item>& source)
// Header file used: bintree.h
{
if (root_ptr == source.root_ptr)
return;
tree_clear(root_ptr);
root_ptr = tree_copy(source.root_ptr);
}
template <class Item>
void bag<Item>::operator +=(const bag<Item>& addend)
{
if (root_ptr == addend.root_ptr)
{
bag<Item> copy = addend;
insert_all(copy.root_ptr);
}
else
insert_all(addend.root_ptr);
}
template <class Item>
bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2)
{
bag<Item> answer = b1;
answer += b2;
return answer;
}
template <class Item>
void bag<Item>::insert_all(binary_tree_node<Item>* addroot_ptr)
// Precondition: addroot_ptr is the root pointer of a binary search tree that
// is separate for the binary search tree of the bag that activated this
// method.
// Postcondition: All the items from the addroot_ptr's binary search tree
// have been added to the binary search tree of the bag that activated this
// method.
{
if (addroot_ptr != NULL)
{
insert(addroot_ptr->data( ));
insert_all(addroot_ptr->left( ));
insert_all(addroot_ptr->right( ));
}
}
}