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
--
http://mail.python.org/mailman/listinfo/python-list
