Sample Programming Assignment
Chapter 6
Software Reuse with Templates
Preliminary Version

Note:

Chapter 6 Assignment
Implement the Bag class from Section 6.5, including the internal iterator.
You may use the template version of the linked list toolkit without
any changes (link2.h and link2.template). Test your implementation, and
also make sure that it works with the demonstration program (bag5demo.cxx).

// FILE: bag5.h
// TEMPLATE CLASS PROVIDED:
//   Bag<Item> (a container template 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, an assignment operator, and operators to test
//   for equality (x == y) and non-equality (x != y).
//
// CONSTRUCTOR for the Bag<Item> template class:
//   Bag(size_t initial_capacity = DEFAULT_CAPACITY)
//     Postcondition: The Bag is empty with an initial capacity given by the
//     parameter. The insert function will work efficiently (without allocating
//     new memory) until this capacity is reached.
//
// MODIFICATION MEMBER FUNCTIONS for the Bag<Item> template class:
//   void resize(size_t new_capacity)
//     Postcondition: The Bag's current capacity is changed to new_capcacity
//     (but not less than the number of items currently in the Bag). The insert
//     function will work efficiently without allocating new memory) until the
//     capacity is reached.
//
//   void insert(const Item& entry)
//     Postcondition: A new copy of entry has been added to 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<Item>& addend)
//     Postcondition: Each item in addend has been added to this Bag.
//
//   void start( )
//     Postcondition: The Bag's internal iterator has been started, so that a
//     programmer may step through the Bag's items one at a time.
//
//   void advance( )
//     Precondition: is_item returns true.
//     Postcondition: If there are more items for the internal iterator to step
//     through, then the internal iterator moves to a new item, and is_item
//     still returns true. Otherwise, is_item now returns false.
//
//   void remove_current( )
//     Precondition: is_item returns true.
//     Postcondition: The current item of the internal iterator has been
//     removed. If there are more items for the internal iterator to step
//     through, then the internal iterator has also been moved to a new item,
//     and is_item still returns true. Otherwise, is_item now returns false.
//
// 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.
//
//   Item grab( ) const
//     Postcondition: The return value is a randomly selected item from the Bag.
//
//   Item current( ) const
//     Precondition: is_item returns true.
//     Postcondition: The return value is the current item of the internal
//     iterator.
//
//   bool is_item( ) const
//     Postcondition: A true return value indicates that the internal iterator
//     has a valid current item that may be retrieved by the current member
//     function. A false return value indicates that there is no valid current
//     item.
//
// NON-MEMBER FUNCTIONS for the Bag<Item> template class:
//   template <class Item>
//   Bag<Item> operator +(const Bag<Item>& b1, const Bag<Item>& 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, resize, insert, operator += , operator +,
//   and the assignment operator.
//
// INTERNAL ITERATOR:
//   Calling insert, remove, or += will invalidate the interal iterator (so
//   that is_item returns false).

#ifndef BAG5_H
#define BAG5_H
#include <stdlib.h>   // Provides size_t and NULL
#include "link2.h"    // Provides the linked list toolkit

    template <class Item>
    class Bag
    {
    public:
        // CONSTRUCTORS and DESTRUCTOR
        Bag( );
        Bag(const Bag& source);
        ~Bag( );
        // MODIFICATION functions
        void insert(const Item& entry);
        void remove(const Item& target);
        void operator +=(const Bag& addend);
        void operator =(const Bag& source);
        void start( ) { current_ptr = head_ptr; }
        void advance( );
        void remove_current( );
        // CONSTANT functions
        size_t size( ) const { return many_nodes; }
        size_t occurrences(const Item& target) const;
        Item grab( ) const;
        Item current( ) const;
        bool is_item( ) const { return (current_ptr != NULL); }
    private:
        Node<Item> *head_ptr;    // Head pointer for the list of items
        Node<Item> *current_ptr; // Points to current item of internal iterator
        size_t many_nodes;       // Number of nodes on the list
    };
    
    // NON-MEMBER functions for the Bag
    template <class Item>
    Bag<Item> operator +(const Bag<Item>& b1, const Bag<Item>& b2);

#include "bag5.template"
#endif