Merging sorted lists/iterators/generators into one stream of values...

[Mike C. Fletcher]

Lasse Vågsæther Karlsen wrote:

>Ok, that one looks more sleak than what I came up with.
>
>Couple of things I learn from your solution, please correct me if I
>misunderstood something:
>
>1. list containing other lists will sort itself based on first element
>on lists inside ?
>  
>
Correct, comparison is recursive for lists/tuples.

>2. sort(), pop() is not costly operations
>  
>
They *can* be costly, but the algorithm reduces the number of times they 
are called to less-than-linear for all but pathological cases (i.e. they 
are only called when you need to switch streams).  It also only requires 
sorting only the number of streams, rather than the whole set.

>Other than that you seem to not use the cmp operator but that's easily
>fixed.
>  
>
Sorry about that, revised version below:

def firstIter( value ):
    it = iter( value )
    try:
        return it.next(), it
    except StopIteration, err:
        return None, None

def cmpFirstWith( comparison ):
    def compare( a,b ):
        return comparison(a[0],b[0])
    return compare

def inorder( comparison, *args ):
    iterators = [
        [value,it]
        for (value,it) in [ firstIter( arg ) for arg in args ]
        if it is not None
    ]
    iterators.sort()
    while iterators:
        yield iterators[0][0]
        try:
            value = iterators[0][0] = iterators[0][1].next()
        except StopIteration, err:
            iterators.pop(0)
        else:
            if len(iterators) > 1 and comparison( value, 
iterators[1][0]) == 1:
                iterators.sort( cmpFirstWith( comparison ) )
                continue

if __name__ == "__main__":
    s1 = [10, 20, 30, 40, 50]
    s2 = [15, 25]
    s3 = [17, 27, 37]
    s4 = []
    for value in inorder(cmp, s1, s2, s3, s4):
        print value
    s1 = [{'a':'b'}, {'a':'e'}]
    s2 = [{'a':'d'}, {'a':'z'}]
    def comp( a,b ):
        return cmp( a['a'],b['a'])
    for value in inorder(cmp, s1, s2 ):
        print value

Have fun,
Mike

-- 
________________________________________________
  Mike C. Fletcher
  Designer, VR Plumber, Coder
  http://www.vrplumber.com
  http://blog.vrplumber.com