NET_RadixTree.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        NET_RadixTree.h
 *
 * COMMENTS:
 *
 */

#ifndef __NET_RADIXTREE_H__
#define __NET_RADIXTREE_H__

#include "NET_API.h"

#include <UT/UT_Assert.h>
#include <UT/UT_Debug.h>
#include <UT/UT_Optional.h>
#include <UT/UT_Set.h>
#include <UT/UT_SharedPtr.h>
#include <UT/UT_StringHolder.h>
#include <UT/UT_UniquePtr.h>
#include <UT/UT_WorkBuffer.h>
#include <UT/UT_IntrusivePtr.h>

#include <SYS/SYS_Compiler.h>

#include <cctype>

/// A simple radix tree implementation
template <typename T>
class NET_RadixTree
{
public:
    class Node;

    using NodeT = UT_IntrusivePtr<Node>;

    class Node : public UT_IntrusiveRefCounter<Node>
    {
    public:
        using Type = T;
        using ValueT = UT_UniquePtr<Type>;

        struct NodeCompare
        {
            bool operator()(const NodeT &lhs, const NodeT &rhs) const
            {
                return std::toupper(lhs->myPrefix[0]) ==
                       std::toupper(rhs->myPrefix[0]);
            }
        };

        using ChildrenT = UT_Set<NodeT, hboost::hash<NodeT>, NodeCompare>;

        Node() : myPrefix(), myValue(), myChildren(), myAllowsPartial(false) {}

        Node(const UT_StringHolder &prefix, bool allows_partial = false)
            : myPrefix(prefix),
              myValue(),
              myChildren(),
              myAllowsPartial(allows_partial)
        {
        }
        Node(const UT_StringHolder &prefix,
             const T &data,
             bool allows_partial = false)
            : myPrefix(prefix),
              myValue(UTmakeUnique<T>(data)),
              myChildren(),
              myAllowsPartial(allows_partial)
        {
        }

        SYS_FORCE_INLINE UT_Optional<Type &> value() const
        {
            if (!myValue)
                return hboost::none;
            return *myValue.get();
        }
        SYS_FORCE_INLINE bool hasValue() const { return myValue != nullptr; }
        SYS_FORCE_INLINE const UT_StringHolder &prefix() const
        {
            return myPrefix;
        }
        SYS_FORCE_INLINE bool isLeaf() const { return myChildren.size() == 0; }
        SYS_FORCE_INLINE bool allowsPartial() const { return myAllowsPartial; }

        void insert(const UT_StringHolder &key,
                    const T &data,
                    bool allow_partial = false)
        {
            UT_ASSERT(key.length() > 0);

            auto it = findPartialPrefixChild(key);
            if (it == myChildren.end())
            {
                // No child partially matched the prefix so we will create
                // one
                auto child = UTmakeIntrusive<Node>(key, data, allow_partial);
                myChildren.insert(child);
            }
            else
            {
                auto child = *it;
                UT_ASSERT(child);

                const exint prefix_length = getPrefixLength(
                    key, child->myPrefix);

                // Check if this is a duplicate key
                if (key.length() == child->myPrefix.length() &&
                    key.length() == prefix_length)
                {
                    if (child->hasValue())
                        return;

                    child->myValue = UTmakeUnique<Type>(data);
                    child->myAllowsPartial = allow_partial;
                    return;
                }
                // The childs key is the prefix of the insert item
                // abc -> abc - d [ after inserting "abcd" ]
                else if (prefix_length == child->myPrefix.length())
                {
                    UT_StringHolder suffix(key.begin() + prefix_length);
                    child->insert(suffix, data, allow_partial);
                    return;
                }
                // The insert item is the prefix of the childs prefix
                // abc -> ab - c [after inserting "abc"]
                else if (prefix_length == key.length())
                {
                    UT_StringHolder suffix(child->myPrefix.begin() +
                                           prefix_length);

                    auto new_child = UTmakeIntrusive<Node>(
                        key, data, allow_partial);

                    // Remove the current child
                    myChildren.erase(child);
                    // Update the child prefix
                    child->myPrefix = suffix;
                    // Add old child to the new child
                    new_child->myChildren.insert(child);

                    // Attach the new child to the current children
                    myChildren.insert(new_child);
                }
                // Inserting item and childs key have the same common prefix
                else
                {
                    // We need to split the current child and the suffix
                    // into
                    // two children whos parent is the prefix of the two
                    // children
                    UT_StringHolder item_prefix(
                        child->myPrefix.begin(), prefix_length);
                    UT_StringHolder item_suffix(child->myPrefix.begin() +
                                                prefix_length);

                    // remove the existing child as this will be move to the
                    // parent of the two children.
                    UT_VERIFY(myChildren.erase(child) == 1);

                    auto parent = UTmakeIntrusive<Node>(item_prefix);
                    // Add the prefix of the old child and the new key into
                    // this children set.
                    myChildren.insert(parent);

                    // update the new prefix
                    child->myPrefix = item_suffix;
                    // Add the suffix of the old key into the new branch
                    parent->myChildren.insert(child);

                    // Add the suffix of the key into the new split branch
                    UT_StringHolder suffix(key.begin() + prefix_length);
                    auto new_child = UTmakeIntrusive<Node>(
                        suffix, data, allow_partial);
                    parent->myChildren.insert(new_child);
                }
            }
        }

        // Find a child based on the prefix
        NodeT findChild(const UT_StringView prefix)
        {
            UT_ASSERT(prefix.length() > 0);

            auto it = findPartialPrefixChild(prefix);
            if (it == myChildren.end() || !prefix.startsWith((*it)->myPrefix))
                return nullptr;

            return *it;
        }

        void debug(UT_WorkBuffer &wbuf, unsigned indent = 0)
        {
            wbuf.append(indent, ' ');
            wbuf.append(myPrefix.length() > 0 
                ? static_cast<const char *>(myPrefix) : "<empty>");
            wbuf.append(' ');
            if (hasValue())
                wbuf.appendFormat("{}", *myValue);
            else
                wbuf.append("<None>");
            wbuf.append('\n');

            for (auto &&child : myChildren)
                child->debug(wbuf, indent + 1);
        }

    private:
        // Find the max length that both key and node prefix share
        exint getPrefixLength(const UT_StringHolder &key,
                              const UT_StringHolder &node_prefix)
        {
            exint length = 0;

            for (auto k_it = key.begin(), np_it = node_prefix.begin();
                 k_it != key.end() && np_it != node_prefix.end();
                 ++length, ++k_it, ++np_it)
            {
                if (*k_it != *np_it)
                    break;
            }

            return length;
        }

        // Find a child that is a partial match to the prefix.
        typename ChildrenT::iterator findPartialPrefixChild(
            const UT_StringHolder &prefix)
        {
            if (prefix.length() <= 0)
                return myChildren.end();

            char item = prefix[0];
            for (auto it = myChildren.begin(); it != myChildren.end(); it++)
            {
                if ((*it)->myPrefix[0] == item)
                    return it;
            }
            return myChildren.end();
        }

        UT_StringHolder myPrefix;
        ValueT myValue;
        ChildrenT myChildren;
        // If the node allows for partial matches
        bool myAllowsPartial;
    };

    /// Insert a node
    void insert(const UT_StringHolder &name,
                const T &data,
                bool allow_partial = false)
    {
        if (!myRoot)
            myRoot = UTmakeIntrusive<Node>();
        myRoot->insert(name, data, allow_partial);
    }

    /// Find the node based on the provided prefix.
    NodeT find(const UT_StringHolder &prefix) const
    {
        if (myRoot == nullptr)
            return nullptr;

        if (myRoot->prefix() == prefix)
            return myRoot;

        auto child = myRoot;
        NodeT last_partial = nullptr;
        UT_WorkBuffer wbuf(prefix);

        exint offset = 0;
        while (offset < wbuf.length() && child != nullptr)
        {
            UT_ASSERT(wbuf.begin() + offset <= wbuf.end());
            UT_StringView view(wbuf.begin() + offset, wbuf.end());
            child = child->findChild(view);

            if (child)
            {
                offset += child->prefix().length();
                // If this child allows for partial matches then update the
                // last partial node we found.
                if (child->allowsPartial())
                    last_partial = child;
            }
            // If we didnt find a child that matches check if our traversal came
            // across a node that allows for partial matches. If we found one
            // then return this node instead of reporting nothing found.
            else if (last_partial != nullptr)
                return last_partial;
        }

        return child;
    }

    /// Find the node that fully matches the prefix or partially matches based
    /// on the tree node being setup for it. Basically this method only returns
    /// a viable node if it "fully" matches the prefix. Use find() if you want
    /// find any node that will either partially match or fully match the
    /// prefix.
    SYS_NO_DISCARD_RESULT NodeT match(const UT_StringHolder &prefix) const
    {
        NodeT node = find(prefix);
        // Check that the node we found actually has a value (is an actuall
        // value in our tree).
        if (node == nullptr || !node->hasValue())
            return nullptr;
        return node;
    }

    /// Check if the tree contains the provided string
    SYS_NO_DISCARD_RESULT bool contains(const UT_StringHolder &prefix) const
    {
        NodeT node = find(prefix);

        return node != nullptr && node->hasValue();
    }

    /// Write out the tree into the work buffer. This is pretty printed.
    void debug(UT_WorkBuffer &wbuf)
    {
        wbuf.clear();

        if (myRoot)
            myRoot->debug(wbuf, 0);
        else
            wbuf = "<empty>";
    }

    /// Clear out the tree
    void clear() { myRoot.reset(); }

private:
    NodeT myRoot;
};

#endif // __NET_RADIXTREE_H__