12
\$\begingroup\$

I implemented class Range as an equivalent to Python built-in range for practicing purposes. No features were added. Hope it mimics all aspects of range behavior, but maybe you can point out something I forgot. Also I tried to make the code efficient, that's why Range doesn't inherit from collections.abc.Sequence and doesn't use any of it's not abstract methods. All feedback on how to improve the code is welcome!

pyrange.py

"""
Pure Python implementation of built-in range
"""


import math
import collections.abc
import numbers


def interpret_as_integer(obj):
    if hasattr(obj, '__index__'):
        return obj.__index__()
    raise TypeError(
        '\'{}\' object cannot be interpreted as an integer'.format(
            type(obj).__name__
        )
    )


def adjust_indices(length, start, stop, step):
    if step is None:
        step = 1
    else:
        step = interpret_as_integer(step)

    if start is None:
        start = length - 1 if step < 0 else 0
    else:
        start = interpret_as_integer(start)
        if start < 0:
            start += length
            if start < 0:
                start = -1 if step < 0 else 0
        elif start >= length:
            start = length - 1 if step < 0 else length

    if stop is None:
        stop = -1 if step < 0 else length
    else:
        stop = interpret_as_integer(stop)
        if stop < 0:
            stop += length
            if stop < 0:
                stop = -1 if step < 0 else 0
        elif stop >= length:
            stop = length - 1 if step < 0 else length

    return start, stop, step


class Range:
    """
    Range(stop) -> Range object
    Range(start, stop[, step]) -> Range object

    Return an object that produces a sequence of integers from start (inclusive)
    to stop (exclusive) by step. Range(i, j) produces i, i+1, i+2, ..., j-1.
    start defaults to 0, and stop is omitted!  Range(4) produces 0, 1, 2, 3.
    These are exactly the valid indices for a list of 4 elements.
    When step is given, it specifies the increment (or decrement).
    """

    __slots__ = ('start', 'stop', 'step', '_len')

    def __init__(self, start, stop=None, step=1):
        if stop is None:
            start, stop = 0, start
        self.start, self.stop, self.step = (
            interpret_as_integer(obj) for obj in (start, stop, step)
        )
        if step == 0:
            raise ValueError('Range() arg 3 must not be zero')
        step_sign = int(math.copysign(1, self.step))
        self._len = max(
            1 + (self.stop - self.start - step_sign) // self.step, 0
        )

    def __contains__(self, value):
        if isinstance(value, numbers.Integral):
            return self._index(value) != -1
        return any(n == value for n in self)

    def __eq__(self, other):
        if not isinstance(other, Range):
            return False
        if self._len != len(other):
            return False
        if self._len == 0:
            return True
        if self.start != other.start:
            return False
        if self[-1] == other[-1]:
            return True
        return False

    def __getitem__(self, index):
        if isinstance(index, slice):
            start, stop, step = adjust_indices(
                self._len, index.start, index.stop, index.step
            )
            return Range(
                self.start + self.step * start,
                self.start + self.step * stop,
                self.step * step
            )
        index = interpret_as_integer(index)
        if index < 0:
            index += self._len
        if not 0 <= index < self._len:
            raise IndexError('Range object index out of Range')
        return self.start + self.step * index

    def __hash__(self):
        if self._len == 0:
            return id(Range)
        return hash((self._len, self.start, self[-1]))

    def __iter__(self):
        value = self.start
        if self.step > 0:
            while value < self.stop:
                yield value
                value += self.step
        else:
            while value > self.stop:
                yield value
                value += self.step

    def __len__(self):
        return self._len

    def __repr__(self):
        if self.step == 1:
            return 'Range({}, {})'.format(self.start, self.stop)
        return 'Range({}, {}, {})'.format(self.start, self.stop, self.step)

    def __reversed__(self):
        return iter(self[::-1])

    def _index(self, value):
        index_mul_step = value - self.start
        if index_mul_step % self.step:
            return -1
        index = index_mul_step // self.step
        if 0 <= index < self._len:
            return index
        return -1

    def count(self, value):
        """
        Rangeobject.count(value) -> integer
        Return number of occurrences of value.
        """
        return sum(1 for n in self if n == value)

    def index(self, value, start=0, stop=None):
        """
        Rangeobject.index(value, [start, [stop]]) -> integer
        Return index of value.
        Raise ValueError if the value is not present.
        """
        if start < 0:
            start = max(self._len + start, 0)
        if stop is None:
            stop = self._len
        if stop < 0:
            stop += self._len

        if isinstance(value, numbers.Integral):
            index = self._index(value)
            if start <= index < stop:
                return index
            raise ValueError('{} is not in Range'.format(value))

        i = start
        n = self.start + self.step * i
        while i < stop:
            if n == value:
                return i
            i += 1
            n += self.step
        raise ValueError('{} is not in Range'.format(value))


collections.abc.Sequence.register(Range)

test_pyrange.py

# pylint: disable = too-few-public-methods

import itertools

from pyrange import Range


class Equal:
    def __eq__(self, other):
        return True


class Indexable:
    def __init__(self, n):
        self.n = n

    def __index__(self):
        return self.n


def test_basic():
    small_builtin_range = range(10)
    small_my_range = Range(10)
    equal = Equal()
    assert small_builtin_range.count(equal) == small_my_range.count(equal) == 10
    assert small_my_range.index(equal) == small_my_range.index(equal) == 0

    big_my_range = Range(0, 10 ** 20, 10 ** 5)
    assert 10 ** 15 in big_my_range
    assert big_my_range[Indexable(10 ** 3)] == 10 ** 8
    assert big_my_range[
        Indexable(10 ** 3):Indexable(10 ** 6):Indexable(10 ** 2)
    ] == Range(10 ** 8, 10 ** 11, 10 ** 7)


def test_slicing():
    for start, stop, step in itertools.product(range(-3, 3), repeat=3):
        if step == 0:
            continue
        builtin_range = range(start, stop, step)
        my_range = Range(start, stop, step)
        for slice_start, slice_stop, slice_step in itertools.product(
                list(range(-3, 3)) + [None], repeat=3
        ):
            if slice_step == 0:
                continue
            slc = slice(slice_start, slice_stop, slice_step)
            builtin_range_slice = builtin_range[slc]
            my_range_slice = my_range[slc]
            for name in ('start', 'stop', 'step'):
                assert (
                    getattr(builtin_range_slice, name) ==
                    getattr(my_range_slice, name)
                ), (start, stop, step, slice_start, slice_stop, slice_step)


def test_eq_and_hash():
    for start, stop, step in itertools.product(range(-3, 3), repeat=3):
        if step == 0:
            continue
        builtin_range = range(start, stop, step)
        my_range = Range(start, stop, step)
        for start_2, stop_2, step_2 in itertools.product(
                range(-3, 3), repeat=3
        ):
            if step_2 == 0:
                continue
            builtin_range_2 = range(start_2, stop_2, step_2)
            my_range_2 = Range(start_2, stop_2, step_2)
            if builtin_range == builtin_range_2:
                assert my_range == my_range_2, (
                    start, stop, step, start_2, stop_2, step_2
                )
                assert hash(my_range) == hash(my_range_2), (
                    start, stop, step, start_2, stop_2, step_2
                )
\$\endgroup\$
  • \$\begingroup\$ Your constructor is __init__(start, stop=None, step=1). Shouldn't start be optional and stop positional? range(3) means [0, 1, 2], not [3, 4, 5, ...]. \$\endgroup\$ – Jack M Sep 15 at 19:19
  • \$\begingroup\$ @JackM in case of Range(3) there are lines if stop is None: start, stop = 0, start. \$\endgroup\$ – sanyash Sep 15 at 19:28
5
\$\begingroup\$

It does not mimic all aspects of range. The range object is immutable:

>>> r = range(1,5,2)
>>> r.start
1
>>> r.start = 3
Traceback (most recent call last):
  module __main__ line 130
    traceback.print_exc()
  module <module> line 1
    r.start = 3
AttributeError: readonly attribute
>>> 

Yours is not. But you might be able to fix that by inheriting from collections.namedtuple.

\$\endgroup\$
  • \$\begingroup\$ Good point about immutability. However I don't think that inhertiting from collections.namedtuple is the best idea. Do you know another alternatives? \$\endgroup\$ – sanyash Sep 15 at 22:33
  • \$\begingroup\$ The are hacks to make objects immutable, such as here and here, but why are you opposed to inheriting from namedtuple? \$\endgroup\$ – AJNeufeld Sep 15 at 22:46
  • \$\begingroup\$ Because logically Range has nothing common with namedtuple or tuple. range_obj[0] == range_obj.start but range_obj[1] != range_obj.stop in many cases and range_obj[2] != range_obj.step in many cases. \$\endgroup\$ – sanyash Sep 15 at 22:51
  • \$\begingroup\$ As I see, hacking __setattr__ is the best way. \$\endgroup\$ – sanyash Sep 15 at 22:56
  • 1
    \$\begingroup\$ Hmm. It seems I can’t subclass a namedtuple and overload the __getitem__ method to a different behaviour. How ... exceptional. Well, you’ve got the __setattr__ hack, so you can make your Range immutable that way. \$\endgroup\$ – AJNeufeld Sep 15 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.