I need to se the bag iterator to print the Items from x to y including the start but not including the end. . If there is no element in the bag that has value x, print nothing Otherwise, if there is no element in the bag, after x, that has the value y, then print from x to the end of the list, and finally the funcion should print the values on one line separated by space.

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 (a collection of items; each item may appear multiple times) // // TYPEDEFS for the bag template class: // bag::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::size_type // This is the data type of any variable that keeps track of how many items // are in a bag // // bag::iterator and bag::const_iterator // Forward iterators for a bag or a const bag. // // CONSTRUCTOR for the bag class: // bag( ) // Postcondition: The bag is empty. // // MODIFICATION MEMBER FUNCTIONS for the bag 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 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 class: // template // bag operator +(const bag& b1, const bag& b2) // Postcondition: The bag returned is the union of b1 and b2. // // VALUE SEMANTICS for the bag class: // Assignments and the copy constructor may be used with bag objects. // // DYNAMIC MEMORY USAGE by the bag: // If there is insufficient dynamic memory, then the following functions throw // bad_alloc: The constructors, insert, operator +=, operator +, and the // assignment operator.

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

template class bag { public: // TYPEDEFS typedef std::size_t size_type; typedef Item value_type; typedef node_iterator iterator; typedef const_node_iterator 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 *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 bag operator +(const bag& b1, const bag& 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 // Provides assert #include // Provides NULL, rand #include "node2.h" // Provides node

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

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

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

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

template typename bag::size_type bag::count(const Item& target) const // Library facilities used: cstdlib, node2.h { size_type answer; const node *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 typename bag::size_type bag::erase(const Item& target) // Library facilities used: cstdlib, node2.h { size_type answer = 0; node *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 bool bag::erase_one(const Item& target) // Library facilities used: cstdlib, node2.h { node *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 Item bag::grab( ) const // Library facilities used: cassert, cstdlib, node2.h { size_type i; const node *cursor;

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

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

template void bag::operator +=(const bag& addend) // Library facilities used: node2.h { node *copy_head_ptr; node *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 void bag::operator =(const bag& source) // Library facilities used: node2.h { node *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 bag operator +(const bag& b1, const bag& b2) { bag 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. // The node_iterator is a forward iterators with two constructors: // (1) A constructor (with a node* 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* . // // TYPEDEF for the node 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::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::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 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 *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 *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 class: // const Item& data( ) const 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 // void list_remove(node* 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 // NodePtr list_search // (NodePtr head_ptr, const Item& target) // The NodePtr may be either node* or const node* // 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 // Provides NULL and size_t #include // Provides iterator and forward_iterator_tag

template 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 void list_clear(node*& head_ptr);

template void list_copy (const node* source_ptr, node*& head_ptr, node*& tail_ptr);

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

template void list_head_remove(node*& head_ptr);

template void list_insert(node* previous_ptr, const Item& entry); template std::size_t list_length(const node* head_ptr);

template NodePtr list_locate(NodePtr head_ptr, SizeType position);

template void list_remove(node* previous_ptr); template 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 node_iterator : public std::iterator { public: node_iterator(node* 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* current; };

template class const_node_iterator : public std::iterator { public: const_node_iterator(const node* 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* 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 // Provides assert #include // Provides NULL and size_t

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

template void list_copy( const node* source_ptr, node*& head_ptr, node*& 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 void list_head_insert(node*& head_ptr, const Item& entry) { head_ptr = new node(entry, head_ptr); }

template void list_head_remove(node*& head_ptr) { node *remove_ptr;

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

template void list_insert(node* previous_ptr, const Item& entry) { node *insert_ptr; insert_ptr = new node(entry, previous_ptr->link( )); previous_ptr->set_link(insert_ptr); }

template std::size_t list_length(const node* head_ptr) // Library facilities used: cstdlib { const node *cursor; std::size_t answer; answer = 0; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) ++answer; return answer; }

template NodePtr list_locate(NodePtr head_ptr, SizeType position) // Library facilities used: cassert, cstdlib { NodePtr cursor; SizeType i; assert(0 link( ); return cursor; }

template void list_remove(node* previous_ptr) { node *remove_ptr;

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

template 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 #include #include #include #include "node2.h" #include "bag5.h"

using namespace std;

// PROTOTYPE for a function used by this demonstration program template void get_items(bag& 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 > user_input; collection.insert(user_input); } cout

int main() { //demostrate how to use set template class set actors1; set actors2; set result; set::iterator role; actors1.insert("moe"); actors1.insert("curly"); actors2.insert("larry"); actors2.insert("curly"); for(role = actors1.begin(); role != actors1.end(); ++role) cout

node_iterator start(head_ptr); node_iterator finish; node_iterator position; for(position = start; position != finish; ++position) cout

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

for(bag::iterator cursor = bag_of_string.begin(); cursor != bag_of_string.end(); ++cursor) cout 1. Print a range Write a bag member function with two parameters. The two parameters are Items x and y. The function should write to the console all Items in the bag that are between the first occurrence of x and the first occurrence of v. You mav assume that items can be compared for equality using Use the following header for the function: void print value range (const Item& x, const Item& y); print value range can be interpreted in a number of ways, but use the following points. This should make the implementation a little easier. Print the Items from x to y including the start but not including the end. . If there is no element in the bag that has value x, print nothing Otherwise, if there is no element in the bag, after x, that has the value y, then print from x to the end of the list Print the values on one line separated by space. Put an end of line after the values are all printed. Here are some examples: Bag [1, 2,3,4,5, 6,7] 2 3 4 prints Bag [1,2,3,4,5, 6, 7] y=78 prints 2 3 4 5 67 1. Print a range Write a bag member function with two parameters. The two parameters are Items x and y. The function should write to the console all Items in the bag that are between the first occurrence of x and the first occurrence of v. You mav assume that items can be compared for equality using Use the following header for the function: void print value range (const Item& x, const Item& y); print value range can be interpreted in a number of ways, but use the following points. This should make the implementation a little easier. Print the Items from x to y including the start but not including the end. . If there is no element in the bag that has value x, print nothing Otherwise, if there is no element in the bag, after x, that has the value y, then print from x to the end of the list Print the values on one line separated by space. Put an end of line after the values are all printed. Here are some examples: Bag [1, 2,3,4,5, 6,7] 2 3 4 prints Bag [1,2,3,4,5, 6, 7] y=78 prints 2 3 4 5 67