@@ -34,3 +34,123 @@ def __init__(self, items=()):
3434
3535def __getitem__ (self ,key ):
3636return dict .get (self ,key ,self .default )
37+
38+ #Pure python implementation of deque taken from the ASPN Python Cookbook
39+ #Original code by Raymond Hettinger
40+
41+ class deque (object ):
42+
43+ def __init__ (self ,iterable = (),maxsize = - 1 ):
44+ if not hasattr (self ,'data' ):
45+ self .left = self .right = 0
46+ self .data = {}
47+ self .maxsize = maxsize
48+ self .extend (iterable )
49+
50+ def append (self ,x ):
51+ self .data [self .right ]= x
52+ self .right += 1
53+ if self .maxsize != - 1 and len (self )> self .maxsize :
54+ self .popleft ()
55+
56+ def appendleft (self ,x ):
57+ self .left -= 1
58+ self .data [self .left ]= x
59+ if self .maxsize != - 1 and len (self )> self .maxsize :
60+ self .pop ()
61+
62+ def pop (self ):
63+ if self .left == self .right :
64+ raise IndexError ('cannot pop from empty deque' )
65+ self .right -= 1
66+ elem = self .data [self .right ]
67+ del self .data [self .right ]
68+ return elem
69+
70+ def popleft (self ):
71+ if self .left == self .right :
72+ raise IndexError ('cannot pop from empty deque' )
73+ elem = self .data [self .left ]
74+ del self .data [self .left ]
75+ self .left += 1
76+ return elem
77+
78+ def clear (self ):
79+ self .data .clear ()
80+ self .left = self .right = 0
81+
82+ def extend (self ,iterable ):
83+ for elem in iterable :
84+ self .append (elem )
85+
86+ def extendleft (self ,iterable ):
87+ for elem in iterable :
88+ self .appendleft (elem )
89+
90+ def rotate (self ,n = 1 ):
91+ if self :
92+ n %= len (self )
93+ for i in xrange (n ):
94+ self .appendleft (self .pop ())
95+
96+ def __getitem__ (self ,i ):
97+ if i < 0 :
98+ i += len (self )
99+ try :
100+ return self .data [i + self .left ]
101+ except KeyError :
102+ raise IndexError
103+
104+ def __setitem__ (self ,i ,value ):
105+ if i < 0 :
106+ i += len (self )
107+ try :
108+ self .data [i + self .left ]= value
109+ except KeyError :
110+ raise IndexError
111+
112+ def __delitem__ (self ,i ):
113+ size = len (self )
114+ if not (- size <= i < size ):
115+ raise IndexError
116+ data = self .data
117+ if i < 0 :
118+ i += size
119+ for j in xrange (self .left + i ,self .right - 1 ):
120+ data [j ]= data [j + 1 ]
121+ self .pop ()
122+
123+ def __len__ (self ):
124+ return self .right - self .left
125+
126+ def __cmp__ (self ,other ):
127+ if type (self )!= type (other ):
128+ return cmp (type (self ),type (other ))
129+ return cmp (list (self ),list (other ))
130+
131+ def __repr__ (self ,_track = []):
132+ if id (self )in _track :
133+ return '...'
134+ _track .append (id (self ))
135+ r = 'deque(%r)' % (list (self ),)
136+ _track .remove (id (self ))
137+ return r
138+
139+ def __getstate__ (self ):
140+ return (tuple (self ),)
141+
142+ def __setstate__ (self ,s ):
143+ self .__init__ (s [0 ])
144+
145+ def __hash__ (self ):
146+ raise TypeError
147+
148+ def __copy__ (self ):
149+ return self .__class__ (self )
150+
151+ def __deepcopy__ (self ,memo = {}):
152+ from copy import deepcopy
153+ result = self .__class__ ()
154+ memo [id (self )]= result
155+ result .__init__ (deepcopy (tuple (self ),memo ))
156+ return result