# Week 2 Solutions Doc
## Research Programming with C++

This week we'll be exploring various aspects of the C++ standard library. If you've learned C++ in an older style then some aspects of this, such as I/O and containers, will be familiar; however we will also see how these are typically used in the modern C++ style, making use of newer features such as type inference, range based loops, smart pointers, and anonymous functions.

## Before You Begin

**Please clone the [Week 2 Exercises repository here](https://github.com/UCL-PHAS0100-22-23/week2_cpp_exercises).**

## Section 1: Working with Containers and the Standard Library

In this section we will mostly explore containers, and some of the things that we can do with them using other parts of the standard library. We will also introduce the idea of a unit test for checking the correctness of our code.

### Exercise 1:

- Open your terminal and move into the `Section_1_Vector_Functionality` folder.

cd Section_1_Vector_Functionality

- Explore the folder structure to familiarise yourself with the files.
- `src` contains the source files for the vector functions that we will be writing and the main function.
- `include` contains the header file for the vector functions.

#### Part 1:
- Complete the function `countMultiplesOfFive` in `vector_functions.cpp` using a range-based loop to determine the number of elements in a `vector<int>` which are equal to a multiple of `5`. (Note that you can use the `%` operator to get the remainder of an integer division e.g. `10 % 3` would return `1`.)
- Write some lines in your main function to check that it works the way that you expect.
- Next week we'll cover _unit tests_ as a better way to test the correctness of our code!
- Note that there is already a `#include "vector_functions.h"` statement at the top of the file, so that the main has access to the declaration of the function that we need to test.
- When testing code, we want to cover multiple test cases which fully explore the behaviour of our function under different circumstances. This is an important part of designing robust software.
- Declare a vector of ints which has multiples of `5` in it (including `0` as a multiple of 5), as well as other values. Check that your count function returns the correct number.
- Declare a vector which contains some integers but no multiples of `5`, and check that your function returns `0`.
- Declare a vector which is empty, and check that your count function returns `0`.
- Build using `g++`
To compile from the `Section_1_Vector_Functionality` folder:

g++ -o build/vector_exercises src/* -Iinclude

and then to run:

./build/vector_exercises

### Solution:

Counting function with a loop should look like this:

int countMultiplesOfFive(const std::vector<int> &v)
{
    int count = 0;

    for(const auto &i : v)
    {
        if(i % 5 == 0) count++;
    }

    return count;
}

Some testing code could look like this:

#include <iostream>
#include "vector_functions.h"
#include <string>

int main()
{
    std::vector<int> some_multiples = {1, 5, 3, 10, 0, 2};
    int count = countMultiplesOfFive(some_multiples);
    std::cout << (count == 3 ? "Check 1 passed" : "Failed first check, should find 3 multiples and found " + std::to_string(count)) << std::endl;
    
    std::vector<int> no_multiples = {2, 3, 9, 18, 47};
    count = countMultiplesOfFive(no_multiples);
    std::cout << (count == 3 ? "Check 1 passed" : "Failed second check, should find 0 multiples and found " + std::to_string(count)) << std::endl;

    std::vector<int> empty_vector;
    count = countMultiplesOfFive(empty_vector);
    std::cout << (count == 3 ? "Check 1 passed" : "Failed third check, should find 0 multiples and found " + std::to_string(count)) << std::endl;
    
    return 0;
}

#### Part 3:
- Rewrite your function to count the number of multiples of 5 in a `vector<int>`, this time using the standard library function [`std::count_if`](https://en.cppreference.com/w/cpp/algorithm/count).
- `std::count_if` should take three arguments: a start iterator, an end iterator, and a _functor_ (usually a function pointer or lambda expression). It returns the number of elements between these iterators for which the function evaluates to `true`.
- Remember that `vector` has the methods `.begin()` and `.end()` to return the first and last iterators in a vector.
- Write your function as a lambda expression (remember the `[](){}` syntax) inside the arguments of `count_if`.
- Recompile your code and run your unit tests to check that your function still works!

### Solution:

To count using algorithm, the previous loop code should be replaced with this:

int countMultiplesOfFive(const std::vector<int> &v)
{
    return std::count_if(v.begin(), v.end(), [](int x){return x % 5 == 0;});
}

Checks should run the same and still pass. It is important to develop the habit of re-running relevant tests each time an implementation like this is changed, so that you know that things are still working. We'll set up this kind of thing properly next week when we look into unit testing!

### Exercise 2:

- The `vector_functions` library defines a function `addElements(vector<int> v, int x, int n)` which adds `n` elements to the vector `v`, each containing the value `x`.
- Call this function in your `main` and test if it works.

- What happens? You can use outputs or debugging to find out what is going wrong.

- Go to the definition of `addElements` in `vector_functions.hpp` and `vector_functions.cpp` and fix the function. Re-compile and run the test again to see that your correction has worked.

#### Solution:

When you call the function your vector will be unchanged.

This is because the vector was passed by **value** instead of by **reference**. This is fixed by passing by reference which means adding an `&` symbol in both the header and the source file.

After you've done this and re-compiled, the test should run and pass.

-------------------------------------------------------

## Section 2: Building an Integrator using the Standard Library

The exercises in this section will continue to build our knowledge of the standard library and practice our C++ programming. We will explore how to read C++ documentation and apply this to a numerical problem.

## Section 2: Random Numbers in the Standard Library

The exercises in this section will continue to build our knowledge of the standard library and practice our C++ programming. We will explore how to read C++ documentation and apply this to a numerical problem.

### Exercise 4:

#### Part 1.

The method of integration that we'll be using will feature random numbers. Random numbers in computing is a broad and complex topic, so this week we'll just focus on the practicalities of _how_ to generate random numbers in C++, which has changed since the introduction of the `<random>` library.

- In your terminal, move into the `Section_2_Monte_Carlo_Integrator` folder, which is where we'll do our coding for this exercise.
- This code calculates the volume of a sphere by generating random points within a three dimensional space and checking if they are inside the sphere.
- In this case it will be a unit sphere (radius = 1), and the points should be generated inside the cube $-1 \le x \le 1$, $-1 \le y \le 1$, $-1 \le z \le 1$.
- The volume of the sphere is the proportion of points inside the sphere multiplied by the volume of the total space in which you are generating the points.
- The volume of the cube is $V_\text{cube} = 2 \times 2 \times 2 = 8$.
- So the volume of the sphere is $V_\text{sphere} = n_\text{inside} / n_\text{outside} \times 8$
- We have provided the code to test if points are within the sphere and calculate the volume.
- You will be adding code to generate the random points inside the box.

- First, open up the [documentation for `random`](https://www.cplusplus.com/reference/random/), which we'll be looking at for this exercise.
- Add an `#include <random>` statement at the top of the file source file in `src`.
- To generate random numbers we need two things: a random number _generator_ and a _distribution_.
- Start by taking a look at the list of distributions that you can use in the `random` documentation. In this exercise we want to generate random `double` (real as opposed to integer) numbers from a _uniform_ distribution.
- Find the appropriate distribution and click on it to go to the documentation for this particular distribution. This will depend both on how we want to points distributed, and the numerical _type_ that we are using.
- You should see at the top of the page that the appropriate header is `<random>` and the **namespace is `std::`**.
- To see how to declare a variable of this type, go to the list of member functions and click on the constructor.
- You should see that the constructor takes two parameters: a lower and an upper bound for the random numbers. (Remember that in this example we want to generate numbers between `-1.0` and `1.0`.)
- You can also see that you can the distribution specifies some type inside angle brackets `<>`, similar to a vector. We want to generate numbers of type `double`, so use `<double>`, or you can just use empty brackets `<>` since it says that `double` is the default type.
- You should now be able to declare your distribution in the C++ code. Declare the generator inside the `IntegrateMonteCarlo3D` function, and give it a sensible name like `uniform_dist`.
- You can look at the example code in the documentation page for the distribution if you're not sure how to declare it!

- Next we need to declare the generator. There are many different random number generators, and the differences between them is a complex topic, so for today we'll just select the [_Mersenne Twister 19937_](https://cplusplus.com/reference/random/mt19937/).
- You can declare the generator with a specific random seed or not.
- `std::mt19937 rng_mt;` will work just fine for now.
- Random number generators are not really random! The sequences of number that they generate are deterministic, but have statistically similar distributions to random. The sequence generated depends on the _seed_, so if you want different sequences, you need to run with different seeds.
- `std::mt19937 rng_mt(1)`; will generate a different sequence from `std::mt19937 rng_mt(2);`
- For most research applications we want to set the seed explicitly, as this makes the results reproducible.
- Declare the generator inside the same function.

- Once we've declared both a generator and a distribution, we can start generating random numbers!
- We actually generate random numbers by calling the _distribution_ rather than the generator.
- The [generator object is callable](https://cplusplus.com/reference/random/uniform_real_distribution/operator()/), which means that the `()` operator is defined for it.
- You pass the random number generator to the distribution, and the distribution uses this to generate a random value and then transform it to match that distribution and type.
- So `uniform_dist(rng_mt)` will return a uniform random number between your max and min value, using your Mersenne Twister generator.
- Inside the loop in `IntegrateMonteCarlo3D`, complete the code to assign random values to `x`, `y`, and `z` between `-1` and `1`.

- Compile and run the integrator. Do you get the value you expect? (Volume of a sphere is $\frac{4}{3} \pi r^3$.)

#### Solution:

You should choose the `uniform_real_distribution<double>` because we want a uniform distribution of doubles i.e. real numbers rather than integers.

double IntegrateMonteCarlo3D(int n_points, double min, double max)
{
    int count = 0;
    double VolCube = std::pow((max - min), 3);

    std::uniform_real_distribution<double> uniform_real(min, max);
    std::mt19937 rng_mt;

    for(int i = 0; i < n_points; i++)
    {
        //generate random point
        double x = uniform_real(rng_mt);
        double y = uniform_real(rng_mt);
        double z = uniform_real(rng_mt);
        if(InsideUnitSphere(x, y, z)) count++;
    }

    return (double)count / n_points * VolCube;
}

#### Part 2.

- We can use [std::bind](https://cplusplus.com/reference/functional/bind/) to avoid passing the generator to the distribution every time.
- `std::bind` is a little complex, but the examples in the documentation help to clarify the usage.
- It can be used to bind an argument to a function, to make a function of fewer (possibly no) arguments.
- e.g. if I have a function `add(int a, int b)` which adds two integers, then `auto add5 = std::bind(add, 5, std::placeholders::_1);` will create a new object which is callable and adds 5 to a single argument e.g. `add5(12)` will return `17`.
- `std::bind(uniform_dist, rng_mt)` will create a new callable object (which takes no arguments) which is equivalent to calling `uniform_dist(rng_mt)`.
- Use `auto` when declaring a variable to get the compiler to infer the type of this object!
- Use bind to create a new object which binds together your generator and your distribution, and use this to generate your random points instead.
- Make sure you've checked what header you need to add to your source file in order to do this!
- Recompile and re-run to check that your program still works.

#### Solution:

double IntegrateMonteCarlo3D(int n_points, double min, double max)
{
    int count = 0;
    double VolCube = std::pow((max - min), 3);

    std::uniform_real_distribution<> uniform_real(min, max);
    std::mt19937 rng_mt;
    auto ran_pos = std::bind(uniform_real, rng_mt);

    for(int i = 0; i < n_points; i++)
    {
        //generate random point
        double x = ran_pos();
        double y = ran_pos();
        double z = ran_pos();
        if(InsideUnitSphere(x, y, z)) count++;
    }

    return (double)count / n_points * VolCube;
}

#### Part 3.
- Having a program that only integrates one function (in our case, the volume of a unit sphere) is not terribly useful! Next we modify `IntegrateMonteCarlo3D` to accept callable `TestPoint` function (e.g. a function pointer or lambda-expression) so that the Monte Carlo integrator can be used to integrate arbitrary volumes / functions.
- We need to take a look at the documentation for [std::function](https://en.cppreference.com/w/cpp/utility/functional/function)
- We can declare objects of the type `std::function<...>`, and these can also be function parameters
- The angle brackets `<>` contain the return type and parameter types of the function. First the return type, then the parameter type in brackets: <return_type(param_type1, param_type2 ...)>
- e.g. a function which takes two `int`s and return an `int` could have the type: `std::function<int(int,int)>`.
- Add a parameter to the `IntegrateMonteCarlo3D` definition so that it can take an `std::function` which takes 3 integers and returns a boolean.
- Replace `InsideUnitSphere` with a call to this code instead.
- In `main`, you will need to change how you call `IntegrateMonteCarlo3D`. Try first by passing it a pointer to `InsideUnitSphere`. Re-compile and run your code to check that it still works as before.
- You can now pass your integrator any function which checks if a point is inside some 3D volume or set!

#### Solution:

`std::function` is essentially a wrapper for callable objects in C++ (e.g. functions, lambda expressions, certain classes), which we need to supply with return and parameter types. Any callabale object for which the `()` operator is overloaded to accept / return these types can be passed in. We can pass our function as a function pointer using the `&` operator (see ln 28).

double IntegrateMonteCarlo3D(int n_points, double min, double max, std::function<bool(double, double, double)> TestPoint)
{
    int count = 0;
    double VolCube = std::pow((max - min), 3);

    std::uniform_real_distribution<double> uniform_real(min, max);
    std::mt19937_64 mt64;
    auto ran_pos = std::bind(uniform_real, mt64);

    for(int i = 0; i < n_points; i++)
    {
        //generate random point
        double x = ran_pos();
        double y = ran_pos();
        double z = ran_pos();
        if(TestPoint(x, y, z)) count++;
    }

    return (double)count / n_points * VolCube;
}



int main()
{
    int N_points = 10000;
    
    double UnitSphereVol = IntegrateMonteCarlo3D(N_points, -1.0, 1.0, &InsideUnitSphere);

    std::cout << "Volume estimate of sphere using " << N_points << " points = " << UnitSphereVol << std::endl;
}

#### Optional Extension (if there's time)

- Add some code to allow a user to determine the number of points that are generated to do the integration without having to recompile the code. You can either use command line arguments or use `std::cin` to read a number in from the terminal at runtime. Use this information to set `N_points`.
- Monte Carlo Integration is most useful for integrating in large dimensional spaces where linear sampling methods become inefficient. Generalise your `IntegrateMonteCarlo3D` to an arbitrary n-dimensional case (the number of dimensions should be a argument for `IntegrateMonteCarloND`).

To use `cin` to get the number of points from the user:

int main()
{
    int N_points;
    std::cout << "Enter the number of points to sample (default 1000): ";
    std::cin >> N_points;
    if(N_points == 0) N_points = 1000;

    double UnitSphereVol = IntegrateMonteCarlo3D(N_points, -1.0, 1.0, &InsideUnitSphere);

    std::cout << "Volume estimate of sphere using " << N_points << " points = " << UnitSphereVol << std::endl;
}

We can generalise to n-dimensions by using a `std::vector` to represent our point rather than three explicit variables. For example:

#include <iostream>
#include <random>
#include <functional>

bool InsideUnitSphere(double x, double y, double z)
{
    return ((x*x + y*y + z*z) <= 1);
}

bool InsideNSphere(std::vector<double> point)
{
    double inner_prod = 0;
    for(const auto &x : point)
    {
        inner_prod += (x*x);
    }
    return (inner_prod <= 1.0);
}

double IntegrateMonteCarloND(int n_points, int num_dim, double min, double max, std::function<bool(std::vector<double>)> TestPoint)
{
    int count = 0;
    double VolSpace = std::pow((max - min), num_dim);

    std::uniform_real_distribution<double> uniform_real(min, max);
    std::mt19937_64 mt64;
    auto ran_pos = std::bind(uniform_real, mt64);

    std::vector<double> point(num_dim);
    for(int i = 0; i < n_points; i++)
    {
        //generate random point
        for(auto &x : point)
        {
            x = ran_pos();
        }
        if(TestPoint(point)) count++;
    }

    return (double)count / n_points * VolSpace;
}



int main()
{
    int N_points;
    std::cout << "Enter the number of points to sample (default 1000): ";
    std::cin >> N_points;
    if(N_points == 0) N_points = 1000;

    double circleArea = IntegrateMonteCarloND(N_points, 2, -1.0, 1.0, &InsideNSphere);
    double sphereVolume = IntegrateMonteCarloND(N_points, 3, -1.0, 1.0, &InsideNSphere);

    std::cout << "Area estimate of unit circle using " << N_points << " points = " << circleArea << std::endl;
    std::cout << "Area estimate of unit sphere using " << N_points << " points = " << sphereVolume << std::endl;
}

To demonstrate this we've used the same function to calculate the area of a circle and the volume of a sphere, just by changing the number of dimensions that we ask for! In order to make this code safer though, we should be sure that the function that we pass to the integrator requires a vector of the same size as the number of dimensions, which isn't guaranteed by static analysis in this example (although it is true for the function that we have passed). Once we've looked at _templates_ next week, we'll actually be able to do better than this!

----------------------------------------------------------------

## Section 3: Classes

### Exercise 1:

We're now going to move into the `Fractions` folder.

cd Fractions

We'll keep our terminal in this folder for the remainder of the exercise, so you'll build and run your program and tests from here.

#### Part 1

In the files `Fraction.h` (in `include`) and `Fraction.cpp` (in `src`), write a class called `Fraction` to model a fraction (i.e. rational number). It should be able to be constructed by passing the numerator and denominator to the constructor.
- It should implement the following (public) functions:
- `Fraction(int a, int b)`
- Constructor for fraction $\frac{a}{b}$
- `Fraction reciprocal()`
- Returns a new fraction which is the reciprocal of the current fraction e.g. the reciprocal of $\frac{2}{3}$ is $\frac{3}{2}$.
- `Fraction multiply(int a)`
- Returns a new fraction which is the current fraction multiplied by an integer.
- `double toDouble()`
- Calculates the value of the fraction as a double
- `std::string toString()`
- Generate a string to represent the fraction
- If the numerator is `0` then the string should be `"0"` regardless of the denominator.
- Otherwise should be in the form `"a/b"`. For example, a `Fraction` representing $\frac{1}{2}$ should return the string `"1/2"`.
- It should preseve the following **invariant**: the fraction should always been in its simplest form. E.g. $\frac{2}{4}$ should be automatically simplified to $\frac{1}{2}$.
- Fractions should be constructed in their simplified form, and **no operation on the `Fraction` object should result in a `Fraction` which is not simplified.**
- You can simplify a fraction by dividing the numerator and denominator by their greatest common divisor. You should implement a class method to simplify a `Fraction`.
- What access specifiers should you use for your data? When do you need to use your simplify method to ensure that your invariant is not violated?

**HINT**: If you are not sure of the `class` syntax, or how to structure a class in `.cpp` and `.h` files, you can look in the `exampleClass` folder. This contains the code for a class representing a sphere called `Sphere`. Note that the class declaration is in the header (.h) file (`Sphere.h` in `include`), and the definition of member functions in the source (.cpp) file (`Sphere.cpp` in `src`). Your code should separate your class declaration and implementation in the same way.

#### Part 2

We've provided some pre-written functions in `FractionChecker.cpp`, which will check your code.
- Compile your code using:

g++ -o build/FractionChecker src/Fraction.cpp src/FractionChecker.cpp -Iinclude

- Run the tests using:

./build/FractionChecker

- If there are problems with any of the checks, you should find out why and fix your code!

#### Solution:

A fraction consists of two pieces of information: a numerator and a denominator. So all we need to do to represent a fraction as data in a class is to store two integers, one to represent the numerator and one to represent the denominator (and be able to know which is which!). We can then implement our member functions by making use of these internal variables.

`Fraction.h`

#pragma once
#include <string>

class Fraction
{
    public:
    Fraction(int a, int b);

    Fraction multiply(int a) const;

    std::string toString() const;

    double toDouble(); const

    Fraction reciprocal();

    private:
    
    void simplify();
    
    int numerator;
    int denominator;
};

- The numerator and denominator are **private** to prevent users from interfering with them an violating the invariant.
- The `simplify` function is private because a user should never need to call it explicitly: the fraction should always be in its simplified state when a user has access to it.
- You can use `const` to mark `multiply`, `toString`, and `toDouble` as not changing the properties of the object.
- You may also want to add a `get` and `set` functionality for your numerator and denominator.

`Fraction.cpp`

#include "Fraction.h"
#include "FractionException.h"
#include <string>

Fraction::Fraction(int a, int b) : numerator(a), denominator(b)
{
    simplify();
}

Fraction::simplify()
{
    int gcd;
    int n = numerator;
    int d = denominator;
    while(d != 0)
    {
        if(n > d)
        {
            n = n - d;
        }
        else
        {
            d = d - n;
        }
    }
    
    numerator = numerator / n;
    denominator = denominator / n;
}

std::string Fraction::toString() const
{
    return numerator == 0 ? "0" : std::to_string(numerator) + "/" + std::to_string(denominator);
}

double Fraction::toDouble() const
{
    return (double) numerator / denominator;
}

Fraction Fraction::reciprocal()
{
    return Fraction(denominator, numerator);
}

Fraction Fraction::multiply(int a) const
{
    return Fraction(a*numerator, denominator);
}

- `simplify` is must be applied at the constructor, because any arguments could be applied.
- It does not need to be applied for `toString` or `toDouble` because these do not change the properties of the fraction.
- It does not need to be applied to `reciprocal`, since the reciprocal of a simplified fraction is also a simplified fraction.
- It does not need to be applied for `multiply` since it is implicitly called in the constructor for the new `Fraction` object.
- If you add a `set` funcion for the numerator or denominator, then you will need to call `simplify` inside that function to maintain the invariant.

---------------------------------------

## Section 3: Smart Pointers

In this section we will explore some of the properties of smart pointers. We recommend that you work in pairs or small groups so that you can discuss the ideas raised in this section with one another.

### Exercise 4:

In this exercise we'll explore how smart pointers work, and why they are useful. We'll be contrasting them with _raw pointers_ to illustrate their differences, but remember that we only want to use raw pointers when we need performant, non-owning pointers in safe contexts.

#### Part 1:
- Quiz!

#### Part 2:
- Open the `smart_pointers.cpp` file.
- For the sake of making things a bit easier see / modify all at once, we're going to have a class definition and `main` in one file. Don't do this in a typical project, it's just to save you some back-and-forth on this miniature application!
- We've provided a simple class called `Reporter`, which prints to the screen when the constructor and destructor are called. This kind of class can be very useful when trying to understand how objects are managed in C++.
- The **constructor** is called when an object (an _instance_ of that class) is created.
- The **destructor** is called when the object goes out of scope. The destructor has the responsibility of cleaning up any memory that isn't automatically freed, e.g. data allocated with `new` or `malloc`.
- Declare two different instances of this class on the heap (i.e. as pointers): one as a _raw pointer_ using (`Reporter *` and `new`), and another as a _unique pointer_. Compile and run your code.
- The `Reporter` constructor takes a string argument which is an identifier. Give each object a unique identifier so you can tell from the output when each one is being created and destroyed.
- Look at your output: what difference is there between your raw pointer and your smart pointer?
- If an object is created (the constructor is called) but not destroyed (destructor is not called) then you have created a memory leak! Memory continues to be occupied by this object until your program terminates (at which point all the memory allocated to that program is released).
- Memory leaks which happen throughout a program can build up and cause you to run out of memory, especially when running large scale computations that run for long periods of time. Programs run on clusters can run for days, weeks, or more, so even small memory leaks can be a big problem if they accumulate.

#### Solution:

int main()
{
    Reporter *raw_ptr = new Reporter("Raw");
    std::unique_ptr<Reporter> smart_ptr = std::make_unique<Reporter>("Unique");

    return 0;
}

will produce output:

$ ./build/smart_pointers 
Creating Reporter Object with ID: Raw
Creating Reporter Object with ID: Unique
Destroying Reporter Object with ID: Unique

We can see that the object memory pointed to by the unique pointer is properly deallocated, but the memory pointed to by the raw pointer is not as no destructor is called for that object. This means we have created a memory leak.

#### Part 3: Aggregation in Class Design

Open the `University` example. This contains two classes:
- `Student` represents a student. Each student has a name (which must be passed to the constructor), and a unique ID.
- `Department` represents a department. Each department has a name (which must be passed to the constructor).

We want to extend this code to represent the following:
- A student may have a department, or may have none.
- A student should be able to change department.
- A department should have a list of students, which may be empty.
- A `Student` object should not copy a `Department`, because this is both wasteful and means that the departmental information may not be up to date. The `Department` should not copy the `Student` data either for the same reasons.
- Multiple students will need to point to the same department.

These considerations lead us to add a pointer type member variable to both `Student` and `Department`.

- Add some kind of pointer to `Department` into the `Student` class, and a setter to set this variable.
- Add a `vector` (or `map`) of a kind of pointer to `Student` to your `Department` class, and a function which adds a student to a department's list. (A department will need to be able to have pointers to many students!)
- Fill in the main so that you can create at least one student and one department. Assign that department to the student and add the student to the department using your settings so that both objects have a pointer to the other.

You can compile with:

g++ -o build/University_example src/University_Main.cpp src/University_Types.cpp -Iinclude

Compile and run your code, and look at the output to check that destructors are being called properly for both of your objects (no memory leaks).

When choosing your pointer types consider:
- What happens when two objects both refer to one another?
- Should either object own the other?
- How will the memory be freed?

If you have time, try to modify your code so that students can be deregistered from a department. (i.e. the pointer to the student is removed from the list of students held by the department.)
- Add a deregister function to your `Department` class
- If you are using a `map` to represent your list of students you can give your student a unique I.D. using a _static class variable_.
- `map` has a useful function [`find`](https://cplusplus.com/reference/map/map/find/) which returns the _iterator_ that matches a given key.
- `map` and `vector` both have an [`erase`](https://cplusplus.com/reference/map/map/erase/) function which takes an iterator and removes that element.
- Any time a `Student` object is destroyed, that `Student` should be deregistered from their department.
- They should also be deregistered from their old department when they are assigned a new one.
- You **must** check that any potentially null pointers are valid before you access them!

#### Solution:

We have the following considerations:
1. We should avoid memory leaks due to circular references. This means we can't use shared pointers for both classes.
2. It doesn't make much sense for instances of either class to own the other. They only need to refer to one another, but their lifetimes are essentially independent.
3. Pointers may be invalidated if one a `Student` or `Department` instance is destroyed and other objects are pointing to it.

The best solution is this case is probably _weak pointers_.

University.h:

#include <memory>
#include <map>
#include <string>

using namespace std;

class Department;

class Student
{
    public:
    Student(const std::string &n);

    ~Student();

    void setDepartment(const shared_ptr<Department> new_dept);

    int getId() const;

    private:
    // Static variable means same value shared by every object in class
    // This allows us to create a unique id for each student by increasing
    // each time
    static int max_id;
    
    string name;
    int id;
    weak_ptr<Department> department;
};

class Department
{
    public:
    Department(const std::string &n);

    ~Department();

    void deregisterStudent(const int id);

    void addStudent(const shared_ptr<Student> new_student);

    private:
    string name;
    map<int, weak_ptr<Student>> students;
};

University.cpp:

#include <memory>
#include <iostream>
#include <string>
#include <map>
#include "departments.h"

using namespace std;

Student::Student(const std::string &n) : name(n), id(max_id++) {}

Student::~Student()
{
    if (!department.expired())
    {
        department.lock()->deregisterStudent(id);
    }
    cout << "Student " << name << " destroyed." << endl;
}

void Student::setDepartment(const shared_ptr<Department> new_dept)
{
    if (!department.expired())
    {
        department.lock()->deregisterStudent(id);
    }
    department = new_dept;
}

int Student::getId() const
{
    return id;
}

int Student::max_id = 0;

Department::Department(const std::string &n) : name(n) {}

Department::~Department()
{
    cout << "Department " << name << " destroyed." << endl;
}

void Department::deregisterStudent(const int id)
{
    //In C++17 onwards we can define a variable inside an "if" condition!
    //This variable is usable inside the code block of the if statement.
    if(auto it = students.find(id); it != students.end())
    {
        students.erase(it);
    }
}

void Department::addStudent(const shared_ptr<Student> new_student)
{
    students[new_student->getId()] = new_student;
}

int main()
{
    shared_ptr<Department> physics = make_shared<Department>("Physics and Astronomy");
    shared_ptr<Department> maths = make_shared<Department>("Mathematics and Statistics");

    shared_ptr<Student> Alice = make_shared<Student>("Alice");
    shared_ptr<Student> Bob = make_shared<Student>("Bob");

    Alice->setDepartment(physics);
    physics->addStudent(Alice);

    return 0;
}

- Weak pointers have an advantage over raw pointers in this case because it makes it easier to check if one of our objects has been destroyed while the other is still pointing to it! This can be an important safety feature in cases like this where we have no guarantee that the object pointed to will be alive for the duration of the pointer's use.
- Weak pointers mean that we have to create our objects as shared pointers. We can't use this solution with ordinary instances declared on the stack.
- To do this with stack variables we'd need to use raw pointers, but then we'd need to be more careful to ensure that we can't end up accessing invalid memory.
- We can mitigate this concern to some extent by using a process like the deregistration. In this case whenever a `Student` that is affiliated with a department is destroyed the department's pointer to that student is discarded. Note that we haven't done anything yet to enforce the same relationship the other way around!

-----------

#### Part 4: Functions with Unique Pointers
- What will happen if we write a function which takes a `unique_ptr`:
- Passing by value?
- Passing by reference?
- What happens if we try to `return` a `unique_ptr`?
- Hint: look a the notes on `return` statements in Passing by Reference and by Value.

#### Solution:

A simple function which takes a unique pointer by value could be:

void takeUniquePointer(std::unique_ptr<int> p)
{
    if(p) std::cout << "Pointer contains: " << *p << std::endl;
}
    
int main()
{
    std::unique_ptr<int> p = std::make_unique<int>(18);
    takeUniquePointer(p);

    return 0;
}

Because this is taken by value we will get the following error:

error: use of deleted function ‘std::unique_ptr<_Tp, _Dp>::unique_ptr(const std::unique_ptr<_Tp, _Dp>&) [with _Tp = int; _Dp = std::default_delete<int>]’
   48 |     takeUniquePointer(p);

This somewhat esoteric message is telling us that the copy constructor for a unique pointer doesn't exist. This is because unique pointers can't be copied, and therefore this code cannot be compiled.

To pass by reference we can modify the function:

void takeUniquePointer(std::unique_ptr<int> &p)
{
    if(p) std::cout << "Pointer contains: " << *p << std::endl;
}

If we pass by reference it will compile fine (since no copy is made) and will just print out the value pointed to by the pointer.

Returning unique pointers is a bit different:

std::unique_ptr<int> returnUniquePointer(int x)
{
    std::unique_ptr<int> p = std::make_unique<int>(x);
    return p;
}

int main()
{
    std::unique_ptr<int> p = returnUniquePointer(12);
    std::cout << *p << std::endl;

    return 0;
}

This compiles fine and prints out the correct value.
The reason this works is because we don't have to copy a unique pointer in order to _return_ it. This is because the compiler knows that the original unique pointer will be immediately destroyed so there's no risk of two unique pointers existing which can be used to access the same data. In this case, the data is simply _moved_ to the new owner (using the _move constructor_). This is the same thing that happens when we use `std::move`. C++ will always use the move constructor for a return if it is available, and use the copy constructor otherwise.

#### Part 5: Writing a Binary Tree Class using Pointers

- Consider the case of a binary tree; this is a kind of graph data structure where nodes contain data, two pointers to "child" nodes (left and right), and a pointer to a parent node:
- If the pointer is null then that child is called a "leaf", i.e. this contains no data.
- If the pointer is not null then it points to another node.
- If the parent pointer is null then that node is the root of a tree.
- What kind of pointers should you use in this example? Should you use different kinds of pointers to point to children and parents? How do we ensure memory safety?
- When a node is deleted, the entire sub-tree beneath that node should be deleted (children, children of children etc.) since they are no longer accessible. Deleting the root node then means that the entire tree is deleted.
- Consider whether there are circular references in this data structure and how that impacts your memory management.
- What is the most appropriate model of ownership?
- Are there any performance considerations for large trees? Consider traversing the tree from top down and from bottom up.
- What pointers would you use if two nodes could point to the same child (i.e. two trees can share a sub-tree) but there are no pointers from child to parent?

#### Solution:

There are two main approaches that you can take to this problem.

1. Use **Shared Pointers** to point to child nodes and **Weak Pointers** to point to parent nodes.
2. Use **Unique Pointers** to point to child nodes and **Raw Pointers** to point to parent nodes.

Given that each child is uniquely owned by its parent, and should go out of scope when the parent goes out of scope, a _unique pointer_ most closely models our ownership. The raw pointer to the parent is safe, because we know that the data will always still be valid: if the child exists, then the parent must also exist (since the parent owns the child data, when the parent is destroyed, the child is destroyed too).

Some other points to consider:
- Circular references: if we use shared pointers to point to children, we will need to use weak pointers to point to the parent in order to avoid circular references of shared pointers, which as we've seen above would cause memory leaks.
- Performance: Traversing trees downwards would involve looking through sequences of pointers to child nodes, which is very fast for unique or shared pointers. Traversing a tree upwards -- looking at parent nodes -- will be more efficient if using raw pointers than weak pointers.
- Sharing sub-trees: If we modified our model to share sub-trees then we would need to use shared pointers for children.

#### Part 6: Move Semantics

Using move semantics can be unsafe if it's not handled properly. Consider a case where have two variables `T x` and `T y` for some type `T`, and initialise `x` as `T x(std::move(y))`.

// declare y 
T y = ...
    
...
    
//initialise x using move constructor to move contents of y into x
T x(std::move(y));

(This is sometimes used in contructors or setters so that an object can take over some resources which were allocated by something else.)

Use the documentation at [cppreference](https://en.cppreference.com/w/) to determine what will happen to `y` (the object whose data has been moved) if the type `T` is:
- a `shared_ptr` or `unique_ptr`
- a `std::string`
- a `vector` or `map`
- an `array` (this one is a little trickier than the others, don't worry if you don't get this one)

You can look for _move constructors_ by looking up the class in the documentation, and then clicking on the constructor definition. Most of the classes will have multiple constructors defined, so underneath the function signatures are a numbered list of explanations: look for the move constructor there. You might also want to try writing some code that uses the move constructor and inspecting what happens.

#### Solution:

1. Shared / unique pointers are left as null pointers after having their data moved.
2. A string is left in a _valid but unspecified_ state after having its data moved. This is often the empty string, but there are no guarantees!
3. A vector or map will be empty after having its data moved.
4. An array will still have the same number of elements after its data is moved. Its data is moved element by element, i.e. `std::move` is applied to each element in the array. What values are left in each element of the array after the move will depend on the type of the elements of the array.