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