efficient idiomatic queue?

[James_Althoff at i2.com]

David Eppstein wrote:
>Ok, but your merge routine gets rid of a key advantage of using
generators:
>it returns a list, rather than yielding the items one at a time, so the
>total time is always Theta(n log n), while for the version I posted (and
>the cleaner ADT-ized version someone else posted later) the merges all
>happen in parallel as items are requested, and the time to pull off the
>first k items from a sorted list of n items is O(n + k log n).

Ok. Here is essentially the same thing but we return an interator instead
of a list (same idea as your version).

BTW, I also like Alex's ADT approach.  Mine was just a suggestion if class
defs were to be avoided.

Jim

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

from __future__ import generators

def gen(alist):
    result = {'isempty':1,'value':None}
    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()
    while 1:
        if next1['isempty'] and next2['isempty']:
            break
        if (next2['isempty'] or
            (not next1['isempty'] and next1['value'] <= next2['value'])):
            yield next1['value']
            next1 = gen1.next()
        else:
            yield next2['value']
            next2 = gen2.next()

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