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