efficient idiomatic queue?

[James_Althoff at i2.com]

David Eppstein wrote:
>Actually, the merge step in merge sort is a great example for simple
>generators, or would be if not for the difficulty of keeping track of the
>first item of each input iterator:

Tim Peters wrote:
>I appreciate the abstract loveliness of this, but it's hard to see under
all
>the syntactic hair.  A lazy functional language (like Haskell) is much
more
>pleasant for writing algorithms in this style.

Here's an approach using generators that gets rid of some of the
"try:except StopIteration" clutter.

Jim

=======================================

from __future__ import generators

def gen(alist):
    result = {'isempty':1,'value':None} # or you could use a list instead
    for value in alist:
        result['isempty'] = 0
        result['value'] = value
        yield result
    result['isempty'] = 1
    while 1:
        yield result

def merge(list1,list2):
    gen1, gen2 = gen(list1), gen(list2)
    next1, next2 = gen1.next(), gen2.next()
    resultList = []
    while 1:
        if next1['isempty'] and next2['isempty']:
            break
        if (next2['isempty'] or
            (not next1['isempty'] and next1['value'] <= next2['value'])):
            resultList.append(next1['value'])
            next1 = gen1.next()
        else:
            resultList.append(next2['value'])
            next2 = gen2.next()
    return resultList

def mergesort(alist):
    if len(alist) <= 1:
        return alist[:]
    return merge(mergesort(alist[:len(alist)//2]),
        mergesort(alist[len(alist)//2:]))