def _accumulate_random(count, found, oldthing, newthing):
    """This performs on-line random selection.

    We have a stream of objects

        o_1,c_1; o_2,c_2; ...

    where there are c_i equivalent objects like o_1.  We'd like to pick
    a random object o uniformly at random from the list

        [o_1]*c_1 + [o_2]*c_2 + ...

    (actually, this algorithm allows arbitrary positive weights, not
    necessarily integers)  without spending the time&space to actually
    create that list.  Luckily, the following works:

        thing = None
        c_tot
        for o_n, c_n in things:
            c_tot += c_n
            if randint(1,c_tot) <= c_n:
                thing = o_n

    This function is written in an accumulator format, so it can be
    used one call at a time:

    EXAMPLE:
        > thing = None
        > count = 0
        > for i in range(10):
        >     c = 10-i
        >     count, thing = accumulate_random(count,c,thing,i)


    INPUTS:
        count: integer, sum of weights found before newthing
        found: integer, weight for newthing
        oldthing: previously selected object (will never be selected
                  if count == 0)
        newthing: incoming object

    OUTPUT:
        (newcount, pick): newcount is count+found, pick is the newly
                          selected object.
    """
    if randint(1, count + found) <= found:
        return count + found, newthing
    else:
        return count + found, oldthing
This performs on-line random selection.

    We have a stream of objects

        o_1,c_1; o_2,c_2; ...

    where there are c_i equivalent objects like o_1.  We'd like to pick
    a random object o uniformly at random from the list

        [o_1]*c_1 + [o_2]*c_2 + ...

    (actually, this algorithm allows arbitrary positive weights, not
    necessarily integers)  without spending the time&space to actually
    create that list.  Luckily, the following works:

        thing = None
        c_tot
        for o_n, c_n in things:
            c_tot += c_n
            if randint(1,c_tot) <= c_n:
                thing = o_n

    This function is written in an accumulator format, so it can be
    used one call at a time:

    EXAMPLE:
        > thing = None
        > count = 0
        > for i in range(10):
        >     c = 10-i
        >     count, thing = accumulate_random(count,c,thing,i)


    INPUTS:
        count: integer, sum of weights found before newthing
        found: integer, weight for newthing
        oldthing: previously selected object (will never be selected
                  if count == 0)
        newthing: incoming object

    OUTPUT:
        (newcount, pick): newcount is count+found, pick is the newly
                          selected object.