November 29th 2008

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)
                return cmp(self.sortval, other.sortval)

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

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

        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

        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,

You can subscribe to new posts via email or RSS.