Iterator version of merge. Assuming l1, l2, l3...ln sorted sequences, return an iterator that yield all the items of l1, l2, l3...ln in ascending order. Input values doesn't need to be lists: any iterable sequence can be used.
(*ln)
| 1 | def xmerge(*ln): |
| 2 | """ Iterator version of merge. |
| 3 | |
| 4 | Assuming l1, l2, l3...ln sorted sequences, return an iterator that |
| 5 | yield all the items of l1, l2, l3...ln in ascending order. |
| 6 | Input values doesn't need to be lists: any iterable sequence can be used. |
| 7 | """ |
| 8 | pqueue = [] |
| 9 | for i in map(iter, ln): |
| 10 | try: |
| 11 | pqueue.append((i.next(), i.next)) |
| 12 | except StopIteration: |
| 13 | pass |
| 14 | pqueue.sort() |
| 15 | pqueue.reverse() |
| 16 | X = max(0, len(pqueue) - 1) |
| 17 | while X: |
| 18 | d,f = pqueue.pop() |
| 19 | yield d |
| 20 | try: |
| 21 | # Insort in reverse order to avoid pop(0) |
| 22 | lo, hi, d = 0, X, f() |
| 23 | while lo < hi: |
| 24 | mid = (lo+hi)//2 |
| 25 | if d > pqueue[mid][0]: hi = mid |
| 26 | else: lo = mid+1 |
| 27 | pqueue.insert(lo, (d,f)) |
| 28 | except StopIteration: |
| 29 | X-=1 |
| 30 | if pqueue: |
| 31 | d,f = pqueue[0] |
| 32 | yield d |
| 33 | try: |
| 34 | while 1: yield f() |
| 35 | except StopIteration:pass |
| 36 | |
| 37 | |
| 38 | def merge(*ln): |