[Python-ideas] Multi-index Containers Library

[Grant Jenks]

As the author of the sortedcontainers project (similar to blist, but
pure-Python and often faster), I thought this problem would be an
interesting application of the library so here goes.

I'll define an IndexedList as a container of (pk, item) pairs with at least
one unique index mapping pk -> pair like so:

from sortedcontainers import SortedListWithKey, SortedDict
from operator import itemgetter

class IndexedList(object):
    def __init__(self, *args, **kwargs):
        self.pk = 0
        self.indices = {}
        self.uniques = {'_pk': SortedDict()}
        self.keys = {'_pk': itemgetter(0)}

Different types of indices are used based on the unique requirement. In
general, I'd use a list since an index might contain duplicates but with
the unique constraint, I can use a dict:

    def add_unique_index(self, name, key):
        key = lambda pair: key(pair[1])
        self.uniques[name] = SortedDict(zip(map(key, self), self))
        self.keys[name] = key

When we have to use a list, we'll store (key, pair) tuples and keep them
sorted by the key.

    def add_index(self, name, key):
        key = lambda pair: key(pair[1])
        items = zip(map(key, self), self)
        self.indices[name] = SortedListWithKey(items, key=itemgetter(0))

When we iterate, we'll return the pairs:

    def __iter__(self):
        return self.uniques['_pk'].values()

The append operation means creating a new pair and updating the indices:

    def append(self, item):
        self.pk += 1
        pair = (self.pk, item)
        for name in self.uniques:
            self.uniques[name][self.keys[name](pair)] = pair
        for name in self.indices:
            self.indices[name].add(pair)

If we want to remove a unique key, we first find the item and then update
the indices:

    def remove_unique(self, name, key):
        item = self.uniques[name][key]
        for name in self.uniques:
            del self.uniques[name][self.keys[name](item)]
        for name in self.indices:
            self.indices[name].remove(item)

Removing a key from a general index is a little more difficult because
there may be many matching items. Because we stored tuples in the index, we
can bisect to find the range of items with matching keys and then remove
them:

    def remove_index(self, name, key):
        start = self.indices[name].bisect_left((key,))
        end = self.indices[name].bisect_right((key,))
        items = map(itemgetter(1), self.indices[name][start:end])
        for item in items:
            self.remove_unique('_pk', item[0])

Finally, David's original api needs only a bit of modification, everything
else remains the same:

def del_order(order):
    book.remove_unique('order_id', order.id)

def close_account(account_id):
    book.remove_index('account_id', account_id)

Here's the whole recipe on pastebin*:
http://pastebin.com/8S71W3Ue

And a link to the SortedContainers project:
http://www.grantjenks.com/docs/sortedcontainers/

Grant

* Beware, I haven't benchmarked or tested this code.


On Mon, Dec 1, 2014 at 7:12 AM, SF Markus Elfring <
elfring at users.sourceforge.net> wrote:

> >> http://www.boost.org/doc/libs/1_57_0/libs/multi_index/doc/index.html
> >
> > This came up on #python just last week, and I've personally encountered
> > a desire for something similar a bunch of times.
>
> How challenging is it to map powerful Boost classes to the Python
> programming language?
>
>
> > Probably, though, the ideal interface to something like this would need
> > some time to evolve before it would be useful to include in the stdlib,
>
> I am curious on how this could happen ...
>
>
> > along with some motivating use cases
>
> Would you like to look at any more examples I could show?
>
>
> > -- at least, it would be nice if there were one or two third party
> > implementations to compare before settling on an interface.
> > I can't think of any existing implementations that operate on purely
> > in-memory structures.
>
> Thanks for your feedback.
>
>
> > Boost::multiindex is pretty awesome, but its interface is also
> > somewhat complicated, and a 1:1 translation wouldn't make for a pretty
> > Python experience.
>
> Will this story become another promising software development adventure?
>
> Regards,
> Markus
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20141201/f42d9814/attachment-0001.html>