Learning Objective: . This assignment will help you to become proficient in using C++ pointers and working with Object Orientated Programs. Starter Code: You can find starter code for this assignment...

Learning Objective:. This assignment will help you to become proficient in using C++ pointers and working with Object Orientated Programs.

Starter Code:You can find starter code for this assignment on Canvas under Files > Assignments > Assignment 4. You should start by downloading all the starter code files, build and run the code, run the code using valgrind. Note: the starter code does leak memory - you should probably fix this first.

Assignment.Develop a full ordered template List class, for discussion purposes, of Object. A template allows any specified type of Object to be stored. You can find starter class List code with the starter code in Canvas Files. Test Assignment 4 on two different types of Objects (code found in Canvas Files),

(a). Employee -- to be sorted alphabetically by last name, then first name

(b). NodeData -- to be sorted by numerical value, then char

As a template, put your declarations in the .h file and your implementation in the .cpp file. You must include your .cpp file in your .h file (after the declarations) for compilation. You should only build nodedata.cpp and listdriver.cpp. The templated classes are built by including the List interface in listdriver.cpp.

The List class includes the following functions. For the examples, assume the following are declared and suppose there are n items of data in any list .

ifstream infile1("data31.txt"), infile2("data32.txt");
bool success;
Employee* oneEmployee;
List company1, company2, company3, company4;

1. All necessary constructors and destructor. (Should all take O(n) time, e.g., something done in one loop is O(n) )


2. void buildList : given datafile, build an ordered list (note that buildList puts the responsibility on the Object class to know how to read from a file.) (insertion sort, O(n2) time, nested loop) E.g., company1.buildList(infile1);


3. bool insert : insert one Object* into its correct sorted position, return whether successful (duplicates allowed)


4. bool remove: remove first parameter, the object, from the list and set the second (pass by reference) parameter to the Object* from the list if it is found. The return value is whether the removal was successful. Second parameter is unreliable (although it's best to set it to nullptr) if return value is false. Remove from list. E.g.,

Employee target("duck", "donald"); // assume constructor exists
success = company1.remove(target, oneEmployee);
if (success) {
cout

delete oneEmployee; // could be inserted into another list
}

Prototype: bool remove(const Object&, Object*&);

5. bool retrieve : similar to remove, but not removed from list. If there are duplicates in the list, the first one encountered is retrieved. Second parameter is null if the return value is false. E.g.,

Employee target("duck", "donald");
success = company1.retrieve(target, oneEmployee);
if (success) { cout

6. void merge -- takes 2 sorted lists and merge into one long sorted list (No new memory is allocated. At termination of function, the two parameter lists are empty unless one is also the current object. Duplicates are allowed in a merged list.) (O(n) time, so insert must not be used or time would be O(n2)) E.g.,

// after this merge, company1 and company2 are empty,
// company3 contains all employees of company1 and company2
company3.merge(company1, company2);
// after merge, company3 is empty,
// company4 contains all employees of company3 and company4
company4.merge(company4, company3);

7. void intersect -- takes 2 sorted lists and finds the items in common in both lists (New memory is allocated; at termination of the function, the two parameter lists are unchanged unless one is also the current object.) E.g.,

// after intersect, company1 and company2 are unchanged,
// company3 holds intersection of company1 and 2
company3.intersect(company1, company2);
// after intersect, company3 is unchanged,
// company4 holds the intersection of company3 and 4
company4.intersect(company3, company4);

8. overload
   


9. bool isEmpty() : determine whether a list is empty


10. void makeEmpty() : empty out the list, deallocate all memory for all Nodes and each Object (note that the destructor can just call makeEmpty)


11. operator= : to assign one list to another, deep copy (all new memory) (Takes O(n) time. No insert() call.)


12. bool operator== and operator!= : compare two lists, == is true if the lists hold identical Objects as defined by Object’s operator==

Notes

You must implement the List class without using a dummy head node. In other words, the first node that the head pointer points to holds a pointer to real data. This forces you to think about the special cases involving the head pointer. You may use the insert and any other functions found in the starter code found or on thissample code page(Links to an external site.).

Implement the list using Nodes defined in the node.h file. Note that the Node class is also partially implemented and that each Node does not hold an Item, but a pointer to an Item. You will need to implement the copy constructor and destructor for the Node class.

NodeData data files are formatted so that each line of data includes an int and a char. For example,

100 x

Code for the NodeData class is with the starter code.

You can assume correctly formatted data (each line will always have one int and one char). So that file reading works in a similar manner under both linux and windows/mac, make sure the last line of data has an end-of-line character (under windows or mac, cursor is on the line below the last line of good data). Checking for eof() as in the List class’ buildList() routine works correctly, so do it that way. Do not use any other libraries.

Employee data files are formatted so that each line of data is the employee's name (last name then first name) followed by IDnumber and salary. For example,

mouse mickey 8584 55000

You can assume correctly formatted data (each line will always have two strings and two ints). Code for the Employee class is with the starter code. The string class has all the expected operators: ==, !=,

The list.h file should not #include other .h files, no nodedata.h, no employee.h.
I will provide my own main, classes, and data files to test your List class.
Any classes used to test your List class will have setData, ==, !=, <,>,

See starter code for a sample main - listdriver.cpp.