Grobe Festlegung der Datenstruktur

In einem ersten Entwurf legen wir fest, welche Klassen, Methoden und Attribute benötigt werden. Im Lösungsvorschlag sind diese zum Beispiel die Klassen:

Eine Klasse Key

Diese enthält zwei statische Methoden:
- size gibt die Anzahl der unterschiedlichen Schlüssel zurück
- map berechnet für ein character den Schlüssel
Beide Methoden sind zudem als constexpr deklariert, so dass der Rückgabewert bereits zur Compile-Zeit bekannt ist (bzw. bekannt sein muss). Damit ist es möglich die Dimension eines C-Arrays über die statische size-Methode festzulegen.
Eine Klasse Trie
- Diese enthält die üblichen Konstruktoren, den Destruktor und einen Zuweisungsoperator.
- Eine size-Methode soll die Anzahl der Blatt-Knoten zurückgeben, d.h. die Anzahl der gespeicherten Objekte.
- Die Methode insert erlaubt das Einfügen eines Schlüssel-Objekt Paares.
- Die Methode visit erlaubt das besuchen aller Objekte, deren Schlüssel mit einem angegebenen Präfix beginnt.
- Eine interne Klasse Node wird benutzt, um einen Konten zu repräsentieren:
  - Da ein Konten ein Objekt enthalten kann oder auch nicht, werden wird zunächst einen Zeigen auf ein Objekt verwenden. Ein Null-Zeiger bedeutet, dass kein Objekt gespeichert ist.
  - Zudem enthält ein Knoten ein Array mit Zeigern auf Unter-Knoten. Enthält ein Array-Eintrag einen Null-Zeiger, dann bedeutet diese, dass kein Unter-Knoten existiert.
    
    Mit Key::map(c) wird aus einem Character c ein Array-Index i berechnet werden.

Hier das so entstandene Grundgerüst:

cpp-lecture/trie/step00/trie.hpp

#ifndef TRIE_TRIE_HPP

#define TRIE_TRIE_HPP

#include <algorithm>

#include <cassert>

#include <string>

struct KeyMap

{

    static constexpr size_t

    numKeys();

    static constexpr size_t

    get(char c);

};

template <typename Object>

class Trie

{

    public:

        Trie();

        Trie(const Trie &rhs);

        Trie(Trie &&trie);

        ~Trie();

        Trie &

        operator=(Trie rhs);

        Trie &

        insert(const std::string &key, const Object &obj);

        std::size_t

        get_size() const;

        template <typename Visitor>

        const Trie &

        visit(const std::string &key, const Visitor &visitor);

    private:

        struct Node

        {

            Node(const Object *value= nullptr);

            Node(const Node &rhs);

            ~Node();

            Node    *node[KeyMap::numKeys()];

            Object  *object;

        };

        void

        recursive_insert(Node *&root, const char *c, const Object &value);

        template <typename Visitor>

        void

        recursive_visit(Node *root, const char *c, const Visitor &visitor) const;

        Node            *node;

        std::size_t     size;

};

#endif // TRIE_TRIE_HPP