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 seq in sequences: 36 it = iter(seq) 37 next = it.next 38 self._add_next(next) 39 40 def sort(self): 41 pass # The output should be sorted. 42 43 def __iter__(self): 44 return self 45 46 def _add_next(self, next): 47 48 """ 49 Store the current value for an iterator, alongside the means of 50 getting the next value: the 'next' method. 51 """ 52 53 try: 54 insort_right(self.iters, (next(), next)) 55 except StopIteration: 56 pass 57 58 def next(self): 59 if self.iters: 60 value, next = self.iters[0] 61 del self.iters[0] 62 self._add_next(next) 63 return value 64 else: 65 raise StopIteration 66 67 # vim: tabstop=4 expandtab shiftwidth=4