Question

Requirements

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);

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]

x = 2

y = 5

prints 2 3 4

Bag [1,2,3,4,5,6,7]

x = 2

y = 78

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)

Remove repetitions

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

Write test program to test the above two member functions

-----------------------------------------------------------------------------------------------------------------------------------------------

#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);

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

void remove_repetitions();

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

---------------------------------------------------------------------------------------------------

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

// implement function

}

  

template < class Item >

void bag <Item > :: remove_repetitions() {

// implement function

}

  

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;

}

-----------------------------------------------------------------------------------------------------

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;

}

----------------------------------------------------------------------------------------------------------------

#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

Answer 1

#ifndef NODE_H
#define NODE_H

class node
{
public:
// TYPEDEF
typedef int value_type;
  
// CONSTRUCTOR
node(
   const value_type& init_data = value_type( ),
   node* init_link = NULL
)
{
data_field = init_data;
link_field = init_link;
}

// Member functions to set the data and link fields:
void set_data(const value_type& new_data) { data_field = new_data; }
void set_link(node* new_link) { link_field = new_link; }

// Constant member function to retrieve the current data:
value_type data( ) const { return data_field; }

// Two slightly different member functions to retreive
// the current link:
const node* link( ) const { return link_field; }
node* link( ) { return link_field; }
  
private:
value_type data_field;
node* link_field;
};

#endif

// ASSIGNMENT.CPP

#include <iostream>
#include "node.h"
using namespace std;

void printData(node* head, const node::value_type& x,
const node::value_type& y);

int main()
{
node* p = new node(2);
p->set_link(new node(5));
p->link()->set_link(new node(7));
p->link()->link()->set_link(new node(9));
p->link()->link()->link()->set_link(new node(11));

printData(p, 5, 9);

return 0;
}

void printData(node* head, const node::value_type& x,
const node::value_type& y)
{
node* firstx = NULL;

while (head != NULL && firstx == NULL)
{
if (head->data() == x)
firstx = head;
head = head->link();
}

while (firstx != NULL)
{
cout << firstx->data() << " ";
if (firstx->data() == y)
break;
firstx = firstx->link();
}
cout << endl;
}