Lichen

lib/__builtins__/sequence.py

932:c07b0dd14f85
10 months ago Paul Boddie Moved integer instantiation support to library functions.
     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