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