Objectives
ˆ Practice creating a more realistic abstract data type ADT
ˆ Using operator overloading to do output, insertion and access into a list.
ˆ Use templates so our ADT can hold objects of any type
Description
In this assignment you will be practicing operator overloading. I will also, for extra credit, give an additional task to convert your class into a class template, so that it will work as a container for any type.
In this assignment you will be expanding on / creating a new version of the ListType data type we have seen examples of before in class. Your task is to create a ListType that holds a list of integers. You will be asked to create several member functions, and then to create several overloaded operators for your list of integers. Your basic task is to user operator overloading to support appending and prepending to a list, outputting the list as a string and to an output stream, accessing the list (using the indexing operator[]), and concatenating lists together (using operator+).
I have given you a starting template for your ListType that already contains 3 versions of the class constructor. I have also already provided you the operator= implementation, to provide the copy operator for your class. You should get your class to work as a simple ListType that holds a list of integers. If you get your class working for integers and submit it, you
1
can then turn your class into a template class, so that your list can work on objects of any type. I will give up to 10 bonus points for implementations of working class templates, if you mostly have your basic ListType working for simple integers. As usual I have also given a with a main function and a lot of commented out tests. You should implement the class member functions in the order specifed next, commenting out each test one at a time, to incrementally develop and test your ListType class implementation.
For this assignment you need to perform the following tasks.
- As mentioned in the starting template I have given you a starting class defnition, some class constructors and the destructor, and the copy operator=. You frst need to write two simple getter methods in order to access the size and allocSize class member values. These should be called getSize() and getAllocSize() respectively. These functions should be class const functions (you guarantee that calling them will not cause the class to be modified. These functions take no parameters as input. They both return an int value, because the size and allocSize member parameters are both integer values.
- Write a function called tostring(). This function will be a const class function (the class is not modified when it is called). This function takes no parameters as input, and it returns a string. We use this function in our testing, so you need to get it correct, but you have implemented versions of this type of function in previous assignments. The function should only create a string of the items currently in the list. So it will return a string like “[3, 5, 4, 2]” if those are the 4 items currently in the list. See the test code for specifics.
- Overload the operator<<() to provide the ability for the ListType class to be output to a stream. This will be a friend function, and again it will be pretty similar to several examples we have seen of overloading the output stream operator. You should use the tostring() method in this function, but it outputs additional information, such as the id, size and allocSize of the list to the output stream.
- Create a function named appendItem(). This function takes an int value as its only parameter, and it does not return a value. The indi- cated integer value should be appended to the end of your list when this function is called. You need to correctly handle causing the size of your memory allocation to grow if needed in this function, if your list is currently using all of the allocated memory. Once this is working,
2
overload the operator&() operator. We will define the & operator to mean list appending. For example, if you do list & 5 it will cause 5 to be appended to the end of the list (assuming list is a variable of List- Type). This function will simply call appendItem() to do the work, the only dificulty is getting the syntax correct to declare you are over- loading the operator. This is not a friend function, like operator<<(). Read our textbook about binary operators to see examples of how to overload a binary operator like this as a member function of a class.
- Create a function name prependItem(). This works the same as the append, but it prepends the indicated integer parameter to the front of the list instead of to the end. However, you still need to check and grow your allocated memory before prepending if your list is currently full. Also prepend is a bit more complicated, because since we are implementing an array based list, you need to shift all of the current items 1 index up in your items before you can prepend to the beginning of the list. We will also overload the operator|() for our class to represent prepending an item. Thus if you do list | 5 this will cause 5 to be prepended to the beginning of the list.
- Overload the operator+() to implement concatenation of two lists. This operator is probably the trickiest I have given you to implement. This operator should take a const reference to another ListType as its parameter for input. This is the list on the right hand side of the + operation. This function should return a reference to a new ListType as its result. It is important that both the input parameter and the return type be both reference parameters for this function. This function should be a const function, as it does not cause the original list to change. Instead you should dynamically allocate a new ListType in this function, fill it with the items from the two lists being concatenated, and then return it as the result from this overloaded function. You should read our textbook example of overloading the operator+() and try and follow that pattern for implementing this function.
- Overload the operator[] indexing operator. This is NOT a const member function, your list can change as a result of calling this func- tion. This function takes an int value as its input parameter. This function should return an int& reference. Again it is very important that this overloaded operator return a reference. If this operator cor- rectly returns an int&, it can actually be used as a setter to set/change
3
the values in the list. This operator works to index your ListType like an array. You should perform bounds checking in this function. If the given input index is not valid (it is bigger than the end of your list, or it is < 0), you should display an error message and simply exit.
If you get all of these 7 steps and member functions mostly working, you should save/submit your work at that point. However, I am also offering the opportunity to earn 10 bonus points on this assignment, which may be helpful for many of you to make up for some previous program grades. As demonstrated in our video for this week, it is usually better if you want to create a class template to start from a non-template working version of the class. As I showed in the video this week, I usually templatize each member function 1 at a time, starting with the class definition and the class constructors. I will give up to 10 bonus points for a partial or complete templatized ListType that supports appending, prepending, indexing, and output to streams using the overloaded operators, but for any type, not just the int type.
You will again be given 3 starting template files as usual, an assg-07.cpp file of tests of your code, and a ListType.hpp and ListType.cpp header and implementation file. As before, you should practice incremental develop- ment, and uncomment the tests in the assg-07.cpp file one at a time, and implement the functions in the order specified. If you implement your code correctly and uncomment all of the tests, you should get the following correct output:
——— Test constructors and getters ————————-
l1 size: 0 allocSize: 0
l2 size: 0 allocSize: 7
l3 size: 5 allocSize: 5
——— Test output stream operator —————————
l2 items: []
ListType <id=2>
size = 0
allocSize = 7
items : []
l3 items: [3, 9, 2, 7, 5]
4
ListType <id=3>
size = 5
allocSize = 5
items : [3, 9, 2, 7, 5]
——— Test append and operator& —————————–
<ListType::growListIfNeeded()> LOG: grow list current alloc 0 new alloc 10
append to empty l1:
ListType <id=1>
size = 1
allocSize = 10
items : [1]
<ListType::growListIfNeeded()> LOG: grow list current alloc 5 new alloc 15
append to nonempty l3:
ListType <id=3>
size = 6
allocSize = 15
items : [3, 9, 2, 7, 5, 12]
operator& test l3:
ListType <id=3>
size = 8
allocSize = 15
items : [3, 9, 2, 7, 5, 12, 6, 11]
mixing append and operator& l1:
ListType <id=1>
size = 5
allocSize = 10
items : [1, 4, 3, 7, 0]
——— Test prepend and operator| —————————-
prepend to empty l2:
ListType <id=2>
5
size = 1
allocSize = 7
items : [8]
prepend to nonempty l3:
ListType <id=3>
size = 9
allocSize = 15
items : [8, 3, 9, 2, 7, 5, 12, 6, 11]
operator| test l3:
ListType <id=3>
size = 11
allocSize = 15
items : [4, 13, 8, 3, 9, 2, 7, 5, 12, 6, 11]
<ListType::growListIfNeeded()> LOG: grow list current alloc 7 new alloc 17
mixing prepend and append and operators l2:
ListType <id=2>
size = 8
allocSize = 17
items : [4, 0, 13, 5, 7, 8, 11, 9]
——— Test concatenation operator —————————-
Test basic append, new l4:
ListType <id=4>
size = 19
allocSize = 19
items : [4, 0, 13, 5, 7, 8, 11, 9, 4, 13, 8, 3, 9, 2, 7, 5, 12, 6, 11]
Test basic append, new l5:
ListType <id=6>
size = 24
allocSize = 24
items : [1, 4, 3, 7, 0, 4, 13, 8, 3, 9, 2, 7, 5, 12, 6, 11, 4, 0, 13, 5, 7, 8, 11, 9]
Test concatentate emptyList, new l6:
ListType <id=8>
6
size = 8
allocSize = 8
items : [4, 0, 13, 5, 7, 8, 11, 9]
Test concatentate emptyList, new l7:
ListType <id=9>
size = 5
allocSize = 5
items : [1, 4, 3, 7, 0]
——— Test operator[] indexing ——————————
l1[0] == 1
l1[2] == 3
l1[4] == 0
Iterate over l2:
ListType <id=2>
size = 8
allocSize = 17
items : [4, 0, 13, 5, 7, 8, 11, 9]
l2[0] == 4
l2[1] == 0
l2[2] == 13
l2[3] == 5
l2[4] == 7
l2[5] == 8
l2[6] == 11
l2[7] == 9
ListType setter using operator[] l2[0] == 8
ListType setter using operator[] l2[4] == -7
ListType setter using operator[] l2[7] == 42
——— main exiting scope, destructors should be invoked —–
ListType: <id=9> out of scope, size: 5 allocSize: 5
ListType: <id=8> out of scope, size: 8 allocSize: 8
ListType: <id=7> out of scope, size: 0 allocSize: 0
7
ListType: <id=6> out of scope, size: 24 allocSize: 24
ListType: <id=4> out of scope, size: 19 allocSize: 19
ListType: <id=3> out of scope, size: 11 allocSize: 15
ListType: <id=2> out of scope, size: 8 allocSize: 17
ListType: <id=1> out of scope, size: 5 allocSize: 10
If you templatize your ListType class, submit this in the second submis- sion folder. You should add tests to try out your list with things other than ints, like double and string lists.
Assignment Submission
A MyLeoOnline submission folder has been created for this assignment. You should attach and upload your completed .cpp source files to the submission folder to complete this assignment. You really do not need to give me the assg-07.cpp file again, as I will have my own file with additional tests of your functions. However, please leave the names of the other two files as QuickSort.hpp and QuickSort.cpp when you submit them.
Requirements and Grading Rubrics
Program Execution, Output and Functional Requirements
- Your program must compile, run and produce some sort of output to be graded. 0 if not satisfied.
- (5 pts.) The getter methods getSize() and getAllocSize() are im- plemented and working.
- (10 pts.) tostring() works and only creates a string with the items of the list and returns it. opeator<<() works, displays the additional information on the output stream, and uses tostring() in its imple- mentation.
- (15 pts.) Got list appending working correctly. The appendItem() member function is implemented correctly, and the operator&() is overloaded as a member function, and it uses appendItem() to do the actual work of appending. Memory is grown if needed by this function.
- (15 pts.) Go list prepending working correctly. The prependItem() member function is implemented correctly, and the operator|() is
8
overloaded as a member function, and it uses prependItem() to do the actual work of prepending. Items are shifted up which is necessary in the array implemented for prepending. Memory is correctly grown if needed by this function.
- (25 pts) operator+() is correctly overloaded. The operator correctly supports concatentation of two lists. The operator is defined as a class const method. The operator correctly dynamically allocates a new list and puts the items of the two lists into it, and returns this newly allocated object as its result. A reference to the other list is given as input, and this function returns a refereunce to a list as the result.
- (20 pts) operator[] is correctly overloaded. The operator returns an int reference as its result. The operator correctly checks for bounds access errors, for indexes to big or less than 0. The operator correctly works as a setter method, so that values can be modified/assigned in the list.
- (5 pts.) All output is correct and matches the correct example output.
- (5 pts.) Followed class style guidelines, especially those mentioned below.
- (10 bonus pts.) You may templatize your class and submit it (complete or partial) for up to 10 bonus points. Your templatized class must support all of the overloaded operations (append, prepend, indexing, output stream), and work with any class, like string, double, etc.
Program Style
Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week.
- Most importantly, make sure you figure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation levels, and all indentation levels must be correctly indented. Also all tabs must be removed from files, and only 2 spaces used for indentation.
- A function header must be present for member functions you define. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and
9
data type of the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers.
- You should have a document header for your class. The class header document should give a description of the class. Also you should doc- ument all private member variables that the class manages in the class document header.
- Do not include any statements (such as system(“pause”) or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is specific to a single operating system, such as the system(“pause”) which is Microsoft Windows specific.