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