def draw_from( c ):
    """
    returns a draw from a probability distribution
    defined by the cumulative distribution c.
    c is a list of `value, cumulative distribution' pairs
    created in randomwalk1.

    For a fair coin, the cumulative distribution
    is 0.5, 1.0. For a drunk man's walk, the values are -1 and +1.
    
    >>> draw_from( [(-1,0.5),(1,1.0)] )
    -1
    >>> draw_from( [(-1,0.5),(1,1.0)] )
    1
    """
    import random
    u = random.random()
    for pair in c:
        if u<=pair[1]:
            return pair[0]
    print "BUG! This line should never be reached. c,u are:"
    print c
    print u
    assert( False )
    pass
    
def randomwalk1( R, T , p , period=1 , \
               when_to_stop_pausing=20 , \
               title='Random walks' ):
    """
    Show R random walks, running for time T.
    The probability distribution
    of each step is defined with a list of tuples
    in p.

    period is the spacing between points logged.

    This routine displays each random walk with Gnuplot
    as soon as the walk is complete.
    
    example:
    >>> from randomwalk1 import *
    >>> randomwalk1( 12, 1000 , [(-1,0.5),(1,0.5)] )
    """

    print "Random walk version 1.1"
    import scipy as S
    import Gnuplot, Gnuplot.funcutils
    g = Gnuplot.Gnuplot(persist=1) #(debug=1, persist=1)
    g.title(title) 
    g('set data style line') 
    keep_pausing=1

    if when_to_stop_pausing > R-1 :
        when_to_stop_pausing = R-1 # no point in pausing when r=R-1
        
    ## work out the cumulative distribution
    cum=0.0 ; c = []
    for pair in p:
        cum += pair[1]
        c.append( (pair[0], cum) )

    assert( cum < 1.01 and c > 0.999999999999 )
    for r in range(R):
        x = 0
        xr=[]
        for t in range(T):
            x += draw_from( c ) # make a random step
            if ( t%period == 0 or t<2 ):
                xr.append( [t,x] )  
        
        if(r==0):
            g.plot(xr)
        else    :
            g.replot(xr)
        # end of plot
        if(keep_pausing and (r<when_to_stop_pausing)):
            if ( raw_input('Press return (or 0 to stop pausing)...\n') == '0' ):
                keep_pausing = 0 
            pass
        pass
    return g # pass back a handle to the plot so that it can be tweaked.

def test():    
    randomwalk1( 7, 1000, [(-1,0.5),(1,0.5)] )
    raw_input('Press return to continue ...\n')
    randomwalk1( 7, 100000, [(-1,0.5),(1,0.5)] , 10 )
    raw_input('Press return to continue ...\n')
    randomwalk1( 7, 1000000, [(-1,0.5),(1,0.5)] ,100)
    raw_input('Press return to continue ...\n')
    g = randomwalk1( 27, 1000000, [(-1,0.5),(1,0.5)] ,500,-1)
    g('set logscale x')
    g.replot()
    pass

def test2():    
    g = randomwalk1( 27, 1000000, [(-1,0.5),(1,0.5)] ,500,-1)
    pass

if __name__ == '__main__': test2()