Write a C++ program that includes the following (I have also incluced all of the

ID: 3674111 • Letter: W

Question

Write a C++ program that includes the following (I have also incluced all of the files you will need including the main.cpp test program:

bag5.h

#ifndef BAG5_H
#define BAG5_H

// FILE: bag5.h (part of the namespace main_savitch_chapter6)
// TEMPLATE CLASS PROVIDED:
// bag<Item> (a collection of items; each item may appear multiple times)
//
// TYPEDEFS for the bag<Item> template class:
// bag<Item>::value_type
// This is the Item type from the template parameter.
// It 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 a test for equality (x == y).
//
// bag<Item>::size_type
// This is the data type of any variable that keeps track of how many items
// are in a bag
//
// bag<Item>::iterator and bag<Item>::const_iterator
// Forward iterators for a bag or a const bag.
//
// CONSTRUCTOR for the bag<Item> class:
// bag( )
// Postcondition: The bag is empty.
//
// MODIFICATION MEMBER FUNCTIONS for the bag<Item> class:
// size_type erase(const Item& target)
// Postcondition: All copies of target have been removed from the bag.
// The return value is the number of copies removed (which could be zero).
//
// bool erase_one(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. A true
// return value indicates that one copy was removed; false indicates that
// nothing was removed.
//
// void insert(const Item& entry)
// Postcondition: A new copy of entry has been inserted into the bag.
//
// void operator +=(const bag& addend)
// Postcondition: Each item in addend has been added to this bag.
//
// CONSTANT MEMBER FUNCTIONS for the bag<Item> class:
// size_type count(const Item& target) const
// Postcondition: Return value is number of times target is in the bag.
//
// Item grab( ) const
// Precondition: size( ) > 0.
// Postcondition: The return value is a randomly selected item from the bag.
//
// size_type size( ) const
// Postcondition: Return value is the total number of items in the bag.
//
// STANDARD ITERATOR MEMBER FUNCTIONS (provide a forward iterator):
// iterator begin( )
// const_iterator begin( ) const
// iterator end( )
// const iterator end( ) const
//
// NONMEMBER FUNCTIONS for the bag<Item> 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> class:
// Assignments and the copy constructor may be used with bag objects.
//
// DYNAMIC MEMORY USAGE by the bag<Item>:
// If there is insufficient dynamic memory, then the following functions throw
// bad_alloc: The constructors, insert, operator +=, operator +, and the
// assignment operator.

#include <cstdlib> // Provides NULL and size_t and NULL
#include "node2.h" // Provides node class

template <class Item>
class bag
{
public:
// TYPEDEFS
   typedef std::size_t size_type;
typedef Item value_type;
   typedef node_iterator<Item> iterator;
   typedef const_node_iterator<Item> const_iterator;

// CONSTRUCTORS and DESTRUCTOR
bag( );
bag(const bag& source);
~bag( );

// MODIFICATION MEMBER FUNCTIONS
size_type erase(const Item& target);
bool erase_one(const Item& target);
void insert(const Item& entry);
void operator +=(const bag& addend);
void operator =(const bag& source);

// CONST MEMBER FUNCTIONS
size_type count(const Item& target) const;
Item grab( ) const;
size_type size( ) const { return many_nodes; }

   // FUNCTIONS TO PROVIDE ITERATORS
   iterator begin( )
   { return iterator(head_ptr); }
   const_iterator begin( ) const
   { return const_iterator(head_ptr); }
   iterator end( )
   { return iterator( ); } // Uses default constructor
   const_iterator end( ) const
   { return const_iterator( ); } // Uses default constructor

private:
node<Item> *head_ptr; // Head pointer for the list of items
size_type many_nodes; // Number of nodes on the list
};

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

// The implementation of a template class must be included in its header file:
#include "bag5.template"

#endif // BAG5_H

bag5.template

// FILE: bag5.template
// CLASS implemented: bag (see bag5.h for documentation)
// NOTE:
// Since bag is a template class, this file is included in node2.h.
// INVARIANT for the bag class:
// 1. The items in the bag are stored on a linked list;
// 2. The head pointer of the list is stored in the member variable head_ptr;
// 3. The total number of items in the list is stored in the member variable
// many_nodes.

#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL, rand
#include "node2.h" // Provides node

template <class Item>
bag<Item>::bag( )
// Library facilities used: cstdlib
{
head_ptr = NULL;
many_nodes = 0;
}

template <class Item>
bag<Item>::bag(const bag<Item>& source)
// Library facilities used: node2.h
{
node<Item> *tail_ptr; // Needed for argument of list_copy

list_copy(source.head_ptr, head_ptr, tail_ptr);
many_nodes = source.many_nodes;
}

template <class Item>
bag<Item>::~bag( )
// Library facilities used: node2.h
{
list_clear(head_ptr);
many_nodes = 0;
}

template <class Item>
typename bag<Item>::size_type bag<Item>::count(const Item& target) const
// Library facilities used: cstdlib, node2.h
{
   size_type answer;
   const node<Item> *cursor;

   answer = 0;
   cursor = list_search(head_ptr, target);
   while (cursor != NULL)
   {
   // Each time that cursor is not NULL, we have another occurrence of
   // target, so we add one to answer, and move cursor to the next
   // occurrence of the target.
   ++answer;
   cursor = cursor->link( );
   cursor = list_search(cursor, target);
   }
   return answer;
}

template <class Item>
typename bag<Item>::size_type bag<Item>::erase(const Item& target)
// Library facilities used: cstdlib, node2.h
{
size_type answer = 0;
node<Item> *target_ptr;

target_ptr = list_search(head_ptr, target);
while (target_ptr != NULL)
{
// Each time that target_ptr is not NULL, we have another occurrence
   // of target. We remove this target using the same technique that
   // was used in erase_one.
++answer;
   --many_nodes;
target_ptr->set_data( head_ptr->data( ) );
target_ptr = target_ptr->link( );
target_ptr = list_search(target_ptr, target);
list_head_remove(head_ptr);
}
return answer;
}

template <class Item>
bool bag<Item>::erase_one(const Item& target)
// Library facilities used: cstdlib, node2.h
{
   node<Item> *target_ptr;

   target_ptr = list_search(head_ptr, target);
   if (target_ptr == NULL)
   return false; // target isn't in the bag, so no work to do
   target_ptr->set_data( head_ptr->data( ) );
   list_head_remove(head_ptr);
   --many_nodes;
   return true;
}

template <class Item>
Item bag<Item>::grab( ) const
// Library facilities used: cassert, cstdlib, node2.h
{
size_type i;
const node<Item> *cursor;

   assert(size( ) > 0);
   i = (std::rand( ) % size( )) + 1;
   cursor = list_locate(head_ptr, i);
   return cursor->data( );
}

template <class Item>
void bag<Item>::insert(const Item& entry)
// Library facilities used: node2.h
{
list_head_insert(head_ptr, entry);
++many_nodes;
}

template <class Item>
void bag<Item>::operator +=(const bag<Item>& addend)
// Library facilities used: node2.h
{
   node<Item> *copy_head_ptr;
   node<Item> *copy_tail_ptr;

   if (addend.many_nodes > 0)
   {
   list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);
   copy_tail_ptr->set_link( head_ptr );
   head_ptr = copy_head_ptr;
   many_nodes += addend.many_nodes;
   }
}

template <class Item>
void bag<Item>::operator =(const bag<Item>& source)
// Library facilities used: node2.h
{
   node<Item> *tail_ptr; // Needed for argument to list_copy

if (this == &source)
return;

list_clear(head_ptr);
many_nodes = 0;

list_copy(source.head_ptr, head_ptr, tail_ptr);
many_nodes = source.many_nodes;
}

template <class Item>
bag<Item> operator +(const bag<Item>& b1, const bag<Item>& b2)
{
bag<Item> answer;

   answer += b1;
   answer += b2;
   return answer;
}

node2.h

#ifndef NODE2_H
#define NODE2_H

// FILE: node2.h (part of the namespace main_savitch_6B)
// PROVIDES: A template class for a node in a linked list, and list manipulation
// functions. The template parameter is the type of the data in each node.
// This file also defines a template class: node_iterator<Item>.
// The node_iterator is a forward iterators with two constructors:
// (1) A constructor (with a node<Item>* parameter) that attaches the iterator
// to the specified node in a linked list, and (2) a default constructor that
// creates a special iterator that marks the position that is beyond the end of a
// linked list. There is also a const_node_iterator for use with
// const node<Item>* .
//
// TYPEDEF for the node<Item> template class:
// Each node of the list contains a piece of data and a pointer to the
// next node. The type of the data (node<Item>::value_type) is the Item type
// from the template parameter. The type may be any of the built-in C++ classes
// (int, char, ...) or a class with a default constructor, an assignment
// operator, and a test for equality (x == y).
// NOTE:
// Many compilers require the use of the new keyword typename before using
// the expression node<Item>::value_type. Otherwise
// the compiler doesn't have enough information to realize that it is the
// name of a data type.
//
// CONSTRUCTOR for the node<Item> class:
// node(
// const Item& init_data = Item(),
// node* init_link = NULL
// )
// Postcondition: The node contains the specified data and link.
// NOTE: The default value for the init_data is obtained from the default
// constructor of the Item. In the ANSI/ISO standard, this notation
// is also allowed for the built-in types, providing a default value of
// zero. The init_link has a default value of NULL.
//
// NOTE about two versions of some functions:
// The data function returns a reference to the data field of a node and
// the link function returns a copy of the link field of a node.
// Each of these functions comes in two versions: a const version and a
// non-const version. If the function is activated by a const node, then the
// compiler choses the const version (and the return value is const).
// If the function is activated by a non-const node, then the compiler choses
// the non-const version (and the return value will be non-const).
// EXAMPLES:
// const node<int> *c;
// c->link( ) activates the const version of link returning const node*
// c->data( ) activates the const version of data returning const Item&
// c->data( ) = 42; ... is forbidden
// node<int> *p;
// p->link( ) activates the non-const version of link returning node*
// p->data( ) activates the non-const version of data returning Item&
// p->data( ) = 42; ... actually changes the data in p's node
//
// MEMBER FUNCTIONS for the node<Item> class:
// const Item& data( ) const <----- const version
// and
// Item& data( ) <----------------- non-const version
// See the note (above) about the const version and non-const versions:
// Postcondition: The return value is a reference to the data from this node.
//
// const node* link( ) const <----- const version
// and
// node* link( ) <----------------- non-const version
// See the note (above) about the const version and non-const versions:
// Postcondition: The return value is the link from this node.
//
// void set_data(const Item& new_data)
// Postcondition: The node now contains the specified new data.
//
// void set_link(node* new_link)
// Postcondition: The node now contains the specified new link.
//
// FUNCTIONS in the linked list toolkit:
// template <class Item>
// void list_clear(node<Item>*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: All nodes of the list have been returned to the heap,
// and the head_ptr is now NULL.
//
// template <class Item>
// void list_copy
// (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr)
// Precondition: source_ptr is the head pointer of a linked list.
// Postcondition: head_ptr and tail_ptr are the head and tail pointers for
// a new list that contains the same items as the list pointed to by
// source_ptr. The original list is unaltered.
//
// template <class Item>
// void list_head_insert(node<Item>*& head_ptr, const Item& entry)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: A new node containing the given entry has been added at
// the head of the linked list; head_ptr now points to the head of the new,
// longer linked list.
//
// template <class Item>
// void list_head_remove(node<Item>*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list, with at
// least one node.
// Postcondition: The head node has been removed and returned to the heap;
// head_ptr is now the head pointer of the new, shorter linked list.
//
// template <class Item>
// void list_insert(node<Item>* previous_ptr, const Item& entry)
// Precondition: previous_ptr points to a node in a linked list.
// Postcondition: A new node containing the given entry has been added
// after the node that previous_ptr points to.
//
// template <class Item>
// size_t list_length(const node<Item>* head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The value returned is the number of nodes in the linked
// list.
//
// template <class NodePtr, class SizeType>
// NodePtr list_locate(NodePtr head_ptr, SizeType position)
// The NodePtr may be either node<Item>* or const node<Item>*
// Precondition: head_ptr is the head pointer of a linked list, and
// position > 0.
// Postcondition: The return value is a pointer that points to the node at
// the specified position in the list. (The head node is position 1, the
// next node is position 2, and so on). If there is no such position, then
// the null pointer is returned.
//
// template <class Item>
// void list_remove(node<Item>* previous_ptr)
// Precondition: previous_ptr points to a node in a linked list, and this
// is not the tail node of the list.
// Postcondition: The node after previous_ptr has been removed from the
// linked list.
//
// template <class NodePtr, class Item>
// NodePtr list_search
// (NodePtr head_ptr, const Item& target)
// The NodePtr may be either node<Item>* or const node<Item>*
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The return value is a pointer that points to the first
// node containing the specified target in its data member. If there is no
// such node, the null pointer is returned.
//
// DYNAMIC MEMORY usage by the toolkit:
// If there is insufficient dynamic memory, then the following functions throw
// bad_alloc: the constructor, list_head_insert, list_insert, list_copy.

#include <cstdlib> // Provides NULL and size_t
#include <iterator> // Provides iterator and forward_iterator_tag

template <class Item>
class node
{
public:
// TYPEDEF
typedef Item value_type;
// CONSTRUCTOR
node(const Item& init_data=Item( ), node* init_link=NULL)
{ data_field = init_data; link_field = init_link; }
// MODIFICATION MEMBER FUNCTIONS
Item& data( ) { return data_field; }
node* link( ) { return link_field; }
void set_data(const Item& new_data) { data_field = new_data; }
void set_link(node* new_link) { link_field = new_link; }
// CONST MEMBER FUNCTIONS
const Item& data( ) const { return data_field; }
const node* link( ) const { return link_field; }
private:
Item data_field;
node *link_field;
};

// FUNCTIONS to manipulate a linked list:
template <class Item>
void list_clear(node<Item>*& head_ptr);

template <class Item>
void list_copy
(const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);

template <class Item>
void list_head_insert(node<Item>*& head_ptr, const Item& entry);

template <class Item>
void list_head_remove(node<Item>*& head_ptr);

template <class Item>
void list_insert(node<Item>* previous_ptr, const Item& entry);

template <class Item>
std::size_t list_length(const node<Item>* head_ptr);

template <class NodePtr, class SizeType>
NodePtr list_locate(NodePtr head_ptr, SizeType position);

template <class Item>
void list_remove(node<Item>* previous_ptr);

template <class NodePtr, class Item>
NodePtr list_search(NodePtr head_ptr, const Item& target);

// FORWARD ITERATORS to step through the nodes of a linked list
// A node_iterator of can change the underlying linked list through the
// * operator, so it may not be used with a const node. The
// node_const_iterator cannot change the underlying linked list
// through the * operator, so it may be used with a const node.
// WARNING:
// This classes use std::iterator as its base class;
// Older compilers that do not support the std::iterator class can
// delete everything after the word iterator in the second line:

template <class Item>
class node_iterator : public std::iterator<std::forward_iterator_tag, Item>
{
public:
   node_iterator(node<Item>* initial = NULL){ current = initial; }

Item& operator *( ) const { return current->data( ); }

node_iterator& operator ++( ) // Prefix ++
   {
       current = current->link( );
       return *this;
   }

node_iterator operator ++(int) // Postfix ++
   {
       node_iterator original(current);
       current = current->link( );
       return original;
   }

bool operator ==(const node_iterator other) const { return current == other.current; }

bool operator !=(const node_iterator other) const { return current != other.current; }
private:
node<Item>* current;
};

template <class Item>
class const_node_iterator : public std::iterator<std::forward_iterator_tag, const Item>
{
public:
   const_node_iterator(const node<Item>* initial = NULL) { current = initial; }

const Item& operator *( ) const { return current->data( ); }

const_node_iterator& operator ++( ) // Prefix ++
   {
       current = current->link( );
       return *this;
   }

const_node_iterator operator ++(int) // Postfix ++
   {
       const_node_iterator original(current);
       current = current->link( );
       return original;
   }

bool operator ==(const const_node_iterator other) const { return current == other.current; }

bool operator !=(const const_node_iterator other) const { return current != other.current; }
private:
   const node<Item>* current;
};

#include "node2.template"

#endif // NODE2_H

node2.template

// FILE: node2.template
// IMPLEMENTS: The functions of the node template class and the
// linked list toolkit (see node2.h for documentation).
//
// NOTE:
// Since node is a template class, this file is included in node2.h.
// Therefore, we should not put any using directives in this file.
//
// INVARIANT for the node class:
// The data of a node is stored in data_field, and the link in link_field.

#include <cassert> // Provides assert
#include <cstdlib> // Provides NULL and size_t

template <class Item>
void list_clear(node<Item>*& head_ptr)
// Library facilities used: cstdlib
{
while (head_ptr != NULL)
list_head_remove(head_ptr);
}

template <class Item>
void list_copy(
   const node<Item>* source_ptr,
   node<Item>*& head_ptr,
   node<Item>*& tail_ptr
)
// Library facilities used: cstdlib
{
   head_ptr = NULL;
   tail_ptr = NULL;

   // Handle the case of the empty list
   if (source_ptr == NULL)
   return;

   // Make the head node for the newly created list, and put data in it
   list_head_insert(head_ptr, source_ptr->data( ));
   tail_ptr = head_ptr;

   // Copy rest of the nodes one at a time, adding at the tail of new list
   source_ptr = source_ptr->link( );
while (source_ptr != NULL)
   {
   list_insert(tail_ptr, source_ptr->data( ));
   tail_ptr = tail_ptr->link( );
   source_ptr = source_ptr->link( );
   }
}

template <class Item>
void list_head_insert(node<Item>*& head_ptr, const Item& entry)
{
   head_ptr = new node<Item>(entry, head_ptr);
}

template <class Item>
void list_head_remove(node<Item>*& head_ptr)
{
node<Item> *remove_ptr;

   remove_ptr = head_ptr;
   head_ptr = head_ptr->link( );
   delete remove_ptr;
}

template <class Item>
void list_insert(node<Item>* previous_ptr, const Item& entry)
{
   node<Item> *insert_ptr;

   insert_ptr = new node<Item>(entry, previous_ptr->link( ));
   previous_ptr->set_link(insert_ptr);
}

template <class Item>
std::size_t list_length(const node<Item>* head_ptr)
// Library facilities used: cstdlib
{
   const node<Item> *cursor;
   std::size_t answer;

   answer = 0;
   for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
   ++answer;

   return answer;
}

template <class NodePtr, class SizeType>
NodePtr list_locate(NodePtr head_ptr, SizeType position)
// Library facilities used: cassert, cstdlib
{
   NodePtr cursor;
   SizeType i;

   assert(0 < position);
   cursor = head_ptr;
   for (i = 1; (i < position) && (cursor != NULL); ++i)
   cursor = cursor->link( );
   return cursor;
}

template <class Item>
void list_remove(node<Item>* previous_ptr)
{
node<Item> *remove_ptr;

   remove_ptr = previous_ptr->link( );
   previous_ptr->set_link(remove_ptr->link( ));
   delete remove_ptr;
}

template <class NodePtr, class Item>
NodePtr list_search(NodePtr head_ptr, const Item& target)
// Library facilities used: cstdlib
{
   NodePtr cursor;

   for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
   if (target == cursor->data( ))
       return cursor;
   return NULL;
}

main.cpp

#include <cstdlib>
#include <iostream>
#include <set>
#include <algorithm>
#include "node2.h"
#include "bag5.h"

using namespace std;

// PROTOTYPE for a function used by this demonstration program
template <class Item, class SizeType, class MessageType>
void get_items(bag<Item>& collection, SizeType n, MessageType description)
// Postcondition: The string description has been written as a prompt to the
// screen. Then n items have been read from cin and added to the collection.
// Library facilities used: iostream, bag4.h
{
Item user_input; // An item typed by the program's user
SizeType i;

cout << "Please type " << n << " " << description;
cout << ", separated by spaces. ";
cout << "Press the <return> key after the final entry: ";
for (i = 1; i <= n; ++i)
{
cin >> user_input;
collection.insert(user_input);
}
cout << endl;
}

int main()
{
//demostrate how to use set template class
set <string> actors1;
set <string> actors2;
set <string> result;
set<string>::iterator role;
actors1.insert("moe");
actors1.insert("curly");
actors2.insert("larry");
actors2.insert("curly");

for(role = actors1.begin(); role != actors1.end(); ++role)
cout<<*role<<" ";
cout<<endl;

for(role = actors2.begin(); role != actors2.end(); ++role)
cout<<*role<<" ";
cout<<endl;

// Notice how we create the output iterator for the fifth argument:
set_union(actors1.begin(), actors1.end(),
actors2.begin(), actors2.end(),
inserter(result, result.begin()));
for (role = result.begin(); role != result.end(); ++role) {
cout << *role << " ";
}
cout << endl;


//demonstrate how to use node iterator for node template class
node<int> *head_ptr = new node<int>();
list_head_insert(head_ptr, 42);
list_head_insert(head_ptr, 13);
list_head_insert(head_ptr, 67);

node_iterator<int> start(head_ptr);
node_iterator<int> finish;
node_iterator<int> position;

for(position = start; position != finish; ++position)
cout<<*position<< " ";
cout<<endl;


//demonstrate bag template class
bag<int> bag_of_int;
bag<string> bag_of_string;

bag_of_int.insert(3);
bag_of_string.insert("hello");
bag_of_string.insert("goodbye");
bag_of_string.insert("auf wiedersehen");
bag_of_string.insert("goodbye");
bag_of_string.insert("hello");
bag_of_string.insert("goodbye");

cout << "count of goodbye: " << bag_of_string.count("goodbye") << endl;
cout << "count of guten morgen: " << bag_of_string.count("guten morgen") << endl;
cout << "count of 3: " << bag_of_int.count(3) << endl;

for(bag<string>::iterator cursor = bag_of_string.begin(); cursor != bag_of_string.end(); ++cursor)
cout<<*cursor<< " ";
cout<<endl;

return EXIT_SUCCESS;
}

Explanation / Answer

#ifndef BAG5_H
#define BAG5_H

#include <cstdlib> // Provides NULL and size_t and NULL
#include "node2.h" // Provides node class

      void print_value_range(const Item& x, const Item& y);

// CONST MEMBER FUNCTIONS
size_type count(const Item& target) const;
Item grab( ) const;
size_type size( ) const { return many_nodes; }

   // FUNCTIONS TO PROVIDE ITERATORS
   iterator begin( )
   { return iterator(head_ptr); }
   const_iterator begin( ) const
   { return const_iterator(head_ptr); }
   iterator end( )
   { return iterator( ); } // Uses default constructor
   const_iterator end( ) const
   { return const_iterator( ); } // Uses default constructor