sequential_tree.cpp

template<class Key, class Value>
class specialized_binary_tree_map{
public:
    typedef Key key_type;
    typedef Value value_type;
    struct item{
        item() : key(), value(){
            for(std::size_t i = 0; i < 2; ++i){ link[i] = nullptr; }
            parent = nullptr;
        }

        ~item(){
            for(std::size_t i = 0; i < 2; ++i){ delete link[i]; }
        }

        item *link[2], *parent;
        key_type key;
        value_type value;
    };

    typedef std::function<void(item&)> scanner;

    specialized_binary_tree_map(){
        root = nullptr;
    }
    
    ~specialized_binary_tree_map(){
        delete root;
    }

    template<class Compare>
    void add(const key_type &key, const value_type &value, Compare cmp){
        item **ptr = &root, *prev = nullptr;
        while(*ptr){
            prev = *ptr;
            int n;
            if(cmp(key, (*ptr)->key)){
                n = 0;
            }else{
                n = 1;
            }
            ptr = &((*ptr)->link[n]);
        }
        *ptr = new item;
        (*ptr)->parent = prev;
        (*ptr)->key = key;
        (*ptr)->value = value;
    }

private:
    item *root;
};

struct cmp{
    cmp() : idx(0){}
    std::size_t idx;
    bool operator()(const std::string &x, const std::string &y){
        for(; ; ){
            if(idx == x.size()){
                if(idx == y.size()){
                    return false;
                }
                if(idx < y.size()){
                    return true;
                }
            }
            if(idx == y.size()){
                return false;
            }
            unsigned char xc = x[idx], yc = y[idx];
            if(xc == yc){ ++idx; }else{
                if(xc < yc){
                    return true;
                }else{
                    if(idx > 0){ --idx; }
                    return false;
                }
            }
        }
    }
};