from collections import Counter
X = [(0,0), (1,1), (2,0), (3,1), (4,0), (5,1)]
y = [0,0,1,1,1,0]
# Fixed recorded bootstrap draws and feature choices for this teaching example.
specs = [([0,0,1,3,4,5],0), ([1,2,2,3,4,5],1), ([0,1,2,3,3,5],0)]
def gini(a):
    return 1-sum((c/len(a))**2 for c in Counter(a).values())
def fit_stump(indices, feature):
    values = sorted({X[i][feature] for i in indices})
    options=[]
    for a,b in zip(values,values[1:]):
        t=(a+b)/2
        left=[y[i] for i in indices if X[i][feature] <= t]
        right=[y[i] for i in indices if X[i][feature] > t]
        score=(len(left)*gini(left)+len(right)*gini(right))/len(indices)
        options.append((score,t,sum(left)/len(left),sum(right)/len(right)))
    _,threshold,pl,pr=min(options)
    return feature,threshold,pl,pr
query=(2.5,0)
forest=[fit_stump(indices,j) for indices,j in specs]
probs=[pl if query[j] <= t else pr for j,t,pl,pr in forest]
mean=sum(probs)/len(probs)
print('stumps',forest)
print('tree p(class1)',probs,'mean',mean)
print('out-of-bag indices', [sorted(set(range(len(y)))-set(idx)) for idx,_ in specs])
assert abs(mean-29/36) < 1e-12
assert len(set(specs[0][0])) < len(specs[0][0])