Data structure and algorithm

--- title: 'Assignment 03: Classes, Pointers and Dynamic Memory' author: 'COSC 2336: Data Structures and Algorithms' date: 'Fall 2020' --- # Objectives - Practice using pointers and dynamically allocating memory - Look at separating class declaration from implementation - Write member functions for classes to implement an abstract data type. # Description In C++ the largest int value is $2147483647$. So, an integer larger than this cannot be stored and processed as an integer. Similarly if the sum or product of two positive integers is greater than $2147483647$, the result will be incorrect. One way to store and manipulate large integers is to store each individual digit of the number in an array. In this assignment, you will design a class named `LargeInteger` such that an object of this class can store an integer of any number of digits. Your abstract data type `LargeInteger` will support member functions to `add()` two `LargeInteger` objects together and return a new resulting `LargeInteger` object. You will only implement an unsigned integer, we will not worry about handling negative large integers in this assignment. Likewise, subtraction and especially multiplication are a bit more complicated, and we will leave those operations for later. But in addition to the `add()` member function, you will implement several other member functions and constructors, that will be useful to implementing addition of the `LargeInteger` values. # Setup For this assignment you will be given the following files: | File Name | Description | |--------------------|------------------------------------------| | `assg03-tests.cpp` | Unit tests for the LargeInteger | | | class you are to write. | | `LargeInteger.hpp` | Header file declaring LargeInteger | | | API to be implemented. | | `LargeInteger.cpp` | Implementation file for the | | | LargeInteger member functions you are to | | | implement for this assignment. | Set up a multi-file project to compile the two `.cpp` source files together and run them as shown for the class. The Makefile you were given should be usable to create a build project using the Atom editor as required in this class. The general approach you should take for this assignment, and all assignment is: 1. Set up your project with the given starting templates. The files should compile and run, but either no tests will be run, or tests will run but be failing. 2. For this project, start by uncommenting the first `TEST_CASE` in the `assg03-tests.cpp` file. These are the unit tests to test the functionality of your `tostring()` member function implementation. We use this function in the rest of the tests so we have to implement this member function first. 3. Add the correct function prototype for the `tostring()` member function to the `LargeInteger.hpp` header file. The prototype consists of the name of the function, its input parameters and their types (none in this case), and the return value of the function (a string). 4. Add a stub/empty implementation of `tostring()` to the `LargeInteger.cpp` implementation file. The function should have the same signature as the prototype you gave in the header file. Documentation for the `tostring()` function has been given to you for this assignment, put your implementation below the documentation as indicated. The function should initially just return an empty string, e.g. return ""; so you can test your project is still compiling and running. 5. Your code should compile and run now. Make sure after adding the function prototype and stub your code compiles and runs. However, some but not all of the unit tests will now be passing, and most will be failing. 6. Incrementally implement the functionality of your `tostring()` member function. You should try to add no more than 2 or 3 lines of code, and then make sure you program still compiles and runs. Start by adding code to get the first failing test to pass. Then once that test passes, move on to the next failing tests until you have all tests passing. If you write something that causes a previously passing test to fail, you should stop and figure out why, and either fix it so that the original test still passes, or remove what you did and try a new approach. 7. Once you have the `tostring()` function implemented and all unit tests passing, you should then move on to the other member functions in the order suggested. Some member functions use previous ones in this assignment, so do them in the order given for you in the tasks below. # Tasks You should set up your project/code as described in the previous section. In this section we give some more details on implementing the member functions for this assignment. You should perform the following tasks for this assignment: 1. Implement a `tostring()` member function. This function will return a string representation of the `LargeInteger`. You should probably used <sstream> string streams to implement this function. Note that the digits of the large integer are stored in reverse of their display order, e.g. the 1's place (10^0) is in index 0 of digits, the 10's place (10^1) is in index 1, etc. The easiest solution is to use a string stream instance to stream the digits into a string stream, then use the `out.str()` member method to convert the string stream to a standard `string` to return. 2. Implement a second constructor for the `LargeInteger`. This constructor will be used to construct a large integer from an array of digits. This constructor takes an int, which is the size of the array of digits, and an integer array as the second parameter. You will need to dynamically allocate the space for the digits in your constructor (see the given constructor for an example, you should do basically the same thing to dynamically allocate an array to hold the digits). 3. Implement a member function named `maxDigits()`. This function will take a *reference* to a `LargeInteger` as its only parameter. This function should return the number of digits in the larger `LargeInteger` comparing the passed in object to this object. 4. Implement a member function named `digitAtPlace()`. This function returns the digit of this large integer object at a particular digit index. So this function takes an integer index as its input parameter, and returns an integer as its result. Again, if you ask for the `digitAtPlace()` index 0, this should return the 1's place 10^0 digit of the integer. If asked for the digit at place 1, this should return the 10's place 10^1 digit. If you ask for a digit place that is larger than the number of digits in the integer the member function should return 0. For example, if the integer represents 345, and you ask for the digit at place 3, then the function will return a 0. Likewise, if a negative index is given to this function, it should also return 0. 5. Implement a member function named `appendDigit()`. This functions takes an int digit as its only parameter. This will be a void function as it does not return any value result from calling it. The function is not something a normal user of the `LargeInteger` type is likely to need to do to an integer, but it will be very useful for our add function. This function appends the digit to become the new most significant digit of the `LargeInteger` object. For example, if the large integer object represents the value 345 and we ask it to `appendDigit(7)`, then the new value of the object will be 7345. This function needs to manage memory to perform its task. You need to perform the following steps 1) allocate a new array of digits of size numDigits+1 (e.g. enough space to hold one more digit). 2) copy the old digits to the new array of digits you created. 3) append the new passed in digit to the end of the array. Then 4) free up the old original array of digits, and make sure you class now uses the new array of allocated digits. Also, you might want to have this function ignore the append of a '0' digit (e.g. do not grow the large integer if trying to append a 0, as this does not need to be represented by the `LargeInteger`). 6. And finally, implement the `add()` member function. This function takes a reference to another `LargeInteger` object, and adds the digits of the other object to this object together. Lets discuss the algorithm for the `add()` member function in more detail. This function will simply take a reference parameter of type `LargeInteger` as its one and only parameter. You need to perform the following steps in your `add()` member function: 1. Dynamically allocate a new array to hold the resulting sum of this and the other `LargeInteger`. Use the `maxDigits()` member function to determine the size needed for this new array. The size of the resulting sum will either be equal to the number of digits of the larger of the 2 numbers, or this value + 1 if there is a carry on the most significant sum. We handle needing to grow the result in the last step of the algorithm. For example if this large integer has the value 4537 (4 digits) and the other has the value of 23 (2 digits), the result will fit in 4 digits, which is what `maxDigits()` should return. Only if we have a carry would we need an extra digit. For example if this is 4537 and the other is 7242 the result of adding them together would be 11779, which needs 5 digits. But as mentioned, we will grow to accommodate a final carry in the last step of the algorithm. 2. Perform the addition, from least significant digit to most significant digit, handling carry as needed. Use the `digitAtPlace()` member function here, as this will determine if each number has a digit, or will return a 0 if you are beyond the size of each number. The resulting digits should be stored in the new array you allocated in step 1. Also make sure you keep track of the carry, and at the end, you should know if a 0 or 1 was carried from the addition of the last most significant digits. 3. Dynamically allocate a new `LargeInteger()` object, using the constructor you created that takes an array as its parameter. You will pass in the array of new digits you summed up in step 2 and its size that you determined and dynamically allocated in step 1. 4. If there was a carry on the last most significant digit, use the `appendDigit()` member function to add the carry value as the new most significant digit to the new `LargeInteger()` you created in step 3. As mentioned above, you could also just have your `appendDigit()` function ignore a request to append a '0' digit, thus in your `add()` you could always just call `appendDigit()` with the final carray, and the append would append or ignore as appropriate. 5. Finally the `add()` function should return a reference to the new `LargeInteger()` that contains the calculated sum you just computed and assigned to it. # Example Output Here is the correct output you get from your program if you correctly implement all the class member functions and successfully pass all of the unit tests given for this assignment. If you invoke your function with no command line arguments, only failing tests are usually shown by default. In the second example, we use the -s command line option to have the unit test framework show both successful and failing tests, and thus we get reports of all of the successfully passing tests as well on the output. ``` ./test =============================================================================== All tests passed (56 assertions in 6 test cases) $ ./test -s ------------------------------------------------------------------------------- test is a Catch v2.7.2 host application. Run with -? for options ------------------------------------------------------------------------------- <tostring()> member function tests using default and standard constructor ------------------------------------------------------------------------------- assg03-tests.cpp:25 ............................................................................... assg03-tests.cpp:28: PASSED: CHECK( li1.tostring() == "0" ) with expansion: "0" == "0" ... output snipped ... =============================================================================== All tests passed (56 assertions in 6 test cases) ``` # Assignment Submission A MyLeoOnline submission folder has been created for this assignment. There is a target named `submit` that will create a tared and gziped file named `assg03.tar.gz`. You should do a `make submit` when finished and upload your resulting gzip file to the MyLeoOnline Submission folder for this assignment. ``` $ make submit tar cvfz assg03.tar.gz assg03-tests.cpp assg03-main.cpp LargeInteger.hpp LargeInteger.cpp assg03-tests.cpp assg03-main.cpp LargeInteger.hpp LargeInteger.cpp ``` # Requirements and Grading Rubrics ## Program Execution, Output and Functional Requirements 1. Your program must compile, run and produce some sort of output to be graded. 0 if not satisfied. 1. 15 pts. Correctly implement the `tostring()` member function. 1. 15 pts. Correctly implement the asked for constructor. Constructor uses dynamic allocation to allocate memory as asked for. 1. 10 pts. `maxDigits()` implementation is correct. 1. 10 pts. `digitAtPlace()` implementation is correct. Function returns 0 for a negative digit or for a digit greater than number of places in the object. 1. 15 pts. `appendDigit()` implemented correctly. Correctly allocating dynamic memory. Correctly freeing up the old memory after not needed. 1. 30 pts. `add()` implemented correctly. 1. 5 pts. All output is correct and matches the correct example output. ## 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. 1. 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. 1. 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 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. 1. You should have a document header for your class. The class header document should give a description of the class. Also you should document all private member variables that the class manages in the class document header. 1. 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.