CSE 201 - Tutorial 3 - A new tutorial on dynamic memory allocation and git

The tutorial this week is split between a set of programming exercises on dynamic memory allocations and a set of exercises on git.

You will be evaluated both on the programming exercises (as usual) and on the git tutorial (more on this later). The programming exercises will give you 60 points, the git tutorial 40.

IMPORTANT (READ THIS!): git is the main tool you will use to collaborate inside your team while developing the project and learning how to use this tool will be fundamental. The tutorial today will help you practice some of the basic commands you need to know to use git (commit your changes to a project, merge the conflicts when different developers modify the same files concurrently, ecc…).

WE WILL EVALUATE YOUR INDIVIDUAL CONTRIBUTIONS during the project looking at the specific code that you contribute to the git repository. This means that we will not consider any code that does not appear as contributed by you on git when evaluating your contribution to the project (i.e., your grade!). So, take all the necessary steps during this tutorial to set up your machine and learn the basics of git.

Recording the projectile telemetry

Today you are going to modify the shooting game adding a telemetry feature that records all the positions of the projectiles shot.

Setting up the tutorial.

Download the handin of the tutorial CSE201-td3-1-handin.zip, extract the archive, and open the Qt Creator project td3.pro. This week you will only need to modify the file td3.cpp.

Evaluation.

You will be evaluated on all the exercises for a total of 60 points:

1 test_extend_array: 10
2 test_shrink_array: 10
3 test_append_to_array: 10
4 test_remove_from_array: 10
5 test_simulate_projectile: 10
6 test_merge_telemetry: 10

Rules for the evaluation:

• A program that does not compile will receive 0 points: this means that your program cannot contain syntax errors (e.g., forgetting the ; sign after a statement) and typing errors (e.g., assigning an array variable to an integer variable);
• Each program will be evaluated running on a set of different inputs. You will receive the points for an exercise if your implementation behaves correctly an all the test cases.

Run the automatic grader on your computer first and submit your solution for each exercise as soon as you have one, so we can track the class progress.

Submitting your Work

You will submit the file td3.cpp:

• The deadline for submitting the exercise is next Sunday, October 15, at 23:59 Paris time. The submission site will not accept new solutions after that date.

1. Extend an array

Implement the function:

double* extend_array(double* array, int length, int new_size);

that increases the size of the array of double array from length to new_size elements.

The function extend_array will:

• ALLOCATE a new array of size new_size, and

• copy all the elements of the array array, up to size length, and

• initialize to 0-s all the remaining array elements (i.e., from index length to index new_size-1), and

• DE-ALLOCATE (delete operator) the memory used by the “old” array (array variable).

• return the newly allocated array as output of the function.

Note that the function allocates an entirely new array and returns its address as output.

An example of usage of the function extend_array is:

int *array;
array = new int[4];
for (int i = 0; i < 4; i++) array[i] = 7; // array is [7,7,7,7]
array = extend_array(array, 4, 8); // array is [7,7,7,7,0,0,0,0]

and in this case array would be a pointer to an area of memory containing the array [7,7,7,7,0,0,0,0].

Furthermore, you are also required to delete the memory allocated for the array array.

Note that you may see a failure in your test case like:

[FAILURE] extend_array([1,2], 2, 4): got an error since your function has not enough delete operations (# of new - # delete) is 1 instead of 0 and uses more memory (48 bytes instead of 32 bytes)  expected [1, 2, 0, 0]

the text above indicates that in your function you did not free some memory. The test case will not show you the content of the modified array until you fix these issues (i.e., first get right the memory allocation/deallocation and setting the array size, then check that you are copying the correct elements in the result array). You will get similar error messages if you do not allocate enough memory.

2. Shrink an array

Implement the function:

double* shrink_array(double* array, int length, int new_size);

that shrinks the array of double array from size length to size new_size. The new array must contains all the elements of array until new_size.

For example, the following code:

int *array;
array = new int[4];
for (int i = 0; i < 4; i++) array[i] = 7;
array = shrink_array(array, 4, 3);

would put in array a pointer to an area of memory containing [7,7,7].

As before, the function will create a new area in memory and delete the memory pointed by array.

3. Append new elements to an array

Implement the function:

double* append_to_array(double element,
                        double* array,
                        int &current_size,
                        int &max_size);

that append the number contained in element to the array array, and returns the array pointer as output.

IMPORTANT The array array points to an allocated area in memory of size max_size but during the execution of the program only uses a total of current_size elements. In practice, the program allocates more memory than the one used. The reason for this technique is (time) performance, since resizing the array requires time, for example to copy the content of the array in the new allocated area of the memory.

So, current_size is a “logical size” for the array while max_size is its physical size.

Your implementation will increase the memory allocated for the array only when needed (i.e., when current_size == max_size). Also, every time you allocate a new array you will increase it’s size by 5 every time (hint: use the previous functions to extend the array size).

Note how both max_size and current_size value can change. current_size changes because you insert a new element in the array and max_size value changes when you extend the allocated memory for the array.

The following code:

double *array;
int total_elements = 4;
int array_size = 5;
array = new double[array_size];
for (int i = 0; i < 4; i++) array[i] = 7;
array = append_to_array(10, array, total_elements, array_size);

would put in array a pointer to an area of memory containing [7,7,7,7,10], change total_elements to 5, and leave array_size equal to 5;

Calling append_to_array another time as:

array = append_to_array(11, array, total_elements, array_size);

would return the array [7,7,7,7,10,11], increase total_elements to 6 and change array_size to 10.

4. Remove the last element

Implement the function:

double* remove_from_array(double* array,
                          int &total_elements,
                          int &array_size);

that removes the last element from array.

The function further shrinks the array when the difference between the total number of used elements total_elements and the array maximum size array_size is at least 5 (remember to update total_elements and array_size).

int *array;
int total_elements = 5;
int array_size = 10;
array = new int[array_size];
for (int i = 0; i < 5; i++) array[i] = 7;
array = remove_from_array(array, total_elements, array_size);

would return a pointer to [7,7,7,7], total_elements would be 4, and the array would be resized to allocate just 5 elements. Also array_size would be 5.

5. Log the telemetry of a projectile

Implement the function:

bool simulate_projectile(const double magnitude, const double angle,
                         const double simulation_interval,
                         double *targets, int &tot_targets,
                         int *obstacles, int tot_obstacles,
                         double* &telemetry,
                         int &telemetry_current_size,
                         int &telemetry_max_size);

that simulates the motion of a projectile, checking its collision with targets and obstacles. We already provided a version of the simulation function that does not record the telemetry.

Your task is to store in the telemetry pointer (NOTE: telemetry is parameter of type *double, a pointer to a double, that is passed by reference) the address to an array of double containing, in sequence, the time, the x coordinate, and the y coordinate simulated for the projectile.

telemetry_current_size will contain the number of elements (and not the number of points) the function stored in telemetry, and in telemetry_max_size the total amount of allocated memory pointed by telemetry.

For example, the simulate_projectile could simulate the following coordinates:

time = 0, x = 0, y = 0
time = 0.01, x = 0.2, y = 0.3
time = 0.02, x = 0.4, y = 0.4
time = 0.03, x = 0.8, y = 0.3

the telemetry array would contain [0,0,0, 0.01,0.2,0.3, 0.02,0.4,0.4, 0.03,0.8,0.3], it’s telemetry_current_size would be 12 ad the telemetry_max_size would be 15 (assuming the initial array started with a maximum size of 5, and that the function used the above implementation of extend_array).

HINT: reuse the function append_to_array.

6. Merging multiple telemetries

Implement the function:

void merge_telemetry(double **telemetries,
                     int tot_telemetries,
                     int *telemetries_sizes,
                     double* &global_telemetry,
                     int &global_telemetry_current_size,
                     int &global_telemetry_max_size);

that “merges” the telemetries of multiple projectiles into a single telemetry.

The simulate_trajectory function can be called for multiple projectiles, thus creating multiple telemetries. Multiple telemetries are stored in the telemetries variable, that is a pointer to a pointer to doubles.

The array of pointers to doubles has tot_telemetries elements (i.e., telemetries points to an allocated area of memory of containing tot_telemetries pointers to doubles). Then, the i-th pointer to doubles pointed by telemetries points to an array of doubles of size telemetries_size[i]. For example, you could print the telemetry for the 2-nd projectile as follows:

for (i = 0; i < telemetries_size[1]; ++i) {
    std::cout << i << "-th element is " << telemetries[1][i] << std::endl;
}

The function merges all the different telemetries in a single one (that you must allocate in the variable global_telemetry) that contains all the samples from each telemetry and where the samples appear ordered by time. The function must also return the total number of elements stored in global_telemetry (in the variable global_telemetry_current_size) and the total amount of elements that have been allocated (in the variable global_telemetry_max_size).

Git tutorial

Submitting your Work To submit the exercises on git you will have to first complete the exercises (from 4 to 7 - the exercises are more a guided tutorial on git, so follow the steps closely), and then complete the questionnaire on Moodle.

4. Configuring GitHub, GitHub Desktop and git

You will use Git as tool for version control and collaborative software development. Git provides you two main features:

• track the different version of your code
• collaborate with multiple developers on the same project.

You can use git not just for software development, but every time you need version control and to work with someone else (e.g., writing papers, …).

You will further use GitHub as code hosting platform: GitHub will host the files of your project (including the source code files) so that you can share them with your colleagues.

As first step you will set up your machine to use git and GitHub: you will install git (the command line tool) and GitHub Desktop (a more user friendly user interface to use git) on your computer, and then set up a (free) user account on GitHub.

You will follow the GitHub desktop documentation Setting up GitHub Desktop - GitHub Docs to:

1. Create a user account on GitHub.

   You need to set up a GitHub account to be able to use the platform. Open the GitHub page and sign up for a new account (sign up button in the top right of the page).

   IMPORTANT: If possible, choose a user-name that we can recognize, e.g., name-surname. Please, do not use something like your favourite Pokemon name, e.g. Pickach-2000, because we will not be able to easily identify the commit you authored in the project (read again the comment about using git for your evaluation at the beginning of the tutorial). If you already have such kind of github username you can still use it for the project (but remember to submit your username via Moodle, see the submission instruction later).

2. Install the git client: Git - Downloads

   • If you have Windows: Downloading Git for Windwos.
   • If you have Linux: Downloading Git for Linux.
   • If you have macOS and you installed Xcode (or the command line tools for Xcode): you are all set and git is already installed! Otherwise, download git here Download Git for macOS.

3. Install GitHub Desktop: Installing GitHub Desktop

   The above guide works if you have Windows or macOS. If you have linux, you will have to use a non-official version of GitHub Desktop:

   • Follow this guide to get the tool installed: Is GitHub Desktop available for GNU/Linux?
   • Otherwise you can download the binary packages directly from Releases - shiftkey/desktop

4. Configure GitHub Desktop

   • Authenticate to GitHub: Authenticating to GitHub

   • Set up the git commit information: Configuring Git for GitHub Desktop

     IMPORTANT Set the email as the email you used to register to GitHub, otherwise GitHub will not annotate correctly your contributions to the project

5. Using Git on a Local Repository

In this exercise you will create a code repository on your computer and you will learn how to create code commits, hence creating a history of changes for your code. Here we focus on using version control locally, so you’ll first work on a local repository (i.e., on your computer). We will see how you can synchronize your work remotely to collaborate with other developers later.

We will create a code repository for the tutorial 3 handin. You will work in [GitHub Desktop] to interact with the repository and in [Qt Creator] to edit the code.

1. [GitHub Desktop] Create a new repository. Go in the menu “File”, then “New Repository…”

   

   In the dialog insert the details of the repository:

   • Name: CSE201-td3-1-handin

     IMPORTANT: use the same name of the handin directory! (otherwise the tool will create a new directory with a different name).

   • Local Path: select the path that CONTAINS the handin directory, and not the directory CSE201-td3-1-handin.

     In the example the path is /Users/sergiomover/works/scratch, because the repository is in /Users/sergiomover/works/scratch/CSE201-td3-1-handin.

   • Select “Initialize this repository with a README”. The README file contains the description of the repository (that is shown on GitHub…)

   • Select “Qt” from the “Git Ignore” list: several files should not be contained in the repository. In particular, this is true for files that are automatically generated, like the executable you obtain compiling your code. Also, other files like local configurations should not be in the repository. The git ignore configuration defines a set of file types (by extension) that are created automatically by Qt and that must be ignored. For now just select this configuration, it can be changed later on (see for example Ignoring files).

     

   Create the repository. You will see that now there is a new repository. You can click on the History button and see that there is already a commit in your repository with summary “Initial commit”, adding all the files from the handin folder.

   The Changes view is empty instead, meaning that the local files are in sync with the version saved in the local repository.

   In other cases you don’t create a new repository but you clone one directly from GitHub (see the guide here).

2. [Qt Creator] Open the project td3.pro in Qt Creator and edit the main.cpp file.

   Change the define #define GRADING 1 to #define GRADING 0. Add the print First Git Commit in the main function:

   int main(int argc, char* argv[])
   {
   #if GRADING != 1
     // START OF THE CUSTOM CODE SECTION
     // This code will be executed only if you set GRADING to a value different from 1
   
     {
           std::cout << "First git commit" << std::endl;
     }
     // END OF THE CUSTOM CODE SECTION
   ...
   }

3. [GitHub Desktop] You will see that the file main.cpp is changed:

   

   GitHub Desktop will show the files that changed on your filesystem that differ from the content of the file in the last commit. The tool also shows a diff, showing both versions of the file (the one committed and the one on your filesystem): the green lines shows the lines that have been added, while the red lines shows the lines that have been removed since the last commit.

   Now you can commit your new changes: Insert the summary message and the description (in the bottom left part) and click on the “Commit to main” button.

   As soon as you commit, then main.cpp file will disappear from the list of changed files, and you can see in the “History” tab that there is a new commit. So, for now you can imagine the history as a list of commits.

From this short exercise you should have a clearer idea about what is a repository, what is a commit, what is the history of a repository.

6. Developing using branches

You can see that you’re working on the “main” branch (look in the middle of the top bar). You can think of a branch as a sequence of commits (i.e., the history we were looking at before). However, code development can diverge, for example when developers work on different features at the same time. For this reason, a repository can have multiple branches. You can think about the history of a repository as a directed acyclic graph where each node is a commit and each edge relates commits temporally.

In the figure above you can see a representation of different branches:

• there are 6 branches (Master, Hotfix, Release, Develop, and two branches named Feature);
• all the nodes are commits, and the time of creation of commits goes from left to right (i.e., a commit on the left was created earlier than a commit on the right);
• a branch can branch from an existing branch and can merge into other branches (e.g., see the node of the Hotfix branch);

1. [GitHub Desktop] Create a new branch called new_initial_message:

   

2. [Qt Creator] Change the message print in the main function from “First git commit” to “New initial message” (save the changes)

3. [GitHub Desktop] Commit your changes

4. [GitHub Desktop] Switch back to the main branch (select the main branch from the branch drop-down box). Take a look at the main.cpp file in Qt Creator: what version of the file are you looking at? (say yes when Qt Creator asks you to update the viewed file).

5. [GitHub Desktop] Create a new branch and name it a_better_message

6. [Qt Creator] Change the message from “First git commit” to “A better message” (save the changes)

7. [GitHub Desktop] Commit your changes

8. [GitHub Desktop] At this point, you are ready to incorporate your changes from the “A better message” in the “main” branch.

   • Select the main branch
   • Merge the a_better_message branch into the main branch, selecting the branches drop-down and then “Choose a branch to merge into main”

   NOTE: all the figures below show a branch called “master” instead of “main”.

    ![Merge into main](resources/merge_into_master.png)
   
    Then select the `a_better_message` branch and merge it.
   
    ![Merge into main details](resources/merge_into_master_details.png)

9. [GitHub Desktop] At this point, try to also merge the branch new_initial_message into the main branch. As soon as you try to merge the branch, you will end up with a conflict: you have a conflict when you are trying to merge two commits that simultaneously changed the same content of a file (in our case, the string printed in the main function).

   You will see a warning sign just before merging the branch:

   

   Proceed and merge, you will see a merge dialog telling you that there is a conflict in the main.cpp file:

   

   Here keep this dialog window open and continue at step 8.

10. [Qt Creator] At this point you have to resolve the conflict, meaning that you have to edit the file that was changed multiple times and select the version (or combination of versions) that you want to keep. Open the file main.cpp in Qt Creator, you will see that your file changed as follows:

    

    Git merged the files adding the lines <<<<<<< HEAD, =======, and >>>>>>> new_initial_message. This notation is a diff, and tells you that the content between the lines <<<<<<< HEAD and ======= comes from the HEAD version (the last commit of the main branch), while the content between the lines ======= and >>>>>>> new_initial_message shows the content of the new_initial_message branch. Notice that in a file you may have several sections marked as above.

    Now, edit the file main.cpp to resolve the conflict, printing the string “A better, new initial message” (and save your changes):

    

    In general, you may have to repeat the same task for all the files that have a conflict (of course, a commit may change multiple files) before you will be able to complete the merge.

11. [GitHub Desktop] In GitHub Desktop you will see that there are no more conflicts and that you can commit the merge of the two branches (the button is not grayed out anymore):

    

7. Synching on GitHub

Now your repository is on your local machine. However, you need to host a repository online to have different people collaborate together. In the following steps you’ll learn how to publish your repository and synchronize your local repository with the remote one.

1. [GitHub Desktop] To publish your repository on GitHub just click on “Publish repository” in the top right corner:

   

   

   Click on “Publish Repository” button. Now you can visit your repository online on GitHub, via https://github.com/<your_username>/CSE201-td3-1-handin. For example:

   

   The GitHub website lets you do several things with your repository, from viewing the files in different branches and commits, to manage issues, …

2. [Qt Creator], [GitHub Desktop] Change the main.cpp file and commit the new change on the main branch.

   Now, your local repository and the remote repository on GitHub differ (the repository on GitHub does not have the last commit). To synchronize the changes you can push them from [GitHub Desktop] (see the button at the top-right of the GitHub Desktop window).

   When you push you synchronize the information from your local repository to the remote one. Now you can check again GitHub and see that it has a new commit.

   IMPORTANT: This step is what you will do to share your work with others.

3. [GitHub] From the GitHub web interface select the README.md file and then edit the file (there is a small pencil icon you can click). GitHub will open an editor inside your browser: add a description for your project and then commit the changes.

4. [GitHub Desktop] Now you can synchronize your local repository (i.e., retrieve the changes on GitHub on your local machine):

   • click on the “Fetch” button. The fetch operation just downloads the data from the remote server (i.e., GitHub) without changing the content of the local repository.
   • click on the “Pull origin” button to merge the new changes in your local repository. These two commands will synchronize your local repository with the remote one.

   IMPORTANT: This step is what you will do to get the changes performed by others.

Submitting exercise 4 to 7 To submit your exercises complete the questionnaire on Moodle.

Here there are some furhter tips for using Git (read them carefully if you become the git responsible for your project):

• You can push your branches to the remote repository with the button “Publish branch” (you need to select the branch to push first). The best practice that you should follow during your project is to push your branch on the remote repository to

  1. work collaboratively on the branch with other developers; and
  2. save your current work on the remote server.

• A more advanced technique (and somehow a standard now) to merge branches is to do it remotely on GitHub using a “Pull Request”

• A best practice to work collaboratively is to always work on a branch different from main. This allows you to edit the files you need without worrying about conflicts. When your work is ready, you can create a Pull Request to merge your changes into the main branch.

• You can use more advanced work-flows, like the GitHub workflow.

• You may have to use a use git via command line. In that case you can find this cheatsheet useful.

• Please, for your project AVOID forks in GitHub (if you don’t know what a fork is, just ignore this). Forks work well when external developer contributs to open-source projects, but do not work well inside a single group of developers.