8
\$\begingroup\$

UPDATE: Thanks everyone for the suggestions! I made a follow up version here which fixes the bugs, incorporates the feedback, and has more tests.


A ReversibleList behaves like a normal list when ReversibleList.reversed == False, but it behaves as if it had been reversed when ReversibleList.reversed == True. The trick is that the underlying list is never actually reversed. This can be a boon for performance [citation needed] if whatever one's doing requires reversing and unreversing a particular list many times, or reversing many lists.

Any suggestions for improvement are welcome! Interested in whether my subclass is properly written and whether the concept makes sense to you/is self-consistent. I have overridden only a few of list's method - just enough for my use case and I'm aware there may be other list methods I may need to override in the future for expanded use cases.

Thanks in advanced for any suggestions!

Implementation

class ReversibleList(list):
    def reverse(self):
        self.reversed = True

    def forwardAll(self):
        self.reversed = False

    def toggleDirectionl(self):
        self.reversed = not self.reversed
    
    def __init__(self, iterable):
        super().__init__(iterable)
        self.reversed = False

    def __getitem__(self, key):
        if self.reversed:
            key = self._getReverseKey(key)
        if isinstance(key, slice):
            return ReversibleList(super().__getitem__(key))
        return super().__getitem__(key)

    def __setitem__(self, key, val):
        if self.reversed:
            key = self._getReverseKey(key)
            if isinstance(key, slice) and not isinstance(val, type(self)):
                super().__setitem__(key, reversed(val))
                return
        super().__setitem__(key, val)

    def __delitem__(self, key):
        if self.reversed:
            key = self._getReverseKey(key)
        return super().__delitem__(key)

    def __str__(self):
        if self.reversed:
            return '[' + ', '.join(map(str, reversed(self))) + ']'
        return super().__str__()

    def __repr__(self):
        return f'ReversibleList({super().__repr__()})'
    
    @classmethod
    def _invalidKeyTypeErrorMsg(cls, key):
        return f'list indices must be integers or slices, not {type(key).__name__}' # same error one gets when doing [0,1,2][1, 2]
    
    def _getReverseKey(self, key):
        if isinstance(key, slice):
            # PRECONDITION: key.step == 1
            N = len(self)
            i, j, _ = key.indices(len(self))
            assert i >= 0 and j >= 0, 'I assumed that slice.indices returns positive values for start and stop, but was wrong.'
            i = i or -N
            j = j or -N
            return slice(-j, -i)
        if not isinstance(key, int):
            raise TypeError(type(self)._invalidKeyTypeErrorMsg('key'))
        return -1-key

Usage

a = ReversibleList([0, 1, 2, 3, 4, 5])
print(a[1]) # 1
print(a) # [0, 1, 2, 3, 4, 5]
print(a[:]) # [0, 1, 2, 3, 4, 5]
print(repr(a)) # ReversibleList([0, 1, 2, 3, 4, 5])

a.reverse()
print(a[1]) # 4
print(a) # [5, 4, 3, 2, 1, 0]
print(a[:]) # [5, 4, 3, 2, 1, 0]
print(repr(a)) # ReversibleList([0, 1, 2, 3, 4, 5])

a[:] = a
print(a) # [5, 4, 3, 2, 1, 0]

a[2:5] = a[2:5]
print(a) # [5, 4, 3, 2, 1, 0]

print(a[2:5]) # [3, 2, 1]

a[2:5] = [3, 2, 1]
print(a) # [5, 4, 3, 2, 1, 0]

a[2:5] = ReversibleList([1, 2, 3])
print(a) # [5, 4, 3, 2, 1, 0]
\$\endgroup\$
0

5 Answers 5

6
\$\begingroup\$

Consider composition over inheritance

Doing inheritance right is very hard. Keep in mind that subclass coupling (when class A is a subclass of class B) is the strongest type of coupling between two classes.

I suggest to only subclass a class when its documentation explicitly encourages that. This is the case for example in frameworks such as Django. I cannot find such guidance in Python's docs on data structures, and I would take that as a clue.

Also note that overriding just the methods for your use case doesn't prevent calling other methods, which may work in unexpected ways. For example I would expect from a list r that r[:] and list(r) and for x in r will produce elements in consistent order with [r[i] for i in range(len(r))], but this is not what happens when r is a ReversibleList that's currently in reversed mode, even though it is a list.

Composition is a lot simpler and widely recommended. Instead of inheriting from list, make the class contain a list attribute, and implement precisely the methods that you want to support. Calling an unsupported operation will be a hard failure, rather than something unsupported without a warning.

Consider for example:

class ReversibleListView:
    """
    A view over a list of items.
    Supports accessing items with integer indexes using [] operator.
    Can present a reversed view in O(1) time.
    """
    
    def __init__(self, items):
        self.items = items
        self.reversed = False

    def reverse(self):
        self.reversed = not self.reversed

    def __getitem__(self, key):
        return self.items[self._key(key)]

    def __setitem__(self, key, value):
        self.items[self._key(key)] = value

    def _key(self, key):
        if not isinstance(key, int):
            raise TypeError("indices must be integers")

        if not self.reversed:
            return key

        size = len(self.items)
        if key < 0:
            key += size

        return size - 1 - key

Demonstrate usage with asserts instead of printing

print statements and the expected outputs as comments are weak. It's better to use assert statements, which also make it easy to make changes to the code and verify it still works.

def tests():
    def to_list(r: ReversibleListView) -> list:
        return [r[i] for i in range(len(r.items))]

    a = ReversibleListView([0, 1, 2, 3, 4, 5])
    assert a[1] == 1
    assert to_list(a) == [0, 1, 2, 3, 4, 5]

    a[1] = 9
    assert to_list(a) == [0, 9, 2, 3, 4, 5]

    a = ReversibleListView([0, 1, 2, 3, 4, 5])
    a.reverse()
    assert a[1] == 4
    assert to_list(a) == [5, 4, 3, 2, 1, 0]

    a[1] = 9
    assert to_list(a) == [5, 9, 3, 2, 1, 0]


if __name__ == '__main__':
    tests()
\$\endgroup\$
3
  • \$\begingroup\$ (As an alternative to a flag reversed, an integer self.direction = 1 negated in reverse() seems to work with _key() returning key * self.direction.) \$\endgroup\$
    – greybeard
    Sep 3, 2022 at 8:04
  • \$\begingroup\$ @greybeard not quite; when not reversed, key should map to key which key * self.direction would do, but when reversed, key should map to -key-1 (0 should map to -1, 1 should map to -2, etc.) so in that case _key() should return self.dir * key + ((self.dir - 1) // 2) s.t. when self.dir == +1, this returns key and when self.dir == -1, this returns -key-1 \$\endgroup\$
    – joseville
    Sep 8, 2022 at 3:48
  • \$\begingroup\$ Thanks everyone for the suggestions! I made a follow up version which fixes the bugs, incorporates the feedback, and has more tests: codereview.stackexchange.com/q/279555/239973 \$\endgroup\$
    – joseville
    Sep 8, 2022 at 16:55
16
\$\begingroup\$

Bug

You have a bug!

a[2:5] = ReversibleList([1, 2, 3])
print(a) # [5, 4, 3, 2, 1, 0]

ReversibleList([1, 2, 3]) is constructing a brand new unreversed list. The final result should be identical to assigning [1, 2, 3] to the slice: ie, [5, 4, 1, 2, 3, 0]

\$\endgroup\$
1
16
\$\begingroup\$

I don't really like the direction toggling stuff. Mostly on the grounds of disliking state if possible. You could end up with the list pointing in the opposite direction to the one intended.

What I might prefer is a reversible view? Something like:

r = l.reverse

In a few circumstances this makes it less likely that you leave the list in the wrong direction, because you are working on a reversed copy.

This stuff is basically doing index arithmetic... which is fine because that's an easy thing to get wrong, and I would prefer this wrapper to forever be writing len(x) - 1. Though I'd note that in practice one avoids using indexes in python whenever possible, and for these purposes for x in reversed(l) does what you want.

One thing to note is that this implementation doesn't support append or pop, Which I use a bit. So you might end up wanting to use a deque under the hood. I'd add that when I use deques a common mistake for me is to call pop instead of popleft etc, so having a reversible view on the deque might simplify things a little - I still probably wouldn't use it - before my coworkers would moan at me, but there's no reason you should care about that. I might end up doing somthing like this if I was reversing lists a lot.

This is a nice example for understanding and implementing python's dunder methods. I'd throw in that there are abstract base classes: https://docs.python.org/3/library/collections.abc.html#module-collections.abc and a set of interfaces for "types of collections" so you might want to subclass one of these if you want to avoid the possibility of surprising users.

\$\endgroup\$
4
  • 4
    \$\begingroup\$ "Mostly on the grounds of disliking state if possible." That ship has already sailed - it's a mutable list. In Python particularly, there is a very good reason for having reverse as a mutator method: the built-in list class has such a method, and Python encourages duck typing. \$\endgroup\$
    – kaya3
    Sep 3, 2022 at 8:57
  • \$\begingroup\$ @kaya3 This might be much worse than leaving it be, but what about reverse being a view that also has a __call__ to act as the mutator method? Shouldn't contradict existing usage, but could be a bit intuitively confusing. (Or the reverse view could be a separate property/method.) \$\endgroup\$ Sep 5, 2022 at 1:15
  • \$\begingroup\$ @UnrelatedString I think that would be strange. There is no problem with having both a reverse mutator method and a "reversed view", but the way people will typically ask for a reversed view is by calling the built-in reversed function, which invokes the class's __reversed__ method if it exists; so if you want to provide your own "reversed view", you should implement __reversed__. That said, this class supports the "sequence protocol", so reversed will actually construct a view automatically; so there's no need to write extra code for a view, unless you want the view to be mutable. \$\endgroup\$
    – kaya3
    Sep 5, 2022 at 8:45
  • \$\begingroup\$ Thanks everyone for the suggestions! I made a follow up version which fixes the bugs, incorporates the feedback, and has more tests: codereview.stackexchange.com/q/279555/239973 \$\endgroup\$
    – joseville
    Sep 8, 2022 at 16:55
5
\$\begingroup\$

Additional Bugs

Your ReversedList has numerous bugs.

  • The reverse() method does not reverse the list when it is already in reversed mode.

    • Correcting that will give the reverse() method the same behavior as toggleDirection(), making the latter redundant.
  • Slices with stride other than 1 do not work correctly when the list is in reversed mode (but they do work when the list is in forward mode)

  • The __repr__() return value does not represent the reversed state of the object. Moreover, there is not presently any good way for it to do so.

    But it could represent that if you provided an optional argument to __init__() by which the initial reversal state could be specified.

  • the __str__() method produces differently-formatted output when the list is in forward mode than when it is in reversed mode. The reversed-mode output format is the one that matches list.

  • your list's index() method returns incorrect results when the list is in reversed mode.

  • your list's sort() method sorts in the reverse of the requested order when the list is in reversed mode

  • your list's copy() method produces an incorrectly-ordered result when it is in reversed mode.

    Also, the copy is an ordinary list, not a ReversedList, though this is not a bug per se.

  • your list's pop() method pops the wrong element when the list is in reversed mode.

  • your list's append() method adds elements at the beginning instead of at the end when the list is in reversed mode.

  • your list's extend() method adds elements at the wrong place and in the wrong order when the list is in reversed mode.

  • lour list's insert() method inserts at the wrong position when the list is in reversed mode.

  • your list's remove() method removes the wrong instance of the target object when there is more than one and the list is in reversed mode.

I acknowledge your remarks that ...

I have overridden only a few of list's method - just enough for my use case and I'm aware there may be other list methods I may need to override in the future for expanded use cases.

... yet this is not really a matter of use cases but of proper subclassing. If it is intended that people need to know that they are working specifically with a ReversibleList in order to use it correctly, then it should not be a subclass of list. You can implement something similar without subclassing list by wrapping a list and writing the methods you want in terms of accesses to that wrapped list. This is more or less the approach @janos recommends.

This being Python, however, I would furthermore recommend that even without extending list, your class should not be positioned for use cases also served by list and provide methods matching list's without being careful to match the behavior of list's methods. If you don't want to implement the whole list API, then it is better to leave methods unimplemented than to provide versions that work differently than expected (whether by inheritance or de novo implementation). Then people, including future you, who try to use those methods will be notified loudly and clearly instead of experiencing silent unexpected behavior.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the thoroughness in your answer and the follow up reasoning. \$\endgroup\$
    – joseville
    Sep 8, 2022 at 3:51
  • \$\begingroup\$ Thanks everyone for the suggestions! I made a follow up version which fixes the bugs, incorporates the feedback, and has more tests: codereview.stackexchange.com/q/279555/239973 \$\endgroup\$
    – joseville
    Sep 8, 2022 at 16:55
3
\$\begingroup\$

I have only one suggestion: remove the forwardAll() method.

As I understand it, the point of ReversibleList is to allow for having something that you can treat exactly like a list but with an O(1) reverse method.

However, with forwardAll(), a ReversibleList is no longer "exactly like a list". A list does not know if it's 'forward' or 'backward'. A ReversibleList knows this internally, and with forwardAll() that detail is exposed, which means a ReversibleList is no longer "just a list".

Anyway - creative idea!

\$\endgroup\$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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