import sys

class Hashable:
    def __hash__(self): return id(self)
    def __cmp__(self, other): return id(self)-id(other)

class Hypo(Hashable, dict):
    """a hypothesis maps from possible values of p to the
    likelihood of the value (or probability, if normalized).
    p is the probability of getting heads.
    """
    def update(self, datum):
        """update this hypothesis with this data;
        datum is either 'a' or 'b'
        """
        for p in self:
            if datum == 'a':
                likelihood = p
            else:
                likelihood = 1-p
            self[p] *= likelihood

    def normalize(self):
        """normalize this hypothesis so that the probabilities
        sum to 1.0
        """
        nc = self.normalizing_constant()
        for p in self:
            self[p] /= nc

    def normalizing_constant(self):
        """compute the normalizing constant for this hypothesis,
        which is the sum of the likelihoods of the micro-hypotheses.
        """
        return sum(self.itervalues())


def make_uniform(n=10):
    """make a hypothesis with n+1 equally spaced micro-hypotheses
    between p=0 and p=1, all with the same likelihood
    """
    h = Hypo()
    low = 0.0
    high = 1.0
    
    for i in range(n+1):
        p = low + (high-low) * i / n
        h[p] = 1.0
    h.normalize()
    return h

def main(name, *args):

    h = make_uniform(1000)

    data = 'aba'
    for datum in data:
        h.update(datum)
    h.normalize()
    
    t = h.items()
    t.sort()
    sum = 0
    for p, like in t:
        sum += like
        print p, sum
 


if __name__ == '__main__':
    main(*sys.argv)