efficient idiomatic queue?

James_Althoff at i2.com James_Althoff at i2.com
Tue Jan 15 21:37:16 CET 2002

```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:]))

```