*****************************NODE2.TEMPLATE************ // 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; }

**************************BAG5.H***************

#include // 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 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 class Item>

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.{ 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;}

********************Please include the bag template file with the two new implemented functions, and also the test program to test those member functions.

thank you

Objectives The purpose of this assignment is to reinforce linked-list version of the bag template class with an iterator in C++. You need to use HW6_Templates zipped files posted on the course Requirements 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 y. You may 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)i 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] prints 2 3 4 Bag 1,2,3,4,5,6,7] prints 2 3 4 5 6 7 Bag [ 1,2,3,4,5, 6, 7] x=2 y-1 prints 2 3 4 5 6 7 Bag [ 1,2,3,4,5, 6, 7] x=8 Y 5 prints (nothing) 2. Remove repetitions Write a member function that deletes al repetitions from the bag. In your assume that items can be compared for equality using Use the following header for the function: void remove_repetitions Here is a brief outline of an algorithm: A node pointer p steps through the bag .For each Item, define a new pointer q equal to p * While the q is not the last Item in the bag If the next Item has data equal to the data in p, remove the next Item Otherwise move q to the next Item in the bag o o