1 #!/usr/bin/env python 2 3 """ 4 An iterator merging class similar to heapq.merge in Python 2.6. 5 6 Copyright (C) 2009 Paul Boddie <paul@boddie.org.uk> 7 8 This program is free software; you can redistribute it and/or modify it under 9 the terms of the GNU General Public License as published by the Free Software 10 Foundation; either version 3 of the License, or (at your option) any later 11 version. 12 13 This program is distributed in the hope that it will be useful, but WITHOUT ANY 14 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A 15 PARTICULAR PURPOSE. See the GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License along 18 with this program. If not, see <http://www.gnu.org/licenses/>. 19 """ 20 21 from bisect import insort_right 22 23 class itermerge: 24 25 """ 26 Merge ordered sequences to produce an ordered, combined sequence of 27 results. 28 """ 29 30 def __init__(self, sequences): 31 self.iters = [] 32 33 # Prepare the underlying iterators. 34 35 for i, seq in enumerate(sequences): 36 self._add_seq(seq, i) 37 38 def _add_seq(self, sequence, i): 39 40 "Store the details of the given 'sequence' at position 'i'." 41 42 iterator = iter(sequence) 43 next = iterator.next 44 self._add_next(next) 45 46 def sort(self): 47 pass # The output should be sorted. 48 49 def __iter__(self): 50 return self 51 52 def _add_next(self, next): 53 54 """ 55 Store the current value for an iterator, alongside the means of 56 getting the next value: the 'next' method. 57 """ 58 59 try: 60 insort_right(self.iters, (next(), next)) 61 except StopIteration: 62 pass 63 64 def next(self): 65 if self.iters: 66 value, next = self.iters[0] 67 del self.iters[0] 68 self._add_next(next) 69 return value 70 else: 71 raise StopIteration 72 73 # vim: tabstop=4 expandtab shiftwidth=4