Lichen

Annotated lib/__builtins__/sequence.py

476:7153e60d49b9
2017-01-19 Paul Boddie Added simple import and __file__ attribute test.
paul@6 1
#!/usr/bin/env python
paul@6 2
paul@6 3
"""
paul@6 4
Sequence operations.
paul@6 5
paul@224 6
Copyright (C) 2015, 2016 Paul Boddie <paul@boddie.org.uk>
paul@6 7
paul@6 8
This program is free software; you can redistribute it and/or modify it under
paul@6 9
the terms of the GNU General Public License as published by the Free Software
paul@6 10
Foundation; either version 3 of the License, or (at your option) any later
paul@6 11
version.
paul@6 12
paul@6 13
This program is distributed in the hope that it will be useful, but WITHOUT
paul@6 14
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
paul@6 15
FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
paul@6 16
details.
paul@6 17
paul@6 18
You should have received a copy of the GNU General Public License along with
paul@6 19
this program.  If not, see <http://www.gnu.org/licenses/>.
paul@6 20
"""
paul@6 21
paul@459 22
from __builtins__.int import maxint
paul@356 23
from native import isinstance as _isinstance
paul@6 24
paul@292 25
class itemaccess:
paul@224 26
paul@292 27
    "An abstract class providing item access."
paul@6 28
paul@287 29
    def _check_index(self, index):
paul@287 30
paul@287 31
        """
paul@287 32
        Check the given absolute 'index', raising an IndexError if out of
paul@287 33
        bounds.
paul@287 34
        """
paul@287 35
paul@402 36
        if index < 0 or index >= self.__len__():
paul@287 37
            raise IndexError(index)
paul@287 38
paul@384 39
    def _check_end_index(self, index):
paul@384 40
paul@384 41
        """
paul@384 42
        Check the given absolute end 'index', raising an IndexError if out of
paul@384 43
        bounds.
paul@384 44
        """
paul@384 45
paul@402 46
        if index < -1 or index > self.__len__():
paul@384 47
            raise IndexError(index)
paul@384 48
paul@224 49
    def __getitem__(self, index):
paul@224 50
paul@224 51
        "Return the item or slice specified by 'index'."
paul@224 52
paul@224 53
        # Normalise any integer indexes, converting negative indexes to positive
paul@224 54
        # ones.
paul@6 55
paul@356 56
        if _isinstance(index, int):
paul@265 57
            index = _get_absolute_index(index, self.__len__())
paul@224 58
            return self.__get_single_item__(index)
paul@224 59
paul@224 60
        # Handle slices separately.
paul@6 61
paul@356 62
        elif _isinstance(index, slice):
paul@295 63
            return self.__getslice__(index.start, index.end, index.step)
paul@224 64
paul@224 65
        # No other kinds of objects are supported as indexes.
paul@6 66
paul@224 67
        else:
paul@282 68
            raise TypeError()
paul@224 69
paul@227 70
    def __setitem__(self, index, value):
paul@227 71
paul@227 72
        "Set at 'index' the given 'value'."
paul@227 73
paul@227 74
        # Normalise any integer indexes, converting negative indexes to positive
paul@227 75
        # ones.
paul@227 76
paul@356 77
        if _isinstance(index, int):
paul@265 78
            index = _get_absolute_index(index, self.__len__())
paul@227 79
            return self.__set_single_item__(index, value)
paul@227 80
paul@227 81
        # Handle slices separately.
paul@227 82
paul@356 83
        elif _isinstance(index, slice):
paul@227 84
            return self.__setslice__(index.start, index.end, value)
paul@227 85
paul@227 86
        # No other kinds of objects are supported as indexes.
paul@227 87
paul@227 88
        else:
paul@282 89
            raise TypeError()
paul@227 90
paul@295 91
    def __getslice__(self, start, end=None, step=1):
paul@6 92
paul@295 93
        """
paul@295 94
        Return a slice of the sequence starting from the 'start' index, ending
paul@295 95
        before the optional 'end' (or at the end of the sequence), and providing
paul@295 96
        items at the frequency given by 'step' (with a default step of 1).
paul@295 97
        """
paul@295 98
paul@295 99
        if step == 0:
paul@295 100
            raise ValueError(step)
paul@224 101
paul@224 102
        length = self.__len__()
paul@6 103
paul@224 104
        # Handle a null start as the first position, otherwise normalising any
paul@224 105
        # start index.
paul@224 106
paul@224 107
        if start is None:
paul@367 108
            if step > 0:
paul@367 109
                start = 0
paul@367 110
            else:
paul@367 111
                start = length - 1
paul@224 112
        else:
paul@265 113
            start = _get_absolute_index(start, length)
paul@6 114
paul@224 115
        # Handle a null end as the first position after the end of the sequence,
paul@224 116
        # otherwise normalising any end index.
paul@224 117
paul@224 118
        if end is None:
paul@367 119
            if step > 0:
paul@367 120
                end = length
paul@367 121
            else:
paul@367 122
                end = -1
paul@224 123
        else:
paul@265 124
            end = _get_absolute_index(end, length)
paul@6 125
paul@384 126
        return self.__get_multiple_items__(start, end, step)
paul@6 127
paul@351 128
    # Methods implemented by subclasses.
paul@351 129
paul@351 130
    def __setslice__(self, start, end, value):
paul@351 131
paul@351 132
        "Method to be overridden by subclasses."
paul@351 133
paul@351 134
        pass
paul@351 135
paul@351 136
    def __get_single_item__(self, index):
paul@351 137
paul@351 138
        "Method to be overridden by subclasses."
paul@351 139
paul@351 140
        return None
paul@351 141
paul@351 142
    def __set_single_item__(self, index, value):
paul@351 143
paul@351 144
        "Method to be overridden by subclasses."
paul@351 145
paul@351 146
        pass
paul@351 147
paul@384 148
    def __get_multiple_items__(self, start, end, step):
paul@384 149
paul@384 150
        "Method to be overridden by subclasses."
paul@384 151
paul@384 152
        return None
paul@384 153
paul@351 154
    def __len__(self):
paul@351 155
paul@351 156
        "Method to be overridden by subclasses."
paul@351 157
paul@351 158
        return 0
paul@351 159
paul@459 160
class hashable(itemaccess):
paul@459 161
paul@459 162
    "An abstract class providing support for hashable sequences."
paul@459 163
paul@459 164
    _p = maxint / 32
paul@459 165
    _a = 31
paul@459 166
paul@459 167
    def _hashvalue(self, fn):
paul@459 168
paul@459 169
        """
paul@459 170
        Return a value for hashing purposes for the sequence using the given
paul@459 171
        'fn' on each item.
paul@459 172
        """
paul@459 173
paul@459 174
        result = 0
paul@459 175
        l = self.__len__()
paul@459 176
        i = 0
paul@459 177
paul@459 178
        while i < l:
paul@459 179
            result = (result * self._a + fn(self.__get_single_item__(i))) % self._p
paul@459 180
            i += 1
paul@459 181
paul@459 182
        return result
paul@459 183
paul@292 184
class sequence(itemaccess):
paul@292 185
paul@292 186
    "A common base class for sequence types."
paul@292 187
paul@292 188
    def _str(self, opening, closing):
paul@292 189
paul@292 190
        "Serialise this object with the given 'opening' and 'closing' strings."
paul@292 191
paul@292 192
        b = buffer()
paul@292 193
        i = 0
paul@292 194
        l = self.__len__()
paul@292 195
        first = True
paul@292 196
paul@292 197
        b.append(opening)
paul@292 198
        while i < l:
paul@292 199
            if first:
paul@292 200
                first = False
paul@292 201
            else:
paul@292 202
                b.append(", ")
paul@292 203
            b.append(repr(self.__get_single_item__(i)))
paul@292 204
            i += 1
paul@292 205
        b.append(closing)
paul@292 206
paul@292 207
        return str(b)
paul@292 208
paul@292 209
    def __contains__(self, value):
paul@292 210
paul@292 211
        "Return whether the list contains 'value'."
paul@292 212
paul@292 213
        # Perform a linear search of the sequence contents.
paul@292 214
paul@292 215
        for v in self:
paul@292 216
paul@292 217
            # Return True if the current value is equal to the specified one.
paul@292 218
            # Note that this is not an identity test, but an equality test.
paul@292 219
paul@292 220
            if v == value:
paul@292 221
                return True
paul@292 222
paul@292 223
        return False
paul@292 224
paul@292 225
    def index(self, value):
paul@292 226
paul@292 227
        "Return the index of 'value' or raise ValueError."
paul@292 228
paul@292 229
        i = 0
paul@402 230
        l = self.__len__()
paul@292 231
        while i < l:
paul@292 232
            if self[i] == value:
paul@292 233
                return i
paul@292 234
            i += 1
paul@292 235
paul@292 236
        raise ValueError(value)
paul@292 237
paul@287 238
    def __eq__(self, other):
paul@287 239
paul@287 240
        "Return whether this sequence is equal to 'other'."
paul@287 241
paul@459 242
        try:
paul@459 243
            return self._eq(other)
paul@459 244
        except TypeError:
paul@459 245
            return NotImplemented
paul@459 246
paul@459 247
    def _eq(self, other):
paul@459 248
paul@459 249
        """
paul@459 250
        Return whether this sequence is equal to 'other' sequence. Note that
paul@459 251
        this method will raise a TypeError if 'other' is not a sequence.
paul@459 252
        """
paul@459 253
paul@287 254
        # Sequences must have equal lengths to be equal.
paul@287 255
paul@287 256
        n = self.__len__()
paul@402 257
        if other.__len__() != n:
paul@287 258
            return False
paul@265 259
paul@287 260
        i = 0
paul@287 261
        while i < n:
paul@287 262
            if self.__getitem__(i) != other.__getitem__(i):
paul@287 263
                return False
paul@287 264
            i += 1
paul@265 265
paul@287 266
        return True
paul@287 267
paul@287 268
    def __ne__(self, other):
paul@287 269
paul@287 270
        "Return whether this sequence is not equal to 'other'."
paul@287 271
paul@287 272
        return not self.__eq__(other)
paul@265 273
paul@351 274
    def __iter__(self):
paul@351 275
paul@351 276
        "Method to be overridden by subclasses."
paul@351 277
paul@351 278
        raise StopIteration()
paul@351 279
paul@384 280
    def __get_multiple_items__(self, start, end, step):
paul@384 281
paul@384 282
        """
paul@384 283
        Return items from 'start' until (but excluding) 'end', at 'step'
paul@384 284
        intervals.
paul@384 285
        """
paul@384 286
paul@384 287
        result = []
paul@384 288
paul@384 289
        while step > 0 and start < end or step < 0 and start > end:
paul@384 290
            result.append(self.__get_single_item__(start))
paul@384 291
            start += step
paul@384 292
paul@384 293
        return result
paul@384 294
paul@6 295
def _get_absolute_index(index, length):
paul@6 296
paul@6 297
    """
paul@6 298
    Return the absolute index for 'index' given a collection having the
paul@6 299
    specified 'length'.
paul@6 300
    """
paul@6 301
paul@6 302
    if index < 0:
paul@6 303
        return length + index
paul@6 304
    else:
paul@6 305
        return index
paul@6 306
paul@6 307
# vim: tabstop=4 expandtab shiftwidth=4