markov_map.cpp

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

#include "markov_map.h"

markov_tree::node::node(markov_tree::node *parent,
            const std::string& value) :
    left_count(0), node_count(0), right_count(0),
    left(NULL), node_parent(parent), right(NULL), balance(0) {
    this->node_value = new char[value.size() + 1];
    strcpy(const_cast<char*>(this->node_value), value.c_str());
}  /* markov_tree::node::node() */

markov_tree::node::node(const markov_tree::node& node) {
    if (node.node_value == NULL) {
    this->node_value = NULL;
    } else {
    this->node_value = new char[strlen(node.node_value) + 1];
    strcpy(const_cast<char*>(this->node_value), node.node_value);
    }

    this->left_count = node.left_count;
    this->node_count = node.node_count;
    this->right_count = node.right_count;

    if (node.left == NULL) {
    this->left = NULL;
    } else {
    this->left = new markov_tree::node(*node.left);
    this->left->node_parent = this;
    }
    this->node_parent = node.node_parent;
    if (node.right == NULL) {
    this->right = NULL;
    } else {
    this->right = new markov_tree::node(*node.right);
    this->right->node_parent = this;
    }

    this->balance = node.balance;
}  /* markov_tree::node::node(const markov_tree::node&) */

markov_tree::node::~node() {
    if (this->node_value != NULL) {
    delete this->node_value;
    }
    if (this->left != NULL) {
    delete this->left;
    }
    if (this->right != NULL) {
    delete this->right;
    }
}  /* markov_tree::node::~node() */

markov_tree::node& markov_tree::node::operator=(const markov_tree::node& node) {
    if (this != &node) {
    if (this->node_value != NULL) {
        delete this->node_value;
        this->node_value = NULL;
    }
    if (node.node_value != NULL) {
        size_t len = strlen(node.node_value) + 1;

        this->node_value = new char[len];
        strcpy(const_cast<char*>(this->node_value), node.node_value);
    }

    this->left_count = node.left_count;
    this->node_count = node.node_count;
    this->right_count = node.right_count;

    if (this->left != NULL) {
        delete this->left;
        this->left = NULL;
    }
    if (node.left != NULL) {
        this->left = new markov_tree::node(*node.left);
        this->left->node_parent = this;
    }
    this->node_parent = node.node_parent;
    if (this->right != NULL) {
        delete this->right;
        this->right = NULL;
    }
    if (node.right != NULL) {
        this->right = new markov_tree::node(*node.right);
        this->right->node_parent = this;
    }

    this->balance = node.balance;
    }
    return *this;
}  /* markov_tree::node::operator=(const markov_tree::node&) */

void markov_tree::node::rebalance(int balance_increment) {
    this->balance += balance_increment;
    if (this->balance == -2) {
    /* Right subtree outweighs left subtree. */
    markov_tree::node *tmp;
    if (this->right->balance == 1) {
        /* Right rotation with R as root (right-left) */
        tmp = this->right->left;

        tmp->right->node_parent = this->right;
        this->right->left = tmp->right;
        this->right->left_count = tmp->right_count;

        this->right->node_parent = tmp;
        tmp->right = this->right;
        tmp->right_count +=
        this->right->node_count + this->right->right_count;

        tmp->node_parent = this;
        this->right = tmp;

        if (this->right->balance == -1) {
        this->right->balance = -2;
        this->right->right->balance = 0;
        } else if (this->right->balance == 0) {
        this->right->balance = -1;
        this->right->right->balance = 0;
        } else {
        this->right->balance = -1;
        this->right->right->balance = -1;
        }
    }
    /* Left rotation with P as root */
    tmp = this->right;

    tmp->left->node_parent = this;
    this->right = tmp->left;
    this->right_count = tmp->left_count;

    tmp->node_parent = this->node_parent;
    if (this->node_parent != NULL) {
        if (this->node_parent->right == this) {
        this->node_parent->right = tmp;
        balance_increment = -1;
        } else {
        this->node_parent->left = tmp;
        balance_increment = 1;
        }
    }

    this->node_parent = tmp;
    tmp->left = this;
    tmp->left_count += this->left_count + this->node_count;

    if (tmp->balance == -2) {
        tmp->balance = 0;
        this->balance = 1;
    } else if (tmp->balance == -1) {
        tmp->balance = 0;
        this->balance = 0;
    }
    } else if (this->balance == 2) {
    /* Left subtree outweighs right subtree. */
    markov_tree::node *tmp;
    if (this->left->balance == -1) {
        /* Left rotation with R as root (right-left) */
        tmp = this->left->right;

        tmp->left->node_parent = this->left;
        this->left->right = tmp->left;
        this->left->right_count = tmp->left_count;

        this->left->node_parent = tmp;
        tmp->left = this->left;
        tmp->left_count +=
        this->left->left_count + this->left->node_count;

        tmp->node_parent = this;
        this->left = tmp;

        if (this->left->balance == 1) {
        this->left->balance = 2;
        this->left->left->balance = 0;
        } else if (this->left->balance == 0) {
        this->left->balance = 1;
        this->left->left->balance = 0;
        } else {
        this->left->balance = 1;
        this->left->left->balance = 1;
        }
    }
    /* Right rotation with P as root */
    tmp = this->left;

    tmp->right->node_parent = this;
    this->left = tmp->right;
    this->left_count = tmp->right_count;

    tmp->node_parent = this->node_parent;
    if (this->node_parent != NULL) {
        if (this->node_parent->right == this) {
        this->node_parent->right = tmp;
        } else {
        this->node_parent->left = tmp;
        }
    }

    this->node_parent = tmp;
    tmp->right = this;
    tmp->right_count += this->node_count + this->right_count;

    tmp->balance = 0;
    tmp->left->balance = 0;
    tmp->right->balance = 0;

    if (tmp->balance == 2) {
        tmp->balance = 0;
        this->balance = -1;
    } else if (tmp->balance == 1) {
        tmp->balance = 0;
        this->balance = 0;
    }
    } else if (this->node_parent != NULL) {
    if (this->node_parent->left == this) {
        this->node_parent->rebalance(1);
    } else if (this->node_parent->right == this) {
        this->node_parent->rebalance(-1);
    }
    }
}  /* markov_tree::node::rebalance() */

void markov_tree::node::fix_count(const markov_tree::node* child) {
    if (child == this->left) {
    this->left_count++;
    } else {
    this->right_count++;
    }
    if (this->node_parent != NULL) {
    this->node_parent->fix_count(this);
    }
}  /* markov_tree::node::fix_count(const markov_tree::node*) */

inline double markov_tree::node::scaled_left_count() const {
    return (double)this->left_count /
    (this->left_count + this->node_count + this->right_count);
}  /* markov_tree::node::scaled_left_count() */

inline double markov_tree::node::scaled_right_count() const {
    return (double)this->right_count /
    (this->left_count + this->node_count + this->right_count);
}  /* markov_tree::node::scaled_right_count() */

inline const std::string markov_tree::node::value() const {
    return std::string(this->node_value);
}  /* markov_tree::node::value() */

inline unsigned long markov_tree::node::count() const {
    return this->node_count;
}  /* markov_tree::node::count() */

const markov_count& markov_tree::node::add(const std::string& x) {
    assert(this->node_value != NULL);
    int order = strcmp(x.c_str(), this->node_value);
    if (order == 0) {
    /* We have a match. */
    this->node_count++;
    this->node_parent->fix_count(this);
    return *this;
    } else if (order < 0) {
    if (this->left == NULL) {
        this->left = new markov_tree::node(this, x);
        this->rebalance(1);  /* Left subtree is now one level deeper. */
    }
    return this->left->add(x);
    } else if (order > 0) {
    if (this->right == NULL) {
        this->right = new markov_tree::node(this, x);
        this->rebalance(-1);  /* Right subtree is now one level deeper. */
    }
    return this->right->add(x);
    } else {
    /* This should never happen. */
    assert(false);
    }
}  /* markov_tree::node::add(const char*) */

const char* markov_tree::node::random(int seed) const {
    if (seed < 0 || seed > RAND_MAX) {
    seed = RAND_MAX;
    }
    double scaled_seed = ((double)seed / ((unsigned int)RAND_MAX + 1));
    if (scaled_seed < this->scaled_left_count()) {
    /* Left of the left bound, so pick from that. */
    return this->left->random((double)seed / this->scaled_left_count());
    } else if ((1.0 - scaled_seed) <= this->scaled_right_count()) {
    /* Right of the right bound, so pick from that. */
    return this->right->random(
        RAND_MAX - (double)(RAND_MAX - seed) / this->scaled_right_count());
    } else {
    /* In the bounds of this node, so pick it. */
    return this->node_value;
    }
}  /* markov_tree::node::random(int) */

inline markov_tree::markov_tree() : root(NULL) {

}  /* markov_tree::markov_tree() */

inline markov_tree::markov_tree(const markov_tree& tree) : root(NULL) {
    if (tree.root != NULL) {
    this->root = new markov_tree::node(*tree.root);
    }
}  /* markov_tree::markov_tree(const markov_tree&) */

inline markov_tree::~markov_tree() {
    if (this->root != NULL) {
    delete this->root;
    }
}  /* markov_tree::~markov_tree() */

inline markov_tree& markov_tree::operator=(const markov_tree& tree) {
    if (this != &tree) {
    if (this->root != NULL) {
        delete this->root;
        this->root = NULL;
    }
    if (tree.root != NULL) {
        this->root = new markov_tree::node(*tree.root);
    }
    }
    return *this;
}  /* markov_tree::operator=(const markov_tree&) */

inline const markov_count& markov_tree::add(const std::string& x) {
    if (this->root == NULL) {
    /* This is the first entry ever inserted into the tree. */
    this->root = new markov_tree::node(NULL, x);
    }
    return this->root->add(x);
}  /* markov_tree::add(const std::string&) */

inline const char* markov_tree::random() const {
    if (this->root == NULL) {
    return "";
    } else {
    return this->root->random(rand());
    }
}  /* markov_tree::random() */

inline markov_map::markov_map() : trees() {

}  /* markov_map::markov_map() */

inline markov_map::markov_map(const markov_map& map) : trees(map.trees) {

}  /* markov_map::markov_map(const markov_map&) */

inline markov_map& markov_map::operator=(const markov_map& map) {
    this->trees = map.trees;
    return *this;
}  /* markov_map::operator=(const markov_map&) */

inline const markov_count& markov_map::add(const std::string& x, const std::string& y) {
    /* Use x as the key to get the probability tree. */
    return this->trees[x.c_str()].add(y);
}  /* markov_map::add(const std::string&, const std::string&) */

inline const std::string markov_map::random(const std::string& x) const {
    stdext::hash_map<const char*, markov_tree, stdext::hash<const char*>, eqstr>::const_iterator iter = this->trees.find(x.c_str());
    if (iter == this->trees.end()) {
    return std::string();
    } else {
    return std::string(iter->second.random());
    }
}  /* markov_map::random(const std::string& x) */