2
\$\begingroup\$

This is a partially persistent data structure using a red black tree. It will copy \$O(lg(n))\$ items for each remove or add operation.

enter image description here

#pragma once

#include <functional>
#include <utility>
#include <iostream>
#include <stack>
#include <queue>
#include <memory>
#include <deque>
#include <iterator>     
#include <type_traits>  
#include <stack>
#include <stdexcept>

namespace dts 
{

    template <typename T, typename Func = std::less<T>>
    class PersistentSet 
    {

public:

        PersistentSet();
        PersistentSet(Func);


        bool add(const T&);
        bool add(T&&);

        bool remove(const T& key);

        bool empty() const;

        size_t history_size() const;


        class TreeIterator
            : public std::iterator<std::forward_iterator_tag,
            std::remove_cv_t<T>,
            std::ptrdiff_t,
            const T*,
            const T&>
        {
            using node = typename dts::PersistentSet< std::remove_cv_t<T>, Func>::Nodeptr;
            node itr;
            node nil;
            std::stack<node> path;

            node find_successor(node n)
            {
                n = n->rigth;
                if (n != nil)
                {
                    while (n->left != nil)
                    {
                        path.push(n);
                        n = n->left;
                    }
                }
                else
                {
                    n = path.top();
                    path.pop();
                }
                return n;
            }
        public:

            explicit TreeIterator(node n, node pnil) : nil(pnil) //begin
            {
                if (n == nil)
                    itr = nil;
                else
                {
                    path.push(nil);
                    while (n->left != nil)
                    {
                        path.push(n);
                        n = n->left;
                    }
                    itr = n;
                }
            }
            explicit TreeIterator(node pnil) // end
                : itr(pnil), nil(pnil)
            { }


            TreeIterator& operator++ () 
            {
                itr = find_successor(itr);
                return *this;
            }
            TreeIterator operator++ (int)
            {
                TreeIterator tmp(*this);
                itr = find_successor(itr);
                return tmp;
            }

            bool operator == (const TreeIterator& rhs) const
            {
                return itr == rhs.itr;
            }

            bool operator != (const TreeIterator& rhs) const
            {
                return itr != rhs.itr;
            }

            const T& operator* () const
            {
                return itr->key;
            }

            const T& operator-> () const
            {
                return itr->key;
            }

        };


        typedef TreeIterator const_iterator;

        const_iterator begin() const
        {
            return begin(roots.size() - 1);
        }
        const_iterator begin(size_t index) const
        {
            if (index >= roots.size())
                throw std::out_of_range("out of range");

            return const_iterator(roots[index], nil);
        }
        const_iterator end() const
        {
            return const_iterator(nil);
        }

    private:

        struct Node;
        using Nodeptr = std::shared_ptr<Node>;

        struct Node
        {
            T key;
            bool isRed;

            Nodeptr left;
            Nodeptr rigth;

            Node(const T& pkey, bool pisRed, Nodeptr pleft, Nodeptr prigth)
                : key(pkey), isRed(pisRed), left(pleft), rigth(prigth)
            { }

            Node(T&& pkey, bool pisRed, Nodeptr pleft, Nodeptr prigth)
                : key(std::move(pkey)), isRed(pisRed), left(pleft), rigth(prigth)
            { }
        };

        std::vector<Nodeptr> roots;
        Func cmp;
        Nodeptr nil;

        template <typename TT>
        Nodeptr create_node(TT&& key);

        Nodeptr copy_node(Nodeptr) const;

        template <typename TT>
        bool generic_add(TT&&);

        template <typename TT>
        Nodeptr BST_add_recursive(std::queue<Nodeptr>&, TT&& key, Nodeptr& node);

        void fixed_add(std::queue<Nodeptr> &x);

        template <typename ChildA, typename ChildB>
        void generic_fixed_add(Nodeptr&, Nodeptr&, std::queue<Nodeptr>&, ChildA, ChildB);

        Nodeptr build_path(const T& key, Nodeptr root, std::deque<Nodeptr>& path);

        void delete_node(std::deque<Nodeptr> &);

        Nodeptr build_min_path(Nodeptr node ,std::deque<Nodeptr>& path);

        void transplant(Nodeptr p, Nodeptr x, Nodeptr y);

        void fixed_remove(Nodeptr x, std::deque<Nodeptr>& path);

        template <typename ChildA, typename ChildB >

        void generic_fixed_delete(Nodeptr&, Nodeptr&, std::deque<Nodeptr> & path, ChildA, ChildB);

        template <typename ChildA, typename ChildB >
        Nodeptr generic_rotate(Nodeptr, Nodeptr ,ChildA, ChildB);

        static Nodeptr& left(Nodeptr x) { return x->left; };

        static Nodeptr& rigth(Nodeptr x) { return x->rigth; };

    };

    template<typename T, typename Func>
    size_t  PersistentSet<T, Func>::history_size() const
    {
        return roots.size();
    }
    template<typename T, typename Func>
    bool PersistentSet<T, Func>::empty() const
    {
        return roots.back() == nil;
    }

    template <typename K, typename Func>
    void PersistentSet<K, Func>::transplant(Nodeptr p , Nodeptr x, Nodeptr y)
    {
        if (p == nil) 
        {   
            roots.pop_back();
            roots.push_back(y);
        }
        else if (p->left == x)
            p->left = y;
        else 
            p->rigth = y;
    }


    template<typename T, typename Func>
    PersistentSet<T, Func>::PersistentSet() : PersistentSet(Func()) {}

    template<typename T, typename Func>
    PersistentSet<T, Func>::PersistentSet(Func pcmp) 
        : cmp(pcmp), 
        roots(std::vector<Nodeptr>()), 
        nil(std::make_shared<Node>(T(), false, nullptr, nullptr) )
    {
        roots.push_back(nil);
    }

    template<typename T, typename Func>
    template <typename ChildA, typename ChildB >
    typename  PersistentSet<T, Func>::Nodeptr 
        PersistentSet<T, Func>::generic_rotate(

            Nodeptr p, 
            Nodeptr x, 
            ChildA childA, 
            ChildB childB )
    {
        Nodeptr y = childB(x);
        childB(x) = childA(y);

        if (x == roots.back())
        {
            roots.pop_back();
            roots.push_back(y);
        }
        else if (x == childA(p))
            childA(p) = y;
        else
            childB(p) = y;

        childA(y) = x;

        return y;
    }

    template <typename T, typename Func>
    template<typename TT>
    bool PersistentSet<T, Func>::generic_add(TT&& element)
    {

        std::queue<Nodeptr> path;
        auto newRoot = BST_add_recursive(
            path,              
            std::forward<TT>(element), 
            roots.back()
        );

        bool added = newRoot != nullptr;
        if (added)
        {
            roots.push_back(newRoot);
            path.push(nil);
            fixed_add(path);
        }
        return added;
    }

    template<typename T, typename Func>
    template<typename TT>
    typename PersistentSet<T, Func>::Nodeptr 
        PersistentSet<T, Func>::BST_add_recursive(std::queue<Nodeptr>& path, TT &&element, Nodeptr & node)
    {

        if (node == nil)
        {
            auto copy = create_node(std::forward<T>(element));
            path.push(copy);
            return copy;
        }

        bool isless = cmp(element, node->key);
        if (!isless && !cmp(node->key, element))
            return nullptr;

        auto dir = isless ? left : rigth;
        auto child = BST_add_recursive(
            path, 
            std::forward<TT>(element), 
            dir(node)
        );

        if (child == nullptr) return child;

        auto copy = copy_node(node);
        path.push(copy);
        dir(copy) = child;

        return copy;
    }

    template <typename T, typename Func>
    typename PersistentSet<T, Func>::Nodeptr 
        PersistentSet<T, Func>::build_path(const T& element, Nodeptr node, std::deque<Nodeptr>& path)
    {
        if (node == nil)
            return nullptr;

        bool isless = cmp(element, node->key);
        if (!isless && !cmp(node->key, element)) 
        {
            auto copy = copy_node(node);
            path.push_back(copy);
            return copy;
        }

        auto dir = isless ? left : rigth;
        auto child = build_path(element, dir(node), path);

        if (child == nullptr) return child;

        auto copy = copy_node(node);
        path.push_back(copy);
        dir(copy) = child;

        return copy;
    }

    template <typename T, typename Func>
    bool PersistentSet<T, Func>::add(const T& element)
    {
        return generic_add(const_cast<T&> (element));
    }

    template <typename T, typename Func>
    bool PersistentSet<T, Func>::add(T&& element)
    {
        return generic_add(std::move(element));
    }

    template<typename T, typename Func>
    typename PersistentSet<T, Func>::Nodeptr 
        PersistentSet<T, Func>::copy_node(Nodeptr node) const
    {
        if (node == nil) return nil;
        return std::make_shared<Node>(node->key, node->isRed, node->left, node->rigth);
    }

    template <typename T, typename Func>
    template <typename TT>
    typename PersistentSet<T, Func>::Nodeptr 
        PersistentSet<T, Func>::create_node(TT&& key)
    {
        return std::make_shared<Node>(std::forward<TT>(key), true, nil, nil);
    }

    template <typename T, typename Func>
    void PersistentSet<T, Func>::delete_node(std::deque<Nodeptr> & path)
    {

        auto z = path.front();
        auto x = z->rigth, y = z;

        if (z->left == nil)
        {   
            path.pop_front();
            transplant(path.front(), z, x);
        }
        else if (z->rigth == nil)
        {
            path.pop_front();
            transplant(path.front(), z, x = z->left);
        }
        else
        {
            z->rigth = copy_node(z->rigth);
            y = build_min_path(z->rigth, path);
            x = y->rigth;
            z->key = std::move(y->key);
            transplant(path.front(), y, x);
        }

        if (!y->isRed)
            fixed_remove(x, path);

    }


    template <typename T, typename Func>
    typename PersistentSet<T, Func>::Nodeptr 
        PersistentSet<T, Func>::build_min_path(Nodeptr node, std::deque<Nodeptr>& path)
    {
        while (node->left != nil) 
        {   
            node->left = copy_node(node->left);
            path.push_front(node);
            node = node->left;
        }
        return node;    
    }

    template <typename T, typename Func>
    void PersistentSet<T, Func>::fixed_remove(Nodeptr x, std::deque<Nodeptr>& path)
    {

        auto p = path.front();
        path.pop_front();
        while (x != roots.back() && !x->isRed)
        {
            if (p->left == x)
                generic_fixed_delete(x, p, path, left, rigth);
            else
                generic_fixed_delete(x, p, path, rigth, left);
        }

        auto newX = copy_node(x);
        transplant(p, x, newX);
        newX->isRed = false;

    }
    template <typename T, typename Func>
    template <typename ChildA, typename ChildB >
    void PersistentSet<T, Func>::generic_fixed_delete(

        Nodeptr& x, 
        Nodeptr& p, 
        std::deque<Nodeptr> & path, 
        ChildA childA, 
        ChildB childB )
    {
        Nodeptr w = childB(p);
        if (w->isRed)
        {   
            w = childB(p) = copy_node(w);

            std::swap(w->isRed, p->isRed);  
            generic_rotate(path.front(), p, childA, childB);
            path.push_front(w);
            w = childB(p);
        }
        if (!w->left->isRed && !w->rigth->isRed)
        {
            w = childB(p) = copy_node(w);

            w->isRed = true;    
            x = p;
            p = path.front();
            path.pop_front();       
        }
        else
        {
            if (!childB(w)->isRed)
            {       
                w = childB(p) = copy_node(w);

                childA(w) = copy_node(childA(w));
                std::swap(w->isRed, childA(w)->isRed);
                w = generic_rotate(p, w, childB, childA);       
            }
            w = childB(p) = copy_node(w);

            childB(w) = copy_node(childB(w));
            w->isRed = p->isRed;
            p->isRed = false;
            childB(w)->isRed = false;
            generic_rotate(path.front(), p, childA, childB);

            x = roots.back();
            p = nil;
        }

    }

    template <typename T, typename Func>
    bool PersistentSet<T, Func>::remove(const T& element)
    {
        std::deque<Nodeptr> dq;

        auto node = build_path(element, roots.back(), dq);
        bool exist = node != nullptr;
        if (exist) 
        {
            roots.push_back(node);
            dq.push_back(nil);
            delete_node(dq);
        }
        return exist;
    }


    template <typename T, typename Func>
    void PersistentSet<T, Func>::fixed_add(std::queue<Nodeptr>& path)
    {

        auto x = path.front();
        path.pop();
        auto p = path.front();
        path.pop();

        while (p->isRed)
        {
            if (path.front()->left == p)
                generic_fixed_add(p, x, path, left, rigth);
            else
                generic_fixed_add(p, x, path, rigth, left);
        }
        roots.back()->isRed = false;

    }

    template <typename T, typename Func>
    template <typename ChildA, typename ChildB >
    void PersistentSet<T, Func>::
        generic_fixed_add(Nodeptr &p, Nodeptr &x, std::queue<Nodeptr>& path, ChildA childA, ChildB childB)
    {
        Nodeptr &uncle = childB(path.front());
        if (uncle->isRed)
        {
            uncle = copy_node(uncle);
            childB(path.front()) = uncle;
            p->isRed = false;
            uncle->isRed = false;
            path.front()->isRed = true;

            x = path.front();
            path.pop();
            p = path.front(); 
            path.pop();
        } 
        else
        {
            if (x == childB(p))
            {
                std::swap(x, p);
                generic_rotate(path.front(), x, childA, childB);
            }
            auto gp = path.front();
            path.pop();

            std::swap(gp->isRed, p->isRed);
            generic_rotate(path.front(), gp, childB, childA);
        }
    }

}

Client code:

int main()
{
    dts::PersistentSet<int> set;
    for (int i = 0; i < 200; ++i) 
        set.add(rand() % 20);

    for (int i = 0; i < 200; ++i)
        set.remove(rand() % 20);

    for (int i = 0; i < set.history_size(); ++i)
    {
        std::for_each(set.begin(i), set.end(), [](int x) {std::cout << x << ",";});
        std::cout << std::endl;
    }
    system("pause");
    return 0;
}

I implemented for the first time a forward iterator, so it would be nice to get some input on that. (I'm not sure if a nested class is the best approach).

Any kind of review is welcome.

|improve this question
\$\endgroup\$
  • \$\begingroup\$ Mini-pre-review: It would be less distracting if you spelled right right throughout; consider editing the code in-place for that. Can you add some commentary on the distinction between nil and nullptr (and why you think you need it)? Re nested classes, google "SCARY iterators" and evaluate for yourself whether you think it'd be worth implementing them in this case. \$\endgroup\$ – Quuxplusone Feb 10 '16 at 10:06
  • \$\begingroup\$ Nil is there for convenience in dealing with boundary conditions. It can be used as any other node. \$\endgroup\$ – MAG Feb 10 '16 at 11:01
  • \$\begingroup\$ Is this partially persistent, or simply persistent? AFAIK partially persistent refers to the ability to make multiple modifications to the current version. \$\endgroup\$ – Noah Watkins Feb 13 '16 at 19:47
  • \$\begingroup\$ I may have used the term wrong then. Each modification creates a new version. And only the most recent can be modified, all previous ones are read only. \$\endgroup\$ – MAG Feb 13 '16 at 20:35
  • \$\begingroup\$ Hi @MAG your implementation of a persistent red-black tree was invaluable in building out a transactional key-value store that we've been working on. If you found this rb-tree fun to hack on, you might be interested in what we are doing on distributed storage: github.com/noahdesu/zlog/blob/master/src/kvstore/… \$\endgroup\$ – Noah Watkins Feb 1 '17 at 20:39
3
\$\begingroup\$

It's been alluded to in the comments by others already, but I feel it needs mentioning as an answer: Your variable naming should be improved, and some comments would help.

In your entire code I find exactly 2 comments:

        explicit TreeIterator(node n, node pnil) : nil(pnil) //begin
        {
            if (n == nil)
                itr = nil;
            else
            {
                path.push(nil);
                while (n->left != nil)
                {
                    path.push(n);
                    n = n->left;
                }
                itr = n;
            }
        }
        explicit TreeIterator(node pnil) // end
            : itr(pnil), nil(pnil)
        { }

//begin and //end.

That's all there is to explanation of your code. And it needs more explanation than that. Your function names already explain part of the code, although if you're not familiar with the workings, the difference between add, fixed_add and generic_fixed_add might not be immediately clear.

Your class name is PersistentSet, but internally you're using a "Red-black tree" - again, for someone not familiar with the thing you're talking about, these concepts aren't directly related.

You should use comments to explain

  • What your class is (What does "PersistentSet" mean? Is it a set backed by a file/database? Is it a set which maintains ordering?)
  • How to use your class
  • What the parameters mean

That way, if you have a coworker who is not so knowledgeable about this sort of data structure, they can use it by reading your documentation, rather than having to figure it out themselves. Failing that, save them a google and put something like "Implements a persistent set via red-black tree, see wikipedia (wikipedia link to persistent sets) (wikipedia link to red-black tree)". It's a half-assed comment, but at least provides a foothold for someone unfamiliar with the topic.

(Which, if you haven't guessed, would be me - your class is not making clear to me what a persistent set or red-black tree is and whilst I might not need to know, lack of usage documentation makes me have to need to know in order to be able to use it.)

But you can reduce the need of comments by having self-explanatory code. It doesn't solve all the problems, but it certainly alleviates them.

Except you often use single-character or dual-character variable names.

Have a look at this:

template <typename T, typename Func>
template <typename ChildA, typename ChildB >
void PersistentSet<T, Func>::
    generic_fixed_add(Nodeptr &p, Nodeptr &x, std::queue<Nodeptr>& path, ChildA childA, ChildB childB)
{
    Nodeptr &uncle = childB(path.front());
    if (uncle->isRed)
    {
        uncle = copy_node(uncle);
        childB(path.front()) = uncle;
        p->isRed = false;
        uncle->isRed = false;
        path.front()->isRed = true;

        x = path.front();
        path.pop();
        p = path.front(); 
        path.pop();
    } 
    else
    {
        if (x == childB(p))
        {
            std::swap(x, p);
            generic_rotate(path.front(), x, childA, childB);
        }
        auto gp = path.front();
        path.pop();

        std::swap(gp->isRed, p->isRed);
        generic_rotate(path.front(), gp, childB, childA);
    }
}

p and x don't tell me anything about what it's for. In the lower half you also use a variable gp which... also doesn't explain anything. Even although you have split up your code to be relatively small, it's still complicated due to the short variable names. If you were to spend a small amount of time on giving them names to the length of one or two words (like uncle, that one tells me it's a node that is above the child node, but not the parent), the quality would be greatly improved.

Lastly, one of the things I see a lot in your code (about 5 times) is the following:

someVariable = path.front();
path.pop();

And you could write a helper function for that. pop_front_and_return or something like that.

|improve this answer
\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.