markov_map.h

/* -*- mode: c++ -*- */
#ifndef __MARKOV_MAP_H
#define __MARKOV_MAP_H 1

#include <cstring>
#include <string>
#include <ext/hash_map>

namespace stdext = __gnu_cxx;

/** A value and the number of observations of the value. */
class markov_count {
public:
    /** The value. */
    virtual const std::string value() const = 0;
    /** The number of observations of the value. */
    virtual unsigned long count() const = 0;
};

struct eqstr {
    bool operator()(const char* s1, const char* s2) const {
    return strcmp(s1, s2) == 0;
    }
};

/** A tree for storing Markov counts for a single key. */
class markov_tree {
public:
    /** A node in a markov_tree. */
    class node : public markov_count {
    private:
    const char* node_value;
    unsigned long left_count, node_count, right_count;
    node *left, *node_parent, *right;
    int balance;

    /** Rebalance this node in an AVL tree. */
    void rebalance(int balance_increment);
    /** Fix the count of the given node. */
    void fix_count(const node* child);

    /** Get the left_count scaled to a probability. */
    double scaled_left_count() const;
    /** Get the right_count scaled to a probability. */
    double scaled_right_count() const;
    public:
    /** Create a new node with a node_count of 0 and no children. */
    node(node* parent, const std::string& value);
    /** The copy constructor. */
    node(const node&);
    /** The destructor. */
    ~node();
    /** The assignment operator. */
    node& operator=(const node&);
    /** Add an instance of x into the subtree having this node as root. */
    const markov_count& add(const std::string& x);
    /** Select a "random" value in this subtree deterministically. */
    const char* random(int seed) const;

    /** The value. */
    const std::string value() const;
    /** The number of observations of the value. */
    unsigned long count() const;
    };
private:
    node* root;
public:
    /** Create an empty markov_tree. */
    markov_tree();
    /** The copy constructor. */
    markov_tree(const markov_tree&);
    /** The destructor. */
    ~markov_tree();
    /** The assignment operator. */
    markov_tree& operator=(const markov_tree&);
    /** Add an instance of x into the markov_tree. */
    const markov_count& add(const std::string& x);
    /** Select a value at random. */
    const char* random() const;
};

/** A map for storing Markov counts for a key-pair. */
class markov_map {
private:
    stdext::hash_map<const char*, markov_tree, stdext::hash<const char*>, eqstr> trees;
public:
    /** Create an empty markov_map. */
    markov_map();
    /** The copy constructor. */
    markov_map(const markov_map&);
    /** The assignment operator. */
    markov_map& operator=(const markov_map&);
    /** Add an instance of y given x into the markov_map. */
    const markov_count& add(const std::string& x, const std::string& y);
    /** Select a value at random given x as a prior. */
    const std::string random(const std::string& x) const;
};

#endif  /* __MARKOV_MAP_H */