paul@33 | 1 | #!/usr/bin/env python |
paul@33 | 2 | |
paul@34 | 3 | "An iterator merging class similar to heapq.merge in Python 2.6." |
paul@33 | 4 | |
paul@34 | 5 | from bisect import insort_right |
paul@33 | 6 | |
paul@34 | 7 | class itermerge: |
paul@33 | 8 | |
paul@34 | 9 | """ |
paul@34 | 10 | Merge ordered sequences to produce an ordered, combined sequence of |
paul@34 | 11 | results. |
paul@34 | 12 | """ |
paul@33 | 13 | |
paul@34 | 14 | def __init__(self, sequences): |
paul@34 | 15 | self.iters = [] |
paul@34 | 16 | |
paul@34 | 17 | # Prepare the underlying iterators. |
paul@34 | 18 | |
paul@34 | 19 | for seq in sequences: |
paul@34 | 20 | it = iter(seq) |
paul@34 | 21 | next = it.next |
paul@34 | 22 | self._add_next(next) |
paul@33 | 23 | |
paul@34 | 24 | def sort(self): |
paul@34 | 25 | pass # The output should be sorted. |
paul@34 | 26 | |
paul@34 | 27 | def __iter__(self): |
paul@34 | 28 | return self |
paul@34 | 29 | |
paul@34 | 30 | def _add_next(self, next): |
paul@33 | 31 | |
paul@34 | 32 | """ |
paul@34 | 33 | Store the current value for an iterator, alongside the means of |
paul@34 | 34 | getting the next value: the 'next' method. |
paul@34 | 35 | """ |
paul@34 | 36 | |
paul@34 | 37 | try: |
paul@34 | 38 | insort_right(self.iters, (next(), next)) |
paul@34 | 39 | except StopIteration: |
paul@34 | 40 | pass |
paul@34 | 41 | |
paul@34 | 42 | def next(self): |
paul@34 | 43 | if self.iters: |
paul@34 | 44 | value, next = self.iters[0] |
paul@34 | 45 | del self.iters[0] |
paul@34 | 46 | self._add_next(next) |
paul@34 | 47 | return value |
paul@33 | 48 | else: |
paul@34 | 49 | raise StopIteration |
paul@33 | 50 | |
paul@33 | 51 | # vim: tabstop=4 expandtab shiftwidth=4 |