15.9 PROGRAM 7: SortedSet class Implement a SortedSet class that is a specializa
ID: 3906592 • Letter: 1
Question
15.9 PROGRAM 7: SortedSet class
Implement a SortedSet class that is a specialization of the IntList class you implemented for PROGRAM 5.
IntList class
The only change to the IntList class from PROGRAM 5 is to change the access privileges of the data fields from private to protected. You may not change or add anything else to the IntList class. If you did not get 100% on the IntList class, you should fix this class first so that you do get 100% on it before going on to the SortedSet class.
SortedSet class
A set is a collection of unique values. That is, a list that does not have any duplicates. In our case, we will also keep the list sorted (ascending order), so our type will be SortedSet. Our SortedSet is a specialization of the IntList you designed for PROGRAM 5, so your SortedSet class will inherit from the IntList class.
You are required to come up with a separate header file (.h) and separate implementation file (.cpp) for the SortedSet class. You should also come up with your own test harness to test just the functions you are currently working on while you are developing the SortedSet class. Never implement more than 1 or 2 member functions without fulling testing them with your own test harness. You can comment out tests once you have verified your function(s) work, but do not delete these tests.
Constructors & Destructor
SortedSet(): The default constructor initializes an empty set.
SortedSet(const SortedSet &): The copy constructor initializes the set to be a copy of the set passed in. Use the IntList copy constructor.
SortedSet(const IntList &): A copy constructor that is passed an IntList instead of a SortedSet. It should initialize the set using the values in the IntList. Again, you can use the IntList copy constructor and then remove all of the duplicates and sort the remaining values.
~SortedSet(): The destructor needs to deallocate all dynamically allocated memory that the IntList destructor will not already deallocate. You may very well find that this function does not need to do anything.
Accessors
in(int data): This function returns true if the value in data is a member of the set, otherwise false.
operator|: This function returns a SortedSet object that is the union of 2 SortedSet objects, the left and right operands of this binary operator. A union of 2 sets is a set that consists of all of the distinct elements of both sets combined. That is, all of the values in both sets, minus any duplicates.
sset1 = sset2 | sset3;
operator&: This function returns a SortedSet object that is the intersection of 2 SortedSet objects, the left and right operands of this binary operator. An intersection of 2 sets is a set of all elements that are in both sets. That is, all of the values that are in both the left operand and the right operand.
sset1 = sset2 & sset3;
Mutators
add(int data): This function adds the value in data to the set. It needs to make sure data does not already exist in the set (no duplicates) and that it is inserted in the proper position (in ascending order).
This must be an O(n) operation (essentially meaning only going through the list once).
This means you cannot call remove_duplicates or selection_sort member functions within this function. Instead, this function must go through the list once (and only once) looking for the location to add the new value and then inserting it only if that location does not already have the value located there. This will be O(n) because you will visit each node in the list at most once. Recall, the remove_duplicates and selection_sort functions are O(n2) functions.
So, this function is basically the insert_sorted function from your IntList, only you don't insert duplicates.
push_front(int data): Override this function so that it inserts the value in data in the proper position (in ascending order) only if the value does not already exist in the set (no duplicates).
In other words, this function should do exactly what add does. The only reason we are overriding this function is so that the push_front from the IntList is not inherited. A user of the SortedSet should not be able to just push any value onto the front of the list.
In fact, since this function should do exactly what add does, this function should just call add to do the work for it.
push_back(int data): Override this function so that it inserts the value in data in the proper position (in ascending order) only if the value does not already exist in the set (no duplicates).
See specs for push_front above. The same rationale for overriding applies to this function.
insert_ordered(int data): Override this function so that it does not insert duplicates.
See specs for push_front above. The same rationale for overriding applies to this function.
operator|=: This function is the union-assign operator function. It returns a union of the left and right operands, but also sets the left operand's value to be that union as well.
See operator| function specs above.
operator&=: This function is the intersection-assign operator function. It returns an intersection of the left and right operands, but also sets the left operand's value to be that intersection as well.
Explanation / Answer
#include<iostream>
using namespace std;
// Creating a NODE Structure
typedef struct node
{
int data;
struct node *next;
};
class IntList
{
struct node *top;
public:
IntList() // constructure
{
top=NULL;
}
void push_front(int data); // to insert an element
int pop_front(); // to delete an element
void display(); // to show the list
void insert_ordered(int data); //to insert in ordered list
void selection_sort(); //to sort list
void remve_duplicates(); //to remove duplicates
void push_back(int data); //to push data at end
};
int isEmpty(struct node *top)
{
if (top == NULL)
return 1;
return 0;
}
// PUSH Operation
void IntList::push_front(int value)
{
//int value;
struct node *ptr =(struct node *)malloc(sizeof(*ptr));
if (ptr == NULL)
{
fprintf(stderr, "Memory allocation failed. ");
return;
}
ptr=new node;
ptr->data=value;
ptr->next=NULL;
if(top!=NULL)
ptr->next=top;
top=ptr;
}
int IntList::pop_front()
{
struct node *temp;
if(top==NULL)
{
cout<<" The list is empty!!!";
}
temp=top;
top=top->next;
cout<<"POP Operation........ Poped value is "<<temp->data <<endl;
return temp->data;
delete temp;
}
// Show list
void IntList::display()
{
struct node *ptr1=top;
cout<<" The list is ";
while(ptr1!=NULL)
{
cout<<ptr1->data<<" ->";
ptr1=ptr1->next;
}
cout<<"NULL ";
}
//insert order function
void IntList::insert_ordered(int x)
{
struct node *ptr;
if (top == NULL || x > top->data)
{
push_front(x);
return;
}
// If top is greater, remove the top item and recur
int temp = pop_front();
insert_ordered(x);
// Put back the top item removed earlier
push_front(10);
}
// Function to sort list
void IntList::selection_sort()
{
//struct node *ptr;
// If stack is not empty
if (top != NULL)
{
// Remove the top item
int x = pop_front();
// Sort remaining list
selection_sort();
// Push the top item back in sorted list
display();
insert_ordered(x);
}
}
void IntList::remve_duplicates()
{
/* Pointer to traverse the linked list */
struct node* current = top;
/* Pointer to store the next pointer of a node to be deleted*/
struct node* next_next;
/* do nothing if the list is empty */
if (current == NULL)
return;
/* Traverse the list till last node */
while (current->next != NULL)
{
/* Compare current node with next node */
if (current->data == current->next->data)
{
/* The sequence of steps is important*/
next_next = current->next->next;
free (current->next);
current->next = next_next;
}
else /* This is tricky: only advance if no deletion */
{
current = current->next;
}
}
}
void IntList::push_back(int data)
{
struct node *new_node=(struct node *)malloc(sizeof(struct node));
new_node->data=data;
new_node->next=NULL;
if(top==NULL)//if list is empty
{
top=new_node;
return;
}
struct node *last=top;//initailly points to the 1st node
while((last)->next != NULL)//traverse till the last node
last=last->next;
last->next=new_node;
}
int main()
{
cout << "Enter a test number(1-5): " << endl;
int test;
cin >> test;
cout << endl;
//tests constructor, destructor, push_front, pop_front, display
if (test == 1) {
cout << " list1 constructor called";
IntList list1;
cout << " pushfront 10";
list1.push_front( 10 );
cout << " pushfront 20";
list1.push_front( 20 );
cout << " pushfront 30";
list1.push_front( 30 );
cout << " list1: ";
list1.display();
cout << " pop";
list1.pop_front();
cout << " list1: ";
list1.display();
cout << " pop";
list1.pop_front();
cout << " list1: ";
list1.display();
cout << " pop";
list1.pop_front();
cout << " list1: ";
list1.display();
cout << endl;
}
if (test == 1) {
cout << "list1 destructor called" << endl;
}
//tests push_back
if (test == 2) {
cout << " list2 constructor called";
IntList list2;
cout << " pushback 10";
list2.push_back( 10 );
cout << " pushback 20";
list2.push_back( 20 );
cout << " pushback 30";
list2.push_back( 30 );
cout << " list2: ";
list2.display();
cout << " pop";
list2.pop_front();
cout << " list2: ";
list2.display();
cout << " pop";
list2.pop_front();
cout << " list2: ";
list2.display();
cout << " pop";
list2.pop_front();
cout << " list2: ";
list2.display();
cout << endl;
}
if (test == 2) {
cout << "list2 destructor called" << endl;
}
//tests selection_sort
if (test == 3)
{
cout << " list3 constructor called";
IntList list3;
cout << " pushfront 20";
list3.push_front( 20 );
cout << " pushfront 10";
list3.push_front( 10 );
cout << " pushfront 30";
list3.push_front( 30 );
cout << " list3: ";
list3.display();
cout << " selection_sort()";
list3.selection_sort();
cout << " list3: ";
list3.display();
cout << " pop";
list3.pop_front();
cout << " pop";
list3.pop_front();
cout << " pop";
list3.pop_front();
cout << " list3: ";
list3.display();
cout << " selection_sort()";
list3.selection_sort();
cout << " list3: ";
list3.display();
cout << " pushfront 10";
list3.push_front( 10 );
cout << " selection_sort()";
list3.selection_sort();
cout << " list3: ";
list3.display();
cout << " pushfront 20";
list3.push_front( 20 );
cout << " list3: ";
list3.display();
cout << " selection_sort()";
list3.selection_sort();
cout << " list3: ";
list3.display();
cout << endl;
}
if (test == 3) {
cout << "list3 destructor called" << endl;
}
//tests insert_sorted
if (test == 4) {
cout << " list4 constructor called";
IntList list4;
cout << " insert 20";
list4.insert_ordered( 20 );
cout << " insert 10";
list4.insert_ordered( 10 );
cout << " insert 30";
list4.insert_ordered( 30 );
cout << " list4: ";
list4.display();
cout << " insert 50";
list4.insert_ordered( 50 );
cout << " list4: ";
list4.display();
cout << " insert 40";
list4.insert_ordered( 40 );
cout << " list4: ";
list4.display();
cout << " insert 11";
list4.insert_ordered( 11 );
cout << " list4: ";
list4.display();
cout << " insert 10";
list4.insert_ordered( 10 );
cout << " list4: ";
list4.display();
cout << " insert 11";
list4.insert_ordered( 11 );
cout << " list4: ";
list4.display();
cout << " insert 9";
list4.insert_ordered( 9 );
cout << " list4: ";
list4.display();
cout << " insert 50";
list4.insert_ordered( 50 );
cout << " list4: ";
list4.display();
cout << " insert 51";
list4.insert_ordered( 51 );
cout << " list4: ";
list4.display();
cout << endl;
}
if (test == 4) {
cout << "list4 destructor called" << endl;
}
//tests remove_duplicates
if (test == 5) {
cout << " list5 constructor called";
IntList list5;
cout << " pushfront 10";
list5.push_front( 10 );
cout << " pushfront 20";
list5.push_front( 20 );
cout << " pushfront 10";
list5.push_front( 10 );
cout << " pushfront 30";
list5.push_front( 30 );
cout << " list5: ";
list5.display();
cout << " remove_duplicates()";
list5.remve_duplicates();
cout << " list5: ";
list5.display();
cout << " pushfront 10";
list5.push_front( 10 );
cout << " list5: ";
list5.display();
cout << " remove_duplicates()";
list5.remve_duplicates();
cout << " list5: ";
list5.display();
cout << " pushfront 20";
list5.push_front( 20 );
cout << " list5: ";
list5.display();
cout << " remove_duplicates()";
list5.remve_duplicates();
cout << " list5: ";
list5.display();
cout << " pushfront 20";
list5.push_front( 20 );
cout << " list5: ";
list5.display();
cout << " remove_duplicates()";
list5.remve_duplicates();
cout << " list5: ";
list5.display();
cout << " pushfront 20";
list5.push_front( 20 );
cout << " pushfront 20";
list5.push_front( 20 );
cout << " list5: ";
list5.display();
cout << " remove_duplicates()";
list5.remve_duplicates();
cout << " list5: ";
list5.display();
cout << " remove_duplicates()";
list5.remve_duplicates();
cout << " list5: ";
list5.display();
cout << " pop";
list5.pop_front();
cout << " pop";
list5.pop_front();
cout << " push_front(30)";
list5.push_front(30);
cout << " list5: ";
list5.display();
cout << " remove_duplicates()" << flush;
list5.remve_duplicates();
cout << " list5: " << flush;
list5.display();
cout << " push_front(30)";
list5.push_front(30);
cout << " push_front(30)";
list5.push_front(30);
cout << " list5: ";
list5.display();
cout << " remove_duplicates()" << flush;
list5.remve_duplicates();
cout << " list5: " << flush;
list5.display();
cout << " remove_duplicates()" << flush;
list5.remve_duplicates();
cout << " list5: " << flush;
list5.display();
cout << " pop";
list5.pop_front();
cout << " list5: ";
list5.display();
cout << " remove_duplicates()" << flush;
list5.remve_duplicates();
cout << " list5: " << flush;
list5.display();
cout << endl;
}
if (test == 5) {
cout << "list5 destructor called" << endl;
}
}
SortedSet.h
#ifndef IntList_SortedSet_h
#define IntList_SortedSet_h
#include "IntList.h"
class SortedSet : public IntList
{
SortedSet();
SortedSet( const SortedSet & );
SortedSet( const IntList & );
~SortedSet( );
const bool in( int data ) const;
const SortedSet operator | (const SortedSet &) const;
const SortedSet operator & (const SortedSet &) const;
void add( int data );
void push_front( int data );
void push_back( int data );
void insert_sorted( int data );
SortedSet& operator |= (const SortedSet &);
SortedSet& operator &= (const SortedSet &);
};
#endif
SortedSet.cpp
#include "SortedSet.h"
#include <iostream>
using namespace std;
SortedSet::SortedSet()
:IntList()
{
}
SortedSet::~SortedSet()
{
}
SortedSet::SortedSet( const SortedSet & a)
:IntList(a)
{
//b.select_sort();
//b.remove_duplicates();
}
SortedSet::SortedSet( const IntList & a)
:IntList(a)
{
remove_duplicates();
select_sort();
}
const bool SortedSet::in( int data ) const
{
for (IntNode *curr = head; curr != 0; curr = curr->next)
{
if(data == curr->data)
{
return true;
}
}
return false;
}
void SortedSet::add( int data )
{
int value = data;
if(head == 0)
{
IntList::push_front(value);
}
else
{
if(value < head->data)
{
IntList::push_front(value);
}
else if(value > tail->data)
{
IntList::push_back(value);
}
else
{
IntNode *prev = head;
IntNode *curr = head->next;
IntNode *temp = new IntNode(value);
while(curr != 0 && curr->next != 0)
{
if(value > prev->data && value < curr->data)
{
temp->next = curr;
prev->next = temp;
prev = curr;
curr = curr->next;
}
prev = curr;
curr = curr->next;
}
if(value > prev->data && value < curr->data)
{
temp->next = curr;
prev->next = temp;
}
}
}
}
void SortedSet::push_front( int data )
{
add(data);
}
void SortedSet::push_back( int data )
{
add(data);
}
void SortedSet::insert_sorted( int data )
{
add(data);
}
const SortedSet SortedSet::operator | (const SortedSet & b) const
{
SortedSet c = *this;
for (IntNode *curr = b.head; curr != 0; curr = curr->next)
{
c.insert_sorted(curr->data);
}
return c;
}
const SortedSet SortedSet::operator & (const SortedSet & b) const
{
}
SortedSet & SortedSet::operator |= (const SortedSet & b)
{
SortedSet c = *this;
for (IntNode *curr = b.head; curr != 0; curr = curr->next)
{
c.insert_sorted(curr->data);
}
return c;
}
SortedSet & SortedSet::operator &= (const SortedSet & b)
{
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.