<s> def split ( xxx_todo_changeme ) : <EOL> ( lo , hi ) = xxx_todo_changeme <EOL> w2 = ( hi - lo ) / <NUM_LIT:2> <EOL> return ( ( lo , lo + w2 ) , ( lo + w2 , hi ) ) <EOL> def contains ( xxx_todo_changeme1 , xxx_todo_changeme2 ) : <EOL> ( la , ra ) = xxx_todo_changeme1 <EOL> ( lb , rb ) = xxx_todo_changeme2 <EOL> return la <= lb and ra >= rb <EOL> def intersects ( xxx_todo_changeme3 , xxx_todo_changeme4 ) : <EOL> ( la , ra ) = xxx_todo_changeme3 <EOL> ( lb , rb ) = xxx_todo_changeme4 <EOL> return ra >= lb and rb >= la <EOL> class node ( object ) : <EOL> __slots__ = ( '<STR_LIT:l>' , '<STR_LIT:r>' , '<STR_LIT>' ) <EOL> def __init__ ( self ) : <EOL> self . l = None <EOL> self . r = None <EOL> self . objects = None <EOL> def get ( self , i ) : <EOL> if i == <NUM_LIT:0> : <EOL> if self . l is None : <EOL> self . l = node ( ) <EOL> return self . l <EOL> else : <EOL> if self . r is None : <EOL> self . r = node ( ) <EOL> return self . r <EOL> def insert ( self , seg , needle ) : <EOL> segs = split ( seg ) <EOL> for i in ( <NUM_LIT:0> , <NUM_LIT:1> ) : <EOL> s = segs [ i ] <EOL> if contains ( s , needle ) : <EOL> return self . get ( i ) . insert ( s , needle ) <EOL> if self . objects is None : <EOL> self . objects = [ needle ] <EOL> else : <EOL> self . objects . append ( needle ) <EOL> def delete ( self , seg , needle ) : <EOL> segs = split ( seg ) <EOL> for i in ( <NUM_LIT:0> , <NUM_LIT:1> ) : <EOL> s = segs [ i ] <EOL> if contains ( s , needle ) : <EOL> return self . get ( i ) . delete ( s , needle ) <EOL> try : <EOL> self . objects . remove ( needle ) <EOL> return True <EOL> except ValueError : <EOL> pass <EOL> def search_apply ( self , seg , needle , fun ) : <EOL> if self . objects is not None : <EOL> for ob in self . objects : <EOL> if intersects ( ob , needle ) : <EOL> fun ( ob ) <EOL> segs = split ( seg ) <EOL> for i in ( <NUM_LIT:0> , <NUM_LIT:1> ) : <EOL> s = segs [ i ] <EOL> if contains ( s , needle ) : <EOL> return self . get ( i ) . search_apply ( s , needle , fun ) <EOL> def dump ( self , line , depth ) : <EOL> print '<STR_LIT:U+0020>' * depth , line , <EOL> if self . objects : <EOL> print self . objects <EOL> else : <EOL> print <EOL> l , r = split ( line ) <EOL> if self . l : <EOL> self . l . dump ( l , depth + <NUM_LIT:1> ) <EOL> if self . r : <EOL> self . r . dump ( r , depth + <NUM_LIT:1> ) <EOL> class bintree : <EOL> def __init__ ( self , line = ( <NUM_LIT:0> , <NUM_LIT> ) ) : <EOL> self . tree = node ( ) <EOL> self . line = line <EOL> self . size = <NUM_LIT:0> <EOL> def __repr__ ( self ) : <EOL> return '<STR_LIT>' % ( <EOL> self . size , <EOL> self . line <EOL> ) <EOL> def dump ( self ) : <EOL> self . tree . dump ( self . line , <NUM_LIT:0> ) <EOL> def insert ( self , line ) : <EOL> while True : <EOL> if contains ( self . line , line ) : <EOL> self . tree . insert ( self . line , line ) <EOL> break <EOL> else : <EOL> n = node ( ) <EOL> ll , lr = line <EOL> sl , sr = self . line <EOL> w = sr - sl <EOL> if ll < sl : <EOL> self . line = sl - w , sr <EOL> n . r , self . tree = self . tree , n <EOL> else : <EOL> self . line = sl , sr + w <EOL> n . l , self . tree = self . tree , n <EOL> self . size += <NUM_LIT:1> <EOL> def delete ( self , needle ) : <EOL> return self . tree . delete ( self . line , needle ) <EOL> def search ( self , needle ) : <EOL> r = [ ] <EOL> self . tree . search_apply ( self . line , needle , r . append ) <EOL> return r <EOL> def search_apply ( self , needle , fun ) : <EOL> self . tree . search_apply ( self . line , needle , fun ) <EOL> def t0 ( ) : <EOL> t = bintree ( ) <EOL> t . insert ( ( <NUM_LIT:0> , <NUM_LIT:200> ) ) <EOL> t . insert ( ( <NUM_LIT> , <NUM_LIT> ) ) <EOL> t . insert ( ( <NUM_LIT> , <NUM_LIT> ) ) <EOL> t . insert ( ( <NUM_LIT> , <NUM_LIT> ) ) <EOL> t . insert ( ( <NUM_LIT:1000> , <NUM_LIT> ) ) <EOL> t . insert ( ( <NUM_LIT> , <NUM_LIT> ) ) <EOL> t . dump ( ) <EOL> t . delete ( ( <NUM_LIT> , <NUM_LIT> ) ) <EOL> t . delete ( ( <NUM_LIT> , <NUM_LIT> ) ) <EOL> t . dump ( ) <EOL> return t </s>
