Circular Range in Python

Question

How can I implement a circular range object in Python?

e.g.

Let S is a circular space modulo 2^3 (range [0, 2^3)). I want to generate a range object like this:

crange(3, 7, 2 ** 3) => a range object [3, 4, 5, 6]
crange(7, 3, 2 ** 3) => a range object [7, 0, 1, 2]

I tryed this:

def crange(start, stop, modulo):
    if start > stop:
        return range(start, modulo) or range(stop)
    else:
        return range(start, stop)

But I can't input bigint to crange e.g. crange(8, 2, 2 ** 160).

OverflowError: Python int too large to convert to C ssize_t

What have you tried already? post it so we can help. SO is not a code writing service — kmaork, Dec 05 '16 at 08:50
What result do you want for `crange(0, 8)` in the example you give? — Mark Dickinson, Dec 05 '16 at 08:50
Sorry for the lack of explanation. I add detail information. — sira, Dec 05 '16 at 08:54
related: [`xrange(2**100)` -> OverflowError: long int too large to convert to int](http://stackoverflow.com/q/1482480/4279). In particular, [`lrange()`](https://github.com/zed/lrange/) — jfs, Dec 05 '16 at 08:56
`crange(8, 2, 2 ** 160)`. Um. Wouldn't this be asking for a list with almost 2**160 elements? If not, what sort of answer do you want here? — Mark Dickinson, Dec 05 '16 at 08:56
@MarkDickinson In Python 3, range generates a range object. I don't want a list with 2**160 elements. — sira, Dec 05 '16 at 09:03
Ah, you should probably clarify your question, then. Your desired outputs look very much like plain old lists. — Mark Dickinson, Dec 05 '16 at 09:05
Interestingly, your code is raising `OverflowError` because evaluating the truthiness of a large `range` apparently raises `OverflowError` (even though the range itself is representable). That's arguably a bug. I've opened http://bugs.python.org/issue28876 — Mark Dickinson, Dec 05 '16 at 09:44
@sira: it is related but it is a different issue (lrange() won't help unless it will define `__bool__` method—it is easy but it will break the compatibility with the range() from Python 3). No range() object would generate `7, 0, 1, 2`. The specific error is due to [bool(range())](https://docs.python.org/3/reference/datamodel.html#object.__bool__) being implemented as len(range()) and due to the implementation history len() is limited to C ssize_t size. Here's what [Guido said about it in 2008](http://bugs.python.org/msg70525) — jfs, Dec 05 '16 at 09:49

score 3 · Answer 1 · answered Dec 05 '16 at 09:05

3

You can avoid the use of range and the storage of a huge list in memory by creating your own generator:

def crange(start, end, modulo):
    if start > end:
        while start < modulo:
            yield start
            start += 1
        start = 0

    while start < end:
        yield start
        start += 1

print list(crange(3, 7, 2 ** 3))
print list(crange(7, 3, 2 ** 3))
print next(crange(8, 2, 2 ** 160))

This code outputs:

[3, 4, 5, 6]
[7, 0, 1, 2]
8

answered Dec 05 '16 at 09:05

kmaork

5,384
2
20
38

`crange(2, 2 ** 100, 2 ** 160)` take up so much memory. How can I fix it? – sira Dec 05 '16 at 09:10
It doesn't. The generator doesn't store anything in memory except for the local variables. – kmaork Dec 05 '16 at 09:11
I understood. Thank you. – sira Dec 05 '16 at 09:13

score 2 · Answer 2 · answered Dec 05 '16 at 09:03

Try this:

def crange(start, stop, modulo):
    result = []
    index = start
    while index != stop:
        result.append(index)
        index = (index + 1) % modulo
    return result

If you know that your list can be too long, you can use a generator instead that generates the necessage sequence:

def crange(start, stop, modulo):
    index = start
    while index != stop:
        yield index
        index = (index + 1) % modulo

sira · Accepted Answer · 2016-12-08T19:31:20.557

Thank you very much, everyone.

I implemented crange which I want (in reference to @Ni and @J.F.Sebastian).

import math


class crange:
    def __init__(self, start, stop, step=None, modulo=None):
        if step == 0:
            raise ValueError('crange() arg 3 must not be zero')

        if step is None and modulo is None:
            self.start = 0
            self.stop = start
            self.step = 1
            self.modulo = stop
        else:
            self.start = start
            self.stop = stop
            if modulo is None:
                self.step = 1
                self.modulo = step
            else:
                self.step = step
                self.modulo = modulo

    def __iter__(self):
        n = self.start
        if n > self.stop:
            while n < self.modulo:
                yield n
                n += 1
            n = 0
        while n < self.stop:
            yield n
            n += 1

    def __contains__(self, n):
        if self.start >= self.stop:
            return self.start <= n < self.modulo or 0 <= n < self.stop
        else:
            return self.start <= n < self.stop

I got the following output:

>>> print(list(crange(start=7, stop=3, modulo=2 ** 4)))
[7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2]
>>> print(3 in crange(start=7, stop=3, modulo=2 ** 4))
False
>>> print(7 in crange(start=7, stop=3, modulo=2 ** 4))
True
>>> print(list(crange(start=3, stop=7, modulo=2 ** 4)))
[3, 4, 5, 6]
>>> print(3 in crange(start=3, stop=7, modulo=2 ** 4))
True
>>> print(7 in crange(start=3, stop=7, modulo=2 ** 4))
False

Circular Range in Python

3 Answers3