import numpy as np
import random
from math import log
import log_add

# Takes as input a log probability vector. The base of the logarithm is 2.
# Returns a sampled position according to the corresponding log probabilities
# Uses the formula from
# http://blog.smola.org/post/987977550/log-probabilities-semirings-and-floating-point-numbers
def sample_from_log_prob(A):
    max_log_prob = max(A)
    C = [A[0]]
    for a in A[1:]:
        C.append(log_add(C[-1], a))
    C_pos = [ -c for c in reversed(C)]
    r = log(random.random(),2)
    pos = np.searchsorted(C_pos,-r)
    return len(C) - pos