Debian Codegraph @

django/contrib/gis/geos/mutable_list.py

raw
1 # Copyright (c) 2008-2009 Aryeh Leib Taurog, all rights reserved.
2 # Released under the New BSD license.
3 """
4 This module contains a base type which provides list-style mutations
5 without specific data storage methods.
6
7 See also http://static.aryehleib.com/oldsite/MutableLists.html
8
9 Author: Aryeh Leib Taurog.
10 """
11
12 from functools import total_ordering
13
14
15 @total_ordering
16 class ListMixin:
17 """
18 A base class which provides complete list interface.
19 Derived classes must call ListMixin's __init__() function
20 and implement the following:
21
22 function _get_single_external(self, i):
23 Return single item with index i for general use.
24 The index i will always satisfy 0 <= i < len(self).
25
26 function _get_single_internal(self, i):
27 Same as above, but for use within the class [Optional]
28 Note that if _get_single_internal and _get_single_internal return
29 different types of objects, _set_list must distinguish
30 between the two and handle each appropriately.
31
32 function _set_list(self, length, items):
33 Recreate the entire object.
34
35 NOTE: items may be a generator which calls _get_single_internal.
36 Therefore, it is necessary to cache the values in a temporary:
37 temp = list(items)
38 before clobbering the original storage.
39
40 function _set_single(self, i, value):
41 Set the single item at index i to value [Optional]
42 If left undefined, all mutations will result in rebuilding
43 the object using _set_list.
44
45 function __len__(self):
46 Return the length
47
48 int _minlength:
49 The minimum legal length [Optional]
50
51 int _maxlength:
52 The maximum legal length [Optional]
53
54 type or tuple _allowed:
55 A type or tuple of allowed item types [Optional]
56 """
57
58 _minlength = 0
59 _maxlength = None
60
61 # ### Python initialization and special list interface methods ###
62
63 def __init__(self, *args, **kwargs):
64 if not hasattr(self, "_get_single_internal"):
65 self._get_single_internal = self._get_single_external
66
67 if not hasattr(self, "_set_single"):
68 self._set_single = self._set_single_rebuild
69 self._assign_extended_slice = self._assign_extended_slice_rebuild
70
71 super().__init__(*args, **kwargs)
72
73 def __getitem__(self, index):
74 "Get the item(s) at the specified index/slice."
75 if isinstance(index, slice):
76 return [
77 self._get_single_external(i) for i in range(*index.indices(len(self)))
78 ]
79 else:
80 index = self._checkindex(index)
81 return self._get_single_external(index)
82
83 def __delitem__(self, index):
84 "Delete the item(s) at the specified index/slice."
85 if not isinstance(index, (int, slice)):
86 raise TypeError("%s is not a legal index" % index)
87
88 # calculate new length and dimensions
89 origLen = len(self)
90 if isinstance(index, int):
91 index = self._checkindex(index)
92 indexRange = [index]
93 else:
94 indexRange = range(*index.indices(origLen))
95
96 newLen = origLen - len(indexRange)
97 newItems = (
98 self._get_single_internal(i) for i in range(origLen) if i not in indexRange
99 )
100
101 self._rebuild(newLen, newItems)
102
103 def __setitem__(self, index, val):
104 "Set the item(s) at the specified index/slice."
105 if isinstance(index, slice):
106 self._set_slice(index, val)
107 else:
108 index = self._checkindex(index)
109 self._check_allowed((val,))
110 self._set_single(index, val)
111
112 # ### Special methods for arithmetic operations ###
113 def __add__(self, other):
114 "add another list-like object"
115 return self.__class__([*self, *other])
116
117 def __radd__(self, other):
118 "add to another list-like object"
119 return other.__class__([*other, *self])
120
121 def __iadd__(self, other):
122 "add another list-like object to self"
123 self.extend(other)
124 return self
125
126 def __mul__(self, n):
127 "multiply"
128 return self.__class__(list(self) * n)
129
130 def __rmul__(self, n):
131 "multiply"
132 return self.__class__(list(self) * n)
133
134 def __imul__(self, n):
135 "multiply"
136 if n <= 0:
137 del self[:]
138 else:
139 cache = list(self)
140 for i in range(n - 1):
141 self.extend(cache)
142 return self
143
144 def __eq__(self, other):
145 olen = len(other)
146 for i in range(olen):
147 try:
148 c = self[i] == other[i]
149 except IndexError:
150 # self must be shorter
151 return False
152 if not c:
153 return False
154 return len(self) == olen
155
156 def __lt__(self, other):
157 olen = len(other)
158 for i in range(olen):
159 try:
160 c = self[i] < other[i]
161 except IndexError:
162 # self must be shorter
163 return True
164 if c:
165 return c
166 elif other[i] < self[i]:
167 return False
168 return len(self) < olen
169
170 # ### Public list interface Methods ###
171 # ## Non-mutating ##
172 def count(self, val):
173 "Standard list count method"
174 count = 0
175 for i in self:
176 if val == i:
177 count += 1
178 return count
179
180 def index(self, val):
181 "Standard list index method"
182 for i in range(0, len(self)):
183 if self[i] == val:
184 return i
185 raise ValueError("%s not found in object" % val)
186
187 # ## Mutating ##
188 def append(self, val):
189 "Standard list append method"
190 self[len(self) :] = [val]
191
192 def extend(self, vals):
193 "Standard list extend method"
194 self[len(self) :] = vals
195
196 def insert(self, index, val):
197 "Standard list insert method"
198 if not isinstance(index, int):
199 raise TypeError("%s is not a legal index" % index)
200 self[index:index] = [val]
201
202 def pop(self, index=-1):
203 "Standard list pop method"
204 result = self[index]
205 del self[index]
206 return result
207
208 def remove(self, val):
209 "Standard list remove method"
210 del self[self.index(val)]
211
212 def reverse(self):
213 "Standard list reverse method"
214 self[:] = self[-1::-1]
215
216 def sort(self, key=None, reverse=False):
217 "Standard list sort method"
218 self[:] = sorted(self, key=key, reverse=reverse)
219
220 # ### Private routines ###
221 def _rebuild(self, newLen, newItems):
222 if newLen and newLen < self._minlength:
223 raise ValueError("Must have at least %d items" % self._minlength)
224 if self._maxlength is not None and newLen > self._maxlength:
225 raise ValueError("Cannot have more than %d items" % self._maxlength)
226
227 self._set_list(newLen, newItems)
228
229 def _set_single_rebuild(self, index, value):
230 self._set_slice(slice(index, index + 1, 1), [value])
231
232 def _checkindex(self, index):
233 length = len(self)
234 if 0 <= index < length:
235 return index
236 if -length <= index < 0:
237 return index + length
238 raise IndexError("invalid index: %s" % index)
239
240 def _check_allowed(self, items):
241 if hasattr(self, "_allowed"):
242 if False in [isinstance(val, self._allowed) for val in items]:
243 raise TypeError("Invalid type encountered in the arguments.")
244
245 def _set_slice(self, index, values):
246 "Assign values to a slice of the object"
247 try:
248 valueList = list(values)
249 except TypeError:
250 raise TypeError("can only assign an iterable to a slice")
251
252 self._check_allowed(valueList)
253
254 origLen = len(self)
255 start, stop, step = index.indices(origLen)
256
257 # CAREFUL: index.step and step are not the same!
258 # step will never be None
259 if index.step is None:
260 self._assign_simple_slice(start, stop, valueList)
261 else:
262 self._assign_extended_slice(start, stop, step, valueList)
263
264 def _assign_extended_slice_rebuild(self, start, stop, step, valueList):
265 "Assign an extended slice by rebuilding entire list"
266 indexList = range(start, stop, step)
267 # extended slice, only allow assigning slice of same size
268 if len(valueList) != len(indexList):
269 raise ValueError(
270 "attempt to assign sequence of size %d "
271 "to extended slice of size %d" % (len(valueList), len(indexList))
272 )
273
274 # we're not changing the length of the sequence
275 newLen = len(self)
276 newVals = dict(zip(indexList, valueList))
277
278 def newItems():
279 for i in range(newLen):
280 if i in newVals:
281 yield newVals[i]
282 else:
283 yield self._get_single_internal(i)
284
285 self._rebuild(newLen, newItems())
286
287 def _assign_extended_slice(self, start, stop, step, valueList):
288 "Assign an extended slice by re-assigning individual items"
289 indexList = range(start, stop, step)
290 # extended slice, only allow assigning slice of same size
291 if len(valueList) != len(indexList):
292 raise ValueError(
293 "attempt to assign sequence of size %d "
294 "to extended slice of size %d" % (len(valueList), len(indexList))
295 )
296
297 for i, val in zip(indexList, valueList):
298 self._set_single(i, val)
299
300 def _assign_simple_slice(self, start, stop, valueList):
301 "Assign a simple slice; Can assign slice of any length"
302 origLen = len(self)
303 stop = max(start, stop)
304 newLen = origLen - stop + start + len(valueList)
305
306 def newItems():
307 for i in range(origLen + 1):
308 if i == start:
309 yield from valueList
310
311 if i < origLen:
312 if i < start or i >= stop:
313 yield self._get_single_internal(i)
314
315 self._rebuild(newLen, newItems())