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