<s> class node : pass <EOL> class DequeDict ( object ) : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , i = [ ] ) : <EOL> self . l = node ( ) <EOL> self . l . next = self . l <EOL> self . l . prev = self . l <EOL> self . l . key = None <EOL> self . l . value = None <EOL> self . d = { } <EOL> if i : self . extend ( i ) <EOL> def extend ( self , l ) : <EOL> """<STR_LIT>""" <EOL> for key , value in l : self . append ( key , value ) <EOL> def append ( self , key , value ) : <EOL> """<STR_LIT>""" <EOL> n = node ( ) <EOL> n . key = key <EOL> n . value = value <EOL> self . l . prev . next = n <EOL> n . prev = self . l . prev <EOL> n . next = self . l <EOL> self . l . prev = n <EOL> self . d [ key ] = n <EOL> def appendleft ( self , key , value ) : <EOL> """<STR_LIT>""" <EOL> n = node ( ) <EOL> n . key = key <EOL> n . value = value <EOL> self . l . next . prev = n <EOL> n . next = self . l . next <EOL> n . prev = self . l <EOL> self . l . next = n <EOL> self . d [ key ] = n <EOL> def pop ( self ) : <EOL> """<STR_LIT>""" <EOL> n = self . l . prev <EOL> n . prev . next = self . l <EOL> self . l . prev = n . prev <EOL> del self . d [ n . key ] <EOL> return ( n . key , n . value ) <EOL> def popleft ( self ) : <EOL> """<STR_LIT>""" <EOL> n = self . l . next <EOL> n . next . prev = self . l <EOL> self . l . next = n . next <EOL> del self . d [ n . key ] <EOL> return ( n . key , n . value ) <EOL> def iteritemsright ( self ) : <EOL> """<STR_LIT>""" <EOL> n = self . l . prev <EOL> while n != self . l : <EOL> yield ( n . key , n . value ) <EOL> n = n . prev <EOL> def iteritems ( self ) : <EOL> """<STR_LIT>""" <EOL> n = self . l . next <EOL> while n != self . l : <EOL> yield ( n . key , n . value ) <EOL> n = n . next <EOL> def iterkeys ( self ) : <EOL> """<STR_LIT>""" <EOL> for key , _ in self . iteritems ( ) : <EOL> yield key <EOL> def itervalues ( self ) : <EOL> """<STR_LIT>""" <EOL> for _ , value in self . iteritems ( ) : <EOL> yield value <EOL> def iterkeysright ( self ) : <EOL> """<STR_LIT>""" <EOL> for key , _ in self . iteritemsright ( ) : <EOL> yield key <EOL> def movehead ( self , key ) : <EOL> """<STR_LIT>""" <EOL> n = self . d [ key ] <EOL> n . next . prev = n . prev <EOL> n . prev . next = n . next <EOL> self . l . next . prev = n <EOL> n . next = self . l . next <EOL> n . prev = self . l <EOL> self . l . next = n <EOL> def keys ( self ) : <EOL> return list ( self . iterkeys ( ) ) <EOL> def values ( self ) : <EOL> return list ( self . itervalues ( ) ) <EOL> def items ( self ) : <EOL> return list ( self . iteritems ( ) ) <EOL> def removeall ( self , key ) : <EOL> if key in self : del self [ key ] <EOL> def __getitem__ ( self , key ) : <EOL> return self . d [ key ] . value <EOL> def __delitem__ ( self , key ) : <EOL> """<STR_LIT>""" <EOL> n = self . d [ key ] <EOL> n . next . prev = n . prev <EOL> n . prev . next = n . next <EOL> del self . d [ key ] <EOL> def __iter__ ( self ) : <EOL> return self . iterkeys ( ) <EOL> def __contains__ ( self , key ) : <EOL> return key in self . d <EOL> def __len__ ( self ) : <EOL> return len ( self . d ) <EOL> def __nonzero__ ( self ) : <EOL> return bool ( self . d ) <EOL> def __getstate__ ( self ) : <EOL> state = self . __dict__ . copy ( ) <EOL> state [ '<STR_LIT:l>' ] = list ( self . iteritems ( ) ) <EOL> del state [ '<STR_LIT:d>' ] <EOL> return state <EOL> def __setstate__ ( self , state ) : <EOL> self . __init__ ( state [ '<STR_LIT:l>' ] ) <EOL> def __repr__ ( self ) : <EOL> return '<STR_LIT>' % '<STR_LIT:U+002C>' . join ( [ '<STR_LIT>' % ( repr ( key ) , repr ( value ) ) for key , value in self . iteritems ( ) ] ) </s>
