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:
#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