Seminars

There are no seminars after week 8. Use the extra time for example for projects of finishing of homework.

8th Week – Python Bindings & Lua Interpreter

Download the zip file exercise08.zip.

This task consists of two independent parts. In the first one, you will create Python bindings for a simple graph library written in C++. In the second part you will implement game of life in such a way, that the user interface and core of the game is implemented in C++, but the app is scriptable via Lua.

Do not get scared, there is not much code you have to write.

Python Bindings

In this part of the exercise you will try to implement Python bindings for a really simple graph library. This whole exercise is located in the python-bindings directory.

You can find the library in the file graph.hpp. The graph is represented by an adjacency list in each vector. The Node class is parametrized by the type of data associated with nodes and edges. The Graph class provides a method for adding new vertices and it allows to walk the graph in DFS manner. When a vertex is visited or left, a user provided callback is called.

The demo is compiled using CMake. Simply run the following command to compile it:

mkdir -p build
cd build
cmake ..
make -j8

Note that the cmake .. might take a while to complete since the pybind11 dependency is downloaded (and FetchContent doesn’t show progress bar).

To execute the Python demo, just run:

PYTHONPATH=path_to_your_build_directory python3 example.py

The goal is to basically make example.py executable by implementing python bindings for the library.

First, create Python classes PlainGraph and PlainNode mapping to Graph< std::string, Nothing > and Graph< std::string, Nothing >::NodeT respectively. The user should be able to create a graph, add nodes and add neighbors. Also, they should be able to walk the graph by supplying arbitrary Python functions as callbacks.

Second, try to implement the Python classes Graph and Node. These should represent a graph where vertex and edge data can be arbitrary Python values.

Some tips

when in doubt, look at the pybind11 documentation
if your Python module segfaults or causes double free, look for improper usage of py::return_value_policy (the automatic one does not fit everywhere)

Game of Life with Lua

Your goal for this exercise is to practice writing Lua bindings in C++. You will create a working Game of Life that uses Lua scripts for the definition of the initial state of the game and for controlling the game itself. This game is quite simple – just read the wiki: https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life You only have to implement the Lua bindings. GUI and game mechanics are implemented.

You should install the SDL2 GUI library, the project itself is a standard CMake project.

Note: If you get linker errors with undefined references to SDL functions, try changing the target_link_libraries line as suggested in the comment in the CMakeLists.txt. (The problem seems to be version- or platform-dependent.)

Execute the game as:

./game_of_life test.lua

Existing code

window.hpp contains cell_state and game_window types. cell_state is an enum that represents the state the cells can be in - ALIVE or DEAD. game_window is a GUI that you will use for visualization of the game. This window can initialize itself and provides you with game_window::cell_matrix type. You should use the cell_matrix type as storage for the actual state of the game. If you want to visualize the cell_matrix just use method form the GUI window: game_window::draw_cell_matrix.

main.cpp contains two functions that represent the mechanics of the game. liveness counts living cells around a specific cell in the matrix. gol_iterate executes one iteration of GoL over the provided matrix and returns a new matrix.

The idea is to iteratively update the game state and draw it.

What you should implement

You have a GUI window to visualize the game and functions for game mechanics. You have to fill in the lua bindings.

The file test.lua is a simple example file that initializes the basic GoL game and executes it. The binding expects that there is only one cell-matrix in the app. For the Lua script, we only use numbers for setting the cell state – 1 means alive, 0 means dead.

Your list of tasks for the bindings is to introduce the following items into the Lua context; these are used by the script provided in this exercise: * variables width and height: the actual dimensions of cell-matrix (The API uses the term global for variables that are accessible from the top level of Lua scripts.) * function set: takes three arguments as input – x and y coordinates and state of cell – and sets the state of the cell at the internal matrix at the coordinates * function get: takes two arguments as input – x and y, returns the state of the cell in the internal matrix * function gol_iterate: executes one iteration of GoL over the internal matrix * function draw: draws the actual state of the cell-matrix in the GUI window * function sleep: allows the app to sleep for 100ms (tip: SDL_Delay)

You should also implement the part of the code that loads the file provided as an argument to the binary and executes it. The simple implementation uses global variables, you have more instructions for avoiding them in the sources zip file.

And one last thing: share your custom Lua scripts!

Solution

The solutions are available.

7th Week – Threading

Threads in GDB quick guide

info threads – show running threads of the process
thread n – select thread n for inspection
set scheduler-locking {on|off} – fix scheduler to the current thread (allow scheduling of all threads)

Parallel queue

Your task this week is to implement a simple thread-safe queue and in doing so get familiar with the basic synchronization primitives from the C++ standard library.

Basic task

Implement class Queue< T > as thread-safe wrapper for std::deque using mutexes and condition variables. It should support following operations:

bool empty() const checks if the queue has no elements.
void push( const T& ) appends the element to the end of the queue.
template< C > void push( const C& ) appends elements from the container to the end of the queue without interruption from other threads. Order of the elements in the queue has to be the same as the order of elements in the container. Assume the container supports forward_iterator (e.g. std::vector ).
void push( std::initializer_list< T > ) the same as above, only for initializer list.
T pop() pops an element from the front of the queue if the queue is not empty, otherwise suspends caller until an element is inserted. If multiple threads are suspended using a conditional variable, only one of them will pop the newly inserted element. You do not have to deal with the situation when there is pending pop during queue destruction.
std::optional< T > try_pop() pops an element if the queue is not empty, otherwise returns std::nullopt.
void clear() clears all the elements from the queue.

Write also a simple multi-threaded program which tests the capabilities of your queue (multiple readers/writers). Before you start, it might be useful to read the relevant parts of cppreference.

Bonus task

When using blocking operations (such as pop) it is often useful to be able to interrupt blocked threads. Add a support for queue shutdown:

void shutdown() – if invoked all pops and try_pops will work normally until the queue is empty. If pop is running on an empty queue after shutdown was invoked (possibly from other thread while the pop was already running) pop will throw an appropriate exception. If shutdown is already running does nothing.
bool shutting_down() – returns true if shutting is running, otherwise returns false.
void cancel_shutdown() – restores pre-shutdown conditions – further pop on an empty queue will block again. If shutdown is not running does nothing.
void kill() – all running or future pop/try_pop operations will end with an exception, regardless of number of elements in the queue. This condition cannot be reset.

Please note that the notion of “future” is somewhat vague in parallel programming. E.g. it is admissible that a pop which is executed in parallel with kill will return a value if the queue is not empty and it is also admissible it will throw an exception. It is, however, not admissible it will block.

Solution

The solution is available.

6th Week

There are two tasks for this week both of them concerning templates and possibly concepts:

a pretty-printer library for printing nested data;
code for deriving operator + from operator += (in the same spirit as used for operator != and operator == in the lecture.

Both of these can make use of concepts, but can be also solved without them. Concept-based solution will probably be shorter and easier to read. If you decide to use concepts, it would be a good idea to refresh your knowledge of requires expressions and on Lecture 2.

Furthermore, you are encouraged to read lecture codes and ask if anything is not clear to you.

Pretty Printer

Write an overloaded function (e.g. format) which is capable of pretty-printing values of different types. It is best to use helper class (e.g. Formatter which has overload member function format and serializes the output to std::stringstream. This class can then be used in format). The advantage of this approach is that member functions can be mutually recursive without needing declarations before use.

Arithmetic types (std::is_arithmetic) should be printed using operator<<.
string operands should be printed in quotation marks (yes, string escaping would be needed for this to work right, but we will omit it).
Containers should be printed in form "[ a0, a1, … ]" (for sequential containers such as vector and deque) or "{ a0, a1, … }" for set-like/mapping containers (set, unordered_set, map, unordered_map). a0, a1, … are results of recursive application of format to respective elements of the container.
- To do this, you can write a helper trait of form
```
template< typename T >
struct IsContainer {
    static constexpr bool is_container = false;
};

template< typename T >
struct IsContainer< std::vector< T > > {
    static constexpr bool is_container = true;
    static constexpr char left_bracket = '[';
    static constexpr char right_bracket = ']';
};
```
  which for (common) containers defines is_container to true and left_bracket and right_bracket to apropriate brackets and for ther types defines is_container to false. Use template specialization for common containers to implement this trait.
- Alternatively, you can define concepts e.g., sequential_container and set_like_container, that detect containers of given kind based on their member functions and/or nested types (hint: containers can be used with begin/end and set-like containers all have key_type)
- Alternatively, as an advanced option, you can use the old ways and detect properties of containers using SFINAE/decltype.
Pairs and tuples should be printed in the form "( fisrtElem, secondElem, … )" where fisrtElem, secondElem are result of recursive aplication of format to elements of the tuple/pair. For printing tuples you will need to extract elements of the tuple somehow, one possibility is using std::apply with an object which defines variadic operator() into which the elements are unwrapped (you can use fold expression, or recursion for the actual printing of these elements).
Compile-time conditions (if constexpr) might be also useful in this exercise. You can use concepts and traits in if constexpr.

Example:

format( 42 ) ⇝ "42"

format( std::pair( 1, "hi" ) ) ⇝ "(1, \"hi\")"

format( std::set{ 1, 2, 3 } ) ⇝ "{ 1, 2, 3 }"

format( std::vector{ 1, 2, 3 } ) ⇝ "[ 1, 2, 3 ]"

format( std::vector< std::set< std::pair< int, std::string > > >
        { { { 1, "ahoj" } }, { { 2, "" }, { 3, "bla" } } } )
    ⇝ "[ { (1, \"ahoj\") }, { (2, \"\"), (3, \"bla\") } ]"

Auto-Deriving `operator +`

Download the zip file exercise06.zip. It contains implementation of Eq and Ord SFINAE helpers as shown in the lecture as well as concept-based alternatives.

Implement Addition helper which provides implementation of operator+ based on operator += implemented in the class. Your operator + should be able to not copy any of the input arguments if the first argument is rvalue. (In general we cannot assume comutativity of +, see e.g. std::string).
Bonus: extend the tag Addition in some way to allow the programmer to indicate that operator + is comutative and handle both cases of rvalues in this case.
Hint: you can use overloads, or if constexpr. std::remove_reference and std::is_lvalue_reference can be useful in some cases.

Solutions

The solution is available.

5th Week

Download the zip file exercise05.zip. As there are no dependencies this week, we do not provide CMake build file.

Exceptions

Create a class which reports use of constructors/destructors.
Use it in functions which throw exception and in functions through which exceptions propagate and observe the results.
Observe what happens if an exception is not caught.
Observe what happens if the program is killed or ends using exit.

Double-Dispatch

In ast.h you are provided with basic interface of part of AST (abstrax syntax tree) implementation which represents nodes for constants and binary operators. Once expression over such nodes is created (see ast.cpp for example) many operations can be done with it, for example it can be printed, or it can evaluated.

Your task is to create printer and evaluator which walk through the AST and perform given operation, try to use different techniques:

visitor pattern,
detecting type of node using dynamic_cast,
anything else you can think of (you can modify the way the AST is created).

Solution

The solution is available:

ast-solution.h contains a basic solution using visitor pattern;
ast-solution-dcast.h contains a solution using dynamic cast;
ast-solution+crtp.h contains the visitor pattern extended with helper classes to avoid some repetitive code using CRTP, which will be explained later in the course;
ast-solution-variant.h contains a solution with std::variant and without an OOP hierarchy – this solution needs the modified ast-variant.cpp.

4th Week

Download the zip file exercise04.zip. There are two exercises in this week, one on iterators and one or ranges. We recommend you do both of them, but they might be longer than two hours together. If you are not familiar with implementation of iterators, you should definitely do the iterators exercise.

Iterators

The first assignment is to write forward iterators for given implementation of block linked list (a linked list which allocates several items in each node to achieve better compromise between iteration speed and insertion speed).

We recommend first disabling the last test and getting iterators to work on the range-for test.
Our tests use RapidCheck which is a library for property testing – it allows us to define tests which get fed by random generated data.
- RapidCheck can also shrink input data for tests – when test fails, RapidCheck will try to run it again with smaller input instances.
- The CMake config file for this exercise will automatically pull RapidCheck and Catch2.
Our coverage target also collects coverage, it should report how many lines were covered.
- You can find more details in file BUILD_DIR/link_n_list.hpp.gcov. Lines prefixed with ##### are not covered, otherwise the number indicates how many times the line was executed; - indicates the line did not generate any code.
- The coverage generation requires gcov if compiled with GCC or llvm-cov for clang. Both Should be included if you have the appropriate compiler. The generation is tested on Linux.
You should provide both iterator and const_iterator, try to avoid code duplication.
- iterator should be convertible to const_iterator.

Ranges

For the ranges, you are given several smaller tasks to familiarize with the area. Currently, this task requires GCC 10, use the one on Aisa if you don’t have your own.

Since the documentation is not particularly easy to read, we give you some useful points here:

For views, you should prefer std::views::X to std::ranges::X_view (i.e., std::views::filter(…)).
Views without parameters are (sometimes templated) variables, they are not called like functions: foo | std::views::keys.
Since all views are actually objects, the documentation on how to call them is in the documentation for the appropriate constructor¹ (e.g., transform).
- Furthermore, the first argument (which is a view) is not explicitly passed to the view when using the pipe syntax.

Tasks

You will find outline for these tasks in the zip file for this exercise. You will also find a basic tests for them there. To simplify the examples, we write ranges and tuples into curly brackets and we write ranges of characters using the string literal notation even if they are not actually strings.

getLonger(range, length) – takes a range of sized ranges and returns a range of those sized ranges that are longer than given length.

getLonger({ "hi", "ahoj", "hello"}, 3) ⇝ { "ahoj", "hello" }
getLonger({ { 1, 2, 3 }, { 1 }, { } }, 2) ⇝ { { 1, 2, 3 } }

summarizePassing(range, limit) – takes a range of pairs (name, points) and a minimum needed to pass a course and produces a range of strings of form “name: points pts” for students that have at least limit points.
```
summarizePassing({ { "A", 42 }, { "B", 1 }, { "C", 25 } }, 25)
    ⇝ { "A: 42 pts", "C: 25 pts" }
```
Hint: you can use std::to_string to convert number to string.
everyNth( range, n ) – takes a range and a positive number and returns a range that contains every n-th element of the input range (starting with the first).
```
everyNth("hello", 2) ⇝ "hlo"
everyNth({ 0, 1, 2, 3, 4, 5, 6 }, 3) ⇝ { 0, 3, 6 }
```
diagSeq() – returns an infinite range that is result of concatenations of sequences [0], [0, 1], [0, 1, 2], …
```
diagSeq() | take(11) ⇝ { 0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0 }
```
diagSums() – returns an infinite range of sums of diagSeq(). I.e., the n-th element of the result contains sum of elements 0…n for diagSeq.
```
diagSums() | take(11) ⇝ { 0, 0, 1, 1, 2, 4, 4, 5, 7, 10, 10 }
```

Solutions

Commented solutions are available.

3rd Week

Download the zip file exercise03.zip.
Your goal is to implement static_vector, a vector-like data structure with a fixed maximal capacity that doesn’t use dynamic allocation of memory. To deal with uninitialized memory, you are going to need the following:
- Uninitialized memory can be obtained either as a character array of proper size and alignment, or using std::aligned_storage. See e.g. https://en.cppreference.com/w/cpp/types/aligned_storage#Possible_implementation.
- placement new: If ptr is a pointer to uninitialized memory, using new ( ptr ) T( /*params*/ ) creates a new object of type T in that memory.
- std::destroy_at( ptr ): Calls the destructor of the object pointed to by ptr without deallocating memory.
- std::destroy( begin, end ): Destroys all objects in the given range without deallocating memory.
- std::uninitialized_copy and std::uninitialized_move work like copy and move (the <algorithm> version), but with uninitialized target memory.
- When using reinterpret_cast, wrap it in a std::launder call to make sure that the compiler does not do any unwanted optimisations. (In certain cases, such as when the pointers have different types, the compiler is allowed to assume that two pointers never point to the same object. Since C++17, std::launder is a way of invalidating this assumption and preventing this kind of optimisations. You don’t need to fully understand std::launder to use it in this exercise.)
A few simple tests can be found in test_static_vector.cpp (link together with main.cpp).

Solutions

The solutions are available.

2nd Week – Concepts, C++17 Library additions

Download the zip file exercise02.zip. The zip contains source files and CMake build file. If you don’t want to use CMake you will need to get Catch2 manually.

`ArraySet` with Concepts

Your first task it to implement missing parts of an ArraySet – a data structure that stores a (sorted) set in an array. This data structure is well suited for cases when we want to check if an element is in a set much more often than insert a new one or in cases where the set size is small.

This task uses C++20 concepts. It is tested to work both in g++ 10 and clang 10, but if you have older GCC/clang it will not work. If you have MS Visual C++, it might work, but we have not tested it. If your compiler does not work with the concepts you need, please use GCC 10 on Aisa.

Your tasks is to fill-in blanks in the implementation – construction, search and insertion. Furthermore, you are expected to add use of concepts to the ArraySet. ArraySet should have one template argument: ArraySet<T> in a manner similar to std::set<T> (except we have dropped the allocator and comparator part). Unlike std::set, ArraySet should use concepts to check that its type argument is actually usable – it is a comparable type and it is also movable and move constructible (so it can be stored in a vector). We have not yet covered move semantics – for now it is sufficient to say that movable and move constructible are weaker constraints then copyable and copy constructible and therefore any object that can be copied can be also moved (just possibly not very efficiently).

All the places you should fill in are marked in the source code. We recommend you have a look at the <concepts> header.

There are some simple unit tests available for this task, you can run them by make arrayset-run-test if you use our CMake.

RPN Calculator with `std::variant` and `std::optional`

In this exercise we will create a modular calculator using the Reverse Polish notation (RPN). The RPN expressions contain numbers and operators in postfix form. We will be writing them into a brace-enclosed list, for example { 3, 2, "-" } represents a mathematical expression 3 − 2 and { 3, 2, "-", 4, "+" } represents (3 − 2) + 4. Please note that RPN does not need brackets.

In C++ we can represent RPN expressions using a vector of variants, where each variant can contain either a number or a string (long or std::string_view in our implementation.). To make the program more compact, we create a type alias for such a vector: rpn::program.

We want to create an evaluator for such expressions – rpn::calculator. Furthermore, we want this evaluator to be modular, i.e., to support addition of operations. To do so, we define a virtual base class rpn::base_op and derive various operations from it (see the source). These operations can be registered using rpn::calculator::register_op.

RPN calculation can be done using a stack – we go over the input program (left to right) and every time we see a number, we push it to the stack. Every time we see an operation, we perform it (removing its arguments from stack) and push it results to the stack. If an operation uses more than one argument, we need to apply the arguments in the right order – the argument on the top of the stack is the rightmost argument of the operation. Let’s have an example: we use program { 3, 2, "-", 4, "+" }:

push 3 to the stack: [3] (stack is in square brackets with top on the right)
push 2 to the stack: [3, 2]
apply − on the stack: 3 − 2 ≡ 1, so stack is now [1]
push 4 to the stack: [1, 4]
apply + on the stack: 1 + 4 ≡ 5, so stack is now [4]

The top (rightmost) element of the stack at the end of the computation is its result.

Your task is to implement the missing functionality in the rpn::calculator. The parts you should implement are marked with TODO. The source also specifies in comments what these parts should do. The rest of the file is also commented.

There are some simple unit tests available for this task, you can run them by make rpn-run-test if you use our CMake. You can also look at the tests for examples of use of our calculator.

Solutions

The solutions are available.

1st Week – CMake, Code analysis, Debugging

If you have not done it already, get your tools ready according to our instructions.
- This includes clang-tidy and the list of checks for it.
Download the zip file exercise01.zip.
Download catch.hpp from this link. Catch2 is a test framework that only needs one header file to work.

CMake Basics

Look at CMakeLists.txt in the aforementioned zip, particularly its usage part for now. This file it is a CMake build description for fixthis.cpp. Use CMake to build the fixthis target in a separate build dir. Then use CMake to build fixthis with an address sanitizer.

Code Analysis, Debugging

Look at fixthis.cpp and try fixing all the problems you can find. Use relevant tools such as clang-tidy, valgrind, and sanitizers.
- Compile without optimizations and with the -g (debug info) flag for best reports from sanitizers and valgrind. (When using cmake both of these conditions are ensured by using the CMAKE_BUILD_TYPE=Debug setting.)
- Do not use valgrind on programs compiled with sanitizers (it will eat all memory).
Look at the files problem{1..7}.cpp. Each of these files contains a specific error that can easily occur in C++ programs (cases 6 and 7 are simplified versions of errors from production code). Sometimes the error can be a crash, sometimes it can mean the program behaves differently than one would expect from the code (the intention can be also marked in the names of functions!).
- Use compiler, clang-tidy, debugger, valgrind or code inspection, or any other tool you fancy to uncover the error.
- You do not need to fix these errors, some of them cannot be fixed without a rewrite which is impossible for the abstracted cases presented here.
- Please note that problem7.cpp expects to be run in the directory where its source code resides.

Extra: Revision, More CMake

If you want more, or if you are not sure about your C++ skills, do also the following tasks.

Implement a doubly-linked list using the template given in linkedlist.h. Write your own test for this implementation using Catch2. Some tests are provided in linkedlist.cpp (but write your own first).
Write a CMake build file for the linked list exercise (or some other simple C++ program)
- use the CMakeLists.txt from the first task as a basis;
- use the CMake documentation if needed.

Solutions

The solutions are available. Each of the problem{1..7}.cpp codes has a corresponding solution file which comments the problem.

In fact, if you are calling the view using the std::view::X path, you are not calling a constructor directly, but instead calling it through a helper object.↩︎

Seminars

8th Week – Python Bindings & Lua Interpreter

Python Bindings

Some tips

Game of Life with Lua

Existing code

What you should implement

Share

Solution

7th Week – Threading

Threads in GDB quick guide

Parallel queue

Basic task

Bonus task

Solution

6th Week

Pretty Printer

Auto-Deriving operator +

Solutions

5th Week

Exceptions

Double-Dispatch

Solution

4th Week

Iterators

Ranges

Tasks

Solutions

3rd Week

Solutions

2nd Week – Concepts, C++17 Library additions

ArraySet with Concepts

RPN Calculator with std::variant and std::optional

Solutions

1st Week – CMake, Code analysis, Debugging

CMake Basics

Code Analysis, Debugging

Extra: Revision, More CMake

Solutions

Auto-Deriving `operator +`

`ArraySet` with Concepts

RPN Calculator with `std::variant` and `std::optional`