<s> import collections <EOL> class OrderedSet ( collections . MutableSet ) : <EOL> def __init__ ( self , iterable = None ) : <EOL> self . end = end = [ ] <EOL> end += [ None , end , end ] <EOL> self . map = { } <EOL> if iterable is not None : <EOL> self |= iterable <EOL> def __len__ ( self ) : <EOL> return len ( self . map ) <EOL> def __contains__ ( self , key ) : <EOL> return key in self . map <EOL> def add ( self , key ) : <EOL> if key not in self . map : <EOL> end = self . end <EOL> curr = end [ <NUM_LIT:1> ] <EOL> curr [ <NUM_LIT:2> ] = end [ <NUM_LIT:1> ] = self . map [ key ] = [ key , curr , end ] <EOL> def discard ( self , key ) : <EOL> if key in self . map : <EOL> key , prev , next = self . map . pop ( key ) <EOL> prev [ <NUM_LIT:2> ] = next <EOL> next [ <NUM_LIT:1> ] = prev <EOL> def __iter__ ( self ) : <EOL> end = self . end <EOL> curr = end [ <NUM_LIT:2> ] <EOL> while curr is not end : <EOL> yield curr [ <NUM_LIT:0> ] <EOL> curr = curr [ <NUM_LIT:2> ] <EOL> def __reversed__ ( self ) : <EOL> end = self . end <EOL> curr = end [ <NUM_LIT:1> ] <EOL> while curr is not end : <EOL> yield curr [ <NUM_LIT:0> ] <EOL> curr = curr [ <NUM_LIT:1> ] <EOL> def pop ( self , last = True ) : <EOL> if not self : <EOL> raise KeyError ( '<STR_LIT>' ) <EOL> key = self . end [ <NUM_LIT:1> ] [ <NUM_LIT:0> ] if last else self . end [ <NUM_LIT:2> ] [ <NUM_LIT:0> ] <EOL> self . discard ( key ) <EOL> return key <EOL> def __repr__ ( self ) : <EOL> if not self : <EOL> return '<STR_LIT>' % ( self . __class__ . __name__ , ) <EOL> return '<STR_LIT>' % ( self . __class__ . __name__ , list ( self ) ) <EOL> def __eq__ ( self , other ) : <EOL> if isinstance ( other , OrderedSet ) : <EOL> return len ( self ) == len ( other ) and list ( self ) == list ( other ) <EOL> return set ( self ) == set ( other ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> s = OrderedSet ( '<STR_LIT>' ) <EOL> t = OrderedSet ( '<STR_LIT>' ) <EOL> print ( s | t ) <EOL> print ( s & t ) <EOL> print ( s - t ) </s>
