Sample Programming Assignment
Chapter 10
Trees
Preliminary Version

Note:

Chapter 10 Assignment
Implement the Bag class from Section 10.5 using a binary search tree.
You may use the header file listed below, and the binary tree toolkit
(bintree2.h and bintree2.template). Test your implementation with
an interactive test program.

// FILE: bag6.h
// TEMPLATE CLASS PROVIDED: Bag<Item> (a container class for a collection of
// items). The template parameter, Item, is the data type of the items in the
// bag. 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
// the six comparison operators forming a total order.
//
// CONSTRUCTOR for the Bag<Item> template class:
//   Bag( )
//     Postcondition: The bag is empty.
//
// MODIFICATION MEMBER FUNCTIONS for the Bag<Item> template class:
//   void insert(const Item& entry)
//     Postcondition: A new copy of entry has been inserted into the bag.
//
//   void remove(const Item& target)
//     Postcondition:If target was in the bag, then one copy of target has
//     been removed from the bag; otherwise the bag is unchanged.
//
//   void operator +=(const Bag& addend)
//     Postcondition: Each item in addend has been added to this bag.
//
// CONSTANT MEMBER FUNCTIONS for the Bag<Item> template class:
//   size_t size( ) const
//     Postcondition: Return value is the total number of items in the bag.
//
//   size_t occurrences(const Item& target) const
//     Postcondition: Return value is number of times target is in the bag.
//
// NONMEMBER functions for the Bag<Item> template class:
//   Bag operator +(const Bag& b1, const Bag& b2)
//     Postcondition: The bag returned is the union of b1 and b2.
//
// VALUE SEMANTICS for the Bag<Item> template class:
//   Assignments and the copy constructor may be used with Bag objects.
//
// DYNAMIC MEMORY USAGE by the Bag<Item> template class:
//   If there is insufficient dynamic memory,
//   then the following functions call new_handler: The constructors,
//   insert, operator +=, operator +, and the assignment operator.

#ifndef BAG_H
#define BAG_H
#include <stdlib.h>   // Provides size_t and NULL
#include "bintree2.h" // Provides BinaryTreeNode and related functions

    template <class Item>
    class Bag
    {
    public:
        // CONSTRUCTORS and DESTRUCTOR
        Bag( ) { root_ptr = NULL; }
        Bag(const Bag<Item>& source);
        ~Bag( );
        // MODIFICATION functions
        void insert(const Item& entry);
        void remove(const Item& target);
        void operator +=(const Bag<Item>& addend);
        void operator =(const Bag<Item>& source);
        // CONSTANT functions
        size_t size( ) const;
        size_t occurrences(const Item& target) const;
    private:
        BinaryTreeNode<Item> *root_ptr; // Root pointer of binary search tree
        void insert_all(BinaryTreeNode<Item>* addroot_ptr);
    };

    // NONMEMBER functions for the Bag
    template <class Item>
    Bag<Item> operator +(const Bag<Item>& b1, const Bag<Item>& b2);

#include "bag6.template"
#endif