Über dieses Übungsblatt

Auf diesem Übungsblatt möchten wir uns weitere möglichkeiten Ansehen mehr Struktur in Code zu bringen. Als erstes schauen wir uns dazu das Decorator-Pattern am Beispiel von Streams an, das uns ermöglicht beliebig komplexe Klassen durch Verschachtelung zu generieren. Im zweiten Teil des Blattes schauen wir uns an, wie funktionale(re)r Code mittels C++ realisiert werden kann.

Aufgabe Stream-Wrapper

Letzte Änderung: 11. January 2021, 12:16 Uhr
20 Punkte — im Detail
Ansicht: |

Über diese Aufgabe

Auf den vergangenen Blättern wurde bereits mit std::cin, std::cout und Dateistreams gearbeitet. In dieser Aufgabe sehen wir uns an, wie man die Funktionalität dieser Objekte erweitern kann. Dazu definieren wir als erstes ein Interface (stream), das am Ende alle Klassen implementieren werden.
Da es leider nicht so einfach ist, C++-Streams objektorientiert direkt zu erweitern, geben wir für diese Aufgabe einen einfachen Wrapper (BasicStreamWrapper) für std::ostream vor. Nun, mit einer eigenen C++-Implementierung können wir eigene Klassen definieren, die davon ableiten: Wir implementieren drei sogenannte Dekoratoren, die das Verhalten des Streams im Gegensatz zum Wrapper auch tatsächlich verändern.

Interface:
Als Basis definieren wir die abstrakte Klasse stream, die das Interface eines Streams festlegt: Jeder Stream stellt eine Methode print bereit, mit der Daten in den Stream geschrieben werden können. Wohin die Daten dann tatsächlich geschrieben werden, ist durch dieses Interface noch nicht festgelegt (theoretisch darf ein Stream auch Daten wegwerfen).

class stream {
public:
    virtual void print(const std::string&) = 0;
    virtual ~stream() = default;
};

Wrapper für std::ostream:
Wir nutzen nun das Interface stream, um eine konkrete Implementierung eines Streams vorzugeben. Die unterhalb definierte Klasse basic_stream_wrapper gibt den übergebenen String auf einem C++-kompatiblen Output-Stream (etwa std::cout) aus und wrappt damit wie die Verwendung von C++-Streams. (Eine mögliche Verwendung wird weiter unten in einem Beispielcodeschnipsel vorgeführt).

basic_stream_wrapper.h

// .h
class basic_stream_wrapper : public stream {
private:
    std::ostream& stream;
public:
    explicit basic_stream_wrapper(std::ostream& s): stream(s) {};
    void print(const std::string&) override;
    ~basic_stream_wrapper() override = default;
};

basic_stream_wrapper.cpp

// .cpp
void basic_stream_wrapper::print(const std::string& string) {
    stream << string;
}

Dekoratoren: Wir können jetzt Modifikationen implementieren, die den auszugebenen String mit Zeilennummern versehen (count_decorator), ein Trennzeichen hinten anfügen (postfix_decorator) oder sogar den eigentlichen Inhalt des Strings überschreiben (caesar_decorator). Um solche Modifikatoren nach einem Baukasten-System zusammensetzen zu können, bedienen wir uns des Decorator-Patterns: Wir leiten für jede Modifikation einen weiteren Stream ab, der in seiner print-Methode die gewünschten Änderungen am String durchführt, dann aber das Ergebnis nicht sofort ausgibt, sondern an einen anderen Stream weitergibt. Der "Dekorator"-Stream hat also dasselbe Interface wie ein normaler Stream, verhält sich aber anders.

class stream_decorator : public stream {
protected:
    stream* stream;
public:
    explicit stream_decorator(Stream* s) : stream(s) {};
    ~stream_decorator() override = default;
};

Die Klasse stream_decorator ist unser Ausgangspunkt für diese Implementierung. stream_decorator leitet zwar von stream ab, überschreibt aber nicht die pure virtuelle Methode print und ist daher selbst eine abstrakte Klasse, kann also nicht instanziiert werden. Jeder stream_decorator führt einen Zeiger auf den Stream mit, auf den letztendlich geschrieben werden soll.

Beispielverwendung:

Wenn Sie alles implementiert haben, sollte das folgende Codebeispiel funktionieren:

#include <ostream>
#include <string>

// Ihre selbst definierten Header kommen hierher.

void do_something(Stream &stream) {
    stream.print("Hello World");
    stream.print("Second Line");
}

int main() {
    std::ostream& out = std::cout;

    basic_stream_wrapper cout(out);
    postfix_decorator postfix(&cout, ".\n");
    count_decorator count(&postfix);
    caesar_decorator caesar(&count, 7);
    do_something(count);
    do_something(caesar);
}

Die Ausgabe ist dann

[0] Hello World.
[1] Second Line.
[2] Olssv Dvysk.
[3] Zljvuk Spul.

Aufgaben

Wir implementierun nun drei spezialisierte Decorators, die von stream_decorator erben:
1. Implementieren Sie als erstes den Wrapper count_decorator, der vor jede Ausgabe eine automatisch inkrementierende Ausgabennummer anhängt.
```
class count_decorator : public stream_decorator {
    uint64_t counter;
public:
    explicit count_decorator(Stream* s, uint64_t initial_counter = 0);
    void print(const std::string&) override;
    ~count_decorator() override = default;
};
```
  Um Ihnen den Einstieg zu erleichtern, geben wir die Implementierung des Konstruktors von count_decorator vor. Die Syntax ... : stream_decorator(s) ... ruft den Konstruktor der Basisklasse stream_decorator mit dem gewrappten Stream auf.
```
count_decorator::count_decorator(stream *s, uint64_t initial_counter) : stream_decorator(s), counter(initial_counter) {}
```
2. Implementieren Sie einen postfix_decorator. Dieser soll einen vorher definierten String an jeden String anhängen, der print übergeben wird.
```
class postfix_decorator : public stream_decorator {
private:
    std::string postfix_string;
public:
    explicit postfix_decorator(stream* s, const std::string& postfix_string = "\n");;
    void print(const std::string&) override;
    ~postfix_decorator() override = default;
};
```
3. Implementieren Sie einen caesar_decorator. Ein caesar_decorator soll jeden String, der an print übergeben wird, nach dem Caesar-Chiffre verschlüsseln. Das Caesar-Chiffre ist eine sehr einfache Verschlüsselung, bei der alle Buchstaben einfach verschoben werden. Andere Zeichen bleiben unverändert. Die Zeichen der oberen Reihe werden in das jeweilige Zeichen der unteren Reihe übersetzt. Hier ein Beispiel für eine Verschiebung um 5 Buchstaben:
```
Klar:    a b c d e f g h i j k l m n o p q r s t u v w x y z
Geheim:  f g h i j k l m n o p q r s t u v w x y z a b c d e
```
  Die Buchstabenverschiebung wird Ihrer Klasse als Konstruktorparameter übergeben.
```
class caesar_decorator : public stream_decorator {
private:
    int32_t shift;
public:
    explicit caesar_decorator(stream* s, int32_t shift = 0);
    void print(const std::string&) override;
    ~caesar_decorator() override = default;
};
```
Finden Sie ein Beispiel für zwei Dekoratoren, bei denen die Reihenfolge, in der sie geschachtelt werden, eine Rolle spielt.
Da stream_decorator eine beliebige Klasse vom Typ stream erwartet können wir auch andere Basisobjekte vom Typ stream dekorieren ohne unseren Klassen vom Typ stream_decorator umschreiben zu müssen. Wir tun dies, indem wir eine Klasse stream_print_wrapper definieren, die statt einem std::ostream die Methode printf (Link zur Dokumentation) wrappt. Implementieren Sie also class stream_print_wrapper : public stream { ... } als zweite Basisklasse.
Zeichnen Sie ein UML-Diagramm, das die sechs hier vorgestellten Klassen in Beziehung setzt.

Aufgabe Higher-Order Functions

Letzte Änderung: 08. January 2021, 18:40 Uhr
20 Punkte — im Detail
Ansicht: |

Vom nächsten Aufgabenblatt an dürfen Sie lambdas und alle Higher-Order Funktionen aus std::numeric und std::algorithm verwenden. (Link zu std::algorithm)

In der Vorlesung haben wir das Konzept der funktionalen Programmierung kennen gelernt. Funktionszeiger sind eine Möglichkeit, Funktionen an andere Funktionen als Argument zu übergeben. In vielen Fällen ist es jedoch unnötig globale Funktionen zu definieren, die dann per Funktionszeiger an etwa nur einer Stelle eingebunden werden. An dieser Stelle kommen Lambda-Funktionen ins Spiel, die Sie eventuell bereits aus Python kennen.

Lambda-Funktionen in C++

In C++ sehen Lambda-Funktionen folgendermaßen aus:

    [](int a, int b) -> int {return a+b;}

Dabei bezeichnet [] die „Capture-List“, () die Argumentliste, der Teil nach -> den Rückgabetypen und {} umfasst den Funktionsrumpf.

Alle Variablen in der Capture-List werden aus dem umgebenden Scope "eingefangen" und stehen der Lambda-Funktion je nach Deklaration als Kopie oder per Referenz zur Verfügung. Beispielsweise für die Variable a wird die Variable mittels

[a] als Wert (Kopie)
[&a] als Referenz

übergeben. Es ist auch möglich, mehrere Variablen anzugeben, etwa durch [x, &y]. Genauso können alle Variablen der umgebenden Scopes eingefangen werden, und zwar durch

[=] als Werte (Kopie)
[&] als Referenz.

Hier gilt außerdem:

Der Rückgabetyp des Lambdas wird automatisch vom Compiler aus dem Ergebnis des return-Statements geschlossen. Obiger Lambda-Ausdruck lässt sich also auch schreiben als [a](int32_t b) {return a + b;}.
Das Schlüsselwort [...](...) mutable {...} sorgt dafür, dass die Call-by-Value-Variablen der Capture-List auch in der Lambda-Funktion verändert werden können.
Lambda-Funktionen haben selbst einen Typ, dieser wird aber vom Compiler erzeugt, man kann ihn also im Allgemeinen nicht explizit hinschreiben. Daher muss bei Variablenzuweisungen auf auto (siehe unten) oder Templates gesetzt werden.

Beispiel:

    auto sum = [](int32_t a, int32_t b){return a + b;}
    int32_t c = sum(5, 6);
    int32_t d = sum(4, 8);

Higher-Order-Functions in C++

Lambdas in Variablen zu speichern und dann damit zu arbeiten ist noch nicht sehr spannend. Interessant wird es aber vor allem dann, wenn wir Funktionen definieren wollen, die selbst wieder Funktionen generieren und/oder Funktionen als Argument(e) erhalten, Higher-Order-Functions (siehe Vorlesung).

Beispiel:

    #include <cmath>
    #include <iostream>
    #include <functional> // benötigt für den abstrakten Typ std::function

    // Diese Funktion wendet f auf das größere der beiden int32_t-Argumente an.
    // Dabei bildet f von einem int32_t auf ein double ab, was in Code nur implizit steht.
    // std::function<double(int)> steht hierbei für eine Funktion, die ein int auf ein double Abbildet. 
    // (In der Klammer können auch mehrere durch Kommata getrennte Argumente stehen).
    double transform_max(int a, int b, std::function<double(int)> f) {
        return a > b ? f(a) : f(b);
    }

    // Alternativ können Lambdas auch mithilfe von Templates einer Funktion übergebenen werden
    // Das Ganze sieht dann folgendermaßen aus:
    template <typename Func>
    double transform_max_tl(int32_t a, int32_t b, Func f) {
        return a > b ? f(a) : f(b);
    }

    // Diese Funktion generiert einne Funktion, die prüft, ob eine Zahl < max ist.
    // bool ist hierbei die Ausgabe aus der Eingabe int
    std::function<bool(int)> make_less_predicate(int max) {
        return [max](int val) -> bool {
            return val < max;
        };
    }

    auto make_less_predicate_tl(int32_t max) {
        return [max](int32_t val) -> bool {
            return val < max;
        };
    }

    int main() {

        // Lambdas können auch direkt übergeben werden, ohne erst in einer Variable
        // gespeichert zu werden. (Insbesondere, wenn man sie nur einmal verwendet)
        double t = transform_max(89, 123, [](int32_t c) -> double {
            return std::sqrt(c);
        });

        // Hinweis: Bei der templatisierten Version wird das Templateargument automatisch ermittelt.
        double t2 = transform_max_tl(89, 123, [](int32_t c) -> double {
            return std::sqrt(c);
        });

        auto less42 = make_less_predicate(42);
        auto less5 = make_less_predicate(5);
        std::cout << "Test: " << less5(8) << " " << less5(48) << std::endl;
        std::cout << "Test: " << less42(8) << " " << less42(48) << std::endl;
    }

Übrigens: Ein Prädikat ist dabei im Allgemeinen der Teil einer atomaren Aussage, der wahrheitsfunktional ist (Quelle: Wikipedia). In unseren Beispielen sind dies also Funktionen, die für beliebige Eingabe entweder wahr (true) bzw falsch (false) zurückgeben.

Aufgaben

Implementieren Sie die folgenden Higher-Order Functions und zeigen Sie ihre Verwendung an mindestens einem Beispiel.

void for_each(std::vector<float> &v, std::function<void(float)> f)
Führt die übergebenen Lambda-Funktion vom Typ void(float) für jedes Element aus.
(Dieses kann zum Beispiel jedes Element auf der Konsole ausgeben).
float find_if(std::vector<float> &v, std::function<bool(float)> f)
Gibt das erste Element der übergebenen Liste aus, das das Prädikat (Funktion vom Typ bool(float)) erfüllt.
float count_if(std::vector<float> &v, std::function<bool(float)> f)
Zählt die Elemente, die das Prädikat (Funktion vom Typ bool(float)) erfüllen.
void transform(std::vector<float> &v, std::function<float(float)> f)
Überschreibt jedes Elment der übergebenen Liste mit dem durch die Funktion f (Typ float(float)) transformierten Element.
float accumulate(std::vector<float> &v, std::function<float(float,float)> f, float start = 0.0)
Summiert die Werte der Liste mithilfe der übergebenen Funktion (Typ float(float,float)) auf.

Es gilt also accumulate(v,f,0) = f(...(f(f(start,v[0]),v[1]),...),v[n]).
void partition(std::vector<float> &v, std::function<bool(float)> f)
„Sortiert“ alle Elemente, die das Prädikat (Typ bool(float)) erfüllen an den Anfang der Liste und alle, die das Prädikat nicht erfüllen ans Ende der Liste.
(Hierfür ist kein Sortieralgorithmus nötig — einfach über die Liste iterieren reicht vollkommen).
template <typename Func1, typename Func2> auto compose(Func1 f1, Func2 f2)
Erhält zwei Funktionen f1 und f2 und gibt die Funktion zurück, die das Ergebnis von f2 in f1 einsetzt.
Beide Funktionen haben den Typ float(float);
Mathematisch ausgedrückt suchen wir die Funktion \[ f_1 \circ f_2: x \mapsto f_1(f_2(x)) \]

(Hinweis: Wir möchten an dieser Stelle die Verwendung templatisierten Funktionen höherer Ordnung üben.)
template <typename Func> auto partial(Func f, float val)
Erhält eine Funktionen f1 mit zwei Argumenten (z.B. Typ float(float,float)) und soll eine Funktion zurückgeben, die das zweite Argument von f festsetzt.
Diese Funktion hat dann den Typ float(float). Mathematisch ausgedrückt suchen wir die Funktion \[ f_a: x \mapsto f(x,a). \]

(Hinweis: Wir möchten an dieser Stelle die Verwendung templatisierten Funktionen höherer Ordnung üben.)
Bonus: Ganz ähnlich wie find_if, count_if könnten auch Funktionen wie etwa any_of, all_of, none_of implementiert werden. Diese sollen die Frage beantworten, ob ein Prädikat für irgendein/kein/alle Elemente gilt.
Bonus: Ganz ähnlich zu partition kann auch ein sort implementiert werden, dass basierend auf einem Comparator-Prädikat vom Typ bool(float,float) (also zwei Eingaben) die Liste sortiert — true entspricht dabei der Aussage, dass die linke Eingabe kleiner ist als die zweite Eingabe.

Aufgabe Bonusaufgabe: Projekterweiterung

Letzte Änderung: 09. October 2020, 09:29 Uhr
zusätzlich 20 Punkte — im Detail
Ansicht: |

Eines der Hauptprobleme in der Softwareentwicklung besteht darin, dass man zum Begin eines Projektes nicht wissen kann in welche Richtung sich ein Projekt entwickeln wird. In dieser Aufgabe können Sie selbst prüfen wie gut Ihr Softwaredesign gewählt wurde, indem wir Ihnen ein Feature geben, dass in Ihren Code von letzter Woche eingebunden werden soll.

Implementieren Sie die Möglickeit weiter Spielfelder mit einander zu verbinden.
Alle Spielfelder sollen durch „Tunnel“ mit einander verbunden werden; bewegt sich ein Objekt in den Tunnel, soll es ganz einfach von einem Spielfeld auf das andere Gesetzt werden, das der Tunnel verbunden hat.
Wichtig Erweitern Sie den Code durch eine Tunnel-Klasse! Sinn dieser Aufgabe ist es, beliebige viele Tunnel einzubinden zu können.

Beispiel: Bewegungssimulation

┌─┬─┬─┬─┬─┬─┬─┬─┐
│ │ │♘│ │ │ │ │ │
├─┼─┼─┼─┼─┼─┼─┼─┼─┬─┐
│ │ │ │ │ │ │ │ │ │ │ tunnel
├─┼─┼─┼─┼─┼─┼─┼─┼─┴─┘
│ │ │ │ │ │ │ │ │
├─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ │ │ │♞│
├─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ │ │ │♚│
├─┼─┼─┼─┼─┼─┼─┼─┤     ┌─┬─┬─┬─┬─┬─┬─┬─┐
│ │♔│ │ │ │ │ │ │     │ │ │ │ │ │ │ │ │
├─┼─┼─┼─┼─┼─┼─┼─┤     ├─┼─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ │ │ │ │     │ │ │ │ │ │ │♚│ │
├─┼─┼─┼─┼─┼─┼─┼─┤     ├─┼─┼─┼─┼─┼─┼─┼─┤
│♘│ │ │ │ │♞│ │ │     │ │ │ │ │ │ │ │ │
└─┴─┴─┴─┴─┴─┴─┴─┘     ├─┼─┼─┼─┼─┼─┼─┼─┤
                      │ │ │♘│ │ │ │ │ │
                      ├─┼─┼─┼─┼─┼─┼─┼─┤
                      │ │ │ │ │ │ │ │ │
                  ┌─┬─┼─┼─┼─┼─┼─┼─┼─┼─┤
           tunnel │ │ │ │ │ │ │ │ │ │ │
                  └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘

Beispiel: Verkehrssimulation

                      +---------------------------------------+
                      | v<<<.<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< |
                      | v --^ ---  --  --  --  --  --  -- - ^ |
                      | .>>>.>>>>>>>>>>>>>>>>>>>>>>>>>>>v   ^ |
                      | v | ^ +-----------------------+ v | ^ |
                      | v   ^ |                       | v   ^ |
                      | v | ^ |                       | v | ^ |
                      | v   ^ |                       | v   ^ |
                      | v | ^ |                       | v | ^ |
                      | v   ^ +-----------------------+ v   ^ |
                      | v   ^<<<<<<<<<<<<<<<<<<<<<<<<<<<.<<<. |
                      | v--  ---  --  --  --  --  --  - v T ^ |
                      | >>>>>>>>>>>>>>>>>>.>>>.>>>>>>>>>>>>>^ |
                      +-----------------| v   ^ |-------------+
                                        | v | ^ |
                                        | v   ^ |
                                        | v | ^ |
                                        |_-----_|
                                        /       \
                                         tunnel



+------------------------------------------------------------------------------------+
| v<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< |
| v  --  --  --  --  --  --  --  --  --  --  --  --  ---  --  --  --  --  --  -- - ^ |
| v | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>.>>>.>>>>>>>>>>>>>>>>>>>>>>>>>>>v   ^ |
| v   ^ +------------------------------------+ v | ^ +-----------------------+ v | ^ |
| v | ^ |                                    | v   ^ |                       | v   ^ |
| v   ^ |                                    | v | ^ |                       | v | ^ |
| v | ^ |                                    | v   ^ |                       | v   ^ |
| v   ^ |                                    | v | ^ |                       | v | ^ |
| v | ^ |              +---------------------+ v   ^ +-----------------------+ v   ^ |
| v   ^ |              | v<<<<<<<<<<<<<<<<<<<<<<<<<.<<<<<<<<<<<<<<<<<<<<<<<<<<<.<<<^ |
| v | ^ |              | v  --  --  --  --  --  --  ---  --  --  --  --  --  - v T ^ |
| v   ^ |              | v | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>.>>>^ |
| v | ^ |              | v   ^ +---------------------------------------------+ v   ^ |
| v   ^ |              | v | ^ |              tunnel                         | v | ^ |
| v | ^ +--------------+ v   ^ |             _________                       | v   ^ |
| v   ^<<<<<<<<<<<<<<<<<<.<<<. |            | _-----_ |                      | v | ^ |
| v | ^  --  --  --  --  v   ^ |            |/ v   ^ \|                      | v   ^ |
| .>>>.>>>>>>>>>>>>>>>>>>.>>>^ |             | v | ^ |                       | v | ^ |
| v | ^ +--------------+ v   ^ |             | v   ^ |                       | v   ^ |
| v   ^ |              | v | ^ |             | v | ^ |                       | v | ^ |
| v | ^ |              | v   ^ |             | v   ^ |                       | v   ^ |
| v   ^ +--------------+ v | ^ +-------------+ v | ^ +-----------------------+ v | ^ |
| v | ^<<<<<<<<<<<<<<<<<<.<<<.<<<<<<<<<<<<<<<<<<<<<.<<<<<<<<<<<<<<<<<<<<<<<<<<<<   ^ |
| v  --  --  --  --  --  v T ^   --  --  --  --  --  ---  -- ^--  --  --  --  -- - ^ |
| >>>>>>>>>>>>>>>>>>>>>>>.>>>.>>>>>>>>>>>>>>>>>>>>>>>>>>>.>>>.>>>>>>>>>>>>>>>>>>>>>^ |
+----------------------+ v | ^ +-----------------------+ v   ^ +---------------------+
                       | v   ^ |                       | v | ^ |
                       | v | ^ |                       | v   ^ |
                       | v   ^ |                       | v | ^ |
                       | v | ^ |                       | v   ^ |
                       | v   ^ +-----------------------+ v | ^ |
                       | v | ^<<<<<<<<<<<<<<<<<<<<<<<<<<<<   ^ |
                       | v  --  --  --  --  --  --  -- --  - ^ |
                       | >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>^ |
                       +---------------------------------------+

Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel

Weitere Architekturbeispiele & Lambda-Ausdrücke

Übung 8

Aufgabe Stream-Wrapper

basic_stream_wrapper.h

basic_stream_wrapper.cpp

Aufgaben

Aufgabe Higher-Order Functions

Lambda-Funktionen in C++

Higher-Order-Functions in C++

Aufgaben

Aufgabe Bonusaufgabe: Projekterweiterung

Institut für Informatik

Michael Wand Christian Ali Mehmeti-Göpel

Weitere Architekturbeispiele & Lambda-Ausdrücke

Übung 8

Aufgabe Stream-Wrapper

basic_stream_wrapper.h

basic_stream_wrapper.cpp

Aufgaben

Aufgabe Higher-Order Functions

Lambda-Funktionen in C++

Higher-Order-Functions in C++

Aufgaben

Aufgabe Bonusaufgabe: Projekterweiterung

Michael Wand
Christian Ali Mehmeti-Göpel