Question

IntList Lab Specifications

You are required to come up with a single header file (IntList.h) that declares and implements the IntNode class (just copy it exactly as it is below) as well as declares the IntList Class interface only. You are also required to come up with a separate implementation file (IntList.cpp) that implements the member functions of the IntList class. While developing your IntList class you must write your own test harness (within a file named main.cpp). Never implement more than 1 or 2 member functions without fulling testing them with your own test harness.

IntNode struct

I am providing the IntNode class you are required to use. Place this class definition within the IntList.h file exactly as is. Make sure you place it above the definition of your IntList class. Notice that you will not code an implementation file for the IntNode class. The IntNode constructor has been defined inline (within the class declaration). Do not write any other functions for the IntNode class. Use as is.

struct IntNode {
    int data;
    IntNode *next;
    IntNode(int data) : data(data), next(0) {}
};

ntList class

Encapsulated (Private) Data Fields

head: IntNode *

tail: IntNode *

Public Interface (Public Member Functions)

IntList(): Initializes an empty list.

~IntList(): Deallocates all remaining dynamically allocated memory (all remaining IntNodes).

void display() const: Displays to a single line all of the int values stored in the list, each separated by a space. This function does NOT output a newline or space at the end.

void push_front(int value): Inserts a data value (within a new node) at the front end of the list.

void pop_front(): Removes the value (actually removes the node that contains the value) at the front end of the list. Does nothing if the list is already empty.

bool empty() const: Returns true if the list does not store any data values (does not have any nodes), otherwise returns false.

The remaining functions may only be developed in your private workspace. Copy the 3 files from lab 7 into your private workspace before beginning on these functions:

IntList(const IntList &cpy): the copy constructor. Make sure this performs deep copy.

IntList & operator=(const IntList &rhs): the overloaded assignment operator. Make sure this performs deep copy.

void push_back(int value): Inserts a data value (within a new node) at the back end of the list.

void clear(): Removes (deallocates) all IntNodes in the IntList. Don't forget to set both head and tail to appropriate values for an empty list.

void selection_sort(): Sorts the integers in the list into ascending order. Do NOT move the nodes, just the integers.

void insert_ordered(int value): Inserts a data value (within a new node) in an ordered list. Assumes the list is already sorted in ascending order (i.e., Do not sort the list first, assume the list is already is sorted.) This function loops through the list until if finds the correct position for the new data value and then inserts the new IntNode in that location. This function may NOT ever sort the list.

void remove_duplicates(): Removes all duplicate data values (actually removes the nodes that contain the values) within the list. Always remove just the later value within the list when a duplicate is found. This function may NOT ever sort the list.

friend ostream & operator<<(ostream &out, const IntList &rhs): A global friend function that outputs to the stream all of the integer values within the list on a single line, each separated by a space. This function does NOT send to the stream a newline or space at the end.

main.cpp test harness for PROGRAM

Use this main.cpp file for testing your IntList.

#include "IntList.h"

#include <iostream>
using namespace std;

int main()
{
   cout << "Enter a test number(1-5): ";
    int test;
    cin >> test;
    cout << endl;
   //tests constructor, destructor, push_front, pop_front, display
   if (test == 1) {
      cout << "\nlist1 constructor called";
      IntList list1;
      cout << "\npushfront 10";
      list1.push_front( 10 );
      cout << "\npushfront 20";
      list1.push_front( 20 );
      cout << "\npushfront 30";
      list1.push_front( 30 );
      cout << "\nlist1: ";
      list1.display();
      cout << "\npop";
      list1.pop_front();
      cout << "\nlist1: ";
      list1.display();
      cout << "\npop";
      list1.pop_front();
      cout << "\nlist1: ";
      list1.display();
      cout << "\npop";
      list1.pop_front();
      cout << "\nlist1: ";
      list1.display();
      cout << endl;
   }
   if (test == 1) {
      cout << "list1 destructor called" << endl;
   }

   //tests push_back
   if (test == 2) {
      cout << "\nlist2 constructor called";
      IntList list2;
      cout << "\npushback 10";
      list2.push_back( 10 );
      cout << "\npushback 20";
      list2.push_back( 20 );
      cout << "\npushback 30";
      list2.push_back( 30 );
      cout << "\nlist2: ";
      list2.display();
      cout << "\npop";
      list2.pop_front();
      cout << "\nlist2: ";
      list2.display();
      cout << "\npop";
      list2.pop_front();
      cout << "\nlist2: ";
      list2.display();
      cout << "\npop";
      list2.pop_front();
      cout << "\nlist2: ";
      list2.display();
      cout << endl;
   }
   if (test == 2) {
      cout << "list2 destructor called" << endl;
   }

   //tests selection_sort
   if (test == 3)
   {
      cout << "\nlist3 constructor called";
      IntList list3;
      cout << "\npushfront 10";
      list3.push_front( 10 );
      cout << "\npushfront 20";
      list3.push_front( 20 );
      cout << "\npushfront 30";
      list3.push_front( 30 );
      cout << "\nlist3: ";
      list3.display();
      cout << "\nselection_sort()";
      list3.selection_sort();
      cout << "\nlist3: ";
      list3.display();
      cout << "\npop";
      list3.pop_front();
      cout << "\npop";
      list3.pop_front();
      cout << "\npop";
      list3.pop_front();
      cout << "\nlist3: ";
      list3.display();
      cout << "\nselection_sort()";
      list3.selection_sort();
      cout << "\nlist3: ";
      list3.display();
      cout << "\npushfront 10";
      list3.push_front( 10 );
      cout << "\nselection_sort()";
      list3.selection_sort();
      cout << "\nlist3: ";
      list3.display();
      cout << "\npushfront 20";
      list3.push_front( 20 );
      cout << "\nlist3: ";
      list3.display();
      cout << "\nselection_sort()";
      list3.selection_sort();
      cout << "\nlist3: ";
      list3.display();
      cout << endl;
   }
   if (test == 3) {
      cout << "list3 destructor called" << endl;
   }

   //tests insert_sorted
   if (test == 4) {
      cout << "\nlist4 constructor called";
      IntList list4;
      cout << "\ninsert 20";
      list4.insert_ordered( 20 );
      cout << "\ninsert 10";
      list4.insert_ordered( 10 );
      cout << "\ninsert 30";
      list4.insert_ordered( 30 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 50";
      list4.insert_ordered( 50 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 40";
      list4.insert_ordered( 40 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 11";
      list4.insert_ordered( 11 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 10";
      list4.insert_ordered( 10 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 11";
      list4.insert_ordered( 11 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 9";
      list4.insert_ordered( 9 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 50";
      list4.insert_ordered( 50 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 51";
      list4.insert_ordered( 51 );
      cout << "\nlist4: ";
      list4.display();
      cout << endl;
   }
   if (test == 4) {
      cout << "list4 destructor called" << endl;
   }

   //tests remove_duplicates
   if (test == 5) {
      cout << "\nlist5 constructor called";
      IntList list5;
      cout << "\npushfront 10";
      list5.push_front( 10 );
      cout << "\npushfront 20";
      list5.push_front( 20 );
      cout << "\npushfront 10";
      list5.push_front( 10 );
      cout << "\npushfront 30";
      list5.push_front( 30 );
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()";
      list5.remove_duplicates();
      cout << "\nlist5: ";
      list5.display();
      cout << "\npushfront 10";
      list5.push_front( 10 );
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()";
      list5.remove_duplicates();
      cout << "\nlist5: ";
      list5.display();
      cout << "\npushfront 20";
      list5.push_front( 20 );
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()";
      list5.remove_duplicates();
      cout << "\nlist5: ";
      list5.display();
      cout << "\npushfront 20";
      list5.push_front( 20 );
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()";
      list5.remove_duplicates();
      cout << "\nlist5: ";
      list5.display();
      cout << "\npushfront 20";
      list5.push_front( 20 );
      cout << "\npushfront 20";
      list5.push_front( 20 );
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()";
      list5.remove_duplicates();
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()";
      list5.remove_duplicates();
      cout << "\nlist5: ";
      list5.display();
      cout << "\npop";
      list5.pop_front();
      cout << "\npop";
      list5.pop_front();
      cout << "\npush_front(30)";
      list5.push_front(30);
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()" << flush;
      list5.remove_duplicates();
      cout << "\nlist5: " << flush;
      list5.display();
      cout << "\npush_front(30)";
      list5.push_front(30);
      cout << "\npush_front(30)";
      list5.push_front(30);
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()" << flush;
      list5.remove_duplicates();
      cout << "\nlist5: " << flush;
      list5.display();
      cout << "\nremove_duplicates()" << flush;
      list5.remove_duplicates();
      cout << "\nlist5: " << flush;
      list5.display();
      cout << "\npop";
      list5.pop_front();
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()" << flush;
      list5.remove_duplicates();
      cout << "\nlist5: " << flush;
      list5.display();
      cout << endl;
   }
   if (test == 5) {
      cout << "list5 destructor called" << endl;
   }

   /*
   * Destructor will be tested by looking at code. There is no run-time 
   * test for it. Make sure your destructor actually deletes ALL nodes, not
   * just the head and/or tail.
   */

   return 0;
}

Answer 1

main.cpp

#include "IntList.h"

#include <iostream>
using namespace std;

int main()
{
   cout << "Enter a test number(1-5): ";
    int test;
    cin >> test;
    cout << endl;
   //tests constructor, destructor, push_front, pop_front, display
   if (test == 1) {
      cout << "\nlist1 constructor called";
      IntList list1;
      cout << "\npushfront 10";
      list1.push_front( 10 );
      cout << "\npushfront 20";
      list1.push_front( 20 );
      cout << "\npushfront 30";
      list1.push_front( 30 );
      cout << "\nlist1: ";
      list1.display();
      cout << "\npop";
      list1.pop_front();
      cout << "\nlist1: ";
      list1.display();
      cout << "\npop";
      list1.pop_front();
      cout << "\nlist1: ";
      list1.display();
      cout << "\npop";
      list1.pop_front();
      cout << "\nlist1: ";
      list1.display();
      cout << endl;
   }
   if (test == 1) {
      cout << "list1 destructor called" << endl;
   }

   //tests push_back
   if (test == 2) {
      cout << "\nlist2 constructor called";
      IntList list2;
      cout << "\npushback 10";
      list2.push_back( 10 );
      cout << "\npushback 20";
      list2.push_back( 20 );
      cout << "\npushback 30";
      list2.push_back( 30 );
      cout << "\nlist2: ";
      list2.display();
      cout << "\npop";
      list2.pop_front();
      cout << "\nlist2: ";
      list2.display();
      cout << "\npop";
      list2.pop_front();
      cout << "\nlist2: ";
      list2.display();
      cout << "\npop";
      list2.pop_front();
      cout << "\nlist2: ";
      list2.display();
      cout << endl;
   }
   if (test == 2) {
      cout << "list2 destructor called" << endl;
   }

   //tests selection_sort
   if (test == 3)
   {
      cout << "\nlist3 constructor called";
      IntList list3;
      cout << "\npushfront 10";
      list3.push_front( 10 );
      cout << "\npushfront 20";
      list3.push_front( 20 );
      cout << "\npushfront 30";
      list3.push_front( 30 );
      cout << "\nlist3: ";
      list3.display();
      cout << "\nselection_sort()";
      list3.selection_sort();
      cout << "\nlist3: ";
      list3.display();
      cout << "\npop";
      list3.pop_front();
      cout << "\npop";
      list3.pop_front();
      cout << "\npop";
      list3.pop_front();
      cout << "\nlist3: ";
      list3.display();
      cout << "\nselection_sort()";
      list3.selection_sort();
      cout << "\nlist3: ";
      list3.display();
      cout << "\npushfront 10";
      list3.push_front( 10 );
      cout << "\nselection_sort()";
      list3.selection_sort();
      cout << "\nlist3: ";
      list3.display();
      cout << "\npushfront 20";
      list3.push_front( 20 );
      cout << "\nlist3: ";
      list3.display();
      cout << "\nselection_sort()";
      list3.selection_sort();
      cout << "\nlist3: ";
      list3.display();
      cout << endl;
   }
   if (test == 3) {
      cout << "list3 destructor called" << endl;
   }

   //tests insert_sorted
   if (test == 4) {
      cout << "\nlist4 constructor called";
      IntList list4;
      cout << "\ninsert 20";
      list4.insert_ordered( 20 );
      cout << "\ninsert 10";
      list4.insert_ordered( 10 );
      cout << "\ninsert 30";
      list4.insert_ordered( 30 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 50";
      list4.insert_ordered( 50 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 40";
      list4.insert_ordered( 40 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 11";
      list4.insert_ordered( 11 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 10";
      list4.insert_ordered( 10 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 11";
      list4.insert_ordered( 11 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 9";
      list4.insert_ordered( 9 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 50";
      list4.insert_ordered( 50 );
      cout << "\nlist4: ";
      list4.display();
      cout << "\ninsert 51";
      list4.insert_ordered( 51 );
      cout << "\nlist4: ";
      list4.display();
      cout << endl;
   }
   if (test == 4) {
      cout << "list4 destructor called" << endl;
   }

   //tests remove_duplicates
   if (test == 5) {
      cout << "\nlist5 constructor called";
      IntList list5;
      cout << "\npushfront 10";
      list5.push_front( 10 );
      cout << "\npushfront 20";
      list5.push_front( 20 );
      cout << "\npushfront 10";
      list5.push_front( 10 );
      cout << "\npushfront 30";
      list5.push_front( 30 );
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()";
      list5.remove_duplicates();
      cout << "\nlist5: ";
      list5.display();
      cout << "\npushfront 10";
      list5.push_front( 10 );
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()";
      list5.remove_duplicates();
      cout << "\nlist5: ";
      list5.display();
      cout << "\npushfront 20";
      list5.push_front( 20 );
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()";
      list5.remove_duplicates();
      cout << "\nlist5: ";
      list5.display();
      cout << "\npushfront 20";
      list5.push_front( 20 );
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()";
      list5.remove_duplicates();
      cout << "\nlist5: ";
      list5.display();
      cout << "\npushfront 20";
      list5.push_front( 20 );
      cout << "\npushfront 20";
      list5.push_front( 20 );
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()";
      list5.remove_duplicates();
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()";
      list5.remove_duplicates();
      cout << "\nlist5: ";
      list5.display();
      cout << "\npop";
      list5.pop_front();
      cout << "\npop";
      list5.pop_front();
      cout << "\npush_front(30)";
      list5.push_front(30);
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()" << flush;
      list5.remove_duplicates();
      cout << "\nlist5: " << flush;
      list5.display();
      cout << "\npush_front(30)";
      list5.push_front(30);
      cout << "\npush_front(30)";
      list5.push_front(30);
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()" << flush;
      list5.remove_duplicates();
      cout << "\nlist5: " << flush;
      list5.display();
      cout << "\nremove_duplicates()" << flush;
      list5.remove_duplicates();
      cout << "\nlist5: " << flush;
      list5.display();
      cout << "\npop";
      list5.pop_front();
      cout << "\nlist5: ";
      list5.display();
      cout << "\nremove_duplicates()" << flush;
      list5.remove_duplicates();
      cout << "\nlist5: " << flush;
      list5.display();
      cout << endl;
   }
   if (test == 5) {
      cout << "list5 destructor called" << endl;
   }

   /*
   * Destructor will be tested by looking at code. There is no run-time
   * test for it. Make sure your destructor actually deletes ALL nodes, not
   * just the head and/or tail.
   */

   return 0;
}

IntList.cpp

#include <iostream>
// #include <algorithm>
using namespace std;

#include "IntList.h"

IntList::IntList(): head(0), tail(0) {}

IntList::~IntList(){
    while (!empty()) {
        pop_front();
    }
}

void IntList::display() const{
    //cout << "Display called." << endl;
    if(empty()) {
        return;
    }
    else {
        IntNode* currentNode = head;
        // currentNode = head->next;
        cout << currentNode->data;
        while(currentNode->next != 0) {
            currentNode = currentNode->next;
            cout << ' ' << currentNode->data;
        }
    }
  
    //tests head and tail addresses, next, and data;
}

void IntList::push_front(int value){
  
    IntNode* temp = new IntNode(value);
  
    temp->next = head;
    head = temp;
    if(tail == 0) {   //if initially empty node
        tail = temp;
    }
}

void IntList::pop_front(){
    if(empty()) {
        return;
    }
    else {
        IntNode* temp = head;
        head = head->next;
        delete temp;
    }
    if(head == 0) { //if go to empty node
        tail = 0;
        // cout << "THIS HAPPENS" << endl;
    }
  
}

bool IntList::empty() const{
    if(head == 0 && tail == 0) {
        return true;
    }
    return false;
}

//if list1=list1, that's self assignment, so just do nothing! >:D

IntList::IntList(const IntList &cpy) {
    // if(cpy.empty()) {
    //     head = 0;
    //     tail = 0;
    // }
    head = 0;
    tail = 0;
    //TODO what if there's only one node????????????
    if(!cpy.empty()) {
        IntNode* curr = cpy.head;
        // cout << endl;
        while(curr != 0) {
            // data = curr->data;
            // next = curr->next;
            push_back(curr->data);
            curr = curr->next;
        }
    }

}

IntList & IntList::operator=(const IntList &rhs) {
    if (this == &rhs) {
        return *this;
    }
    else if(rhs.empty()) {
        head = 0;
        tail = 0;
    }
    else {
        clear();
        IntNode* curr = rhs.head;
        while(curr != 0) {
            // data = curr->data;
            // next = curr->next;
            push_back(curr->data);
            curr = curr->next;
        }
    }
    return *this;
}

void IntList::push_back(int value) {
  
    IntNode* temp = new IntNode(value);

    if (empty()) {
      
        //IntNode* temp = new IntNode(value);
        head = temp;
        tail = temp;
    }
    else {
      
        //IntNode* temp = new IntNode(value);
        tail->next = temp;
        tail = temp;
    }
}
  
void IntList::clear() {
    while (!empty()) {
        pop_front();
    }
}

void IntList::selection_sort() {
    if (empty()) {
        return;
    }
    else {
        IntNode* min = head;   //CHANGED 0 TO HEAD!!!!!!****!*!!*!*!**!
        int temp = 0;
        for (IntNode* i = head; i->next != 0; i = i->next) {
            min = i;
            for(IntNode* j = i->next; j != 0; j = j->next) {
          
                if (min->data > j->data) {
                    min = j;
                }
            }
            temp = i->data;
            i->data = min->data;
            min->data = temp;
        }
    }
}

void IntList::insert_ordered(int value) {//TODO
    if(empty()) {
        push_front(value);
    }
    else if (value <= head->data) { //equal to?????????
        push_front(value);
    }
    else if (value >= tail->data) { //equal to too??????
        push_back(value);
    }
    else {
        IntNode* prev = head;
        IntNode* curr = head->next;
        IntNode* temp = new IntNode(value);
        while(curr != 0) {
          
            if(value < curr->data) {
                prev->next = temp;
                temp->next = curr;
                return; //break????
            }
          
            prev = prev->next;
            curr = curr->next;
        }
    }
  
}

void IntList::remove_duplicates() { //TODO
    if(empty() || head == tail) {
        return;
    }
    else {
        IntNode* prev = 0;
        // int ite9ration = 0;
        // int jiter = 0;
        for(IntNode* i = head; i != 0; i = i->next) { //FIXME seg fault! maybe issue with the deleting??
            prev = i;
            for(IntNode* j = i->next; j != 0; j = prev->next) {
              
                if(i->data == j->data) {
                    if (j == tail) {
                        delete j;
                        tail = prev;
                        tail->next = 0;
                        //cout << "tail" << endl;
                        //cout << "j " << j->next << '/' << j->data << endl;
                        if (head == tail) {
                            //cout << "alsdhalsdkh" << endl;
                            return;
                        }
                    }
                    else {
                        prev->next = j->next;
                        delete j;
                        //j = prev->next;  
                        //cout << "match found" << endl;
                    }
                }
              
              
                // if (j == tail && i->data == j->data) { //working with last node, WORKS!! :D (i think)
                //     delete j;
                //     tail = prev;
                //     tail->next = 0;
                //     cout << "tail" << endl;
                //     if (head == tail) {
                //         //cout << "alsdhalsdkh" << endl;
                //         return;
                //     }
                //     // else {
                //     //     j = tail;
                //     // }
                // }
                // else if(i->data == j->data) {

                //     prev->next = j->next;
                //     delete j;
                //     //j = prev->next;  
                //     cout << "match found" << endl;
                // }
                else {
                    prev = prev->next;
                }
            }
            cout << "J LOOPed" << endl;
        }
    }
}
  
ostream & operator<<(ostream &out, const IntList &rhs) {
    if(rhs.empty()) {
        return out;
    }
    else {
        IntNode* currentNode = rhs.head;
        // currentNode = head->next;
        out << currentNode->data;
        while(currentNode->next != 0) {
            currentNode = currentNode->next;
            out << ' ' << currentNode->data;
        }
    }
    return out;
}

IntList.h

#ifndef INTLIST_H
#define INTLIST_H

#include <iostream>
using namespace std;

struct IntNode {
    int data;
    IntNode *next;
    IntNode(int data) : data(data), next(0) {}
};

class IntList {
    IntNode* head;
    IntNode* tail;
public:
    IntList();
    ~IntList();
    void display() const;
    void push_front(int value);
    void pop_front();
    bool empty() const;
    IntList(const IntList &cpy); //the copy constructor.
    IntList & operator=(const IntList &rhs); //the overloaded assignment operator.
    void push_back(int value); //Inserts a data value (within a new node) at the back end of the list.
    void clear(); //Removes (deallocates) all IntNodes in the IntList.
    void selection_sort(); //Sorts the integers in the list into ascending order.
    void insert_ordered(int value); //Inserts a data value (within a new node) in an ordered list.
    void remove_duplicates(); //Removes all duplicate data values (actually removes the nodes that contain the values) within the list.
    friend ostream & operator<<(ostream &out, const IntList &rhs); //A global friend function that outputs to the stream all of the integer values within the list on a single line, each separated by a space. the end.
};

#endif