1 #!/usr/bin/env python 2 3 """ 4 Sequence operations. 5 6 Copyright (C) 2015, 2016, 2017, 2018 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, is_int, list_element 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 is_int(index): 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 is_int(index): 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 def __get_multiple_items__(self, start, end, step): 119 120 """ 121 Return items from 'start' until (but excluding) 'end', at 'step' 122 intervals. 123 """ 124 125 result = [] 126 127 while step > 0 and start < end or step < 0 and start > end: 128 result.append(self.__get_single_item__(start)) 129 start += step 130 131 return result 132 133 # Methods implemented by subclasses: 134 135 # __setslice__(self, start, end, value) 136 # __get_single_item__(self, index) 137 # __set_single_item__(self, index, value) 138 # __len__(self) 139 140 class hashable(itemaccess): 141 142 "An abstract class providing support for hashable sequences." 143 144 _p = maxint / 32 145 _a = 31 146 147 def _hashvalue(self, fn): 148 149 """ 150 Return a value for hashing purposes for the sequence using the given 151 'fn' on each item. 152 """ 153 154 result = 0 155 l = self.__len__() 156 i = 0 157 158 while i < l: 159 result = (result * self._a + fn(self.__get_single_item__(i))) % self._p 160 i += 1 161 162 return result 163 164 class sequence(itemaccess): 165 166 "A common base class for sequence types." 167 168 def _str(self, opening, closing): 169 170 "Serialise this object with the given 'opening' and 'closing' strings." 171 172 b = buffer() 173 i = 0 174 l = self.__len__() 175 first = True 176 177 b.append(opening) 178 while i < l: 179 if first: 180 first = False 181 else: 182 b.append(", ") 183 b.append(repr(self.__get_single_item__(i))) 184 i += 1 185 b.append(closing) 186 187 return str(b) 188 189 def __contains__(self, value): 190 191 "Return whether the list contains 'value'." 192 193 # Perform a linear search of the sequence contents. 194 195 for v in self: 196 197 # Return True if the current value is equal to the specified one. 198 # Note that this is not an identity test, but an equality test. 199 200 if v == value: 201 return True 202 203 return False 204 205 def index(self, value): 206 207 "Return the index of 'value' or raise ValueError." 208 209 i = 0 210 l = self.__len__() 211 while i < l: 212 if self[i] == value: 213 return i 214 i += 1 215 216 raise ValueError(value) 217 218 def __eq__(self, other): 219 220 "Return whether this sequence is equal to 'other'." 221 222 try: 223 return self._eq(other) 224 except TypeError: 225 return NotImplemented 226 227 def _eq(self, other): 228 229 """ 230 Return whether this sequence is equal to 'other' sequence. Note that 231 this method will raise a TypeError if 'other' is not a sequence. 232 """ 233 234 # Sequences must have equal lengths to be equal. 235 236 n = self.__len__() 237 if other.__len__() != n: 238 return False 239 240 i = 0 241 while i < n: 242 if self.__getitem__(i) != other.__getitem__(i): 243 return False 244 i += 1 245 246 return True 247 248 def __ne__(self, other): 249 250 "Return whether this sequence is not equal to 'other'." 251 252 return not self.__eq__(other) 253 254 # Methods implemented by subclasses: 255 256 # __iter__(self) 257 258 class unpackable(sequence): 259 260 "Class for list and tuple unpacking." 261 262 def __get_single_item_unchecked__(self, index): 263 264 """ 265 This method is provided by a privileged attribute recorded in the common 266 module in the toolchain. Normal programs should not be able to access 267 it. 268 """ 269 270 # NOTE: This uses implementation-specific access. 271 272 return list_element(self.__data__, index) 273 274 def _get_absolute_index(index, length): 275 276 """ 277 Return the absolute index for 'index' given a collection having the 278 specified 'length'. 279 """ 280 281 if index < 0: 282 return length + index 283 else: 284 return index 285 286 def _test_length(seq, length): 287 288 "Helper function for asserting that 'seq' is of the given 'length'." 289 290 if len(seq) != length: 291 raise ValueError, length 292 293 # vim: tabstop=4 expandtab shiftwidth=4