Complete a C++ class implementation for a linked-list of sorted (ascending) positive integers. The class name for this class is LLSortedPosInt and its specification is outlined in the file LLSortedPosInt.h. The specification is accompained by two other files: (1) a partial implementation of the class in the file LLSortedPosInt.cpp and (2) a test program called testLL.cpp. You are to complete the partial implementation of the class by writing code for the stubbed member functions. You may NOT make any changes to the specification file. You may develop and test your class implementation either under Visual Studio or linux; however, your program must be executable under linux, because that is where it will be tested.

Details: Linked lists are useful data structures for storing data records, particularly in situations where the items are to be kept sorted, the number of records are dynamic (i.e., changing during the course of the programs execution) and the maximum number is arbitrary. In this exercise, youll get a chance to complete the implementation of a linked-list specification. In doing so, youll learn not only how to manipulate pointer objects, but also begin to learn how to create a new and useful data type.

To get started, I have written a simple linked list definition within the header file called LLSortedPosInt.h. My definition is, of course, not the only way to define a linked list, but it is suitable for our simple project. Accompanying the definition is a partial implementation in the source file LLSortedPosInt.cpp. You are to edit this file using the comments in the file and the instructions below. Altogether, this assignment asks you to implement 13 functions.

To help with testing your functions implementations, I have provided a main program. This main program is in the source file testLL.cpp. One quick way to repeatedly exercise your function tests is to write a test file (I called mine testCases.txt) and use input re-direction.

The 13 functions you must add to complete the implementation are as follows:

a. Constructors (4): Classes must have constructors to initialize instances of the objects. The constructors you will implement for this project are

i. A default constructor ii. A constructor taking a single int parameter iii. A constructor which builds a list from an array of integers iv. A copy constructor

b. Destructor (1): Because the class specification includes a pointer among the attributes, you will need to implement a destructor to delete (i.e., free or release) any storage allocated in the constructors or other member functions. c. Boolean Functions (2): You are to implement two Boolean functions i. A function isEmpty() which returns true if the associated list contains no data elements, and returns false otherwise. ii. A function containsElement(key) which returns true is key is an element in the list and returns false otherwise. d. Member Operator Functions (3): When a class has a pointer among its attributes, as LLSortedPosInt does, then there is often a need for deep copy during assignment and deep comparison during equality testing. You are to implement such in operator functions for i. An assignment operator. ii. An equality test (i.e., ==) operator. iii. An inequality test (i.e., !=) operator. e. Friend Operator Functions (3): Finally, we need a mechanism for adding and removing items from a list and printing lists. The functions for these operations are

i. A addition operator (+) to add items to the list. ii. A subtraction operator (-) to remove items from the list. iii. A print operator (<<) to print the list naturally.

As mentioned above, I have provided you with a test program, testLL.cpp, which you may use to test your implementation.

Hints:

The order in which you complete the functions should not be arbitrary. If you take a look at the test program, you'll see that the first thing the main program does is to declare an array of NUM_LIST lists. This declaration uses the default constructor, so it would be appropriate to start with that function. The next function called is the constructor using a single integer. After that, we call the assignment operator. Next, if you develop the print operator early, then you'll have something to help you debug your code. My recommendation is that you develop your functions in this order:

The default constructor

The constructor taking a single int parameter

The assignment operator

The print operator

The rest of the constructors

The destructor

The isEmpty() function

The equality operator

The inequality operator

The containsElement() function

The rest of the friend functions

Another IMPORTANT thing to keep in mind is that I have implemented two member helper functions: insert() and remove(). I have also implemented a non-member helper function called createNode(). Take note of what these functions do, because you can use them to simplify the code you write, so use them.

The Files are listed below

LLSortedPosInt.h

// The following pattern is used to prevent multiple inclusion // of class definitions #ifndef LLSPOSINT_H #define LLSPOSINT_H

#include using namespace std;

struct Node; typedef Node* NodePtr;

// The key value HEAD_OF_LIST is used as a "sentinal" value const int HEAD_OF_LIST = -1;

class LLSortedPosInt { public: // constructors LLSortedPosInt(); LLSortedPosInt(int key); LLSortedPosInt(int *keys, int n); LLSortedPosInt(const LLSortedPosInt &l);

// destructor ~LLSortedPosInt();

bool containsElement (int key) const; bool isEmpty ( ) const;

LLSortedPosInt& operator= (const LLSortedPosInt &l); bool operator==(const LLSortedPosInt &l) const; bool operator!=(const LLSortedPosInt &l) const;

friend LLSortedPosInt operator+ (const LLSortedPosInt &l1, const LLSortedPosInt &l2); friend LLSortedPosInt operator- (const LLSortedPosInt &l1, const LLSortedPosInt &l2); friend ostream& operator<<(ostream &out, const LLSortedPosInt &l); private: void insert (int key); void remove (int key);

NodePtr head; };

#endif //LLSPOSINT_H

LLSortedPosInt.cpp (This is the file to edit)

#include "LLSortedPosInt.h"

// The linked-list is constructed of Node elements struct Node { int key; Node *next; };

// createNode() allocates a Node and initializes it with the // given parameter values to simplify the initilization of a Node static NodePtr createNode(int key, NodePtr p) { // allocate a new Node for storing the given key value NodePtr n = new Node;

// store the key value and the next pointer n->key = key; n->next = p;

// return the new Node to the caller return n; }

// Implementation of the LLSortedPosInt begins here // Constructors

LLSortedPosInt::LLSortedPosInt() { // create the sentinal Node at the head of the list }

LLSortedPosInt::LLSortedPosInt(int key) { // create the sentinal Node at the head of the list

// add the single element key, as long as it is positive }

LLSortedPosInt::LLSortedPosInt(int *keys, int n) { // create the sentinal node at the head of the list

// add new Nodes for each positive value in keys }

LLSortedPosInt::LLSortedPosInt(const LLSortedPosInt &l) { // create a deep copy of the input list l }

// Destructor

LLSortedPosInt::~LLSortedPosInt() { // free the Nodes in *this, including the sentinal }

// Boolean Functions

bool LLSortedPosInt::containsElement (int key) const { // return true if key is in the list; return false otherwise return false; }

bool LLSortedPosInt::isEmpty ( ) const { // return true if only the sentinal is in the list; return false otherwise return false; }

// Operators

LLSortedPosInt& LLSortedPosInt::operator= (const LLSortedPosInt &l) { // handle self assignment if (this == &l) { return *this; }

// free old elements of the list before the new elements from l are assigned

// if necessary, rebuild the sentinal

// build the list as a deep copy of l

// return *this return *this; }

bool LLSortedPosInt::operator==(const LLSortedPosInt &l) const { // compare the Nodes in *this with the Nodes in l // if all Node key values in *this match the cooresponding // Node key values in l, then the lists are equivalent return false; }

bool LLSortedPosInt::operator!=(const LLSortedPosInt &l) const { // do the opposite of operator== return true; }

LLSortedPosInt operator+ (const LLSortedPosInt &l1, const LLSortedPosInt &l2) { // create a copy of l1 and add each element of l2 to it in // the correct (sorted ascending) order, allow duplicates LLSortedPosInt sum; return sum; }

LLSortedPosInt operator- (const LLSortedPosInt &l1, const LLSortedPosInt &l2) { // copy l1 and remove all of l2 from l1, taking care to // reclaim any storage -- do not to remove the sentinal Node LLSortedPosInt diff; return diff; }

ostream& operator<< (ostream &out, const LLSortedPosInt &l) { // an empty list will be printed as <> // a singleton list (a list having one key value k) will be // printed as // a list having multiple keys such as 2, 5, 7 will be printed // as <2, 5, 7>

// print the left angle bracket // print the keys in the list l

// print the right angle bracket

return out; }

// The following helper functions are provide to assist you in // building the class--these helper functions are useful in // several places among the functions you will write--take time // to learn what they do

// insert() inserts an element in the linked list in sorted order void LLSortedPosInt::insert(int key) {

// setup pointers to walk the list NodePtr npp = head; NodePtr npc = head->next;

// walk the list, searching until the given key value is exceeded while (npc != NULL && npc->key <= key) { npp = npc; npc = npc->next; }

// insert the new value into the list npp->next = createNode(key, npc); }

// remove() removes an element from the list (if it is present) void LLSortedPosInt::remove(int key) {

// negative values should not be stored in the list if (key <= 0) { return; }

// setup pointers to walk the list NodePtr npp = head; NodePtr npc = head->next;

// search the list until the end (if necessary) while (npc != NULL) {

// if the key value is found, then splice this Node from the list and // reclaim its storage if (npc->key == key) { npp->next = npc->next; delete npc; break; }

// walk the pointers to the next Node npp = npc; npc = npc->next; } }

TestLL.cpp

#include #include #include

// Include the linked-list specification, so we can use them in // our test prgm #include "LLSortedPosInt.h" using namespace std;

#define NUM_LISTS 5

void showMenu(); int rangeCorrect(int);

int main() { // create several lists to work with LLSortedPosInt l[NUM_LISTS];

int a[] = {3, 5, -6, 2, 7, 4};

// test the different constructors l[2] = LLSortedPosInt(2); l[3] = LLSortedPosInt(a, 6); l[4] = LLSortedPosInt(l[3]);

{ // test for memory leak LLSortedPosInt temp = l[4]; }

// variables to test our implementation int i, k, lnum; char cmd;

// try various linked-list functions, until 'q' is typed do { showMenu(); cin >> cmd;

switch (cmd) {

// print a list case 'p' : cin >> lnum; cerr << "List[" << lnum << "]: "; lnum = rangeCorrect(lnum); cerr << l[lnum] << endl; break;

// print all lists case 'P' : for (i = 0; i < NUM_LISTS; i++) { cerr << "List[" << i << "]: "; cerr << l[i] << endl; } break;

// insert an element into a list case 'i' : cin >> i >> lnum; lnum = rangeCorrect(lnum); cerr << "Inserting " << i << " into list[" << lnum << "] "; l[lnum] = l[lnum] + i; break;

// remove an element from a list case 'r' : cin >> i >> lnum; lnum = rangeCorrect(lnum); cerr << "Removing " << i << " from list[" << lnum << "] "; l[lnum] = l[lnum] - i; break;

// assign one list to another case 'a' : cin >> i >> lnum; i = rangeCorrect(i); lnum = rangeCorrect(lnum); cerr << "Assigning list[ " << i << "] to list[" << lnum << "] "; l[lnum] = l[i]; break;

// merge two lists together case 'm' : cin >> i >> k >> lnum; i = rangeCorrect(i); k = rangeCorrect(k); lnum = rangeCorrect(lnum); cerr << "Merging list[ " << i << "] and list[" << k << "] as list[" << lnum << "] "; l[lnum] = l[i] + l[k]; break;

// subtract one list from another case 's' : cin >> i >> k >> lnum; i = rangeCorrect(i); k = rangeCorrect(k); lnum = rangeCorrect(lnum); cerr << "Subtracting list[ " << k << "] from list[" << i << "] as list[" << lnum << "] "; l[lnum] = l[i] - l[k]; break;

// test if the list is empty case 'y' : cin >> lnum; lnum = rangeCorrect(lnum); if (l[lnum].isEmpty()) { cerr << "List[" << lnum << "] is empty "; } else { cerr << "List[" << lnum << "] is not empty "; } break;

// test if the list as a certain element case 'c' : cin >> i >> lnum; lnum = rangeCorrect(lnum); if (l[lnum].containsElement(i)) { cerr << "List[" << lnum << "] contains " << i << " "; } else { cerr << "List[" << lnum << "] does not contain " << i << " "; } break;

// test two lists for equality case 'e' : cin >> i >> lnum; i = rangeCorrect(i); lnum = rangeCorrect(lnum); if (l[i] == l[lnum]) { cerr << "List[" << i << "] is identical to list [" << lnum << "] "; } else { cerr << "List[" << i << "] is different from list [" << lnum << "] "; } break;

// test two lists for inequality case 'n' : cin >> i >> lnum; i = rangeCorrect(i); lnum = rangeCorrect(lnum); if (l[i] != l[lnum]) { cerr << "List[" << i << "] is different from list [" << lnum << "] "; } else { cerr << "List[" << i << "] is identical to list [" << lnum << "] "; } break;

// quit the program case 'q' : break;

// any other leading letter is considered a comment default : { string dummy; getline(cin, dummy); } break; } } while (cmd != 'q');

return 0; }

// display the menu of choices void showMenu() { cout << "This program tests the linked list implementation "; cout << "Use the following single-letter commands to test: "; cout << " e # # - compare two lists "; cout << "n # # - compare lists (not equal) "; cout << " p # - print list # "; cout << "P - print all lists "; cout << " i #1 #2 - insert elem 1 into list 2 "; cout << "r #1 #2 - remove elem 1 from list 2 "; cout << " s #1 #2 #3 - subtract list 2 frm 1 to 3 "; cout << "m #1 #2 #3 - merge list 1 & 2 into 3 "; cout << " y # - ask if list # is empty "; cout << "c #1 #2 - ask is elem 1 in list 2 "; cout << " a #1 #2 - assign list 1 to list 2 "; cout << "q - quit the test program "; cout << "Command: "; }

int rangeCorrect(int n) { if (n < 0 || n > NUM_LISTS-1) { cerr << "rangeCorrect error: list index " << n << " is outside range 0 to " << NUM_LISTS-1 << endl; }

return max(0, min(NUM_LISTS-1, n)); }

NOTE: So far all that i have done is create a default which I am not sure if even that is correct.

head=createnode(HEAD_OF_LIST,nullptr);