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, 2011 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 self.first = None 33 34 # Prepare the underlying iterators. 35 36 for i, seq in enumerate(sequences): 37 self._add_seq(seq, i) 38 39 def _add_seq(self, sequence, i): 40 41 "Store the details of the given 'sequence' at position 'i'." 42 43 iterator = iter(sequence) 44 next = iterator.next 45 self._add_next(next) 46 47 def __getitem__(self, i): 48 if i == 0: 49 if self.first is None: 50 value, next = self.iters[0] 51 self.first = value 52 return self.first 53 else: 54 raise IndexError, "Index %d cannot be accessed in this iterator." % i 55 56 def sort(self): 57 pass # The output should be sorted. 58 59 def __iter__(self): 60 return self 61 62 def _add_next(self, next): 63 64 """ 65 Store the current value for an iterator, alongside the means of 66 getting the next value: the 'next' method. 67 """ 68 69 try: 70 insort_right(self.iters, (next(), next)) 71 except StopIteration: 72 pass 73 74 def next(self): 75 if self.iters: 76 value, next = self.iters[0] 77 if len(self.iters) > 1: 78 del self.iters[0] 79 self._add_next(next) 80 else: 81 try: 82 self.iters[0] = next(), next 83 except StopIteration: 84 self.iters = [] 85 return value 86 else: 87 raise StopIteration 88 89 # vim: tabstop=4 expandtab shiftwidth=4