Chris Lamb

Re: A timeline view in Django

Alex Gaynor writes about "timeline views" in Django. The abstract problem is to merge already-sorted lazily evaluated lists by some specified attribute.

My solution is similar to Malcolm's suggestion in the comments and improves upon Alex's in that has superior space considerations, as well as supporting reverse ordering with the usual Django syntax:

import heapq

def merge_querysets(*querysets, **kwargs):
    order_by = kwargs.get('order_by', None)
    if order_by is None:
        raise ValueError, "Must specify order_by in keyword arguments"

    # Are we sorting in reverse?
    reverse = False
    if order_by.startswith('-'):
        order_by = order_by[1:]
        reverse = True

    class Wrapper(object):
        """
        Hacky wrapper class for custom sorting.
        """
        def __init__(self, sortval, val):
            self.sortval = sortval
            self.val = val

        def __cmp__(self, other):
            if reverse:
                return cmp(other.sortval, self.sortval)
            else:
                return cmp(self.sortval, other.sortval)

    iterables = map(iter, querysets)
    heap = []

    while True:
        for it in iterables:
            try:
                val = it.next()
                sortval = getattr(val, order_by)
                heapq.heappush(heap, Wrapper(sortval, val))
            except StopIteration:
                # This QuerySet has been exhausted
                iterables.remove(it)
                continue

        if not iterables:
            # All QuerySets have been exhausted; just yield from the heap
            # to save cost of insertion.
            for item in heap:
                yield item.val
            return

        yield heapq.heappop(heap).val

def my_view(request):
    tickets = Ticket.objects.order_by('-create_date')
    wikis = WikiEdit.objects.order_by('-create_date')
    changesets = Changeset.objects.order_by('-create_date')
    objs = merge_querysets(tickets, wikis, changesets, order_by='-create_date')
    return render_to_response('my_app/template.html', {
        'objects': objs,
    })

Chris Lamb is a freelance Django developer and Debian developer. You can read other posts by me, see software I have written or read more about me. You can also follow me @lolamby.


Tags: Django

Planets: WUGLUG UWCS Debian ALUG

Saturday 29th November 2008


Two comments