Use the following program to test your ADT Bag implemented by doubly linked list
ID: 3591002 • Letter: U
Question
Use the following program to test your ADT Bag implemented by doubly linked list
// This program tests the ADT Bag class which is implemented by a doubly
// linked list.
#include <iostream>
#include <string>
#include "DLinkedBag.h" //doubly linked list bag
using namespace std;
void displayBag(const DLinkedBag<string>& bag)
{
cout << "The bag contains " << bag.getCurrentSize()
<< " items:" << endl;
vector<string> bagItems = bag.toVector();
int numberOfEntries = (int) bagItems.size();
for (int i = 0; i < numberOfEntries; i++)
{
cout << bagItems[i] << " ";
} // end for
cout << endl << endl;
} // end displayBag
void bagTester(DLinkedBag<string>& bag)
{
cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 1 (true)" << endl;
displayBag(bag);
string items[] = {"one", "two", "three", "four", "five", "one"};
cout << "Add 6 items to the bag: " << endl;
for (int i = 0; i < 6; i++)
{
bag.add(items[i]);
} // end for
displayBag(bag);
cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 0 (false)" << endl;
cout << "getCurrentSize: returns " << bag.getCurrentSize()
<< "; should be 6" << endl;
cout << "Try to add another entry: add("extra") returns "
<< bag.add("extra") << endl;
cout << "contains("three"): returns " << bag.contains("three")
<< "; should be 1 (true)" << endl;
cout << "contains("ten"): returns " << bag.contains("ten")
<< "; should be 0 (false)" << endl;
cout << "getFrequencyOf("one"): returns "
<< bag.getFrequencyOf("one") << " should be 2" << endl;
cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 1 (true)" << endl;
cout << "getFrequencyOf("one"): returns "
<< bag.getFrequencyOf("one") << " should be 1" << endl;
cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 1 (true)" << endl;
cout << "remove("one"): returns " << bag.remove("one")
<< "; should be 0 (false)" << endl;
cout << endl;
displayBag(bag);
cout << "After clearing the bag, ";
bag.clear();
cout << "isEmpty: returns " << bag.isEmpty()
<< "; should be 1 (true)" << endl;
} // end bagTester
int main()
{
DLinkedBag<string> bag;
cout << "Testing the Link-Based Bag:" << endl;
cout << "The initial bag is empty." << endl;
bagTester(bag);
cout << "All done!" << endl;
return 0;
} // end main
[Hint: you need to define a class to represent a node in a doubly linked list by modifying the node class we used for linked base implementation of ADT Bag]
Explanation / Answer
Given below is the implentation of DLinkedBag and output. Please don't forget to rate the answer if it helped. Thank you.
DLNode.h
#ifndef DLNode_h
#define DLNode_h
template <typename T>
class DLNode
{
private:
T data;
DLNode<T> *prev;
DLNode<T> *next;
public:
DLNode(T data);
DLNode(T data, DLNode<T>* prev, DLNode<T>* next);
T getData();
void setData();
DLNode<T>* getPrevious();
DLNode<T>* getNext();
void setPrevious(DLNode<T>* p);
void setNext(DLNode<T>* n);
};
template <typename T>
DLNode<T>::DLNode(T data)
{
this->data = data;
this->prev = NULL;
this->next = NULL;
}
template <typename T>
DLNode<T>::DLNode(T data, DLNode<T>* prev, DLNode<T>* next)
{
this->data = data;
setPrevious(prev);
setNext(next);
}
template <typename T>
T DLNode<T>::getData()
{
return data;
}
template <typename T>
void DLNode<T>::setData()
{
this->data = data;
}
template <typename T>
DLNode<T>* DLNode<T>::getPrevious()
{
return prev;
}
template <typename T>
DLNode<T>* DLNode<T>::getNext()
{
return next;
}
template <typename T>
void DLNode<T>::setPrevious(DLNode<T>* p)
{
this->prev = p;
if(p != NULL)
p->next = this;
}
template <typename T>
void DLNode<T>::setNext(DLNode<T>* n)
{
this->next = n;
if(n != NULL)
n->prev = this;
}
#endif /* DLNode_h */
DLinkedBag.h
#ifndef DLinkedBag_h
#define DLinkedBag_h
#include "DLNode.h"
#include <vector>
using namespace std;
template <typename T>
class DLinkedBag
{
private:
DLNode<T> *head, *tail;
int count;
public:
DLinkedBag();
vector<T> toVector() const;
bool contains(T data);
int getFrequencyOf(T data);
int getCurrentSize() const;
bool add(T data);
bool remove(T data);
bool isEmpty();
void clear();
};
template <typename T>
DLinkedBag<T>::DLinkedBag()
{
head = NULL;
tail = NULL;
count = 0;
}
template <typename T>
vector<T> DLinkedBag<T>::toVector() const
{
vector<T> v ;
DLNode<T>* curr = head;
while(curr != NULL)
{
v.push_back(curr->getData());
curr = curr->getNext();
}
return v;
}
template <typename T>
bool DLinkedBag<T>::contains(T data)
{
DLNode<T>* curr = head;
while(curr != NULL)
{
if(curr->getData() == data)
return true;
curr = curr->getNext();
}
return false;
}
template <typename T>
int DLinkedBag<T>::getFrequencyOf(T data)
{
DLNode<T>* curr = head;
int total = 0;
while(curr != NULL)
{
if(curr->getData() == data)
total++;
curr = curr->getNext();
}
return total;
}
template <typename T>
int DLinkedBag<T>::getCurrentSize() const
{
return count;
}
template <typename T>
bool DLinkedBag<T>::add(T data)
{
DLNode<T>* n = new DLNode<T>(data, tail, NULL);
tail = n;
if(head == NULL)
head = n;
count++;
return true;
}
template <typename T>
bool DLinkedBag<T>::remove(T data)
{
DLNode<T>* curr =head;
while(curr != NULL)
{
if(curr->getData() == data)
break;
curr = curr->getNext();
}
if(curr == NULL)
return false;
else
{
DLNode<T>* prev = curr->getPrevious();
if(curr == head) //deleteing head node
head = curr->getNext();
else
prev->setNext(curr->getNext());
if(head == NULL) //delete the only single item in bag
tail = NULL;
delete curr;
count--;
return true;
}
}
template <typename T>
bool DLinkedBag<T>::isEmpty()
{
return count == 0;
}
template <typename T>
void DLinkedBag<T>::clear()
{
if(head == NULL) return;
DLNode<T>* curr = head;
while(curr != NULL)
{
DLNode<T>* next = curr->getNext();
delete curr;
curr = next;
}
head = NULL;
tail = NULL;
count = 0;
}
#endif /* DLinkedBag_h*/
output
Testing the Link-Based Bag:
The initial bag is empty.
isEmpty: returns 1; should be 1 (true)
The bag contains 0 items:
Add 6 items to the bag:
The bag contains 6 items:
one two three four five one
isEmpty: returns 0; should be 0 (false)
getCurrentSize: returns 6; should be 6
Try to add another entry: add("extra") returns 1
contains("three"): returns 1; should be 1 (true)
contains("ten"): returns 0; should be 0 (false)
getFrequencyOf("one"): returns 2 should be 2
remove("one"): returns 1; should be 1 (true)
getFrequencyOf("one"): returns 1 should be 1
remove("one"): returns 1; should be 1 (true)
remove("one"): returns 0; should be 0 (false)
The bag contains 5 items:
two three four five extra
After clearing the bag, isEmpty: returns 1; should be 1 (true)
All done!
Program ended with exit code: 0