Lichen

lib/__builtins__/sequence.py

580:e703b981b9b1
2017-02-13 Paul Boddie Eliminated redundant struct usage. method-wrapper-for-context
     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