<s> from fn import Stream <EOL> from fn . uniform import reduce <EOL> from fn . iters import takewhile <EOL> class Vector ( object ) : <EOL> """<STR_LIT>""" <EOL> __slots__ = ( "<STR_LIT>" , "<STR_LIT>" , "<STR_LIT:root>" , "<STR_LIT>" ) <EOL> class _Node ( object ) : <EOL> __slots__ = ( "<STR_LIT>" ) <EOL> def __init__ ( self , values = None , init = None ) : <EOL> self . array = values or [ None ] * <NUM_LIT:32> <EOL> if init is not None : self . array [ <NUM_LIT:0> ] = init <EOL> def __str__ ( self ) : <EOL> return str ( self . array ) <EOL> def __iter__ ( self ) : <EOL> s = reduce ( lambda acc , el : acc << ( el if isinstance ( el , self . __class__ ) else [ el ] ) , <EOL> takewhile ( lambda el : el is not None , self . array ) , <EOL> Stream ( ) ) <EOL> return iter ( s ) <EOL> def __init__ ( self , length = <NUM_LIT:0> , shift = None , root = None , tail = None ) : <EOL> self . length = length <EOL> self . shift = shift if shift is not None else <NUM_LIT:5> <EOL> self . root = root or self . __class__ . _Node ( ) <EOL> self . tail = tail if tail is not None else [ ] <EOL> def assoc ( self , pos , el ) : <EOL> """<STR_LIT>""" <EOL> if pos < <NUM_LIT:0> or pos > self . length : raise IndexError ( ) <EOL> if pos == self . length : return self . cons ( el ) <EOL> if pos < self . _tailoff ( ) : <EOL> up = self . __class__ . _do_assoc ( self . shift , self . root , pos , el ) <EOL> return self . __class__ ( self . length , self . shift , up , self . tail ) <EOL> up = self . tail [ : ] <EOL> up [ pos & <NUM_LIT> ] = el ; <EOL> return self . __class__ ( self . length , self . shift , self . root , up ) <EOL> def _tailoff ( self ) : <EOL> if self . length < <NUM_LIT:32> : return <NUM_LIT:0> <EOL> return ( ( self . length - <NUM_LIT:1> ) >> <NUM_LIT:5> ) << <NUM_LIT:5> <EOL> @ classmethod <EOL> def _do_assoc ( cls , level , node , pos , el ) : <EOL> r = cls . _Node ( node . array [ : ] ) <EOL> if level == <NUM_LIT:0> : <EOL> r . array [ pos & <NUM_LIT> ] = el <EOL> else : <EOL> sub = ( pos >> level ) & <NUM_LIT> <EOL> r . array [ sub ] = cls . _do_assoc ( level - <NUM_LIT:5> , node . array [ sub ] , pos , el ) <EOL> return r <EOL> def cons ( self , el ) : <EOL> if ( self . length - self . _tailoff ( ) ) < <NUM_LIT:32> : <EOL> tailup = self . tail [ : ] <EOL> tailup . append ( el ) <EOL> return self . __class__ ( self . length + <NUM_LIT:1> , self . shift , self . root , tailup ) <EOL> tailnode = self . __class__ . _Node ( self . tail ) <EOL> if ( self . length >> <NUM_LIT:5> ) > ( <NUM_LIT:1> << self . shift ) : <EOL> uproot = self . __class__ . _Node ( init = self . root ) <EOL> uproot . array [ <NUM_LIT:1> ] = self . __class__ . _make_path ( self . shift , tailnode ) <EOL> shift = self . shift + <NUM_LIT:5> <EOL> else : <EOL> uproot = self . _push_tail ( self . shift , self . root , tailnode ) <EOL> shift = self . shift <EOL> return self . __class__ ( self . length + <NUM_LIT:1> , shift , uproot , [ el ] ) <EOL> def _push_tail ( self , level , root , tail ) : <EOL> sub = ( ( self . length - <NUM_LIT:1> ) >> level ) & <NUM_LIT> <EOL> r = self . __class__ . _Node ( root . array [ : ] ) <EOL> if level == <NUM_LIT:5> : <EOL> r . array [ sub ] = tail <EOL> else : <EOL> child = root . array [ sub ] <EOL> if child is not None : <EOL> r . array [ sub ] = self . _push_tail ( level - <NUM_LIT:5> , child , tail ) <EOL> else : <EOL> r . array [ sub ] = self . __class__ . _make_path ( level - <NUM_LIT:5> , tail ) <EOL> return r <EOL> @ classmethod <EOL> def _make_path ( cls , level , node ) : <EOL> if level == <NUM_LIT:0> : return node <EOL> return cls . _Node ( init = cls . _make_path ( level - <NUM_LIT:5> , node ) ) <EOL> def get ( self , pos ) : <EOL> """<STR_LIT>""" <EOL> if pos < <NUM_LIT:0> or pos >= self . length : raise IndexError ( ) <EOL> return self . _find_container ( pos ) [ pos & <NUM_LIT> ] <EOL> def peek ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . length == <NUM_LIT:0> : return None <EOL> return self . get ( self . length - <NUM_LIT:1> ) <EOL> def pop ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . length == <NUM_LIT:0> : raise ValueError ( "<STR_LIT>" ) <EOL> if self . length == <NUM_LIT:1> : return self . __class__ ( ) <EOL> if self . length - self . _tailoff ( ) > <NUM_LIT:1> : <EOL> return self . __class__ ( self . length - <NUM_LIT:1> , self . shift , self . root , self . tail [ : - <NUM_LIT:1> ] ) <EOL> tail = self . _find_container ( self . length - <NUM_LIT:2> ) <EOL> root = self . _pop_tail ( self . shift , self . root ) or self . __class__ . _Node ( ) <EOL> shift = self . shift <EOL> if shift > <NUM_LIT:5> and root . array [ <NUM_LIT:1> ] is None : <EOL> root = root . array [ <NUM_LIT:0> ] <EOL> shift -= <NUM_LIT:5> <EOL> return self . __class__ ( self . length - <NUM_LIT:1> , shift , root , tail ) <EOL> def _find_container ( self , pos ) : <EOL> if pos < <NUM_LIT:0> or pos > self . length : raise IndexError ( ) <EOL> if pos >= self . _tailoff ( ) : return self . tail <EOL> bottom = reduce ( lambda node , level : node . array [ ( pos >> level ) & <NUM_LIT> ] , <EOL> range ( self . shift , <NUM_LIT:0> , - <NUM_LIT:5> ) , self . root ) <EOL> return bottom . array <EOL> def _pop_tail ( self , level , node ) : <EOL> sub = ( ( self . length - <NUM_LIT:2> ) >> level ) & <NUM_LIT> <EOL> if level > <NUM_LIT:5> : <EOL> child = self . _pop_tail ( level - <NUM_LIT:5> , node . array [ sub ] ) <EOL> if child is None and sub == <NUM_LIT:0> : return None <EOL> r = self . __class__ . _Node ( node . array [ : ] ) <EOL> r . array [ sub ] = child <EOL> return r <EOL> elif sub == <NUM_LIT:0> : return None <EOL> else : <EOL> r = self . __class__ . _Node ( node . array [ : ] ) <EOL> r . array [ sub ] = None <EOL> return r <EOL> def subvec ( self , start , end = None ) : <EOL> """<STR_LIT>""" <EOL> pass <EOL> def __len__ ( self ) : <EOL> return self . length <EOL> def __iter__ ( self ) : <EOL> s = Stream ( ) << self . root << self . tail <EOL> return iter ( s ) <EOL> def __getitem__ ( self , pos ) : <EOL> return self . get ( pos ) <EOL> def __setitem__ ( self , pos , val ) : <EOL> raise NotImplementedError ( ) </s>
