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 tried 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

Answer 1

Python 3.x's range objects provides more functionality than just iteration and membership testing: subscripting (indexing), reverse iteration, length testing (which implies boolean coercion), the .count and .index methods (all of these collectively being the Sequence protocol), plus __str__ and __repr__.

To emulate these, we can wrap a range object, delegating to its methods with modified arguments. We can also leverage collections.abc in order to avoid the need to delegate everything, relying on mixins from the Sequence ABC instead.

There's also an issue here in that the input specification is tricky to interpret in corner cases, and inflexible (for example, we can't represent an iterator over [3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6]). The simple way around this is to redefine: a crange(start, stop, step, modulo) iterates over the values start % modulo, (start + step) % modulo ... (start + n * step) % modulo, such that (start + n * step) is limited to stop. (That is: the same values as would be in the range, but applying the specified modulo value to each of them.)

This is fairly straightforward to implement, as we need only __getitem__ and __len__:

from collections.abc import Sequence
class crange(Sequence):
    def __init__(self, start, stop, *, step=1, modulo=None):
        self._modulo, self._impl = modulo, range(start, stop, step)
    def __getitem__(self, index):
        result = self._impl[index]
        if self._modulo is not None:
            result %= self._modulo
        return result
    def __len__(self):
        return len(self._impl)
    def __repr__(self):
        return f'c{self._impl}'

Now we can do fun things like:

>>> list(reversed(crange(7, 19, step=3, modulo=8)))
[0, 5, 2, 7]

Answer 2

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

Answer 3

I made my own version that can slice forwards and backwards. What it can't do in this state is use negative integers and different step sizes than one though, so that would need to be implemented to cover the whole gamut of slicing options in python. I bet that's an easy addition though.

l = list(range(10))

def crange(l,a,b):
  
  assert a >= 0
  assert b >= 0
  
  d = b-a 
  
  if d == 0:
    return
  elif d > 0:
    increment = 1
  elif d < 0:
    increment = -1
  
  start = a%len(l)
  counter = 0
  
  while counter <= abs(d):
    index = abs(start + counter*increment)%len(l)
    yield l[index]
    counter += 1
    
print(list(l))
print(list(crange(l,0,6)))
print(list(crange(l,6,10)))
print(list(crange(l,10,25)))
print(list(crange(l,9,0)))
print(list(crange(l,10,5)))

Answer 4

Added no reset to start and subscriptability. original copied from answer by @sira

class Crange:
    def __init__(self, start, stop, step=None, modulo=None, no_reset=True):
        if step == 0:
            raise ValueError('crange() arg 3 must not be zero')
        self.no_reset = no_reset
        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 += self.step
            if n > self.modulo: 
                n = n-self.modulo if self.no_reset else 0
            else: n=0
        while n < self.stop:
            yield n
            n += self.step
            
    def __getitem__(self, __name):
        return [*self][__name]
        
    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
    

Answer 5

An equivalent solution to that of @Fomalhaut but simpler:

def crange(start, end, modulo):
    for i in range(start,end):
        yield i % modulo

Answer 6

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

Answer 7

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