1 #!/usr/bin/env python 2 3 """ 4 Sequence operations. 5 6 Copyright (C) 2015, 2016, 2017 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 15 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 16 details. 17 18 You should have received a copy of the GNU General Public License along with 19 this program. If not, see <http://www.gnu.org/licenses/>. 20 """ 21 22 from __builtins__.int import maxint 23 from native import isinstance as _isinstance 24 25 class itemaccess: 26 27 "An abstract class providing item access." 28 29 def _check_index(self, index): 30 31 """ 32 Check the given absolute 'index', raising an IndexError if out of 33 bounds. 34 """ 35 36 if index < 0 or index >= self.__len__(): 37 raise IndexError(index) 38 39 def _confine_index(self, index): 40 41 """ 42 Return the given absolute 'index', confined by the bounds of the 43 sequence. 44 """ 45 46 length = self.__len__() 47 48 if index < 0: 49 return 0 50 elif index > length: 51 return length 52 else: 53 return index 54 55 def __getitem__(self, index): 56 57 "Return the item or slice specified by 'index'." 58 59 # Normalise any integer indexes, converting negative indexes to positive 60 # ones. 61 62 if _isinstance(index, int): 63 index = _get_absolute_index(index, self.__len__()) 64 return self.__get_single_item__(index) 65 66 # Handle slices separately. 67 68 elif _isinstance(index, slice): 69 return self.__getslice__(index.start, index.end, index.step) 70 71 # No other kinds of objects are supported as indexes. 72 73 else: 74 raise TypeError() 75 76 def __setitem__(self, index, value): 77 78 "Set at 'index' the given 'value'." 79 80 # Normalise any integer indexes, converting negative indexes to positive 81 # ones. 82 83 if _isinstance(index, int): 84 index = _get_absolute_index(index, self.__len__()) 85 return self.__set_single_item__(index, value) 86 87 # Handle slices separately. 88 89 elif _isinstance(index, slice): 90 return self.__setslice__(index.start, index.end, value) 91 92 # No other kinds of objects are supported as indexes. 93 94 else: 95 raise TypeError() 96 97 def __getslice__(self, start, end=None, step=1): 98 99 """ 100 Return a slice of the sequence starting from the 'start' index, ending 101 before the optional 'end' (or at the end of the sequence), and providing 102 items at the frequency given by 'step' (with a default step of 1). 103 """ 104 105 if step == 0: 106 raise ValueError(step) 107 108 length = self.__len__() 109 110 # Handle a null start as the first position, otherwise normalising any 111 # start index. 112 113 if start is None: 114 if step > 0: 115 start = 0 116 else: 117 start = length - 1 118 else: 119 start = _get_absolute_index(start, length) 120 121 # Handle a null end as the first position after the end of the sequence, 122 # otherwise normalising any end index. 123 124 if end is None: 125 if step > 0: 126 end = length 127 else: 128 end = -1 129 else: 130 end = _get_absolute_index(end, length) 131 132 return self.__get_multiple_items__(start, end, step) 133 134 # Methods implemented by subclasses. 135 136 def __setslice__(self, start, end, value): 137 138 "Method to be overridden by subclasses." 139 140 pass 141 142 def __get_single_item__(self, index): 143 144 "Method to be overridden by subclasses." 145 146 return None 147 148 def __set_single_item__(self, index, value): 149 150 "Method to be overridden by subclasses." 151 152 pass 153 154 def __get_multiple_items__(self, start, end, step): 155 156 "Method to be overridden by subclasses." 157 158 return None 159 160 def __len__(self): 161 162 "Method to be overridden by subclasses." 163 164 return 0 165 166 class hashable(itemaccess): 167 168 "An abstract class providing support for hashable sequences." 169 170 _p = maxint / 32 171 _a = 31 172 173 def _hashvalue(self, fn): 174 175 """ 176 Return a value for hashing purposes for the sequence using the given 177 'fn' on each item. 178 """ 179 180 result = 0 181 l = self.__len__() 182 i = 0 183 184 while i < l: 185 result = (result * self._a + fn(self.__get_single_item__(i))) % self._p 186 i += 1 187 188 return result 189 190 class sequence(itemaccess): 191 192 "A common base class for sequence types." 193 194 def _str(self, opening, closing): 195 196 "Serialise this object with the given 'opening' and 'closing' strings." 197 198 b = buffer() 199 i = 0 200 l = self.__len__() 201 first = True 202 203 b.append(opening) 204 while i < l: 205 if first: 206 first = False 207 else: 208 b.append(", ") 209 b.append(repr(self.__get_single_item__(i))) 210 i += 1 211 b.append(closing) 212 213 return str(b) 214 215 def __contains__(self, value): 216 217 "Return whether the list contains 'value'." 218 219 # Perform a linear search of the sequence contents. 220 221 for v in self: 222 223 # Return True if the current value is equal to the specified one. 224 # Note that this is not an identity test, but an equality test. 225 226 if v == value: 227 return True 228 229 return False 230 231 def index(self, value): 232 233 "Return the index of 'value' or raise ValueError." 234 235 i = 0 236 l = self.__len__() 237 while i < l: 238 if self[i] == value: 239 return i 240 i += 1 241 242 raise ValueError(value) 243 244 def __eq__(self, other): 245 246 "Return whether this sequence is equal to 'other'." 247 248 try: 249 return self._eq(other) 250 except TypeError: 251 return NotImplemented 252 253 def _eq(self, other): 254 255 """ 256 Return whether this sequence is equal to 'other' sequence. Note that 257 this method will raise a TypeError if 'other' is not a sequence. 258 """ 259 260 # Sequences must have equal lengths to be equal. 261 262 n = self.__len__() 263 if other.__len__() != n: 264 return False 265 266 i = 0 267 while i < n: 268 if self.__getitem__(i) != other.__getitem__(i): 269 return False 270 i += 1 271 272 return True 273 274 def __ne__(self, other): 275 276 "Return whether this sequence is not equal to 'other'." 277 278 return not self.__eq__(other) 279 280 def __iter__(self): 281 282 "Method to be overridden by subclasses." 283 284 raise StopIteration() 285 286 def __get_multiple_items__(self, start, end, step): 287 288 """ 289 Return items from 'start' until (but excluding) 'end', at 'step' 290 intervals. 291 """ 292 293 result = [] 294 295 while step > 0 and start < end or step < 0 and start > end: 296 result.append(self.__get_single_item__(start)) 297 start += step 298 299 return result 300 301 def _get_absolute_index(index, length): 302 303 """ 304 Return the absolute index for 'index' given a collection having the 305 specified 'length'. 306 """ 307 308 if index < 0: 309 return length + index 310 else: 311 return index 312 313 # vim: tabstop=4 expandtab shiftwidth=4