<s> from __future__ import print_function <EOL> from sys import hexversion <EOL> import copy <EOL> import bisect <EOL> import random <EOL> from . context import sortedcontainers <EOL> from sortedcontainers import SortedListWithKey <EOL> from nose . tools import raises <EOL> from functools import wraps <EOL> class SortedList ( SortedListWithKey ) : <EOL> pass <EOL> if hexversion < <NUM_LIT> : <EOL> from itertools import izip as zip <EOL> range = xrange <EOL> random . seed ( <NUM_LIT:0> ) <EOL> actions = [ ] <EOL> def frange ( start , stop , step ) : <EOL> while start < stop : <EOL> yield start <EOL> start += step <EOL> class actor : <EOL> def __init__ ( self , count ) : <EOL> self . _count = count <EOL> def __call__ ( self , func ) : <EOL> actions . extend ( [ func ] * self . _count ) <EOL> return func <EOL> def not_empty ( func ) : <EOL> @ wraps ( func ) <EOL> def wrapper ( slt ) : <EOL> if len ( slt ) < <NUM_LIT:100> : <EOL> stress_update ( slt ) <EOL> func ( slt ) <EOL> return wrapper <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_clear ( slt ) : <EOL> if random . randrange ( <NUM_LIT:100> ) < <NUM_LIT:10> : <EOL> slt . clear ( ) <EOL> else : <EOL> values = list ( slt ) <EOL> slt . clear ( ) <EOL> slt . update ( values [ : int ( len ( values ) / <NUM_LIT:2> ) ] ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_add ( slt ) : <EOL> if random . randrange ( <NUM_LIT:100> ) < <NUM_LIT:10> : <EOL> slt . clear ( ) <EOL> slt . add ( random . random ( ) ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_update ( slt ) : <EOL> slt . update ( ( random . random ( ) for rpt in range ( <NUM_LIT> ) ) ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_contains ( slt ) : <EOL> if random . randrange ( <NUM_LIT:100> ) < <NUM_LIT:10> : <EOL> slt . clear ( ) <EOL> assert <NUM_LIT:0> not in slt <EOL> else : <EOL> val = slt [ random . randrange ( len ( slt ) ) ] <EOL> assert val in slt <EOL> assert <NUM_LIT:1> not in slt <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_discard ( slt ) : <EOL> val = slt [ random . randrange ( len ( slt ) ) ] <EOL> slt . discard ( val ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_discard2 ( slt ) : <EOL> if random . randrange ( <NUM_LIT:100> ) < <NUM_LIT:10> : <EOL> slt . clear ( ) <EOL> slt . discard ( random . random ( ) ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_remove ( slt ) : <EOL> if len ( slt ) > <NUM_LIT:0> : <EOL> val = slt [ random . randrange ( len ( slt ) ) ] <EOL> slt . remove ( val ) <EOL> try : <EOL> slt . remove ( <NUM_LIT:1> ) <EOL> assert False <EOL> except ValueError : <EOL> pass <EOL> try : <EOL> slt . remove ( - <NUM_LIT:1> ) <EOL> assert False <EOL> except ValueError : <EOL> pass <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_delitem ( slt ) : <EOL> del slt [ random . randrange ( len ( slt ) ) ] <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_getitem ( slt ) : <EOL> if len ( slt ) > <NUM_LIT:0> : <EOL> pos = random . randrange ( len ( slt ) ) <EOL> assert slt [ pos ] == list ( slt ) [ pos ] <EOL> try : <EOL> slt [ - ( slt . _len + <NUM_LIT:5> ) ] <EOL> assert False <EOL> except IndexError : <EOL> pass <EOL> try : <EOL> slt [ slt . _len + <NUM_LIT:5> ] <EOL> assert False <EOL> except IndexError : <EOL> pass <EOL> else : <EOL> try : <EOL> slt [ <NUM_LIT:0> ] <EOL> assert False <EOL> except IndexError : <EOL> pass <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_setitem ( slt ) : <EOL> pos = random . randrange ( len ( slt ) ) <EOL> slt [ pos ] = slt [ pos ] <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_setitem2 ( slt ) : <EOL> pos = random . randrange ( int ( len ( slt ) / <NUM_LIT:100> ) ) * <NUM_LIT:100> <EOL> slt [ pos ] = slt [ pos ] <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_getset_slice ( slt ) : <EOL> start , stop = sorted ( random . randrange ( len ( slt ) ) for rpt in range ( <NUM_LIT:2> ) ) <EOL> step = random . choice ( [ - <NUM_LIT:3> , - <NUM_LIT:2> , - <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] ) <EOL> lst = slt [ start : stop : step ] <EOL> assert all ( lst [ pos - <NUM_LIT:1> ] <= lst [ pos ] for pos in range ( <NUM_LIT:1> , len ( lst ) ) ) <EOL> slt [ start : stop : step ] = lst <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_delitem_slice ( slt ) : <EOL> start , stop = sorted ( random . randrange ( len ( slt ) ) for rpt in range ( <NUM_LIT:2> ) ) <EOL> step = random . choice ( [ - <NUM_LIT:3> , - <NUM_LIT:2> , - <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:1> , <NUM_LIT:2> , <NUM_LIT:3> ] ) <EOL> del slt [ start : stop : step ] <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_iter ( slt ) : <EOL> itr1 = iter ( slt ) <EOL> itr2 = ( slt [ pos ] for pos in range ( len ( slt ) ) ) <EOL> assert all ( tup [ <NUM_LIT:0> ] == tup [ <NUM_LIT:1> ] for tup in zip ( itr1 , itr2 ) ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_reversed ( slt ) : <EOL> itr = reversed ( list ( reversed ( slt ) ) ) <EOL> assert all ( tup [ <NUM_LIT:0> ] == tup [ <NUM_LIT:1> ] for tup in zip ( slt , itr ) ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_bisect_left ( slt ) : <EOL> values = list ( slt ) <EOL> value = random . random ( ) <EOL> values . sort ( ) <EOL> assert bisect . bisect_left ( values , value ) == slt . bisect_left ( value ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_bisect ( slt ) : <EOL> values = list ( slt ) <EOL> value = random . random ( ) <EOL> values . sort ( ) <EOL> assert bisect . bisect ( values , value ) == slt . bisect ( value ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_bisect_right ( slt ) : <EOL> values = list ( slt ) <EOL> value = random . random ( ) <EOL> values . sort ( ) <EOL> assert bisect . bisect_right ( values , value ) == slt . bisect_right ( value ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_dups ( slt ) : <EOL> pos = min ( random . randrange ( len ( slt ) ) , <NUM_LIT> ) <EOL> val = slt [ pos ] <EOL> for rpt in range ( pos ) : <EOL> slt . add ( val ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_count ( slt ) : <EOL> values = list ( slt ) <EOL> val = slt [ random . randrange ( len ( slt ) ) ] <EOL> assert slt . count ( val ) == values . count ( val ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_append ( slt ) : <EOL> if random . randrange ( <NUM_LIT:100> ) < <NUM_LIT:10> : <EOL> slt . clear ( ) <EOL> if len ( slt ) == <NUM_LIT:0> : <EOL> slt . append ( random . random ( ) ) <EOL> else : <EOL> slt . append ( slt [ - <NUM_LIT:1> ] ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_extend ( slt ) : <EOL> if random . randrange ( <NUM_LIT:100> ) < <NUM_LIT:10> : <EOL> slt . clear ( ) <EOL> if len ( slt ) == <NUM_LIT:0> : <EOL> slt . extend ( float ( val ) / <NUM_LIT:1000> for val in range ( <NUM_LIT:1000> ) ) <EOL> else : <EOL> slt . extend ( frange ( slt [ - <NUM_LIT:1> ] , <NUM_LIT:1> , <NUM_LIT> ) ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_insert ( slt ) : <EOL> slt . insert ( <NUM_LIT:0> , slt [ <NUM_LIT:0> ] ) <EOL> slt . insert ( - ( len ( slt ) + <NUM_LIT:10> ) , slt [ <NUM_LIT:0> ] ) <EOL> slt . insert ( len ( slt ) , slt [ - <NUM_LIT:1> ] ) <EOL> slt . insert ( len ( slt ) + <NUM_LIT:10> , slt [ - <NUM_LIT:1> ] ) <EOL> pos = random . randrange ( len ( slt ) ) <EOL> slt . insert ( pos , slt [ pos ] ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_insert2 ( slt ) : <EOL> if random . randrange ( <NUM_LIT:100> ) < <NUM_LIT:10> : <EOL> slt . clear ( ) <EOL> if len ( slt ) == <NUM_LIT:0> : <EOL> slt . insert ( <NUM_LIT:0> , random . random ( ) ) <EOL> else : <EOL> values = list ( slt ) [ : <NUM_LIT> ] <EOL> for val in values : <EOL> slt . insert ( slt . index ( val ) , val ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_pop ( slt ) : <EOL> pos = random . randrange ( len ( slt ) ) + <NUM_LIT:1> <EOL> assert slt [ - pos ] == slt . pop ( - pos ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_index ( slt ) : <EOL> values = set ( slt ) <EOL> slt . clear ( ) <EOL> slt . update ( values ) <EOL> pos = random . randrange ( len ( slt ) ) <EOL> assert slt . index ( slt [ pos ] ) == pos <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_index2 ( slt ) : <EOL> values = list ( slt ) [ : <NUM_LIT:3> ] * <NUM_LIT:200> <EOL> slt = SortedList ( values ) <EOL> for idx , val in enumerate ( slt ) : <EOL> assert slt . index ( val , idx ) == idx <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_mul ( slt ) : <EOL> values = list ( slt ) <EOL> mult = random . randrange ( <NUM_LIT:10> ) <EOL> values *= mult <EOL> values . sort ( ) <EOL> assert ( slt * mult ) == values <EOL> @ actor ( <NUM_LIT:1> ) <EOL> def stress_imul ( slt ) : <EOL> mult = random . randrange ( <NUM_LIT:10> ) <EOL> slt *= mult <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_reversed ( slt ) : <EOL> itr = reversed ( slt ) <EOL> pos = random . randrange ( <NUM_LIT:1> , len ( slt ) ) <EOL> for rpt in range ( pos ) : <EOL> val = next ( itr ) <EOL> assert val == slt [ - pos ] <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_eq ( slt ) : <EOL> values = [ ] <EOL> assert not ( values == slt ) <EOL> @ actor ( <NUM_LIT:1> ) <EOL> @ not_empty <EOL> def stress_lt ( slt ) : <EOL> values = list ( slt ) <EOL> assert not ( values < slt ) <EOL> values = SortedList ( value - <NUM_LIT:1> for value in values ) <EOL> assert values < slt <EOL> values = [ ] <EOL> assert values < slt <EOL> assert not ( slt < values ) <EOL> def test_stress ( repeat = <NUM_LIT:1000> ) : <EOL> slt = SortedList ( ( random . random ( ) for rpt in range ( <NUM_LIT:1000> ) ) ) <EOL> for rpt in range ( repeat ) : <EOL> action = random . choice ( actions ) <EOL> action ( slt ) <EOL> slt . _check ( ) <EOL> while len ( slt ) > <NUM_LIT> : <EOL> pos = random . randrange ( len ( slt . _maxes ) ) <EOL> del slt . _maxes [ pos ] <EOL> del slt . _keys [ pos ] <EOL> del slt . _lists [ pos ] <EOL> slt . _len = sum ( len ( sublist ) for sublist in slt . _lists ) <EOL> slt . _index = [ ] <EOL> slt . _check ( ) <EOL> slt . _check ( ) <EOL> stress_update ( slt ) <EOL> while len ( slt ) > <NUM_LIT:0> : <EOL> pos = random . randrange ( len ( slt ) ) <EOL> del slt [ pos ] <EOL> slt . _check ( ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> import sys <EOL> from datetime import datetime <EOL> start = datetime . now ( ) <EOL> print ( '<STR_LIT>' , sys . version_info ) <EOL> try : <EOL> num = int ( sys . argv [ <NUM_LIT:1> ] ) <EOL> print ( '<STR_LIT>' , num ) <EOL> except : <EOL> print ( '<STR_LIT>' ) <EOL> num = <NUM_LIT:1000> <EOL> try : <EOL> pea = int ( sys . argv [ <NUM_LIT:2> ] ) <EOL> random . seed ( pea ) <EOL> print ( '<STR_LIT>' , pea ) <EOL> except : <EOL> print ( '<STR_LIT>' ) <EOL> random . seed ( <NUM_LIT:0> ) <EOL> try : <EOL> test_stress ( num ) <EOL> except : <EOL> raise <EOL> finally : <EOL> print ( '<STR_LIT>' , ( datetime . now ( ) - start ) ) </s>
