ObjectTrie.hpp

Go to the documentation of this file.

// @formatter:off
//
// Balau core C++ library
//
// Copyright (C) 2008 Bora Software (contact@borasoftware.com)
//
// Licensed under the Boost Software License - Version 1.0 - August 17th, 2003.
// See the LICENSE file for the full license text.
//


#ifndef COM_BORA_SOFTWARE__BALAU_CONTAINER__BALAU_TRIE
#define COM_BORA_SOFTWARE__BALAU_CONTAINER__BALAU_TRIE

#include <Balau/Util/Vectors.hpp>

// Avoid false positives.
#pragma clang diagnostic push
#pragma ide diagnostic ignored "OCUnusedGlobalDeclarationInspection"

namespace Balau::Container {

template <typename T> class ObjectTrie;

template <typename T> class ObjectTrieNode {
    // Used in the fluent API.
    private: class ObjectAdder {
        friend class ObjectTrieNode<T>;
        T value;
        std::vector<ObjectAdder> childAdders;

        ObjectAdder(T && value_, std::vector<ObjectAdder> && childAdders_)
            : value(std::move(value_))
            , childAdders(std::move(childAdders_)) {}

        public: ObjectAdder(ObjectAdder && ) noexcept = default;
    };

    public: static ObjectAdder child(T && value) {
        return ObjectAdder(std::move(value), {});
    }

    public: template <typename ... ObjectAdderT>
    static ObjectAdder child(T && value, ObjectAdderT && ... childAdder) {
        return ObjectAdder(std::move(value), Util::Vectors::pushBack(std::move(childAdder) ... ));
    }

    public: template <typename ... ObjectAdderT>
    ObjectTrieNode<T> & add(T && value, ObjectAdderT && ... childAdder) {
        auto & child = addAndReturnChild(std::move(value));
        child.add(Util::Vectors::pushBack(std::move(childAdder) ... ));
        return *this;
    }

    public: ObjectTrieNode<T> & add(std::vector<ObjectAdder> && childAdders) {
        for (auto & childAdder : childAdders) {
            children.emplace_back(ObjectTrieNode<T>(std::move(childAdder.value)));
            children.back().add(std::move(childAdder.childAdders));
        }

        return *this;
    }

    public: T value;

    public: ObjectTrieNode<T> & add(T && value) {
        addAndReturnChild(std::move(value));
        return *this;
    }

    public: ObjectTrieNode<T> & add(const T & value) {
        addAndReturnChild(value);
        return *this;
    }

    public: ObjectTrieNode<T> & addOrReplace(T && value) {
        ObjectTrieNode<T> * match = find(value);

        if (match) {
            match->value = std::move(value);
        } else {
            addAndReturnChild(std::move(value));
        }

        return *this;
    }

    public: ObjectTrieNode<T> & addOrReplace(const T & value) {
        ObjectTrieNode<T> * match = find(value);

        if (match) {
            match->value = value;
        } else {
            addAndReturnChild(value);
        }

        return *this;
    }

    public: template <typename CompareT>
    ObjectTrieNode<T> & addOrReplace(T && value, CompareT compare) {
        ObjectTrieNode<T> * match = find(value, compare);

        if (match) {
            match->value = std::move(value);
        } else {
            addAndReturnChild(std::move(value));
        }

        return *this;
    }

    public: template <typename CompareT>
    ObjectTrieNode<T> & addOrReplace(const T & value, CompareT compare) {
        ObjectTrieNode<T> * match = find(value, compare);

        if (match) {
            match->value = value;
        } else {
            addAndReturnChild(value);
        }

        return *this;
    }

    public: template <typename CompareT, typename ReplaceT, ReplaceT replace>
    ObjectTrieNode<T> & addOrReplace(T && value, CompareT compare) {
        ObjectTrieNode<T> * match = find(value, compare);

        if (match) {
            replace(match->value, std::move(value));
        } else {
            addAndReturnChild(std::move(value));
        }

        return *this;
    }

    public: template <typename CompareT, typename ReplaceT>
    ObjectTrieNode<T> & addOrReplace(const T & value, CompareT compare, ReplaceT replace) {
        ObjectTrieNode<T> * match = find(value, compare);

        if (match) {
            replace(match->value, value);
        } else {
            addAndReturnChild(value);
        }

        return *this;
    }

    public: ObjectTrieNode<T> & addAndReturnChild(const T & value) {
        children.emplace_back(ObjectTrieNode<T>(value));
        return children.back();
    }

    public: ObjectTrieNode<T> & addAndReturnChild(T && value) {
        children.emplace_back(ObjectTrieNode<T>(std::move(value)));
        return children.back();
    }

    public: ObjectTrieNode<T> & addOrReplaceAndReturnChild(const T & value) {
        ObjectTrieNode<T> * match = find(value);

        if (match) {
            match->value = value;
            return *match;
        } else {
            return addAndReturnChild(value);
        }
    }

    public: ObjectTrieNode<T> & addOrReplaceAndReturnChild(T && value) {
        ObjectTrieNode<T> * match = find(value);

        if (match) {
            match->value = std::move(value);
            return *match;
        } else {
            return addAndReturnChild(std::move(value));
        }
    }

    public:  template <typename CompareT>
    ObjectTrieNode<T> & addOrReplaceAndReturnChild(const T & value, CompareT compare) {
        ObjectTrieNode<T> * match = find(value, compare);

        if (match) {
            match->value = value;
            return *match;
        } else {
            return addAndReturnChild(value);
        }
    }

    public: template <typename CompareT>
    ObjectTrieNode<T> & addOrReplaceAndReturnChild(T && value, CompareT compare) {
        ObjectTrieNode<T> * match = find(value, compare);

        if (match) {
            match->value = std::move(value);
            return *match;
        } else {
            return addAndReturnChild(std::move(value));
        }
    }

    public:  template <typename CompareT, typename ReplaceT>
    ObjectTrieNode<T> & addOrReplaceAndReturnChild(const T & value, CompareT compare, ReplaceT replace) {
        ObjectTrieNode<T> * match = find(value, compare);

        if (match) {
            replace(match->value, value);
            return *match;
        } else {
            return addAndReturnChild(value);
        }
    }

    public: template <typename CompareT, typename ReplaceT>
    ObjectTrieNode<T> & addOrReplaceAndReturnChild(T && value, CompareT compare, ReplaceT replace) {
        ObjectTrieNode<T> * match = find(value, compare);

        if (match) {
            replace(match->value, std::move(value));
            return *match;
        } else {
            return addAndReturnChild(std::move(value));
        }
    }

    public: ObjectTrieNode<T> * find(const T & value) {
        for (size_t m = 0; m < children.size(); m++) {
            if (children[m].value == value) {
                return &children[m];
            }
        }

        return nullptr;
    }

    public: const ObjectTrieNode<T> * find(const T & value) const {
        for (size_t m = 0; m < children.size(); m++) {
            if (children[m].value == value) {
                return &children[m];
            }
        }

        return nullptr;
    }

    public: template <typename CompareT>
    ObjectTrieNode<T> * find(const T & value, CompareT compare) {
        for (size_t m = 0; m < children.size(); m++) {
            if (compare(children[m].value, value)) {
                return &children[m];
            }
        }

        return nullptr;
    }

    public: template <typename CompareT>
    const ObjectTrieNode<T> * find(const T & value, CompareT compare) const {
        for (size_t m = 0; m < children.size(); m++) {
            if (compare(children[m].value, value)) {
                return &children[m];
            }
        }

        return nullptr;
    }

    public: template <typename U, typename CompareT>
    ObjectTrieNode<T> * find(const U & value, CompareT compare) {
        for (size_t m = 0; m < children.size(); m++) {
            if (compare(children[m].value, value)) {
                return &children[m];
            }
        }

        return nullptr;
    }

    public: template <typename U, typename CompareT>
    const ObjectTrieNode<T> * find(const U & value, CompareT compare) const {
        for (size_t m = 0; m < children.size(); m++) {
            if (compare(children[m].value, value)) {
                return &children[m];
            }
        }

        return nullptr;
    }

    public: ObjectTrieNode<T> & findOrAddChild(const T & value) {
        for (size_t m = 0; m < children.size(); m++) {
            if (children[m].value == value) {
                return children[m];
            }
        }

        children.emplace_back(ObjectTrieNode<T>(value));
        return children.back();
    }

    public: ObjectTrieNode<T> & findOrAddChild(T && value) {
        for (size_t m = 0; m < children.size(); m++) {
            if (children[m].value == value) {
                return children[m];
            }
        }

        children.emplace_back(ObjectTrieNode<T>(std::move(value)));
        return children.back();
    }

    public: template <typename U, typename CompareT>
    ObjectTrieNode<T> & findOrAddChild(const U & value, CompareT compare) {
        for (size_t m = 0; m < children.size(); m++) {
            if (compare(children[m].value, value)) {
                return children[m];
            }
        }

        children.emplace_back(ObjectTrieNode<T>(T(value)));
        return children.back();
    }

    public: template <typename U, typename CompareT, typename Create>
    ObjectTrieNode<T> & findOrAddChild(const U & value, CompareT compare, Create create) {
        for (size_t m = 0; m < children.size(); m++) {
            if (compare(children[m].value, value)) {
                return children[m];
            }
        }

        children.emplace_back(ObjectTrieNode<T>(create(value)));
        return children.back();
    }

    public: ObjectTrieNode<T> & operator [] (size_t index) {
        return children[index];
    }

    public: const ObjectTrieNode<T> & operator [] (size_t index) const {
        return children[index];
    }

    public: size_t count() const {
        return children.size();
    }

    public: bool empty() const {
        return children.empty();
    }

    public: ObjectTrieNode<T> * begin() {
        return &children[0];
    }

    public: const ObjectTrieNode<T> * begin() const {
        return &children[0];
    }

    public: ObjectTrieNode<T> * end() {
        return &children.back();
    }

    public: const ObjectTrieNode<T> * end() const {
        return &children.back();
    }


    // Used to support the child array allocation.
    private: explicit ObjectTrieNode()
        : value() {}

    // Required public for std::vector
    public: ObjectTrieNode(ObjectTrieNode<T> && rhs) noexcept
        : value(std::move(rhs.value))
        , children(std::move(rhs.children)) {}

    // Required public for std::vector
    public: ObjectTrieNode(const ObjectTrieNode<T> & copy)
        : value(copy.value)
        , children(copy.children) {}

    private: explicit ObjectTrieNode(const T & value_)
        : value(value_) {}

    private: explicit ObjectTrieNode(T && value_)
        : value(std::move(value_)) {}

    private: ObjectTrieNode<T> & operator = (const ObjectTrieNode<T> & copy) {
        value = copy.value;
        children = copy.children;
        return *this;
    }

    // Required for std::move.
    public: ObjectTrieNode<T> & operator = (ObjectTrieNode<T> && rhs) noexcept {
        value = std::move(rhs.value);
        children = std::move(rhs.children);
        return *this;
    }

    // Used in the public cascade copy method.
    private: void cascadeChildren(const ObjectTrieNode<T> & toCascade) {
        for (size_t m = 0; m < toCascade.children.size(); m++) {
            const ObjectTrieNode<T> & childToCascade = toCascade.children[m];
            ObjectTrieNode<T> * selfChild = find(childToCascade.value);

            if (selfChild) {
                selfChild->value = childToCascade.value;
                selfChild->cascadeChildren(childToCascade);
            } else {
                addAndReturnChild(childToCascade.value).cascadeChildren(childToCascade);
            }
        }
    }

    // Used in the public cascade move method.
    private: template <typename U> void cascadeChildren(ObjectTrieNode<T> & toCascade, U moveFunction) {
        for (size_t m = 0; m < toCascade.children.size(); m++) {
            ObjectTrieNode<T> & childToCascade = toCascade.children[m];
            ObjectTrieNode<T> * selfChild = find(childToCascade.value);

            if (selfChild) {
                selfChild->value = moveFunction(childToCascade.value);
                selfChild->cascadeChildren(childToCascade);
            } else {
                addAndReturnChild(moveFunction(childToCascade.value)).cascadeChildren(childToCascade);
            }
        }
    }

    template <typename U> friend class ObjectTrie;

    private: std::vector<ObjectTrieNode<T>> children;
};


template <typename T> class ObjectTrie {
    public: class DepthIterator {
        private: class IteratorNode {
            public: ObjectTrieNode<T> * node;
            // The index is offset by +1 in order to assign 0 to the current node.
            public: size_t index;

            public: IteratorNode(ObjectTrieNode<T> * node_, size_t index_) : node(node_), index(index_) {}
        };

        public: DepthIterator(const DepthIterator & copy)
            : nodeStack(copy.nodeStack) {}

        public: DepthIterator & operator = (const DepthIterator & copy) {
            nodeStack = copy.nodeStack;
            return *this;
        }

        public: DepthIterator & operator ++ () {
            if (!nodeStack.size()) {
                return endMarker;
            }

            while (nodeStack.size() > 0) {
                if (nodeStack.back().index < nodeStack.back().node->children.size()) {
                    ++nodeStack.back().index;
                    nodeStack.push_back({ &nodeStack.back().node->children[nodeStack.back().index - 1], 0 });
                    return *this;
                } else {
                    nodeStack.pop_back();
                }
            }

            return endMarker;
        }

        public: ObjectTrieNode<T> & operator * () {
            return *nodeStack.back().node;
        }

        public: const ObjectTrieNode<T> & operator * () const {
            return *nodeStack.back().node;
        }

        public: ObjectTrieNode<T> * operator -> () {
            return nodeStack.back().node;
        }

        public: const ObjectTrieNode<T> * operator -> () const {
            return nodeStack.back().node;
        }

        public: ObjectTrieNode<T> * getAncestor(size_t level) {
            if (nodeStack.size() <= level) {
                return nullptr;
            }

            return nodeStack[nodeStack.size() - 1 - level].node;
        }

        public: const ObjectTrieNode<T> * getAncestor(size_t level) const {
            if (nodeStack.size() <= level) {
                return nullptr;
            }

            return nodeStack[nodeStack.size() - 1 - level].node;
        }

        public: void getAncestors(std::vector<const ObjectTrieNode<T> *> & output) const {
            output.clear();

            for (const auto & iteratorNode : nodeStack) {
                output.emplace_back(iteratorNode.node);
            }
        }

        public: bool operator == (const DepthIterator & rhs) const {
            return nodeStack.size() == rhs.nodeStack.size()
                && (!nodeStack.size() || nodeStack.back().node == rhs.nodeStack.back().node);
        }

        public: bool operator != (const DepthIterator & rhs) const {
            return ! operator == (rhs);
        }

        friend class ObjectTrie<T>;

        private: DepthIterator() = default;

        private: explicit DepthIterator(ObjectTrie<T> * parent)
            : nodeStack({ IteratorNode(&parent->trieRoot, 0) }) {}

        private: static DepthIterator endMarker;
        private: std::vector<IteratorNode> nodeStack;
    };

    public: class ConstDepthIterator {
        private: class IteratorNode {
            public: const ObjectTrieNode<T> * node;
            // The index is offset by +1 in order to assign 0 to the current node.
            public: size_t index;

            public: IteratorNode(const ObjectTrieNode<T> * node_, size_t index_) : node(node_), index(index_) {}
        };

        public: ConstDepthIterator(const ConstDepthIterator & copy)
            : nodeStack(copy.nodeStack) {}

        public: ConstDepthIterator & operator = (const ConstDepthIterator & copy) {
            nodeStack = copy.nodeStack;
            return *this;
        }

        public: ConstDepthIterator & operator ++ () {
            if (!nodeStack.size()) {
                return endMarker;
            }

            while (nodeStack.size() > 0) {
                if (nodeStack.back().index < nodeStack.back().node->children.size()) {
                    ++nodeStack.back().index;
                    nodeStack.push_back({ &nodeStack.back().node->children[nodeStack.back().index - 1], 0 });
                    return *this;
                } else {
                    nodeStack.pop_back();
                }
            }

            return endMarker;
        }

        public: const ObjectTrieNode<T> & operator * () const {
            return *nodeStack.back().node;
        }

        public: const ObjectTrieNode<T> * operator -> () const {
            return nodeStack.back().node;
        }

        public: const ObjectTrieNode<T> * getAncestor(size_t level) const {
            if (nodeStack.size() <= level) {
                return nullptr;
            }

            return nodeStack[nodeStack.size() - 1 - level].node;
        }

        public: void getAncestors(std::vector<ObjectTrieNode<T> * const> & output) const {
            output.clear();

            for (const auto & iteratorNode : nodeStack) {
                output.emplace_back(iteratorNode.node);
            }
        }

        public: bool operator == (const ConstDepthIterator & rhs) const {
            return nodeStack.size() == rhs.nodeStack.size()
                && (!nodeStack.size() || nodeStack.back().node == rhs.nodeStack.back().node);
        }

        public: bool operator != (const ConstDepthIterator & rhs) const {
            return ! operator == (rhs);
        }

        friend class ObjectTrie<T>;

        private: ConstDepthIterator() = default;

        private: explicit ConstDepthIterator(const ObjectTrie<T> * parent)
            : nodeStack({ IteratorNode(&parent->trieRoot, 0) }) {}

        private: static ConstDepthIterator endMarker;
        private: std::vector<IteratorNode> nodeStack;
    };

    using iterator = DepthIterator;

    using const_iterator = ConstDepthIterator;

    public: class BreadthIterator {
        public: BreadthIterator(const BreadthIterator & copy)
            : nodeQueue(copy.nodeQueue) {}

        public: BreadthIterator & operator = (const BreadthIterator & copy) {
            nodeQueue = copy.nodeQueue;
            return *this;
        }

        public: BreadthIterator & operator ++ () {
            if (!nodeQueue.size()) {
                return endMarker;
            }

            ObjectTrieNode<T> * previous = nodeQueue.front();
            nodeQueue.pop();

            for (size_t m = 0; m < previous->children.size(); m++) {
                nodeQueue.push(&previous->children[m]);
            }

            if (!nodeQueue.size()) {
                return endMarker;
            }

            return *this;
        }

        public: ObjectTrieNode<T> & operator * () {
            return *nodeQueue.front();
        }

        public: const ObjectTrieNode<T> & operator * () const {
            return *nodeQueue.front();
        }

        public: ObjectTrieNode<T> * operator -> () {
            return nodeQueue.front();
        }

        public: const ObjectTrieNode<T> * operator -> () const {
            return nodeQueue.front();
        }

        public: bool operator == (const BreadthIterator & rhs) const {
            return nodeQueue.size() == rhs.nodeQueue.size()
                && (!nodeQueue.size() || nodeQueue.front() == rhs.nodeQueue.front());
        }

        public: bool operator != (const BreadthIterator & rhs) const {
            return ! operator == (rhs);
        }

        friend class ObjectTrie<T>;

        private: BreadthIterator() = default;

        private: explicit BreadthIterator(ObjectTrie<T> * parent)
            : nodeQueue({ &parent->trieRoot }) {}

        private: static BreadthIterator endMarker;
        private: std::queue<ObjectTrieNode<T> *> nodeQueue;
    };

    public: class ConstBreadthIterator {
        public: ConstBreadthIterator(const ConstBreadthIterator & copy)
            : nodeQueue(copy.nodeQueue) {}

        public: ConstBreadthIterator & operator = (const ConstBreadthIterator & copy) {
            nodeQueue = copy.nodeQueue;
            return *this;
        }

        public: ConstBreadthIterator & operator ++ () {
            if (!nodeQueue.size()) {
                return endMarker;
            }

            const ObjectTrieNode<T> * previous = nodeQueue.front();
            nodeQueue.pop();

            for (size_t m = 0; m < previous->children.size(); m++) {
                nodeQueue.push(&previous->children[m]);
            }

            if (!nodeQueue.size()) {
                return endMarker;
            }

            return *this;
        }

        public: const ObjectTrieNode<T> & operator * () const {
            return *nodeQueue.front();
        }

        public: const ObjectTrieNode<T> * operator -> () const {
            return nodeQueue.front();
        }

        public: bool operator == (const ConstBreadthIterator & rhs) const {
            return nodeQueue.size() == rhs.nodeQueue.size()
                && (!nodeQueue.size() || nodeQueue.front() == rhs.nodeQueue.front());
        }

        public: bool operator != (const ConstBreadthIterator & rhs) const {
            return ! operator == (rhs);
        }

        friend class ObjectTrie<T>;

        private: ConstBreadthIterator() = default;

        private: explicit ConstBreadthIterator(const ObjectTrie<T> * parent)
            : nodeQueue({ &parent->trieRoot }) {}

        private: static ConstBreadthIterator endMarker;
        private: std::queue<const ObjectTrieNode<T> *> nodeQueue;
    };

    public: ObjectTrie() = default;

    public: explicit ObjectTrie(const T & trieRoot_) : trieRoot(trieRoot_) {}

    public: explicit ObjectTrie(T && trieRoot_) : trieRoot(std::move(trieRoot_)) {}

    public: ObjectTrie(const ObjectTrie<T> & copy) : trieRoot(copy.trieRoot) {}

    public: ObjectTrie(ObjectTrie<T> && rhs) noexcept : trieRoot(std::move(rhs.trieRoot)) {}

    public: ObjectTrie<T> & operator = (ObjectTrie<T> && rhs) noexcept {
        trieRoot = std::move(rhs.trieRoot);
        return *this;
    }

    public: ObjectTrie<T> & operator = (const ObjectTrie<T> & rhs) {
        trieRoot = rhs.trieRoot;
        return *this;
    }

    public: ObjectTrieNode<T> & root() {
        return trieRoot;
    }

    public: const ObjectTrieNode<T> & root() const {
        return trieRoot;
    }

    public: template <typename ... ObjectAdderT>
    ObjectTrieNode<T> & add(T && value, ObjectAdderT && ... childNode) {
        auto & child = trieRoot.addAndReturnChild(std::move(value));
        child.add(Util::Vectors::pushBack(std::move(childNode) ... ));
        return trieRoot;
    }

    public: ObjectTrieNode<T> & add(const T & value) {
        return trieRoot.add(value);
    }

    public: ObjectTrieNode<T> & add(T && value) {
        return trieRoot.add(std::move(value));
    }

    public: ObjectTrieNode<T> & addOrReplace(const T & value) {
        return trieRoot.addOrReplace(value);
    }

    public: ObjectTrieNode<T> & addOrReplace(T && value) {
        return trieRoot.addOrReplace(std::move(value));
    }

    public: template <typename CompareT>
    ObjectTrieNode<T> & addOrReplace(const T & value, CompareT compare) {
        return trieRoot.addOrReplace(value, compare);
    }

    public: template <typename CompareT>
    ObjectTrieNode<T> & addOrReplace(T && value, CompareT compare) {
        return trieRoot.addOrReplace(std::move(value), compare);
    }

    public: template <typename CompareT, typename ReplaceT>
    ObjectTrieNode<T> & addOrReplace(const T & value, CompareT compare, ReplaceT replace) {
        return trieRoot.addOrReplace(value, compare, replace);
    }

    public: template <typename CompareT, typename ReplaceT>
    ObjectTrieNode<T> & addOrReplace(T && value, CompareT compare, ReplaceT replace) {
        return trieRoot.addOrReplace(std::move(value), compare, replace);
    }

    public: ObjectTrieNode<T> & addAndReturnChild(const T & value) {
        return trieRoot.addAndReturnChild(value);
    }

    public: ObjectTrieNode<T> & addAndReturnChild(T && value) {
        return trieRoot.addAndReturnChild(std::move(value));
    }

    public: ObjectTrieNode<T> & addOrReplaceAndReturnChild(const T & value) {
        return trieRoot.addOrReplaceAndReturnChild(value);
    }

    public: ObjectTrieNode<T> & addOrReplaceAndReturnChild(T && value) {
        return trieRoot.addOrReplaceAndReturnChild(std::move(value));
    }

    public: template <typename CompareT>
    ObjectTrieNode<T> & addOrReplaceAndReturnChild(const T & value, CompareT compare) {
        return trieRoot.addOrReplaceAndReturnChild(value, compare);
    }

    public: template <typename CompareT>
    ObjectTrieNode<T> & addOrReplaceAndReturnChild(T && value, CompareT compare) {
        return trieRoot.addOrReplaceAndReturnChild(std::move(value), compare);
    }

    public: template <typename CompareT, typename ReplaceT>
    ObjectTrieNode<T> & addOrReplaceAndReturnChild(const T & value, CompareT compare, ReplaceT replace) {
        return trieRoot.addOrReplaceAndReturnChild(value, compare, replace);
    }

    public: template <typename CompareT, typename ReplaceT>
    ObjectTrieNode<T> & addOrReplaceAndReturnChild(T && value, CompareT compare, ReplaceT replace) {
        return trieRoot.addOrReplaceAndReturnChild(std::move(value), compare, replace);
    }

    public: ObjectTrieNode<T> & operator [] (size_t index) {
        return trieRoot.children[index];
    }

    public: const ObjectTrieNode<T> & operator [] (size_t index) const {
        return trieRoot.children[index];
    }

    public: size_t count() const {
        return trieRoot.children.size();
    }

    public: bool empty() const {
        return trieRoot.children.empty();
    }

    public: DepthIterator begin() {
        return depthBegin();
    }

    public: ConstDepthIterator begin() const {
        return depthBegin();
    }

    public: DepthIterator end() {
        return depthEnd();
    }

    public: ConstDepthIterator end() const {
        return depthEnd();
    }

    public: DepthIterator depthBegin() {
        return DepthIterator(this);
    }

    public: ConstDepthIterator depthBegin() const {
        return ConstDepthIterator(this);
    }

    public: DepthIterator depthEnd() {
        return DepthIterator::endMarker;
    }

    public: ConstDepthIterator depthEnd() const {
        return ConstDepthIterator::endMarker;
    }

    public: BreadthIterator breadthBegin() {
        return BreadthIterator(this);
    }

    public: ConstBreadthIterator breadthBegin() const {
        return ConstBreadthIterator(this);
    }

    public: BreadthIterator breadthEnd() {
        return BreadthIterator::endMarker;
    }

    public: ConstBreadthIterator breadthEnd() const {
        return ConstBreadthIterator::endMarker;
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC>
    ObjectTrieNode<T> * find(const ContainerT<U, UC ...> & values, bool skipRoot = true) {
        return find(values, [] (auto & lhs, auto & rhs) { return lhs == rhs; }, skipRoot);
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC>
    const ObjectTrieNode<T> * find(const ContainerT<U, UC ...> & values, bool skipRoot = true) const {
        return find(values, [] (auto & lhs, auto & rhs) { return lhs == rhs; }, skipRoot);
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC, typename CompareT>
    ObjectTrieNode<T> * find(const ContainerT<U, UC ...> & values, CompareT compare, bool skipRoot = true) {
        if (values.empty()) {
            return nullptr;
        }

        auto iter = values.begin();

        if (!skipRoot) {
            if (!(compare(trieRoot.value, *iter))) {
                return nullptr;
            }

            ++iter;
        }

        ObjectTrieNode<T> * node = &trieRoot;

        while (iter != values.end()) {
            node = node->template find<U, CompareT>(*iter, compare);

            if (node == nullptr) {
                return nullptr;
            }

            ++iter;
        }

        return node;
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC, typename CompareT>
    const ObjectTrieNode<T> * find(const ContainerT<U, UC ...> & values, CompareT compare, bool skipRoot = true) const {
        if (values.empty()) {
            return nullptr;
        }

        auto iter = values.begin();

        if (!skipRoot) {
            if (!(compare(trieRoot.value, *iter))) {
                return nullptr;
            }

            ++iter;
        }

        const ObjectTrieNode<T> * node = &trieRoot;;

        while (iter != values.end()) {
            node = node->template find<U, CompareT>(*iter, compare);

            if (node == nullptr) {
                return nullptr;
            }

            ++iter;
        }

        return node;
    }


    public: template <typename U, template <typename ...> class ContainerT, typename ... UC>
    ObjectTrieNode<T> & findOrAdd(const ContainerT<U, UC ...> & values) {
        return findOrAdd(values, [] (auto & lhs, auto & rhs) { return lhs == rhs; });
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC, typename CompareT>
    ObjectTrieNode<T> & findOrAdd(const ContainerT<U, UC ...> & values, CompareT compare) {
        ObjectTrieNode<T> * node = &trieRoot;

        if (values.empty()) {
            return *node;
        }

        auto iter = values.begin();

        while (iter != values.end()) {
            node = &node->template findOrAddChild<U, CompareT>(*iter, compare);
            ++iter;
        }

        return *node;
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC, typename CompareT, typename Create>
    ObjectTrieNode<T> & findOrAdd(const ContainerT<U, UC ...> & values, CompareT compare, Create create) {
        ObjectTrieNode<T> * node = &trieRoot;

        if (values.empty()) {
            return *node;
        }

        auto iter = values.begin();

        while (iter != values.end()) {
            node = &node->template findOrAddChild<U, CompareT>(*iter, compare, create);
            ++iter;
        }

        return *node;
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC>
    ObjectTrieNode<T> * findNearest(const ContainerT<U, UC ...> & values, bool skipRoot = true) {
        return findNearest(values, [] (auto & lhs, auto & rhs) { return lhs == rhs; }, skipRoot);
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC>
    const ObjectTrieNode<T> * findNearest(const ContainerT<U, UC ...> & values, bool skipRoot = true) const {
        return findNearest(values, [] (auto & lhs, auto & rhs) { return lhs == rhs; }, skipRoot);
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC, typename CompareT>
    ObjectTrieNode<T> * findNearest(const ContainerT<U, UC ...> & values, CompareT compare, bool skipRoot = true) {
        if (values.empty()) {
            return nullptr;
        }

        auto iter = values.begin();
        ObjectTrieNode<T> * nodeToSearch = &trieRoot;
        ObjectTrieNode<T> * currentNode = nullptr;

        if (!skipRoot) {
            if (!compare(trieRoot.value, *iter)) {
                return nullptr;
            }

            ++iter;
            currentNode = &trieRoot;
        }

        ObjectTrieNode<T> * nextNode;

        while (iter != values.end()) {
            nextNode = nodeToSearch->find(*iter, compare);

            if (nextNode == nullptr) {
                return currentNode;
            }

            ++iter;
            currentNode = nextNode;
            nodeToSearch = nextNode;
        }

        return currentNode;
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC, typename CompareT>
    const ObjectTrieNode<T> * findNearest(const ContainerT<U, UC ...> & values, CompareT compare, bool skipRoot = true) const {
        if (values.empty()) {
            return nullptr;
        }

        auto iter = values.begin();
        const ObjectTrieNode<T> * nodeToSearch = &trieRoot;
        const ObjectTrieNode<T> * currentNode = nullptr;

        if (!skipRoot) {
            if (!compare(trieRoot.value, *iter)) {
                return nullptr;
            }

            ++iter;
            currentNode = &trieRoot;
        }

        const ObjectTrieNode<T> * nextNode;

        while (iter != values.end()) {
            nextNode = nodeToSearch->find(*iter, compare);

            if (nextNode == nullptr) {
                return currentNode;
            }

            ++iter;
            currentNode = nextNode;
            nodeToSearch = nextNode;
        }

        return currentNode;
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC>
    ObjectTrieNode<T> * findNearestLeaf(const ContainerT<U, UC ...> & values, bool skipRoot = true) {
        return findNearestLeaf(values, [] (auto & lhs, auto & rhs) { return lhs == rhs; }, skipRoot);
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC>
    const ObjectTrieNode<T> * findNearestLeaf(const ContainerT<U, UC ...> & values, bool skipRoot = true) const {
        return findNearestLeaf(values, [] (auto & lhs, auto & rhs) { return lhs == rhs; }, skipRoot);
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC, typename CompareT>
    ObjectTrieNode<T> * findNearestLeaf(const ContainerT<U, UC ...> & values, CompareT compare, bool skipRoot = true) {
        auto node = findNearest(values, compare, skipRoot);
        return node != nullptr && node->children.empty() ? node : nullptr;
    }

    public: template <typename U, template <typename ...> class ContainerT, typename ... UC, typename CompareT>
    const ObjectTrieNode<T> * findNearestLeaf(const ContainerT<U, UC ...> & values, CompareT compare, bool skipRoot = true) const {
        auto node = findNearest(values, compare, skipRoot);
        return node != nullptr && node->children.empty() ? node : nullptr;
    }

    public: void cascade(const ObjectTrie<T> & toCascade) {
        cascade(toCascade, stdCopyFunction);
    }

    public: void cascade(ObjectTrie<T> && toCascade) {
        cascade(std::move(toCascade), stdMoveFunction);
    }

    public: template <typename U> void cascade(const ObjectTrie<T> & toCascade, U copyFunction) {
        if (!(trieRoot.value == toCascade.trieRoot.value)) {
            return; // NOP
        }

        trieRoot.value = copyFunction(toCascade.trieRoot.value);
        trieRoot.cascadeChildren(toCascade.trieRoot);
    }

    public: template <typename U> void cascade(ObjectTrie<T> && toCascade, U moveFunction) {
        if (!(trieRoot.value == toCascade.trieRoot.value)) {
            return; // NOP
        }

        trieRoot.value = moveFunction(toCascade.trieRoot.value);
        trieRoot.cascadeChildren(toCascade.trieRoot, moveFunction);
    }


    private: static const T & stdCopyFunction(const T & in) {
        return in;
    }

    private: static T && stdMoveFunction(T & in) {
        return std::move(in);
    }

    private: ObjectTrieNode<T> trieRoot;
};

template <typename T>
typename ObjectTrie<T>::DepthIterator ObjectTrie<T>::DepthIterator::endMarker;

template <typename T>
typename ObjectTrie<T>::ConstDepthIterator ObjectTrie<T>::ConstDepthIterator::endMarker;

template <typename T>
typename ObjectTrie<T>::BreadthIterator ObjectTrie<T>::BreadthIterator::endMarker;

template <typename T>
typename ObjectTrie<T>::ConstBreadthIterator ObjectTrie<T>::ConstBreadthIterator::endMarker;

template <typename T>
std::ostream & operator << (std::ostream & stream, const ObjectTrie<T> & trie) {
    typename ObjectTrie<T>::ConstBreadthIterator iter = trie.breadthBegin();
    typename ObjectTrie<T>::ConstBreadthIterator end = trie.breadthEnd();

    while (iter != end) {
        stream << iter->value << "\n";
        ++iter;
    }

    return stream;
}

} // namespace Balau::Container

#pragma clang diagnostic pop

#endif // COM_BORA_SOFTWARE__BALAU_CONTAINER__BALAU_TRIE