Persistent set (Red black tree)

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.

```
#pragma once

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

namespace dts
{

template >
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::ptrdiff_t,
const T*,
const T&>
{
using node = typename dts::PersistentSet, Func>::Nodeptr;
node itr;
node nil;
std::stack 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);

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 
template 
void PersistentSet::
    generic_fixed_add(Nodeptr &p, Nodeptr &x, std::queue& 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.

StackExchange Code Review Q#119444, answer score: 4