Question

Write a member function that deletes all repetitions from the bag. In your implementation, 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

This is what I have so far, the issue being it doesn't delete properly and does not print out the list. Thanks in advance!

template <class Item>
void bag<Item>::remove_repetitions(){
    std::cout<<"Working progress"<<std::endl;
    node<Item> *p;
    //node<Item> *temp;
    p=head_ptr;
    while(p!=NULL && p->link()!=NULL){
        node<Item> *q;
        node<Item> *target;
        for(q=p->link(); q!=NULL; q=q->link()){
            if(p->data()==q->data()){
                target = q;
                q->set_link(q->link());
                delete(target);
            }
        }
        p=p->link();
    }
}

//The main file

#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.\n";
    cout << "Press the <return> key after the final entry:\n";
    for (i = 1; i <= n; ++i)
    {
        cin >> user_input;
        collection.insert(user_input);
    }
    cout << endl;
}

int main()
{
    //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;
  
   bag<int> bag_int;
   bag_int.insert (7);
   bag_int.insert (6);
   bag_int.insert (5);
   bag_int.insert (4);
   bag_int.insert (5);
   bag_int.insert (3);
   bag_int.insert (2);
   bag_int.insert (1);
   bag_int.insert (1);
   bag_int.insert (5);
   bag_int.print_value_range (5,20);
   bag_int.remove_repetitions();
   bag_int.print_value_range (5,20);
   return EXIT_SUCCESS;
  
}

#ifndef NODE2_H
#define NODE2_H

//the node header file with template implementations
#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

#ifndef BAG5_H
#define BAG5_H

//bag header file with template
#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);
        void print_value_range(const Item& x, const Item& y);
        void remove_repetitions(); //<-- Implement this!!!!!

        // 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

Answer 1

template <class Item>
void bag<Item>::remove_repetitions(){
  
   std::cout<<"Working progress"<<std::endl;
node<Item> *p = head_ptr;
  
   // loop over the bag from start to last element
   while(p!=NULL && p->link()!=NULL){
// set q equal to p
       node<Item> *q = p;
       // set next equal to node next to p
       node<Item> *next = p->link();
// loop over the bag from node next to p to end
       while(next != NULL)
       {
// next's data = p's data
           if(p->data() == next->data())
           {
               // delete next node
               // update link of q to node next to next
q->set_link(next->link());
               // delete the next node
               next->set_link(NULL);
               delete(next);
               // update next to new node next to q
               next = q->link();
}
           else // next's data != p's data
           {
               // set q to next
               q = next;
               // update next to node after next
               next = next->link();
           }
}
      
       // set p to node next to p
p=p->link();
}  
}