| 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()) |