|
1 | 1 | from __future__importabsolute_import |
2 | | -try: |
3 | | -frozenset |
4 | | -exceptNameError: |
5 | | -#Import from the sets module for python 2.3 |
6 | | -fromsetsimportSetasset |
7 | | -fromsetsimportImmutableSetasfrozenset |
8 | | - |
9 | 2 | fromtypesimportModuleType |
10 | 3 |
|
11 | 4 |
|
@@ -41,145 +34,6 @@ def __getitem__(self, key): |
41 | 34 | returndict.get(self,key,self.default) |
42 | 35 | __getitem__.func_annotations= {} |
43 | 36 |
|
44 | | -#Pure python implementation of deque taken from the ASPN Python Cookbook |
45 | | -#Original code by Raymond Hettinger |
46 | | - |
47 | | -classdeque(object): |
48 | | - |
49 | | -def__init__(self,iterable=(),maxsize=-1): |
50 | | -ifnothasattr(self,u'data'): |
51 | | -self.left=self.right=0 |
52 | | -self.data= {} |
53 | | -self.maxsize=maxsize |
54 | | -self.extend(iterable) |
55 | | -__init__.func_annotations= {} |
56 | | - |
57 | | -defappend(self,x): |
58 | | -self.data[self.right]=x |
59 | | -self.right+=1 |
60 | | -ifself.maxsize!=-1andlen(self)>self.maxsize: |
61 | | -self.popleft() |
62 | | -append.func_annotations= {} |
63 | | - |
64 | | -defappendleft(self,x): |
65 | | -self.left-=1 |
66 | | -self.data[self.left]=x |
67 | | -ifself.maxsize!=-1andlen(self)>self.maxsize: |
68 | | -self.pop() |
69 | | -appendleft.func_annotations= {} |
70 | | - |
71 | | -defpop(self): |
72 | | -ifself.left==self.right: |
73 | | -raiseIndexError(u'cannot pop from empty deque') |
74 | | -self.right-=1 |
75 | | -elem=self.data[self.right] |
76 | | -delself.data[self.right] |
77 | | -returnelem |
78 | | -pop.func_annotations= {} |
79 | | - |
80 | | -defpopleft(self): |
81 | | -ifself.left==self.right: |
82 | | -raiseIndexError(u'cannot pop from empty deque') |
83 | | -elem=self.data[self.left] |
84 | | -delself.data[self.left] |
85 | | -self.left+=1 |
86 | | -returnelem |
87 | | -popleft.func_annotations= {} |
88 | | - |
89 | | -defclear(self): |
90 | | -self.data.clear() |
91 | | -self.left=self.right=0 |
92 | | -clear.func_annotations= {} |
93 | | - |
94 | | -defextend(self,iterable): |
95 | | -foreleminiterable: |
96 | | -self.append(elem) |
97 | | -extend.func_annotations= {} |
98 | | - |
99 | | -defextendleft(self,iterable): |
100 | | -foreleminiterable: |
101 | | -self.appendleft(elem) |
102 | | -extendleft.func_annotations= {} |
103 | | - |
104 | | -defrotate(self,n=1): |
105 | | -ifself: |
106 | | -n%=len(self) |
107 | | -foriinxrange(n): |
108 | | -self.appendleft(self.pop()) |
109 | | -rotate.func_annotations= {} |
110 | | - |
111 | | -def__getitem__(self,i): |
112 | | -ifi<0: |
113 | | -i+=len(self) |
114 | | -try: |
115 | | -returnself.data[i+self.left] |
116 | | -exceptKeyError: |
117 | | -raiseIndexError |
118 | | -__getitem__.func_annotations= {} |
119 | | - |
120 | | -def__setitem__(self,i,value): |
121 | | -ifi<0: |
122 | | -i+=len(self) |
123 | | -try: |
124 | | -self.data[i+self.left]=value |
125 | | -exceptKeyError: |
126 | | -raiseIndexError |
127 | | -__setitem__.func_annotations= {} |
128 | | - |
129 | | -def__delitem__(self,i): |
130 | | -size=len(self) |
131 | | -ifnot (-size<=i<size): |
132 | | -raiseIndexError |
133 | | -data=self.data |
134 | | -ifi<0: |
135 | | -i+=size |
136 | | -forjinxrange(self.left+i,self.right-1): |
137 | | -data[j]=data[j+1] |
138 | | -self.pop() |
139 | | -__delitem__.func_annotations= {} |
140 | | - |
141 | | -def__len__(self): |
142 | | -returnself.right-self.left |
143 | | -__len__.func_annotations= {} |
144 | | - |
145 | | -def__cmp__(self,other): |
146 | | -iftype(self)!=type(other): |
147 | | -returncmp(type(self),type(other)) |
148 | | -returncmp(list(self),list(other)) |
149 | | -__cmp__.func_annotations= {} |
150 | | - |
151 | | -def__repr__(self,_track=[]): |
152 | | -ifid(self)in_track: |
153 | | -returnu'...' |
154 | | -_track.append(id(self)) |
155 | | -r=u'deque(%r)'% (list(self),) |
156 | | -_track.remove(id(self)) |
157 | | -returnr |
158 | | -__repr__.func_annotations= {} |
159 | | - |
160 | | -def__getstate__(self): |
161 | | -return (tuple(self),) |
162 | | -__getstate__.func_annotations= {} |
163 | | - |
164 | | -def__setstate__(self,s): |
165 | | -self.__init__(s[0]) |
166 | | -__setstate__.func_annotations= {} |
167 | | - |
168 | | -def__hash__(self): |
169 | | -raiseTypeError |
170 | | -__hash__.func_annotations= {} |
171 | | - |
172 | | -def__copy__(self): |
173 | | -returnself.__class__(self) |
174 | | -__copy__.func_annotations= {} |
175 | | - |
176 | | -def__deepcopy__(self,memo={}): |
177 | | -fromcopyimportdeepcopy |
178 | | -result=self.__class__() |
179 | | -memo[id(self)]=result |
180 | | -result.__init__(deepcopy(tuple(self),memo)) |
181 | | -returnresult |
182 | | -__deepcopy__.func_annotations= {} |
183 | 37 |
|
184 | 38 | #Some utility functions to dal with weirdness around UCS2 vs UCS4 |
185 | 39 | #python builds |
|