Programming assig 3: Pointers and Dynamic Memory

profileJohn@123
ProgrammingAssignment03PointersandDynamicMemoryattachedfilesSep1420191130AM.zip
Home>Computer Science homework help>Programming assig 3: Pointers and Dynamic Memory

assg-03.cpp

assg-03.cpp

/** 
 *  @author  Jane Programmer
 *  @cwid    123 45 678
 *  @class   COSC 2336, Spring 2019
 *  @ide     Visual Studio Community 2017
 *  @date    January 12, 2019
 *  @assg    Assignment 03
 * 
 *  @description  Assignment 03
 */
#include   < iostream >
#include   < iomanip >
#include   < string >
#include   < cassert >
#include   "LargeInteger.hpp"

using   namespace  std ;


/** main 
 * The main entry point for this program.  Execution of this program
 * will begin with this main function.
 *
 *  @param  argc The command line argument count which is the number of
 *     command line arguments provided by user when they started
 *     the program.
 *  @param  argv The command line arguments, an array of character
 *     arrays.
 *
 *  @returns  An int value indicating program exit status.  Usually 0
 *     is returned to indicate normal exit and a non-zero value
 *     is returned to indicate an error condition.
 */
int  main ( int  argc ,   char **  argv )
{
   // test constructors, destructors and tostring()
  cout  <<   "Testing Constructors, tostring() and destructor:"    <<  endl ;
  cout  <<   "-------------------------------------------------------------"   <<  endl ;
   LargeInteger  li1 ( 3483 );
   //cout << "li1 = " << li1.tostring() << endl;
   //assert(li1.tostring() == "3483");

   //int digits2[] = {8, 4, 6, 3, 8, 4, 7, 4, 1, 2};
   //LargeInteger li2(10, digits2);
   //cout << "li2 = " << li2.tostring() << endl;
   //assert(li2.tostring() == "2147483648");

   LargeInteger *  li3  =   new   LargeInteger ( 193839 );
   //cout << "li3 = " << li3->tostring() << endl;
   //assert(li3->tostring() == "193839");
   delete  li3 ;   // should invoke the class destructor
  
  
   // test maxDigits() member function
  cout  <<  endl ;
  cout  <<   "Testing maxDigits() member function"   <<  endl ;
  cout  <<   "-------------------------------------------------------------"   <<  endl ;
   int  maxDigits ;
   //maxDigits = li1.maxDigits(li2);
   //cout << "The maximum digits between l1 and l2 is: " << maxDigits << endl;
   //assert(maxDigits == 10);

   //LargeInteger li4(398298312);
   //int digits5[] = {3, 3, 1, 4, 2, 1, 5, 1, 2, 4, 7, 6, 9, 3, 9, 5, 6};
   //LargeInteger li5(17, digits5);
   //cout << "li4 = " << li4.tostring() << " and li5 = " << li5.tostring() << endl;
   //maxDigits = li5.maxDigits(li4);
   //cout << "The maximum digits between l5 and l4 is: " << maxDigits << endl;
   //assert(maxDigits == 17);
  

   // test digitAtPlace() member function
  cout  <<  endl ;
  cout  <<   "Testing digitAtPlace() member function"   <<  endl ;
  cout  <<   "-------------------------------------------------------------"   <<  endl ;
   //cout << "li5[0] == " << li5.digitAtPlace(0) << endl;
   //assert(li5.digitAtPlace(0) == 3);
   //cout << "li5[16] == " << li5.digitAtPlace(16) << endl;
   //assert(li5.digitAtPlace(16) == 6);
   //cout << "li5[17] == " << li5.digitAtPlace(17) << endl;
   //assert(li5.digitAtPlace(17) == 0);
   //cout << "li5[4] == " << li5.digitAtPlace(4) << endl;
   //assert(li5.digitAtPlace(4) == 2);
   //cout << "li5[10] == " << li5.digitAtPlace(10) << endl;
   //assert(li5.digitAtPlace(10) == 7);
   //cout << "li5[25] == " << li5.digitAtPlace(25) << endl;
   //assert(li5.digitAtPlace(25) == 0);
   //cout << "li5[-1] == " << li5.digitAtPlace(-1) << endl;
   //assert(li5.digitAtPlace(-1) == 0);
   //cout << endl;

   //cout << "li4[0] == " << li4.digitAtPlace(0) << endl;
   //assert(li4.digitAtPlace(0) == 2);
   //cout << "li4[8] == " << li4.digitAtPlace(8) << endl;
   //assert(li4.digitAtPlace(8) == 3);
   //cout << "li4[9] == " << li4.digitAtPlace(9) << endl;
   //assert(li4.digitAtPlace(9) == 0);
   //cout << "li4[2] == " << li4.digitAtPlace(2) << endl;
   //assert(li4.digitAtPlace(2) == 3);
   //cout << "li4[33] == " << li4.digitAtPlace(33) << endl;
   //assert(li4.digitAtPlace(33) == 0);
   //cout << "li4[-5] == " << li4.digitAtPlace(-5) << endl;
   //assert(li4.digitAtPlace(-5) == 0);

  
   // test append digit
  cout  <<  endl ;
  cout  <<   "Testing appending digits appendDigit() member function"   <<  endl ;
  cout  <<   "-------------------------------------------------------------"   <<  endl ;
   //li5.appendDigit(1);
   //cout << "li5 after appendDigit(1) = " << li5.tostring() << endl;
   //assert(li5.tostring() == "165939674215124133");
   //li5.appendDigit(0);
   //cout << "li5 after appendDigit(0) = " << li5.tostring() << endl;
   //assert(li5.tostring() == "165939674215124133");

   //li4.appendDigit(7);
   //cout << "li4 after appendDigit(7) = " << li4.tostring() << endl;
   //assert(li4.tostring() == "7398298312");
   //li4.appendDigit(0);
   //cout << "li4 after appendDigit(0) = " << li4.tostring() << endl;
   //assert(li4.tostring() == "7398298312");
  
  
   // test addition operator
  cout  <<  endl ;
  cout  <<   "Testing LargeInteger addition add() member function"   <<  endl ;
  cout  <<   "-------------------------------------------------------------"   <<  endl ;
   //LargeInteger li6 = li4.add(li5);
   //cout << "Addition of li4 + li5 = " << li6.tostring() << endl;
   //assert(li6.tostring() == "165939681613422445");
    
   //LargeInteger li7 = li5.add(li4);
   //cout << "Addition of li5 + li4 = " << li7.tostring() << endl;
   //assert(li7.tostring() == "165939681613422445");

   //assert(li6.tostring() == li7.tostring());

   // test carry
   //LargeInteger li8(999999999);
   //int digits9[] = {9, 9, 9, 9, 9, 9, 9, 9, 9};
   //LargeInteger li9(9, digits9);

   //cout << setw(12) << right << li8.tostring() << endl;
   //cout << "+" << setw(11) << right << li9.tostring() << endl;
   //cout << "------------" << endl;
   //LargeInteger li10 = li8.add(li9);
   //cout << setw(12) << right << li10.tostring() << endl;
  cout  <<  endl ;
  
   // return 0 to indicate successful completion
   return   0 ;
}

LargeInteger.cpp

LargeInteger.cpp

/** 
 *  @author  Jane Programmer
 *  @cwid    123 45 678
 *  @class   COSC 2336, Spring 2019
 *  @ide     Visual Studio Community 2017
 *  @date    January 12, 2019
 *  @assg    Assignment 03
 * 
 *  @description  LargeInteger class.  Represent an arbitrarily large
 *   (signed) integer.  This class keeps the digits of the integer in
 *   an array of integers internally.  The array of integers is 
 *   dynamically resized as necessary during LargeInteger operations.
 *   This abstract data type supports addition of large integers.
 */
#include   "LargeInteger.hpp"

using   namespace  std ;


// integer to create unique id for new LargeInteger instances
// please set and use this in the same way in the constructor you
// create for this assignment
static   int  nextLargeIntegerId  =   1 ;

/** LargeInteger constructor
 * Constructor for LargeInteger class that takes a simple built-in
 * integer to be used as the initial value of the large integer.
 * 
 *  @param  value A regular (32-bit) integer that we will use as the
 *    initial value of this LargeInteger data type.
 */
LargeInteger :: LargeInteger ( int   value )
{
   // set this instance id
  id  =  nextLargeIntegerId ++ ;
  
   // first determine number of digits, so we know what size of array
   // to construct dynamically
   // https://stackoverflow.com/questions/1489830/efficient-way-to-determine-number-of-digits-in-an-integer
  numDigits  =   ( int )  log10 (( double )   value )   +   1 ;

   // allocate an array of the right size
  digits  =   new   int [ numDigits ];

   // iterate through the digits in value, putting them into our
   // array of digits.
   int  digit ;
   for   ( int  digitIndex  =   0 ;  digitIndex  <  numDigits ;  digitIndex ++ )
   {
     // least significant digit
    digit  =   value   %   10 ;
    digits [ digitIndex ]   =  digit ;

     // integer division to chop of least significant digit
     value   =   value   /   10 ;
   }
}

/** LargeInteger destructor
 * Destructor for the LargeInteger class.  Make sure we are good
 * managers of memory by freeing up our digits when this object
 * goes out of scope.
 */
LargeInteger ::~ LargeInteger ()
{
   // We display a log message to track destructor invocation.  In
   // a real application we might send this to a log file, and parameterize
   // whether to log these type of events or not.
  cout  <<   "<LargeInteger::~LargeInteger> destructor entered, freeing my digits"   <<  endl
        <<   "     id = "   <<  id  <<  endl
     //<< "     value=" << tostring() // uncomment this after you implement tostring()
        <<  endl ;
   delete   []   this -> digits ;
}

LargeInteger.hpp

/** * @author Jane Programmer * @cwid 123 45 678 * @class COSC 2336, Spring 2019 * @ide Visual Studio Community 2017 * @date January 12, 2019 * @assg Assignment 03 * * @description LargeInteger class. Represent an arbitrarily large * (signed) integer. This class keeps the digits of the integer in * an array of integers internally. The array of integers is * dynamically resized as necessary during LargeInteger operations. * This abstract data type supports addition of large integers. */ #ifndef _LARGEINTEGER_H_ #define _LARGEINTEGER_H_ #include <iostream> #include <string> #include <sstream> #include <cmath> using namespace std; /** LargeInteger class. * * @param id Private member integer variable, this is not strictly needed * for this class, but we assign a unique id to each instance of * LargeInteger that is created, so that you can more easily see how * the destructor works and is being called. You should set the * id and increment it in any constructors you create for this class. * @param numDigits Private member integer variable, contains the number * of digits currently in the LargeInteger, or equivalently, the size * of they digits array of integers. * @param digits A dynamically allocated array of integers. This array * holds the digits of the large integer this object represents. The * digits in the array are orderd such that the 1's place (10^0) is in * index 0 of the array, the 10's place (10^1) is in the index 1, and so * on. */ class LargeInteger { private: int id; int numDigits; // number of digits in LargeInt / size of alloc array int* digits; // the digits of the LargeInt we are representing public: LargeInteger(int value); ~LargeInteger(); }; #endif

assg-03.pdf

Assg 03: Pointers and Dynamic Memory

COSC 2336 Data Structures

Objectives

• Practice using pointers and dynamically allocating memory

• Practice writing an Abstract Data Type using a class

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 as- signment. 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.

For this assignment you need to perform the following tasks. You will be given 3 template files, and some of the LargeInteger class will already have been implemented for you (I will give you a simple constructor and the class destructor). You should implement the member functions, in this order, and uncomment the test code incrementally to test your functions as you implement them.

1

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 (100) is in index 0 of digits, the 10’s place (101) is in index 1, etc.

2. Implement a second constructor for the LargeInteger. This construc- tor 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 dy- namically allocate the space for the digitis in your constructor (see the given constructor for an example).

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 in- dex. So this function takes an integer index as its input parameter, and returns an integer as its result. Again, if you ask for the digi- tAtPlace() index 0, this should return the 1’s place 100 digit of the integer. If asked for the digit at place 1, this should return the 10’s place 101 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

2

1) allocate a new array of digits of 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 significat sum. We handle needing to grow the result in the last step of the algorithm. For example if this large ineteger 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 accomodate 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

3. Dynamically allocate a new LargeInteger() object, using the con- structor 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 append- Digit() member function to add the carry value as the new most sig- nificant digit to the new LargeInteger() you created in step 3. As mentioned above, you could also just have your appendDigit() func- tion 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.

In this assignment, you will be given 3 starting template files, named assg- 03.cpp, LargeInteger.cpp and LargeInteger.hpp. This is our first example of breaking code up into multiple files. You should add the function prototypes to the class declaration in the LargeInteger.hpp file, and implement the class member functions asked for in the LargeInteger.cpp file. You should not add any code to the assg-03.cpp file, only remove the comments to perform the tests shown on your functions (though make sure you add your name and information to the top of all 3 files in the file headers). The assg-03.cpp tests are designed to be implemented incrementally. You should first uncomment the first tests to test out your tostring() implementation. Once you have that working, move on to creating the asked for constructor, etc. If you perform all of the above tasks correctly, the tests given to you in the starting template will produce the following correct output:

Testing Constructors, tostring() and destructor: ------------------------------------------------------------- li1 = 3483 li2 = 2147483648 li3 = 193839 <LargeInteger::~LargeInteger> destructor entered, freeing my digits

id = 3 value=193839

Testing maxDigits() member function

4

------------------------------------------------------------- The maximum digits between l1 and l2 is: 10 li4 = 398298312 and li5 = 65939674215124133 The maximum digits between l5 and l4 is: 17

Testing digitAtPlace() member function ------------------------------------------------------------- li5[0] == 3 li5[16] == 6 li5[17] == 0 li5[4] == 2 li5[10] == 7 li5[25] == 0 li5[-1] == 0

li4[0] == 2 li4[8] == 3 li4[9] == 0 li4[2] == 3 li4[33] == 0 li4[-5] == 0

Testing appending digits appendDigit() member function ------------------------------------------------------------- li5 after appendDigit(1) = 165939674215124133 li5 after appendDigit(0) = 165939674215124133 li4 after appendDigit(7) = 7398298312 li4 after appendDigit(0) = 7398298312

Testing LargeInteger addition add() member function ------------------------------------------------------------- Addition of li4 + li5 = 165939681613422445 Addition of li5 + li4 = 165939681613422445

999999999 + 999999999 ------------

1999999998

<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 10

5

value=1999999998 <LargeInteger::~LargeInteger> destructor entered, freeing my digits

id = 9 value=999999999

<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 8 value=999999999

<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 7 value=165939681613422445

<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 6 value=165939681613422445

<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 5 value=165939674215124133

<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 4 value=7398298312

<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 2 value=2147483648

<LargeInteger::~LargeInteger> destructor entered, freeing my digits id = 1 value=3483

Assignment Submission

A MyLeoOnline submission folder has been created for this assignment. You should attach and upload your completed .cpp and .hpp source files to the submission folder to complete this assignment. You really do not need to give me the assg-03.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 LargeInteger.hpp and LargeInteger.cpp when you submit them.

6

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.

2. 10 pts. Correctly implement the tostring() member function.

3. 15 pts. Correctly implement the asked for constructor. Constructor uses dynamic allocation to allocate memory as asked for.

4. 10 pts. maxDigits() implementation is correct.

5. 10 pts. digitsAtPlace() implementation is correct. Function returns 0 for a negative digit or for a digit greater than number of places in the object.

6. 15 pts. appendDigit() implemented correctly. Correctly allocat- ing dynamic memory. Correctly freeing up the old memory after not needed.

7. 30 pts. add() implemented correctly.

8. 5 pts. All output is correct and matches the correct example output.

9. 5 pts. Followed class style guidelines, especially those mentioned below.

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.

2. 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.

7

3. 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.

4. 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.

8