MarkovDecision/Samplingtree.cpp at master · jrahim/MarkovDecision · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
//
// Created by jamal on 30/09/2018.
//

#include <math.h>
#include "Samplingtree.h"
#include <iostream>
#include <stdlib.h>
#include <time.h>

Samplingtree::Samplingtree(int n, double* inprobs) {

    int n2 = (n > 1) ? pow(2, ceil(log2(n))) : 2;
    numProbs = n2;
    numOrgProbs = n;
    probs = new SamplingTreeNode*[n2];
    for (int i = 0; i < n2; i++) {
        probs[i] = new SamplingTreeNode;
        if (i < n) {
            probs[i]->setProbability(inprobs[i]);
            probs[i]->setIndex(i);
        }
    }
    makeTree();
}

void Samplingtree::makeTree() {

    SamplingTreeNode** currentlayer = probs;
    SamplingTreeNode** nextlayer = nullptr;
    for (int i = log2(numProbs); i > 0; i--) {
        const int sizee = pow(2, i-1);
        nextlayer = new SamplingTreeNode*[sizee];
        int j = 0;
        while (j < (pow(2, i))) {
            auto* newNode = new SamplingTreeNode;
            newNode->setLeftChild(currentlayer[j]);
            newNode->setRightChild(currentlayer[j+1]);
            newNode->setProbability(currentlayer[j]->getProbability() + currentlayer[j+1]->getProbability());
            currentlayer[j]->setParent(newNode);
            currentlayer[j+1]->setParent(newNode);
            nextlayer[j/2] = newNode;
            j += 2;
        }
        if (i != log2(numProbs)) {
            delete [] currentlayer;
        }
        currentlayer = nextlayer;
        if (i==1) {
            root = nextlayer[0];
        }
    }
}

void Samplingtree::traversePostOrderHelper(SamplingTreeNode* node) {
    // first recur on left subtree
    if (node->getLeftChild() != nullptr) {
        traversePostOrderHelper(node->getLeftChild());

        // then recur on right subtree
        traversePostOrderHelper(node->getRightChild());
    }

    // now deal with the node
    cout << node->getProbability() << " ";
}

void Samplingtree::traversePostOrder() {
    traversePostOrderHelper(root);
    cout << endl;
}

void Samplingtree::updateHelper(SamplingTreeNode *node) {
    if (node->getLeftChild() != nullptr) {
        updateHelper(node->getLeftChild());
        updateHelper(node->getRightChild());
        node->recalculateProbability();
    }
}

void Samplingtree::updateProb(double * newprob) {
    for (int i = 0; i < numOrgProbs; i++) {
        probs[i]->setProbability(newprob[i]);
    }
    updateHelper(root);
}

void Samplingtree::updateProb(int index, double newprob) {
    SamplingTreeNode *node = probs[index];
    node->setProbability(newprob);
    while (node->getParent() != nullptr) {
        node = node->getParent();
        node->recalculateProbability();
    }
}

void Samplingtree::deleteTreeHelper(SamplingTreeNode* node) {
    // first recur on left subtree
    if (node->getLeftChild() != nullptr) {
        deleteTreeHelper(node->getLeftChild());

        // then recur on right subtree
        deleteTreeHelper(node->getRightChild());
    }

    // now deal with the node
    delete node;
}

void Samplingtree::deleteTree() {
    deleteTreeHelper(root);
}

int Samplingtree::performSampling() {
    SamplingTreeNode* node = root;
    while (node->getLeftChild() != nullptr) {
        SamplingTreeNode* leftChild = node->getLeftChild();
        double prob = leftChild->getProbability() / node->getProbability();
        double rndnum = (double) rand() / RAND_MAX;
        if (rndnum < prob) {
            node = leftChild;
        } else {
            node = node->getRightChild();
        }
    }
    return node->getIndex();
}