from cdi import *

def select(X, W) :
    W = normalize(W)
    r = rd_float()

    aw = 0  #accumulated weight
    for w in range(len(W)) :
        if (r <= W[w] + aw) : return X[w]
        else : aw += W[w]

    return 'cdi/impossible error'   #if we get to the last step, r <= 1 always true

def test_select(X, W, iters = 1000) :
    L = []
    for _ in range(iters) : L += select(X, W)
    for x in range(len(X)) :
        f = len([e for e in L if e == X[x]]) / len(L)
        print(X[x], 'has prob.', W[x], ', and has appeared', f, 'times')

#test the select function, see if it selects elements with according to their
#expected probability
test_select('ABC', [0.1, 0.3, 0.6])