List rotation

Jeremy Bowers jerf at jerf.org
Thu Sep 30 21:48:37 CEST 2004


On Thu, 30 Sep 2004 04:11:47 +0100, M. Clift wrote:

> Hi All,
> 
> Could someone help me out with this?
> 
> items = ('a', 'b', 'c', 'd')
> items + 1 = ( 'b', 'c', 'd', 'a')
> items + 2 = ( 'c', 'd', 'a', 'b')
> items + 3 = ( 'd', 'a', 'b', 'c')

I keep seeing this come up and waiting for someone to post this answer,
which is what I think I would use. It happens to nearly work like you
wrote, too, though I actually had this idea formulated before your post:

----------------

class Rotater(object):
    """Rotater takes a sequence of fixed length (__len__ is
    defined) that uses __getitem__ from 0 to len - 1, and translates
    accesses such that the resulting list appears rotated, without
    building any new lists.

    Usage examples:

    >>> l = ['a', 'b', 'c', 'd', 'e']
    >>> r = Rotater(l) # No initial translation
    >>> r[0] == 'a'
    True
    >>> r[-1] == 'e'
    True
    >>> r += 1 # translate by one more
    >>> r[0] == 'b'
    True
    >>> r[-1] == 'a'
    True
    >>> list(r) == ['b', 'c', 'd', 'e', 'a']
    True
    >>> r += 9 # can go beyond one rotation
    >>> list(r) == l
    True
    >>> r -= 11 # can use negative rotation
    >>> list(r)
    ['e', 'a', 'b', 'c', 'd']
    >>> list(r+1)
    ['a', 'b', 'c', 'd', 'e']
    >>> list(r-1)
    ['d', 'e', 'a', 'b', 'c']
    >>> list(1+r)
    ['a', 'b', 'c', 'd', 'e']
    """

    def __init__(self, wrapped, offset = 0):
        self.wrapped = wrapped
        self.offset = offset

    def __getitem__(self, index):
        index += self.offset
        index %= len(self.wrapped)
        return self.wrapped[index]

    def __iadd__(self, offset):
        self.offset += offset
        return self

    def __isub__(self, offset):
        self.offset -= offset
        return self

    def __add__(self, offset):
        return Rotater(self.wrapped, self.offset + offset)
    def __sub__(self, offset):
        return Rotater(self.wrapped, self.offset - offset)
    def __radd__(self, offset):
        return Rotater(self.wrapped, self.offset + offset)

    def __iter__(self):
        for i in range(len(self.wrapped)):
            yield self[i]

if __name__ == "__main__":
    import sys
    import doctest
    doctest.testmod(sys.modules[__name__])

------------

This wins big for large lists that are rotated a lot by not constructing
extra lists. Note changes to the underlying lists are reflected in the
rotations, which can be a feature or a mis-feature depending on the
problem. In the small, it can be more convenient to work with than the
other solutions... or not, again depending on the problem.




More information about the Python-list mailing list