<s> """<STR_LIT>""" <EOL> from __future__ import division , print_function <EOL> import cython <EOL> import time <EOL> import operator <EOL> import optparse <EOL> import random <EOL> random . seed ( <NUM_LIT> ) <EOL> from functools import reduce <EOL> if not cython . compiled : <EOL> from math import sqrt <EOL> class GVector ( object ) : <EOL> def __init__ ( self , x = <NUM_LIT:0> , y = <NUM_LIT:0> , z = <NUM_LIT:0> ) : <EOL> self . x = x <EOL> self . y = y <EOL> self . z = z <EOL> def Mag ( self ) : <EOL> return sqrt ( self . x ** <NUM_LIT:2> + self . y ** <NUM_LIT:2> + self . z ** <NUM_LIT:2> ) <EOL> def dist ( self , other ) : <EOL> return sqrt ( ( self . x - other . x ) ** <NUM_LIT:2> + <EOL> ( self . y - other . y ) ** <NUM_LIT:2> + <EOL> ( self . z - other . z ) ** <NUM_LIT:2> ) <EOL> @ cython . locals ( self = "<STR_LIT>" , other = "<STR_LIT>" ) <EOL> def __add__ ( self , other ) : <EOL> if not isinstance ( other , GVector ) : <EOL> raise ValueError ( "<STR_LIT>" + str ( type ( other ) ) ) <EOL> v = GVector ( self . x + other . x , self . y + other . y , self . z + other . z ) <EOL> return v <EOL> @ cython . locals ( self = "<STR_LIT>" , other = "<STR_LIT>" ) <EOL> def __sub__ ( self , other ) : <EOL> return self + other * - <NUM_LIT:1> <EOL> @ cython . locals ( self = "<STR_LIT>" , other = cython . double ) <EOL> def __mul__ ( self , other ) : <EOL> v = GVector ( self . x * other , self . y * other , self . z * other ) <EOL> return v <EOL> __rmul__ = __mul__ <EOL> @ cython . locals ( other = "<STR_LIT>" , l1 = cython . double , l2_ = cython . double ) <EOL> def linear_combination ( self , other , l1 , l2 = None ) : <EOL> l2_ = <NUM_LIT:1> - l1 if l2 is None else l2 <EOL> v = GVector ( self . x * l1 + other . x * l2_ , <EOL> self . y * l1 + other . y * l2_ , <EOL> self . z * l1 + other . z * l2_ ) <EOL> return v <EOL> def __str__ ( self ) : <EOL> return "<STR_LIT>" % ( self . x , self . y , self . z ) <EOL> def __repr__ ( self ) : <EOL> return "<STR_LIT>" % ( self . x , self . y , self . z ) <EOL> def GetKnots ( points , degree ) : <EOL> knots = [ <NUM_LIT:0> ] * degree + range ( <NUM_LIT:1> , len ( points ) - degree ) <EOL> knots += [ len ( points ) - degree ] * degree <EOL> return knots <EOL> class Spline ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , points , degree = <NUM_LIT:3> , knots = None ) : <EOL> """<STR_LIT>""" <EOL> if knots is None : <EOL> self . knots = GetKnots ( points , degree ) <EOL> else : <EOL> if len ( points ) > len ( knots ) - degree + <NUM_LIT:1> : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> elif len ( points ) < len ( knots ) - degree + <NUM_LIT:1> : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> last = knots [ <NUM_LIT:0> ] <EOL> for cur in knots [ <NUM_LIT:1> : ] : <EOL> if cur < last : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> last = cur <EOL> self . knots = knots <EOL> self . points = points <EOL> self . degree = degree <EOL> def GetDomain ( self ) : <EOL> """<STR_LIT>""" <EOL> return ( self . knots [ self . degree - <NUM_LIT:1> ] , <EOL> self . knots [ len ( self . knots ) - self . degree ] ) <EOL> @ cython . locals ( ik = cython . long , ii = cython . long , I = cython . long , <EOL> ua = cython . long , ub = cython . long , u = cython . double , <EOL> dom = ( cython . long , cython . long ) ) <EOL> def __call__ ( self , u ) : <EOL> """<STR_LIT>""" <EOL> dom = self . GetDomain ( ) <EOL> if u < dom [ <NUM_LIT:0> ] or u > dom [ <NUM_LIT:1> ] : <EOL> raise ValueError ( "<STR_LIT>" ) <EOL> if u == dom [ <NUM_LIT:0> ] : <EOL> return self . points [ <NUM_LIT:0> ] <EOL> if u == dom [ <NUM_LIT:1> ] : <EOL> return self . points [ - <NUM_LIT:1> ] <EOL> I = self . GetIndex ( u ) <EOL> d = [ self . points [ I - self . degree + <NUM_LIT:1> + ii ] <EOL> for ii in range ( self . degree + <NUM_LIT:1> ) ] <EOL> U = self . knots <EOL> for ik in range ( <NUM_LIT:1> , self . degree + <NUM_LIT:1> ) : <EOL> for ii in range ( I - self . degree + ik + <NUM_LIT:1> , I + <NUM_LIT:2> ) : <EOL> ua = U [ ii + self . degree - ik ] <EOL> ub = U [ ii - <NUM_LIT:1> ] <EOL> co1 = ( ua - u ) / ( ua - ub ) <EOL> co2 = ( u - ub ) / ( ua - ub ) <EOL> index = ii - I + self . degree - ik - <NUM_LIT:1> <EOL> d [ index ] = d [ index ] . linear_combination ( d [ index + <NUM_LIT:1> ] , co1 , co2 ) <EOL> return d [ <NUM_LIT:0> ] <EOL> @ cython . locals ( ii = cython . long , I = cython . long , dom = ( cython . long , cython . long ) ) <EOL> def GetIndex ( self , u ) : <EOL> dom = self . GetDomain ( ) <EOL> for ii in range ( self . degree - <NUM_LIT:1> , len ( self . knots ) - self . degree ) : <EOL> if self . knots [ ii ] <= u < self . knots [ ii + <NUM_LIT:1> ] : <EOL> I = ii <EOL> break <EOL> else : <EOL> I = dom [ <NUM_LIT:1> ] - <NUM_LIT:1> <EOL> return I <EOL> def __len__ ( self ) : <EOL> return len ( self . points ) <EOL> def __repr__ ( self ) : <EOL> return "<STR_LIT>" % ( self . points , self . degree , self . knots ) <EOL> class Chaosgame ( object ) : <EOL> @ cython . locals ( splines = list , thickness = cython . double , maxlength = cython . double , length = cython . double , <EOL> curr = GVector , last = GVector , p = GVector , spl = Spline , t = cython . double , i = int ) <EOL> def __init__ ( self , splines , thickness = <NUM_LIT:0.1> ) : <EOL> self . splines = splines <EOL> self . thickness = thickness <EOL> self . minx = min ( [ p . x for spl in splines for p in spl . points ] ) <EOL> self . miny = min ( [ p . y for spl in splines for p in spl . points ] ) <EOL> self . maxx = max ( [ p . x for spl in splines for p in spl . points ] ) <EOL> self . maxy = max ( [ p . y for spl in splines for p in spl . points ] ) <EOL> self . height = self . maxy - self . miny <EOL> self . width = self . maxx - self . minx <EOL> self . num_trafos = [ ] <EOL> maxlength = thickness * self . width / self . height <EOL> for spl in splines : <EOL> length = <NUM_LIT:0> <EOL> curr = spl ( <NUM_LIT:0> ) <EOL> for i in range ( <NUM_LIT:1> , <NUM_LIT:1000> ) : <EOL> last = curr <EOL> t = <NUM_LIT:1> / <NUM_LIT> * i <EOL> curr = spl ( t ) <EOL> length += curr . dist ( last ) <EOL> self . num_trafos . append ( max ( <NUM_LIT:1> , int ( length / maxlength * <NUM_LIT> ) ) ) <EOL> self . num_total = reduce ( operator . add , self . num_trafos , <NUM_LIT:0> ) <EOL> def get_random_trafo ( self ) : <EOL> r = random . randrange ( int ( self . num_total ) + <NUM_LIT:1> ) <EOL> l = <NUM_LIT:0> <EOL> for i in range ( len ( self . num_trafos ) ) : <EOL> if l <= r < l + self . num_trafos [ i ] : <EOL> return i , random . randrange ( self . num_trafos [ i ] ) <EOL> l += self . num_trafos [ i ] <EOL> return len ( self . num_trafos ) - <NUM_LIT:1> , random . randrange ( self . num_trafos [ - <NUM_LIT:1> ] ) <EOL> @ cython . locals ( neighbour = "<STR_LIT>" , basepoint = "<STR_LIT>" , derivative = "<STR_LIT>" , <EOL> seg_length = cython . double , start = cython . double , end = cython . double , <EOL> t = cython . double ) <EOL> def transform_point ( self , point , trafo = None ) : <EOL> x = ( point . x - self . minx ) / self . width <EOL> y = ( point . y - self . miny ) / self . height <EOL> if trafo is None : <EOL> trafo = self . get_random_trafo ( ) <EOL> start , end = self . splines [ trafo [ <NUM_LIT:0> ] ] . GetDomain ( ) <EOL> length = end - start <EOL> seg_length = length / self . num_trafos [ trafo [ <NUM_LIT:0> ] ] <EOL> t = start + seg_length * trafo [ <NUM_LIT:1> ] + seg_length * x <EOL> basepoint = self . splines [ trafo [ <NUM_LIT:0> ] ] ( t ) <EOL> if t + <NUM_LIT:1> / <NUM_LIT> > end : <EOL> neighbour = self . splines [ trafo [ <NUM_LIT:0> ] ] ( t - <NUM_LIT:1> / <NUM_LIT> ) <EOL> derivative = neighbour - basepoint <EOL> else : <EOL> neighbour = self . splines [ trafo [ <NUM_LIT:0> ] ] ( t + <NUM_LIT:1> / <NUM_LIT> ) <EOL> derivative = basepoint - neighbour <EOL> if derivative . Mag ( ) != <NUM_LIT:0> : <EOL> basepoint . x += derivative . y / derivative . Mag ( ) * ( y - <NUM_LIT:0.5> ) * self . thickness <EOL> basepoint . y += - derivative . x / derivative . Mag ( ) * ( y - <NUM_LIT:0.5> ) * self . thickness <EOL> else : <EOL> print ( "<STR_LIT:r>" , end = '<STR_LIT>' ) <EOL> self . truncate ( basepoint ) <EOL> return basepoint <EOL> def truncate ( self , point ) : <EOL> if point . x >= self . maxx : <EOL> point . x = self . maxx <EOL> if point . y >= self . maxy : <EOL> point . y = self . maxy <EOL> if point . x < self . minx : <EOL> point . x = self . minx <EOL> if point . y < self . miny : <EOL> point . y = self . miny <EOL> @ cython . locals ( x = cython . long , y = cython . long ) <EOL> def create_image_chaos ( self , timer , w , h , n ) : <EOL> im = [ [ <NUM_LIT:1> ] * h for i in range ( w ) ] <EOL> point = GVector ( ( self . maxx + self . minx ) / <NUM_LIT:2> , <EOL> ( self . maxy + self . miny ) / <NUM_LIT:2> , <NUM_LIT:0> ) <EOL> times = [ ] <EOL> for _ in range ( n ) : <EOL> t1 = timer ( ) <EOL> for i in range ( <NUM_LIT> ) : <EOL> point = self . transform_point ( point ) <EOL> x = int ( ( point . x - self . minx ) / self . width * w ) <EOL> y = int ( ( point . y - self . miny ) / self . height * h ) <EOL> if x == w : <EOL> x -= <NUM_LIT:1> <EOL> if y == h : <EOL> y -= <NUM_LIT:1> <EOL> im [ x ] [ h - y - <NUM_LIT:1> ] = <NUM_LIT:0> <EOL> t2 = timer ( ) <EOL> times . append ( t2 - t1 ) <EOL> return times <EOL> def main ( n , timer = time . time ) : <EOL> splines = [ <EOL> Spline ( [ <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) , <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) , <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) , <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) , <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) , <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) , <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) ] , <EOL> <NUM_LIT:3> , [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:2> , <NUM_LIT:2> ] ) , <EOL> Spline ( [ <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) , <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) , <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) , <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) ] , <EOL> <NUM_LIT:3> , [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> ] ) , <EOL> Spline ( [ <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) , <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) , <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) , <EOL> GVector ( <NUM_LIT> , <NUM_LIT> , <NUM_LIT> ) ] , <EOL> <NUM_LIT:3> , [ <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> ] ) <EOL> ] <EOL> c = Chaosgame ( splines , <NUM_LIT> ) <EOL> return c . create_image_chaos ( timer , <NUM_LIT:1000> , <NUM_LIT> , n ) <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> import util <EOL> parser = optparse . OptionParser ( <EOL> usage = "<STR_LIT>" , <EOL> description = "<STR_LIT>" ) <EOL> util . add_standard_options_to ( parser ) <EOL> options , args = parser . parse_args ( ) <EOL> util . run_benchmark ( options , options . num_runs , main ) </s>
