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