Implement a python list with constraints

Question

I need a python list object which, upon insert, automatically checks for certain constraints of the form: "A must always come before B" or "If C is included, it must always come last".

What's the easiest/fastest way to go about implementing this. The obvious approach is to override all the methods of the list data type which alter its contents (append, extend, insert, etc), and verify that constraints still hold after the operation. It's just that this is pretty tedious as there are a lot of these methods. Is there an easier way?

Answer 1

I would strongly recommend subclassing from the collections.MutableSequence abstract base class. The drawback is that it won't be recognized as a subclass of list (as user4815162342 points out). However, that should almost never matter as long as people using the resulting class are doing the right thing (i.e. using duck typing or passing abstract base classes rather than concrete classes to isinstance).

The wonderful thing about this is that once you've defined the following methods, you get the rest of the MutableSequence interface for free. Here's a concrete subclass of MutableSequence that you can use as a template for further customization. In your case, you should only have to customize __init__, __setitem__, insert, and __delitem__. Everything else is defined in terms of those, and so will perform whatever checks you insert:

import collections
class MyList(collections.MutableSequence):
    def __init__(self, it=()):
        self._inner = list(it)
    def __len__(self):
        return len(self._inner)
    def __iter__(self):
        return iter(self._inner)
    def __contains__(self, item):
        return item in self._inner
    def __getitem__(self, index):
        return self._inner[index]
    def __setitem__(self, index, value):
        self._inner[index] = value
    def __delitem__(self, index):
        del self._inner[index]
    def __repr__(self):
        return 'MyList({})'.format(self._inner)
    def insert(self, index, item):
        return self._inner.insert(index, item)

A couple of simple tests:

>>> ml = MyList('foo')
>>> ml
MyList(['f', 'o', 'o'])
>>> ml.append(5)
>>> ml
MyList(['f', 'o', 'o', 5])
>>> ml.reverse()
>>> ml
MyList([5, 'o', 'o', 'f'])

Answer 2

If your type must be a subtype of list, your options are limited. You must subclass list and override the mutator methods, not forgetting the special methods such as __setitem__. The bad news is that there is no way to enforce that these methods will be used. Anyone, at any time, can call: list.append(your_list, new_elem), and bypass your append. Even worse, Python's implementation does exactly that in places. (This is more often the case with dicts and tuples.)

If your type doesn't need to inherit from list, take a look at UserList and at collections.MutableSequence.