Hi everyone!

Some of you may remember my entry about policy based data structures. In addition to a review article on these structures, I also wanted to write about the possibility of using your own Node_Update class. Then I hadn't enough time for it, but now I can and I want to catch up and share with you some new knowledge.

So, let's start. Node_update class should looks like this:

template<class Node_CItr,
	 class Node_Itr,
	 class Cmp_Fn,
	 class _Alloc>
struct my_node_update
{
    typedef my_type metadata_type;

    void operator()(Node_Itr it, Node_CItr end_it)
    {
        ...
    }
};

Let's consider how this class works. Policy based tree, which is using update policy will additionally keep in node one variable of type my_type. When the tree is rebuilt, part of the metadata spoils, so for each node, which could be damaged applied the operator (). At the same time this operator begins to be applied firstly to the leaves, that is, we guarantee that if () is applied to the node, its metadata can be damaged, but the metadata of its children will be intact. The function has two arguments let's learn them.

Node_Itr it & mdash; iterator pointing to the node from which was called (). Node_CItr end_it & mdash; const-iterator to the node referenced by all NIL-tops. Node_iterator has the following methods:

1. get_l_child () & mdash; returns node_iterator on left child or node_end, if it does not exist.
2. get_r_child () is the same for the right child.
3. get_metadata () & mdash; returns const reference to metadata stored in the node.
4. * & mdash; dereference. Returns reference to a regular iterator of this item in set.

For clarity, I give an example of the function () to support the size of the subtree starting at the node:

    void operator()(Node_Itr it, Node_CItr end_it)
    {
        auto l=it.get_l_child();
        auto r=it.get_r_child();
        int left=0,right=0;
        if(l!=end_it) left =l.get_metadata();
        if(r!=end_it) right=r.get_metadata();
        const_cast<int&>(it.get_metadata())=left+right+1;
    }

Well, we learned how to update invariants. Now let's learn how to use them.In order to do this we note that any public-methods of node_update automatically become public in tree. In addition, we have access to all of the virtual methods in the base class, if we declare them as virtual in node_update. In this regard, we add to our class the following lines:

    virtual Node_CItr
    node_begin() const = 0;
 
    virtual Node_CItr
    node_end() const = 0;

This will give us the opportunity to gain direct access to the tree. In particular, node_begin() will point to the root of the tree, and node_end() to the place where all NIL-nodes are. Finally, we are ready to entirely manage the metadata at the nodes of our tree. For example, here is the function that finds order of int key in set:

    int order_of_key(int x)
    {
        int ans=0;
        auto it=node_begin();
        while(it!=node_end())
        {
            auto l=it.get_l_child();
            auto r=it.get_r_child();
            if(Cmp_Fn()(x,**it))
            {
                it=l;
            }
            else
            {
                ans++;
                if(l!=node_end()) ans+=l.get_metadata();
                it=r;
            }
        }
        return ans;
    }

Currently I have two examples of problems solved with node_update it is task D (7485682) from recent contest and solution of the problem GCD2010 from the timus (sol). In the near future I will try to find and solve more problems with update policy and add to the article. If there is a problem that you think can be well solved by the structure & mdash; I will be glad if you lay them out now :)