Rotating list in python

Question

This is a list class which allows users to "turn" the list while keeping track of the current position. For efficiency, the list is not actually rotated on each rotation, but instead an offset keeps track of where the "0" in the list is. However, this makes addition and multiplication less efficient as these operations require to bring the list "in order" first. Another attempt has been made in the comments at this link upon which this class is loosely based.

class Ring(UserList.UserList):
    def __init__(self, initlist=None, offset=0):
        self.offset=offset
        self.data = []
        if initlist is not None:
            # XXX should this accept an arbitrary sequence?
            if type(initlist) == type(self.data):
                self.data[:] = initlist
            elif isinstance(initlist, UserList):
                self.data[:] = initlist.data[:]
            else:
                self.data = list(initlist)
    def __repr__(self): return repr(self.data[len(self.data)-self.offset:len(self.data)]+self.data[0:len(self.data)-self.offset])
    def __lt__(self, other): return self.data[len(self.data)-self.offset:len(self.data)]+self.data[0:len(self.data)-self.offset] <  self.__cast(other)
    def __le__(self, other): return self.data[len(self.data)-self.offset:len(self.data)]+self.data[0:len(self.data)-self.offset] <= self.__cast(other)
    def __eq__(self, other): return self.data[len(self.data)-self.offset:len(self.data)]+self.data[0:len(self.data)-self.offset] == self.__cast(other)
    def __ne__(self, other): return self.data[len(self.data)-self.offset:len(self.data)]+self.data[0:len(self.data)-self.offset] != self.__cast(other)
    def __gt__(self, other): return self.data[len(self.data)-self.offset:len(self.data)]+self.data[0:len(self.data)-self.offset] >  self.__cast(other)
    def __ge__(self, other): return self.data[len(self.data)-self.offset:len(self.data)]+self.data[0:len(self.data)-self.offset] >= self.__cast(other)
    def __cast(self, other):
        if isinstance(other, Ring):
            return other.data[len(other.data)-other.offset:len(other.data)]+other.data[0:len(other.data)-other.offset]
        elif isinstance(other, type(self.data)):
            return other
        else:
            return list(other)
    def __cmp__(self, other):
        return cmp(self.data[len(self.data)-self.offset:len(self.data)]+self.data[0:len(self.data)-self.offset], self.__cast(other))
    def __getitem__(self, i):
        if abs(i)>=len(self.data):
            return self.data[i] # raise IndexError
        elif (i-self.offset)<0:
            return self.data[i-self.offset+len(self.data)]
        else:
            return self.data[(i-self.offset)]
    def __setitem__(self, i, item):
        if abs(i)>=len(self.data):
            raise IndexError('list assignment index out of range')
        elif (i-self.offset)<0:
            self.data[i-self.offset+len(self.data)] = item
        else:
            self.data[(i-self.offset)] = item
    def __delitem__(self, i):
        if abs(i)>=len(self.data):
            raise IndexError('list assignment index out of range')
        elif (i-self.offset)<0:
            del self.data[i-self.offset+len(self.data)]
        else:
            del self.data[(i-self.offset)]
    def __getslice__(self, i, j):
        i = max(i, 0); j = max(j, 0)
        #it may be possible to avoid some of the complications below by setting i and j to the minimum of i, j and the length of the data
        if i>j:
            return list(None)
        elif j-self.offset<0:
            return self.__class__(self.data[i-self.offset+len(self.data):j-self.offset+len(self.data)],j-i)
        elif i-self.offset<0:
            return self.__class__(self.data[i-self.offset+len(self.data):len(self.data)]+self.data[0:min(j-self.offset,len(self.data)-self.offset)],self.offset-i)
        else:
            return self.__class__(self.data[i-self.offset:min(j-self.offset,len(self.data)-self.offset)],0)
    def __setslice__(self, i, j, other):
        i = max(i, 0); j = max(j, i)
        if isinstance(other, type(Ring)):
            sliced = other.data
            #this is not correct. slice needs to take into account the offset from the ring in other
        elif isinstance(other, type(self.data)):
            sliced = other
        else:
            sliced = list(other)
        if j-self.offset<0:
            self.data[i-self.offset+len(self.data):j-self.offset+len(self.data)]=sliced
        elif i-self.offset<0:
            self.data[0:j-self.offset]=sliced[len(sliced)-(j-self.offset):len(sliced)]
            self.data[i-self.offset+len(self.data):len(self.data)]=sliced[0:len(sliced)-(j-self.offset)]
        else:
            self.data[i-self.offset:j-self.offset]=sliced
        if self.offset>i:
            self.offset = self.offset+len(sliced)-j+i

    def __delslice__(self, i, j):
        i = max(i, 0); j = max(j, 0)
        if i>j:
            self.data=self.data
        elif j-self.offset<0:
            del self.data[i-self.offset+len(self.data):j-self.offset+len(self.data)]
        elif i-self.offset<0:
            del self.data[0:j-self.offset]
            del self.data[i-self.offset+len(self.data):len(self.data)]
        else:
            del self.data[i-self.offset:j-self.offset]
    def __add__(self, other):
        return self.__class__(self.data[0:len(self.data)-self.offset] + self.__cast(other) + self.data[len(self.data)-self.offset:len(self.data)], self.offset)
    def __radd__(self, other):
        return self.__cast(other) + self.__class__(self.data[0:len(self.data)-self.offset] + self.data[len(self.data)-self.offset:len(self.data)], 0)
    def __iadd__(self, other):
        self.data=(self.data[0:len(self.data)-self.offset] + self.__cast(other) + self.data[len(self.data)-self.offset:len(self.data)])
        return self
    def __mul__(self, n):
        return self.__class__((self.data[0:len(self.data)-self.offset] + self.data[len(self.data)-self.offset:len(self.data)])*n,0)
    __rmul__ = __mul__
    def __imul__(self, n):
        self.data=(self.data[len(self.data)-self.offset:len(self.data)] + self.data[0:len(self.data)-self.offset] )*n
        self.offset=0
        return self
    def pop(self, i=-1): 
        if abs(i)>len(self.data):
            raise IndexError
        elif i<0:
            if i-self.offset<-len(self.data):
                self.offset=self.offset-1
                return self.data.pop(i-self.offset-1+len(self.data))
            else:
                return self.data.pop(i-self.offset+len(self.data))
        else:
            if i<= self.offset:
                self.offset=self.offset-1
                return self.data.pop(i-self.offset-1+len(self.data))
            else:
                return self.data.pop(i-self.offset+len(self.data))
    def turn(self, n=1):
        self.offset = self.offset+n
        self.offset = divmod(self.offset, len(self.data))[1]
    def append(self, item):
        self.data.insert(len(self.data)-self.offset, item)
    def insert(self, i, item):
        self.data.insert((len(self.data)-self.offset + i)%len(self.data), item)
        if i==0:
            self.offset +=1
    def index(self, item, *args):
        try:
            index=self.data[len(self.data)-self.offset:len(self.data)].index(item, *args)
        except(ValueError):
            index=self.data[0:len(self.data)-self.offset].index(item, *args)+self.offset
        return index
    def reverse(self):
        self.data = self.data[0:len(self.data)-self.offset].reverse() + self.data[len(self.data)-self.offset:len(self.data)].reverse()
        self.offset = len(self.data)-self.offset
    def sort(self, *args, **kwds):
        self.data.sort(*args, **kwds)
        self.offset=0
    def extend(self, other):
        self.data = self.data[len(self.data)-self.offset:len(self.data)] + self.data[0:len(self.data)-self.offset] + self.__cast(other)
        self.offset=0

After noticing how many class methods had to be rewritten when using the offset, I started to think that simply adding a turn() method which actually changes self.data would have been easier.

PS: To make this class more like a list without beginning and end (which the name Ring seems to imply) one can change the iter() function to continue iterating endlessly.

Answer 1

Your code is long, very long. Instead of looking for premature optimizations, I'd ask you if you really can't do this with just the built-in list?

If you subtype list, then you can get all the methods and so allows us to do something as simple as:

class Ring(list):
    def turn(self, amount):
        if amount != 0:
            super(Ring, self).__init__(self[amount:] + self[:amount])

    def __repr__(self):
        # To show the object is not a list.
        return 'Ring' + super(Ring, self).__repr__()

And yes this does work as you want:

# input
r = Ring([1, 2, 3])
print(r)
r.turn(2)
print(r)
r.turn(-1)
print(r)
r += [1]
print(r)

#output
Ring[1, 2, 3]
Ring[3, 1, 2]
Ring[2, 3, 1]
Ring[2, 3, 1, 1]

---

Lets assume that you do need the performance, so we'll be going from your code. Take the following example:

r = Ring([1, 2, 3, 4, 5])
r.turn(3)
print r == [1, 2, 3] or r == [4, 5]

Not using \$O\$, what is the problem?

It's changing the list twice. Instead I'd set the list to the updated list and check if the offset is not 0. Then either way check if they are the same. You can make a small function that does this:

def update_once(self):
    if self.offset:
        self.data = self.data[len(self.data)-self.offset:len(self.data)]+self.data[0:len(self.data)-self.offset]
        self.offset = 0

I'd say the biggest problem with this, is the unneeded len(self.data) and 0. Instead remove them. After this you can re-write your special method:

def __eq__(self, other):
    self.update_once()
    return list.__eq__(self.data, other)

But that's a lot of boiler-plate for each of the special methods. And so I'd change update_once to be a wrapper.

It needs to take the function, and the data. We know that the first argument will be self and we'll write it with that in mind.

def update_once(fn):
    def call(self, other):
        if self.offset:
            self.data = self.data[-self.offset:] + self.data[:-self.offset]
            self.offset = 0
        return fn(self.data, other)
    return call

This allows you to make most of the special methods with ease:

def update_once(fn):
    def call(self, *args):
        if self.offset:
            self.data = self.data[-self.offset:] + self.data[:-self.offset]
            self.offset = 0
        return fn(self.data, *args)
    return call

class Ring(UserList.UserList):
    def __init__(self, initlist=None, offset=0):
        self.offset = offset
        self.data = []
        if initlist is not None:
            # XXX should this accept an arbitrary sequence?
            if type(initlist) == type(self.data):
                self.data[:] = initlist
            elif isinstance(initlist, UserList):
                self.data[:] = initlist.data[:]
            else:
                self.data = list(initlist)

    @update_once
    def __repr__(self):
        return 'Ring' + repr(self)

    __lt__ = update_once(list.__lt__)
    __le__ = update_once(list.__le__)
    __eq__ = update_once(list.__eq__)
    __ne__ = update_once(list.__ne__)
    __gt__ = update_once(list.__gt__)
    __ge__ = update_once(list.__ge__)
    __add__ = update_once(list.__add__)
    __mul__ = update_once(list.__mul__)
    __rmul__ = update_once(list.__rmul__)

Now we have all the not-so-easy to optimize functions made. But this still leaves us with a lot of functions to optimize. To optimize these, I'd make a new function that transforms the input index to the correct shifted index. Something simple like:

def _shift(self, *indexes):
    size = len(self.data)
    offset = self.offset
    for index in indexes:
        yield (index + offset) % size

Which allows us to do (you always have to use tuple unpacking a, = not a =):

a, b = self._shift(1, -1)
a, = self._shift(1)

This allows us to re-write pop:

def pop(self, i=-1):
    i, = self._shift(i)
    return self.data.pop(i)

Which is really nice compared to what it was before. And so you should be able to change the rest of your functions using the above, to much smaller functions.