<commit_before>#include <vector>
#include <ostream>
#include <boost/optional/optional.hpp>

namespace rbm {

    enum Color {RED, BLACK};
    enum Child {LEFT, RIGHT};

    std::ostream& operator<<(std::ostream &o, Color n) { switch(n){
        case RED: return o<<"R";
        case BLACK: return o<<"B";
        default: return o<<"(invalid value)"; }}

    template <typename Key, typename Value>
    struct Visit {
        Color c;
        Key k;
        boost::optional<Value> v;
        Visit(Color c, Key k) : c(c), k(k) {};
        Visit(Color c, Key k, Value v) : c(c), k(k), v(v) {};
    };

    template <typename Key, typename Value><commit_msg>Comments<commit_after>/*

llrb.hpp
<NAME> <<EMAIL>> <<EMAIL>>
October 2012

A generic implementation of Left-Leaning RedBlack Trees [1,2]. 

Unlike in most RedBlack tree implementations [3,4], the 
tree structure itself is not assumed to reside in memory, and the edges
are not assumed to be pointers. Instead, the LLRB-tree operations are 
defined as traversals over a "Zipper" [5] machine, which exposes a few 
instructions for traversing and modifying a local context within a tree.

Specializations include:

1. Default/identity: an ordinary pointer-based tree in memory 
   (see c_redblack_main.cpp)

2. Merkle trees: the tree is augmented with hash digests stored
   at each node.

3. Merkle validation: the tree does not reside in memory, but
   instead the operations are "simulated" using an (untrusted)
   Verification Object (a sequence of data containing just the
   nodes visited, in order)


[1] Left-Leaning Red Black Trees. 
<NAME>
http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf
http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf

[2] Purely Functional Left-Leaning Red Black Trees
<NAME>. 2011
http://www.mew.org/~kazu/proj/red-black-tree/

[3] sys/tree.h  (in BSD standard lib)
<NAME>. 2002. 
http://fxr.watson.org/fxr/source/sys/tree.h

[4] rb.h
<NAME>. 2010
http://www.canonware.com/rb/

[5] Functional Pearl: The Zipper
<NAME>. 1996
http://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf

*/


#include <vector>
#include <ostream>
#include <boost/optional/optional.hpp>


namespace rbm {

    enum Color {RED, BLACK};
    enum Child {LEFT, RIGHT};

    std::ostream& operator<<(std::ostream &o, Color n) { switch(n){
        case RED: return o<<"R";
        case BLACK: return o<<"B";
        default: return o<<"(invalid value)"; }}

    template <typename Key, typename Value>
    struct Visit {
        Color c;
        Key k;
        boost::optional<Value> v;
        Visit(Color c, Key k) : c(c), k(k) {};
        Visit(Color c, Key k, Value v) : c(c), k(k), v(v) {};
    };

    template <typename Key, typename Value>
{'fraction_non_alphanumeric': 0.13467153284671532, 'fraction_numerical': 0.013503649635036497, 'mean_word_length': 3.2364760432766615, 'pattern_counts': {'":': 0, '<': 41, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 5, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '7435887', 'n_tokens_mistral': 963, 'n_tokens_neox': 898, 'n_words': 301}