Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Project 2 – OOP & Dynamic Memory

COMP 280: DATA STRUCTURES AND ALGORITHMS

1 PROJECT LOGISTICS

1.1 SUBMISSION

You must submit your final project code via Gradescope for grading, project left on korriban won’t be graded and will result in 0 being awarded!

Only modify and submit the following 4 files geometry.h geometry.cpp point_array.h point_array.cpp

You may submit your code to Gradescope as many times as you like, up until the deadline. and receive real time grading results. We will only grade your most recent submission. Also only basic section (before Section 5) counts against your course score, section 5 onwards is extra knowledge and extra work, will award raffle tickets for drawing a few prizes at the end of the semester.

1.2 WORK ON PROJECT WITH KORRIBAN & VSCODE

For guide on working with VSCode, Terminal & Korriban, go back and review Project 01 and my video demo on BlackBoard.

1.3 GRADING CRITERIA

Project will be graded on correctness. Majority of your grade is determined by how many test cases your code passes. The points breakdown is as follows:

● Autograder Test Cases: 90%

○ We have configured an autograder in Gradescope which will run your code against predefined test cases to check for correctness.

○ Any solutions that try to game the test cases will receive zero credit. For example, if input = bla, then return bla.

○ STL containers (a.k.a. std::vector / std::list / std::map) are not allowed, usage of them will result in 0% being awarded

○ You code must compile, non compilable code will not be graded at all, there is no concept of partial correctness when code does not compile

● Coding practice: 10%

○ Declaraction should be in h file and definition should be in cpp file. 10%. If you forgot what this means, review Lecture 05 C++ Basics 02 & Lecture 06 OOP

1.4 RECOMMENDATION

We recommend getting started on the project early so you have time to ask questions in case you get stuck. We also recommend trying to submit your code on Gradescope well ahead of the deadline, even if you’re not done with all the questions, so you can see how the autograder works and understand whether your code is passing the test cases.

Please remember to follow our guidelines for academic integrity.

1.5 SIMPLE DEBUG DEMO

I have recorded a simple debugging demo uploaded to BlackBoard, it is not using any fancy toolings like GDB, checkpoints and all that, but instead, rely on the simplest, dumbest way to find my buggy line. If you have trouble debugging, getting frustrated that some part of your code you don’t know where is having issues, I am sure it would be helpful.

2 REVIEW KNOWLEDGE

2.1 ARRAYS OF CLASS OBJECTS

We will practice manipulating some raw format, thus, std::vector is not allowed, nor is std::list / std::forward_list etc. only raw C array is allowed. If you forgot how to write raw C array, review Lecture 05 C++ Basics 02

An array of class objects is like an array of some other data type.

To access the object at position i of the array, we write

and to call a method on that object method, we write

To get the address of a particular element in C++ array

We can also allocate an array of objects dynamically using the new operator (hint, you will use this line in this project), note that we are receiving the return type with a Point *, not Point [], this is just syntax and as we discussed in Lecture 05 C++ Basics 02, pointer is array, array is just pointer point to the beginning of the array (first element)

However, any new’ed item, must be “delete”ed, otherwise, those things won’t be released and will stay around forever, (think about a gradually getting slower machine). To remove them

2.2 C ARRAY AND C POINTER

After array is initialized, it is basically a pointer pointing to the first element of an array, thus, functions taking array takes pointer, functions taking pointers take array. In short, pointer is array, array is pointer.

You can also access the nth element of an array via its pointer form.

3 POINT

For the next several problems, you should put declarations in a header file and your function definitions in cpp file, doing so for all of your functions will get you 10 points.

There is a skeleton file already exist, you need to fill them out.

In this section you will implement a class representing a point, appropriately named Point, in geometry.h geometry.cpp files.

To test it, run the following command:

3.1 FOUNDATION

Fill the class with two private int32_t. Name them x and y.

3.2 CONSTRUCTORS

Implement constructor(s) that, if called with 0 arguments, initializes a point to the origin – (0, 0) – but if called with two arguments x and y, creates a point located at (x,y).

(Hint: You can choose to use default arguments)

If you forgot about how to write classes, review Lecture 06 OOP, here is also some extra information to read if you are still confused: https://www.geeksforgeeks.org/constructors-c/, https://www.geeksforgeeks.org/function-overloading-c/)

3.3 MEMBER FUNCTIONS

Support the following operations using the given function signatures (don’t be smart and make up other names, autograder only recognize names I listed here):

Get the x coordinate

Get the y coordinate

Set the x coordinate

Set the y coordinate

4 POINTARRAY

In this section you will implement a class representing an array of Points, kind of a vector<Point>. It will allow dynamically resizing the array, and it will track its own length so that if you were to pass it to a function, you would not need to pass its length separately. You should write them in point_array.h point_array.cpp

4.1 FOUNDATION

Inspect the class, it already has two private members, a pointer to the start of an array of Points and an uint32_t that stores the size (length) of the array. Review Lecture 05 C++ Basics 02 for why we are doing this. To test the project, run the following statements:

4.2 DEBUGGING FOR A PARTICULAR TEST CASE

Even though there is just one command (or a few) to run test cases, and in this case, is ./point_array_test, there are many independent test cases inside. Autograding will actually run them separately so if one of them crash, you still get points for the rest.

However, ./point_array_test crash on a particular test will prevent it from printing out your result for other tests, so if it is happening, you can run each test individually, by putting the test name as a parameter, such as, for PointArray Test 01

To find all the provided test cases, you can look into /tests/point_array_tests.cpp

4.3 CONSTRUCTOR

Implement the default constructor (a constructor with no arguments) with the following signature. It should create an array with size 0.

Implement a constructor that takes a Point array called points and an int called size as its arguments. It should initialize a PointArray with the specified size, copying the values from points. You will need to dynamically allocate the PointArray’s internal array to the specified size.

Hint, you should use “storage = new Point[size];” to dynamically allocate a buffer for the array.

4.4 DESTRUCTOR

Because PointArray holds an array that is dynamically allocated, we need to make sure we delete it when PointArray die. Review Lecture 07 Dynamic Memory if you forgot, any new-ed element must be delete-ed, otherwise it will be left in memory and become orphan.

If you forgot how to write a destructor, review Lecture 06 OOP, in short, you should have this in h file

And this in cpp file

4.5 MEMBER FUNCTIONS

Implement public functions to perform the following operations:

Add a Point to the end of the array

Insert a Point at some arbitrary position (subscript) of the array, shifting the elements past position to the right

Remove the Point at some arbitrary position (subscript) of the array, shifting the remaining elements to the left

Get the size of the array

Remove everything from the array and sets its size to 0

Get a pointer to the element at some arbitrary position in the array, where positions start at 0 as with arrays

If get is called with an index larger than the array size, there is no Point you can return a pointer to, so your function should return a null pointer. Be sure your member functions all behave correctly in the case where you have a 0-length array (i.e., when your PointArray contains no points, such as after the default constructor is called).

4.6 DEALING WITH AN EVER-CHANGING ARRAY

Since we will allow modifications to our array, you’ll find that the internal array grows and shrinks quite often. A simple (though very inefficient) way to deal with this without repetitively writing similar code is to write a member function PointArray::resize(uint32_t n) that allocates a new array of size n, copies the first min(previous array size, n) existing elements into it, and deallocates the old array. If doing so has increased the size, it’s fine for resize to leave the new spaces uninitialized; whatever member function calls it will be responsible for filling those spaces in. Then every time the array size changes at all (including clear), you can call this function.

In some cases, after you call this function, you will have to subsequently shift some of the contents of the array right or left in order to make room for a new value or get rid of an old one. This is of course inefficient; for the purposes of this exercise, however, we won’t be worrying about efficiency. If you wanted to do this the “right” way, you’d remember both how long your array is and how much of it is filled, and only reallocate [double the capacity] when you reach your current limit or when it dips to 1/3 of its capacity and reallocate to cut half of the capacity.

Add the PointArray::resize(uint32_t n) function as specified above to your PointArray class. Give it an appropriate access modifier, keeping in mind that this is meant for use only by internal functions, don’t forget to remove the old array (delete[] old_array)

If this section is too difficult for you, you can create a very large array during construction (300 or more) and then keep it that size, you will lose 21% of the points without this functionality.

5 STRETCH SECTION:

As we stated, this section does not count against your final score, they award raffle points. This part award 50 raffle tickets.

5.1 SUBMISSION LOGISTICS

Stretch section is separate from the basic section, even though, they share many of the files. To submit project_02 stretch section, you should submit all your basic section files + shape.h shape.cpp and answer.txt to Project 02 Stretch on GradeScope.

You may submit your code to Gradescope as many times as you like, up until the deadline. and receive real time grading results. We will only grade your most recent submission.

Autograding accounts for 60% of the points, and the questions and logistics at the end accounts for 40%

5.2 CONST MEMBER FUNCTIONS

It is clear what const-ness means for a simple value like an int, but it is not clear what functions should be available on a const object, since functions may allow modifications in subtle ways that ought to be forbidden on const objects. To specify to the compiler that a given member function is safe to call on const objects, you can declare the function with the const keyword. This specifies that the function is a “read-only” function that does not modify the object on which it is called.

To declare a const member function, place the const keyword after the closing parenthesis of the argument list. The const keyword is required in both the declaration and the definition. A const member function cannot modify any data members or call any member functions that aren’t also declared const.

Generally, const member functions should return const values, since they often return references/pointers to internal data, and we wouldn’t want to allow someone to get a modifiable reference to the data of a const object.

If an object of class Person would be declared as const Person jesse, no non-const member functions could be called on it. In other words, the set of const member functions of a class defines the set of operations that can be performed on const objects of that class.

5.3 COPY CONSTRUCTORS & COPY ASSIGNMENT OPERATOR

Finally, implement a constructor that creates a copy of a given PointArray (a copy constructor).

Remember, you cannot just do new_array = old_array to copy arrays, this way only copies the pointers pointing to the first element of the array, effectively, they points to the same array.

(Hint: Make sure that the two PointArrays do not end up using the same memory for their internal arrays. Also make sure that the contents of the original array are copied, as well. If you forgot what this is, here is something to read: https://www.geeksforgeeks.org/copy-constructor-in-cpp/)

(Hint2: If you are a little confused about how to create an internal array, see the “Additional Material” section above)

Technically, if you wrote a copy constructor, you should also write an assignment operator and a destructor, called the rule of three (newer c++ rule of five), we did not touch this in class and it is just for you to learn if you are interested, you can read about it here: (https://www.geeksforgeeks.org/copy-constructor-vs-assignment-operator-in-c/ https://www.geeksforgeeks.org/rule-of-three-in-cpp/)

To test this section, run

5.4 ADDITION INFORMATION:

5.4.1 Static members and variables

You can read the below information, or read from: https://www.geeksforgeeks.org/static-data-members-c/, https://www.geeksforgeeks.org/some-interesting-facts-about-static-member-functions-in-c/, which is probably better, but longer.

Static data members of a class are also known as “class variables,” because there is only one unique value for all the objects of that class. Their content is not different from one object of this class to another.

For example, it may be used for a variable within a class that can contain a counter with the number of objects of the class that are currently allocated, as in the following example:

5.4.2

In fact, static members have the same properties as global variables, but they can only be referenced via the class: either in class methods, via a class instance some_object.static_variable, or via the ClassName::variable.

Note: line 13 must be in the cpp file, it is technically the definition, it is actually where the variable lives!

Classes can also have static member functions – that is, member functions which are associated with the class but do not operate on a particular class instance. Such member functions may not access non-static data members. For instance, we might replace CDummy above with the following class definition:

getN could then be called as c->getN() or CDummy::getN(), note that getN() does not reference a particular instance, it cannot any non static member variable that is associated to a particular instance.

5.5 POLYGON

In this section you will implement a class for a convex polygon called Polygon. A convex polygon is a simple polygon whose interior is a convex set; that is, if for every pair of points within the object, every point on the straight-line segment that joins them is also within the object.

Polygon will be an abstract class – that is, it will be a placeholder in the class hierarchy, but only its subclasses may be instantiated. Polygon will be an immutable type – that is, once you create the Polygon, you will not be able to change it.

Throughout this problem, remember to use the const modifier where appropriate.

5.5.1 Foundation

Create the class with two protected members: a PointArray and a static uint32_t to keep track of the number of Polygon instances currently in existence.

5.5.2 Constructors/Destructors

Implement a constructor that creates a Polygon from two arguments: an array of Points and the length of that array.

Use member initializer syntax to initialize the internal PointArray object of the Polygon, passing the Polygon constructor arguments to the PointArray constructor. You should need just one line of code in the actual constructor body. [5%] – Not a question, doing so will award 5%

Make sure that your constructors and destructors are set up so that they correctly update the static int that tracks the number of Polygon instances.

5.5.3 Member Functions

Implement the following public functions according to the descriptions:

Calculates the area of the Polygon as a double. Make this function pure virtual, so that the subclasses must define it in order to be instantiated. (This makes the class abstract.)

Returns the number of Polygons currently in existence, can be called even without referencing a Polygon instance. (Hint: Use the static int.)

Returns the number of sides of the Polygon.

Returns an unmodifiable reference to the PointArray of the Polygon.

5.6 RECTANGLE

Write a derived class of Polygon called Rectangle that models a rectangle. Your code should allow constructing a Rectangle from two Points (the lower left coordinate and the upper right coordinate)

Override the Polygon::area’s behavior such that the rectangle’s area is calculated by multiplying its length by its width, but still return the area as a double.

5.7 TRIANGLE

Write a subclass of Polygon called Triangle that models a triangle. Your code should construct a Triangle from three Points

Override the area function such that it calculates the area using Heron’s formula: (you may use std::sqrt) in your code, don’t forget to “#include <cmath>”

where a, b, and c are the side lengths of the triangle and s = (a + b + c) / 2

5.8 DELEGATE CONTRUCTOR

Sometimes there are many ways to write constructors, and there might be many duplications, to avoid such, some constructors can delegate to other constructors. For example:

More information: https://www.geeksforgeeks.org/constructor-delegation-c/

Correctly implemented this would make Triangle & Rectangle’s constructor free from modifying any member variable (like PointArray), it might be slightly tricky here, but if you figured it out, it is [10%]

5.9 QUESTION:

You should write a Answer.txt file to submit as well, with the answer to this question. (25%)

1. Will the default copy constructor work here? Explain what happens to the PointArray field if we try to copy a Polygon and don’t define our own copy constructor. [5%]

2. In section 4.6, why do we need const and non-const versions of get? (Think about what would happen if we only had one or the other, in particular, what would happen if we had a const PointArray object.) [5%]

3. In the Point class, what would happen if the constructors were private? [5%]

4. Describe what happens to the fields of a Polygon object when the object is destroyed / dies, what in your design (code) is taking this into consideration. [5%]

5. Why did we need to make the fields of Polygon protected, any other approach? [5%]

Just to put it here:

1. If code correctly use constructor delegation [10%]

2. Correctly use initializer [5%]