Back     Next Browse Files

Erster Schritt: Einfügen von Objekten

Zunächst soll nur der Default-Konstruktor, der Destruktor und die insert-Methode implementiert werden. Ein Test-Programm könnte dazu so aussehen:

cpp-lecture/trie/step01/testit.cpp
#include "trie.hpp"
#include <iostream>

int
main()
{
    Trie<double>    trie;

    trie.insert("Lehn", 42);
    std::cout << "trie.size() = " << trie.size() << std::endl;

    trie.insert("lehn", 42);
    std::cout << "trie.size() = " << trie.size() << std::endl;

    trie.insert("lehr", 42);
    std::cout << "trie.size() = " << trie.size() << std::endl;

    trie.insert("le", 42);
    std::cout << "trie.size() = " << trie.size() << std::endl;
}

Zu beachten ist, dass wir hier ein paar C++14 Features benutzen und entsprechend übersetzen müssen:

$shell> g++ -Wall -std=c++14 testit.cpp
$shell> 

In der Implementierung sind vorerst noch Ausgaben eingefügt, so dass wir erkennen, wenn beispielsweise beim Einfügen ein bereits eingetragenes Objekt verdrängt wird:

$shell> ./a.out
trie.size() = 1
Remove old object!
trie.size() = 1
trie.size() = 2
trie.size() = 3
$shell> 

Spannend ist natürlich, wie die Implementierung der Trie-Klasse aussieht:

cpp-lecture/trie/step01/trie.hpp
#ifndef TRIE_TRIE_HPP
#define TRIE_TRIE_HPP

#include <algorithm>
#include <cassert>
#include <string>
#include <iostream>

struct Key
{
    static constexpr size_t
    size()
    {
        return ('Z' - 'A' + 1) + ('z' - 'a' + 1);
    }

    static constexpr size_t
    map(char c)
    {
        assert(c>='a' && c<='z' || c>='A' && c<='Z');
        if (c>='a' && c<='z') {
            c = c - 'a' + 'A';
        }
        return c - 'A';
    }
};

template <typename Object>
class Trie
{
    public:
        Trie()
            : node{nullptr}, size_{0}
        {
        }

        // Done later ..
        Trie(const Trie &rhs) = delete;

        // Done later ..
        Trie(Trie &&trie) = delete;

        ~Trie()
        {
            delete node;
        }

        // Done later ..
        Trie &
        operator=(Trie rhs) = delete;

        Trie &
        insert(const std::string &key, const Object &obj)
        {
            recursive_insert(node, key.c_str(), obj);
            return *this;
        }

        std::size_t
        size() const
        {
            return size_;
        }

        // Done later ..
        template <typename Visitor>
        const Trie &
        visit(const std::string &key, const Visitor &visitor) const = delete;

    private:

        struct Node
        {
            Node(const Object *value= nullptr)
                : node{}, object{nullptr}
            {
                if (value) {
                    object = new Object(*value);
                }
            }

            // Done later ..
            Node(const Node &rhs) = delete;

            ~Node()
            {
                for (std::size_t i=0; i<Key::size(); ++i) {
                    delete node[i];
                }
                delete object;
            }

            Node    *node[Key::size()];
            Object  *object;
        };

        void
        recursive_insert(Node *&root, const char *c, const Object &value)
        {
            if (!root) {
                root = new Node();
            }

            if (*c) {
                std::size_t key = Key::map(*c);
                recursive_insert(root->node[key], c+1, value);
            } else {
                if (root->object) {
                    std::cout << "Remove old object!" << std::endl;
                    delete root->object;
                } else {
                    ++size_;
                }
                root->object = new Object(value);
            }
        }

        Node            *node;
        std::size_t     size_;
};

#endif // TRIE_TRIE_HPP
    Back     Next