rstdocs/examples/iterqueue.py

   1 #!/usr/bin/env python
   2 # -*- coding: utf8 -*-
   3
   4 # ************************************
   5 # Extending Iterators for use as Queue
   6 # ************************************
   7 #
   8 # :Version:   0.2
   9 # :Date:      2007-01-15
  10 # :Copyright: 2005, 2007 Guenter Milde.
  11 #             Released under the terms of the GNU General Public License
  12 #             (v. 2 or later)
  13 # :Changelog: 2005-06-29 Initial version
  14 #             2007-01-07 literate version, more examples
  15 # :Abstract:  There are many variants of "rich iterators" with varying
  16 #             efficiency, conventions, naming, and behaviour. This survey will
  17 #             compare them and provide a case for the inclusion of a "rich
  18 #             iterator wrapper" to the Python Standard Library
  19 #
  20 # .. contents::
  21 #
  22 # ::
  23
  24 """iterqueue: mutable iterators
  25
  26 Classes for "extended iterators" with methods to let iterators be used as
  27 queue
  28
  29    `push` or
  30    `append left`     -- push back values
  31    `peek`           -- get a value without "using it up"
  32    `__nonzero__`    -- test for empty iterator
  33
  34 """
  35
  36 # Imports
  37 #
  38 # The `itertools` module provides a set of building blocks for the work with
  39 # iterators (but misses a class for "mutable" iterators). ::
  40
  41 import itertools
  42
  43 # The `collections` module with the efficient double-sided queue was
  44 # introduced in Python 2.4. The following construct provides a minimal
  45 # compatibility definition if it is not available::
  46
  47 try:
  48     from collections import deque
  49 except ImportError:
  50     class deque(list):
  51         def appendleft(self, value):
  52             self.insert(0, value)
  53
  54
  55 # Iterables and Iterators
  56 # =======================
  57 #
  58 # Iterables and iterators are defined by the iterator protocol as laid out in
  59 # the section on `Iterator Types`_ in the Python Library Reference`:
  60 #
  61 # Iterables:
  62 #   One method needs to be defined for container objects to provide iteration
  63 #   support:
  64 #
  65 #   :__iter__(): Return an iterator object. [...] If a container supports
  66 #                different types of iteration, additional methods can be
  67 #                provided to specifically request iterators for those
  68 #                iteration types. [...]
  69 #
  70 # ::
  71
  72 def is_iterable(object):
  73     """Check if the argument is iterable"""
  74     return hasattr(object, "__iter__") and is_iterator(iter(object))
  75
  76 # Iterators:
  77 #   The *iterator objects* themselves are required to support the following
  78 #   two methods, which together form the *iterator protocol*:
  79 #
  80 #   :__iter__(): Return the iterator object itself. This is required to allow
  81 #                both containers and iterators to be used with the `for` and
  82 #                `in` statements...
  83 #
  84 #   :next(): Return the next item from the container. If there are no further
  85 #            items, raise the `StopIteration` exception.
  86 #
  87 #            [...] once an iterator's next() method raises `StopIteration`,
  88 #            it will continue to do so on subsequent calls. Implementations
  89 #            that do not obey this property are deemed broken.
  90 #
  91 # Check if an object is an iterator::
  92
  93 def is_iterator(object):
  94     """check if the argument is an iterator"""
  95     if not hasattr(object, "__iter__"):
  96         return False
  97     return (object.__iter__() is object) and hasattr(object, "next")
  98
  99
 100 # Try it:
 101 #
 102 #   >>> import iterqueue
 103 #   >>> iterqueue.is_iterator(23)
 104 #   False
 105 #   >>> iterqueue.is_iterator(iter(range(3)))
 106 #   True
 107 #
 108 # The iterator protocol was primarily designed to be the *minimum* necessary
 109 # to work in `for statements`, translating (behind the scene)::
 110
 111 # |  for item in iterable:
 112 # |      <statements>
 113 #
 114 # into the equivalent of::
 115
 116 # |  iterator = iter(iterable)
 117 # |  while 1:
 118 # |    try:
 119 # |          item = iterator.next()
 120 # |    except StopIteration: break
 121 # |          <statements>
 122 #
 123 #
 124 # To add iterator behaviour to your classes, define an `__iter__` method which
 125 # returns an object with a `next` method.  If the class defines `next`, then
 126 # `__iter__` can just return `self`.  (`tutorial chapter on iterators`_)
 127 #
 128 # Python's *generators* provide a convenient way to implement the iterator
 129 # protocol. Generator objects are returned by *generator functions* (functions
 130 # with the ``yield`` keyword, new in 2.3) and *generator expressions* (new in
 131 # 2.4).
 132 #
 133 # .. _`Iterator Types`:
 134 #    http://docs.python.org/library/stdtypes.html#iterator-types
 135 # .. _`tutorial chapter on iterators`:
 136 #    http://docs.python.org/tutorial/classes.html#iterators
 137 #
 138 # Limitations of iterator objects
 139 # ===============================
 140 #
 141 # Most built-in Python iterator objects (including generator objects) are
 142 # non-mutable (except the call to the `next` method). They "produce the data
 143 # just in time", which is fast and memory efficient.
 144 #
 145 # However:
 146 #
 147 # 1. In some occasions, it is important to
 148 #
 149 #    * find out whether an iterator is empty or
 150 #    * to "peek" at a data value
 151 #
 152 #    without advancing the iterator.
 153 #
 154 # 2. In a state machine, an iterator holding the input values can be passed
 155 #    around to the state handling functions. If a state handler realises that
 156 #    a value should be processed by another state handler, it needs to
 157 #    "push it back".
 158 #
 159 # 3. One might want modify the object iterated over in a `for` statement.
 160 #
 161 #    Generally, the object in a `for` statement can not be changed inside the
 162 #    loop.
 163 #
 164 #      >>> from collections import deque
 165 #      >>> it = deque(range(3))
 166 #      >>> for v in it:
 167 #      ...     print v,
 168 #      ...     if v == 1:
 169 #      ...        it.appendleft("eins")
 170 #      ...
 171 #      Traceback (most recent call last):
 172 #        File "doctest.py", line 1248, in __run
 173 #          compileflags, 1) in test.globs
 174 #        File "<doctest iterqueue.py.txt[8]>", line 1, in ?
 175 #          for v in it:
 176 #      RuntimeError: deque mutated during iteration
 177 #
 178 # Pushing the limits
 179 # ====================
 180 #
 181 # There are many ways to live with the limits of iterators. Most often it
 182 # helps to get a true understanding of their nature and try to count for it in
 183 # the code.  However, the "never ending" discussion and varying recipes for
 184 # enhanced iterators show the ongoing public demand. This is why I argue for
 185 # the inclusion of a 'rich iterator' wrapper class into the standard library
 186 # based on the _`standardisation argument` in the itertools_ module.
 187 #
 188 #   Standardisation helps avoid the readability and reliability problems which
 189 #   arise when many different individuals create their own slightly varying
 190 #   implementations, each with their own quirks and naming conventions.
 191 #
 192 #
 193 # .. _itertools: http://docs.python.org/library/itertools.html
 194 #
 195 # Recode to work with iterators as they are
 196 # -----------------------------------------
 197 #
 198 # The most straightforward way is to translate code like
 199 #
 200 #   >>> def print_first(l):
 201 #   ...     if not l:
 202 #   ...         print "list empty"
 203 #   ...     else:
 204 #   ...         print l[0]
 205 #   ...
 206 #   >>> print_first([1, 2])
 207 #   1
 208 #   >>> print_first([])
 209 #   list empty
 210 #
 211 # into something in the line of
 212 #
 213 #   >>> def print_next(it):
 214 #   ...     try:
 215 #   ...         value = it.next()
 216 #   ...     except StopIteration:
 217 #   ...         print "list empty"
 218 #   ...     else:
 219 #   ...         print value
 220 #   ...
 221 #   >>> print_next(iter([1, 2]))
 222 #   1
 223 #   >>> print_next(iter([]))
 224 #   list empty
 225 #
 226 # In a `for` statement, the `else` keyword can be utilised to call an
 227 # expression (or a block) if the end of the iterator is reached:
 228 #
 229 #   >>> def find_five(iterable):
 230 #   ...     for i in iterable:
 231 #   ...         if i == 5:
 232 #   ...             print "5 found"
 233 #   ...             break
 234 #   ...     else:
 235 #   ...         print "5 not found"
 236 #
 237 # If the loop is aborted, the else clause is skipped
 238 #
 239 #   >>> find_five(range(7))
 240 #   5 found
 241 #
 242 # Otherwise it prints its message:
 243 #
 244 #   >>> find_five(range(3))
 245 #   5 not found
 246 #
 247 # However, there might be cases where this is not applicable and a test for
 248 # the emptiness or a peek at the first value without advancing the iterator
 249 # would enable much cleaner code.
 250 #
 251 # Use a container object
 252 # ----------------------
 253 #
 254 # One could wrap e.g. a generator into a `list` or `collections.deque` to add
 255 # random access as well as extensibility.
 256 #
 257 #   >>> que = deque(xrange(3))
 258 #   >>> que.appendleft("foo")
 259 #   >>> print que
 260 #   deque(['foo', 0, 1, 2])
 261 #
 262 # However, it will put all iterator values into memory which becomes a problem
 263 # for large iterators (and is non-feasible for unlimited iterators).
 264 #
 265 # Also, iterating in a `for` statement will loose the rich behaviour. Instead
 266 # a construct with a `while` statement is needed, e.g:
 267 #
 268 #   >>> que = deque(range(3))
 269 #   >>> while que:
 270 #   ...     v = que.popleft()
 271 #   ...     print v,
 272 #   ...     if v == 1:
 273 #   ...        que.appendleft("eins")
 274 #   ...
 275 #   0 1 eins 2
 276 #
 277 # Use a rich iterator
 278 # -------------------
 279 #
 280 # If the argument of a `for` statement is an iterator (whose `__iter__`
 281 # method returns `self`), it is available unchanged inside the loop. A *rich
 282 # iterator* provides additional methods besides the ones required for the
 283 # iterator protocol.
 284 #
 285 # State Reporting Iterator
 286 # ~~~~~~~~~~~~~~~~~~~~~~~~
 287 #
 288 # An iterator that returns an indicator "full or empty" (values waiting or
 289 # not) when converted to Boolean will be called *state reporting iterator*::
 290
 291 def is_state_reporting(object):
 292     return hasattr(object, "__nonzero__") or hasattr(object, "__len__")
 293
 294 # Peekable Iterator
 295 # ~~~~~~~~~~~~~~~~~
 296 #
 297 # An iterator that provides a `peek` method will be called a
 298 # *peekable iterator*::
 299
 300 def is_peekable(object):
 301     return hasattr(object, "peek")
 302
 303
 304 # Push Iterator
 305 # ~~~~~~~~~~~~~
 306 #
 307 # An iterator that provides for push-back will be called *push-iterator*::
 308
 309 def is_pushable(object):
 310     return hasattr(object, "appendleft") or hasattr(object, "push")
 311
 312 # Push iterators can be easily extended with `peek` and test of emptiness
 313 # (see `PushIterator`_).
 314 #
 315 # Iterator Queue
 316 # ~~~~~~~~~~~~~~
 317 # An iterator that also provides methods for appending and extending will be
 318 # called *iterator_queue*.
 319 #
 320 # Methods that need access from the "right" side or knowledge of the length of
 321 # the iterator are not included in the iterator_queue specification as they
 322 # clash with the "just in time" acquisition of the values that give iterators
 323 # time and memory advantage over sequences. ::
 324
 325 def is_iterator_queue(object):
 326     return (is_state_reporting(object)
 327             and hasattr(object, "append")
 328             and hasattr(object, "appendleft")
 329             and hasattr(object, "extend")
 330             and hasattr(object, "extendleft")
 331             and hasattr(object, "clear")
 332             and hasattr(object, "rotate")
 333            )
 334
 335 # Rich iterator examples
 336 # ======================
 337 #
 338 # The following examples are the result of a net survey and own ideas.
 339 # The will be compared and profiled in this paper.
 340 #
 341 # All of them are iterator-wrappers::
 342
 343 def is_iterator_wrapper(obj):
 344     """Try if obj can wrap an iterator"""
 345     try:
 346         it = obj(xrange(1))
 347     except:
 348         return False
 349     try:
 350         return is_iterator(it)
 351     except:
 352         return False
 353
 354 # Xiterwrapper
 355 # ------------
 356 #
 357 # Tom Andersson suggested in the Python list an `xiterable protocol`__ for
 358 # extended iterables and a wrapper to convert a "traditional" iterator to an
 359 # extended version
 360 #
 361 # __ http://mail.python.org/pipermail/python-list/2006-January/360162.html
 362 #
 363 # ::
 364
 365 def xiter(iterable):
 366     if (hasattr(iterable, "__xiter__")):
 367         return iterable.__xiter__()
 368     else:
 369         return xiterwrapper(iter(iterable))
 370
 371 class xiterwrapper(object):
 372     def __init__(self, it):
 373         self.it = it
 374         self.advance()
 375     def hasNext(self):
 376         return hasattr(self, "_next")
 377     def next(self):
 378         try:
 379             cur = self._next
 380             self.advance()
 381             return cur
 382         except AttributeError:
 383             raise StopIteration
 384     def peek(self):
 385         try:
 386             return self._next
 387         except AttributeError:
 388             raise StopIteration
 389     def advance(self):
 390         try:
 391             self._next = self.it.next()
 392         except StopIteration:
 393             if (hasattr(self, "_next")):
 394                 del self._next
 395     def __xiter__(self):
 396         return self
 397     def __iter__(self):
 398         return self
 399
 400 # Usage
 401 # ~~~~~
 402 #
 403 #   >>> import iterqueue
 404 #   >>> it = iterqueue.xiter(xrange(3))
 405 #   >>> iterqueue.is_iterator(it)
 406 #   True
 407 #   >>> iterqueue.is_peekable(it)
 408 #   True
 409 #   >>> iterqueue.is_pushable(it)
 410 #   False
 411 #
 412 # We add the __nonzero__ method for a non-destructive test of waiting values
 413 # to add the state reporting feature::
 414
 415     __nonzero__ = hasNext
 416
 417 # >>> iterqueue.is_state_reporting(it)
 418 # True
 419 #
 420 # Adding a `push` method is not possible without major changes to the code.
 421 #
 422 # IteratorWrapper BFL
 423 # -------------------
 424 #
 425 # In a `post on python-3000`__ Guido van Rossum argued against inclusion of an
 426 # "emptiness" test in the iterator protocol, as  "that's just not something
 427 # that generators can be expected to support" and hence would exclude
 428 # generators from the definition of an iterator.
 429 #
 430 # __ http://mail.python.org/pipermail/python-3000/2006-March/000058.html
 431 #
 432 #    ... you can always write a helper class that takes an iterator and
 433 #    returns an object that represents the same iterator, but sometimes
 434 #    buffers one element. But the buffering violates the coroutine-ish
 435 #    properties of generators, so it should not be the only (or even the
 436 #    default) way to access generators.
 437 #    ...
 438 #
 439 #    Here's a sample wrapper (untested)
 440 #
 441 # ::
 442
 443 class IteratorWrapperBFL(object):
 444     def __init__(self, it):
 445         self.it = iter(it)
 446         self.buffer = None
 447         self.buffered = False
 448         self.exhausted = False
 449     def __iter__(self):
 450         return self
 451     def next(self):
 452         if self.buffered:
 453             value = self.buffer
 454             self.buffered = False
 455             self.buffer = None
 456             return value
 457         if self.exhausted:
 458             raise StopIteration()
 459         try:
 460             return self.it.next()
 461         except StopIteration:
 462             self.exhausted = True
 463             raise
 464     def __nonzero__(self):
 465         if self.buffered:
 466             return True
 467         if self.exhausted:
 468             return False
 469         try:
 470             self.buffer = self.it.next()
 471         except StopIteration:
 472             self.exhausted = True
 473             return False
 474         self.buffered = True
 475         return True
 476
 477 # This example provides an "emptiness" test but no peek or push-back:
 478 #
 479 # >>> it = iterqueue.IteratorWrapperBFL(xrange(3))
 480 # >>> iterqueue.is_state_reporting(it)
 481 # True
 482 #
 483 # Peeking could be easily added, though::
 484
 485     def peek(self):
 486         self.buffer = self.next()
 487         self.buffered = True
 488         return self.buffer
 489
 490 # >>> iterqueue.is_peekable(it)
 491 # True
 492 #
 493 # IteratorWrapper DD
 494 # ------------------
 495 #
 496 # Daniel Dittmar wrote on Di 22 Jul. 2003 on comp.lang.python
 497 #
 498 # It shouldn't be too difficult to write an iterator wrapper class that does
 499 # exactly what you want (not tested)::
 500
 501 class IteratorWrapperDD:
 502     def __init__ (self, iterArg):
 503         iterArg = iter (iterArg)
 504         try:
 505             self.firstElement = iterArg.next ()
 506             self.isEmpty = false
 507             self.next = self.returnFirstElement
 508             self.baseIter = iterArg
 509         except StopIteration:
 510             self.isEmpty = true
 511             self.next = self.throwStopIteration
 512
 513     def returnFirstElement(self):
 514         self.next = self.baseIter.next
 515         return self.firstElement
 516
 517     def throwStopIteration(self):
 518         raise StopIteration
 519
 520
 521 # PushIterator
 522 # ------------
 523 #
 524 # In the slides to the `Effective Python Programming`_ OSCON 2005 tutorial by
 525 # Anthony Baxter, I found a genially simple example for an iterator with a
 526 # `push` method.
 527 #
 528 # .. _`Effective Python Programming`:
 529 #    http://www.interlink.com.au/anthony/tech/talks/OSCON2005/effective_r27.pdf
 530 #
 531 # ::
 532
 533 class PushIterator:
 534     def __init__(self, iterable):
 535         """Store iterator as data argument and set up cache"""
 536         self.it = iter(iterable)
 537         self.cache = []
 538
 539     def __iter__(self):
 540         return self
 541
 542     def next(self):
 543         """Return next value (from cache or iterator)"""
 544         if self.cache:
 545             return self.cache.pop()
 546         return self.it.next()
 547
 548     def push(self, value):
 549         """Push back one value (will become the `next` value)"""
 550         self.cache.append(value)
 551
 552 # Once `push` is defined, it is easy to add `peek` and `__nonzero__`.
 553 #
 554 # The question arises, what should be returned by `peek()` if the iterator is
 555 # empty. The easiest option is to raise `StopIteration`, but this might come
 556 # unhandy in some cases. My proposal is to add an optional `default` argument,
 557 # which is returned in case the iterator is empty. (As there is no sensible
 558 # default value for the `default` argument, it cannot be implemented as
 559 # keyword arg, instead an argument list is used)::
 560
 561     def peek(self, *defaults):
 562         """Return next value but do not advance the iterator"""
 563         try:
 564             value = self.next()
 565         except StopIteration:
 566             if defaults:
 567                 return defaults[0]
 568             raise
 569         self.push(value)
 570         return value
 571
 572     def __nonzero__(self):
 573         """Test whether the iterator is empty"""
 574         try:
 575             self.peek()
 576         except StopIteration:
 577             return False
 578         return True
 579
 580 # An alias makes the class more compatible with `collections.deque` ::
 581
 582     appendleft = push
 583
 584 # Optimisation of `peek` and `__nonzero__` is is left out in favour of
 585 # improved clarity.
 586 #
 587 # Usage
 588 # ~~~~~
 589 #
 590 # Create an instance from an iterable object:
 591 #
 592 #   >>> it = iterqueue.PushIterator(range(4))
 593 #
 594 # Test for values:
 595 #
 596 #   >>> bool(it)
 597 #   True
 598 #
 599 # Have a peek ...
 600 #
 601 #   >>> it.peek(None)
 602 #   0
 603 #
 604 # the value is still there:
 605 #
 606 #   >>> it.next()
 607 #   0
 608 #
 609 # See what is left
 610 #
 611 #   >>> [i for i in it]
 612 #   [1, 2, 3]
 613 #
 614 # It should be empty now:
 615 #
 616 #   >>> bool(it)
 617 #   False
 618 #
 619 # So a peek will return the default:
 620 #
 621 #   >>> print it.peek(None)
 622 #   None
 623 #
 624 # PushIt
 625 # -------------
 626 #
 627 # The wrapping of an iterator in a class leads to performance loss, as every
 628 # call to `next()` is a relatively costly function call.
 629 #
 630 # Remapping of self.next leads to a more more efficient implementation
 631 # of the PushIterator for the case that `peek` or `push` is called far
 632 # less frequently than `next` ('normal' iterating with occasional peek or
 633 # backtrack).  ::
 634
 635 class PushIt(PushIterator):
 636     def __init__(self, iterable):
 637         self.it = iter(iterable)
 638         self.cache = []
 639         self.next = self.it.next
 640
 641     def _next(self):
 642         """Return next element. Try cache first."""
 643         if self.cache:
 644             return self.cache.pop()
 645         self.next = self.it.next
 646         return self.next()
 647
 648     def push(self, value):
 649         """Push back one value to the iterator"""
 650         self.cache.append(value)
 651         self.next = self._next
 652
 653     def peek(self):
 654         """Return next value but do not advance the iterator"""
 655         if self.cache:
 656             return self.cache[-1]
 657         value = self.it.next()
 658         self.push(value)
 659         return value
 660
 661
 662 # IterQueue
 663 # ---------
 664 #
 665 # The `IterQueue` class adds iterator behaviour to a double-ended queue::
 666
 667 class IterQueue(deque):
 668     """Iterator object that is also a queue"""
 669     def __iter__(self):
 670         return self
 671     def next(self):
 672         try:
 673             return self.popleft()
 674         except IndexError:
 675             raise StopIteration
 676     #
 677     def peek(self):
 678         """Return next value but do not advance the iterator"""
 679         value = self.next()
 680         self.appendleft(value)
 681         return value
 682
 683
 684 # Usage
 685 # ~~~~~
 686 #
 687 # Creating an instance wraps an iterable in an iterator queue
 688 #
 689 #   >>> it = iterqueue.IterQueue(xrange(3))
 690 #
 691 # which is an iterator according to the iterator protocol with "queue"
 692 # methods
 693 #
 694 #   >>> iterqueue.is_iterator_queue(it)
 695 #   True
 696 #
 697 # We can test whether there is data in the iterator or get the length of it:
 698 #
 699 #   >>> bool(it)
 700 #   True
 701 #   >>> len(it)
 702 #   3
 703 #
 704 # It is possible to modify this iterator in the middle of a `for` statement:
 705 #
 706 #   >>> for v in it:
 707 #   ...     print v,
 708 #   ...     if v == 1:
 709 #   ...        it.appendleft("eins")
 710 #   ...
 711 #   0 1 eins 2
 712 #
 713 # As iteration is done on the object itself and not on a copy, it is exhausted
 714 # now:
 715 #
 716 #   >>> print it
 717 #   deque([])
 718 #
 719 # (the iterator advertises itself as `deque`, as we did not override the
 720 # `__repr__` method)
 721 #
 722 # We can make up for this ::
 723
 724     def __repr__(self):
 725         return "<IterQueue instance>"
 726
 727 # but there might be other problems left...
 728 #
 729 #
 730 # Problems
 731 # ~~~~~~~~
 732 #
 733 # Converting an iterable to a `collections.deque` object creates a list of all
 734 # values in the memory, loosing the memory saving advantages of generator
 735 # objects with "just in time" production of the data.
 736 #
 737 # Printing (and probably other uses as well) "use up" the iterator
 738 #
 739 #   >>> it = iterqueue.IterQueue(range(3))
 740 #   >>> print it
 741 #   deque([0, 1, 2])
 742 #   >>> print it
 743 #   deque([])
 744 #
 745 #
 746 # IQueue
 747 # ------
 748 #
 749 # The following class implements an iterator queue that is
 750 #
 751 # * memory efficient, as generators are kept as generators
 752 #
 753 # * mostly compatible to `collections.deque` (offering all methods of a
 754 #   `deque` for appends)
 755 #
 756 # It does not offer
 757 #
 758 # * random access to the values, nor
 759 #
 760 # * pop from the right end,
 761 #
 762 # as this would require to convert the iterator to a sequence loosing the
 763 # memory-saving advantage.
 764 #
 765 # Iterating over instances is less fast, as the next() method is redefined
 766 # (a function call is needed for every step). Implementing in C would help
 767 # to improve speed.
 768 #
 769 # But,
 770 #
 771 #     itertools.queue() was rejected because it didn't fit naturally into
 772 #     applications -- you had to completely twist your logic around just to
 773 #     accommodate it.  Besides, it is already simple to iterate over a list
 774 #     while appending items to it as needed.
 775 #
 776 #     -- Raymond Hettinger 03-13-05 http://www.codecomments.com/message423138.html
 777 #
 778 # However, both, the speed increase as well as the `standardisation argument`_
 779 # given for the `itertools` hold also in this case
 780 # Maybe IQueue should become a collections candidate?
 781 #
 782 # ::
 783
 784 class IQueue:
 785     """Iterator with "on-line extensibility"
 786
 787     An iterator with methods to append or extend it from left or right
 788     (even while the iterator is in use).
 789
 790     Can be conceived as a mixture of `itertools.chain` and
 791     `collections.deque`.
 792
 793     As `next` is redefined, there is a performance loss when iterating
 794     over large iterators.
 795     """
 796
 797     def __init__(self, *iterables):
 798         """Convert `iterables` to a queue object"""
 799         self.iterators = deque(iterables)
 800     #
 801     def __iter__(self):
 802         return self
 803
 804     def next(self):
 805         while True:
 806             try:
 807                 return self.iterators[0].next()
 808             except AttributeError:      # convert iterable to iterator
 809                 self.iterators[0] = iter(self.iterators[0])
 810             except StopIteration:       # switch to next iterator
 811                 del(self.iterators[0])
 812             except IndexError:          # all iterators exhausted
 813                 raise StopIteration
 814     #
 815     def append(self, value):
 816         """append `value` to self
 817
 818         The value is wrapped in an iterable and
 819         appended to the queue of iterables
 820         """
 821         self.iterators.append(iter((value,)))
 822     #
 823     def appendleft(self, value):
 824         """Prepend one (scalar) value to the iterator.
 825
 826         The value is wrapped in an iterable and
 827         inserted at the first position in the list of iterables
 828         """
 829         self.iterators.appendleft(iter((value,)))
 830     #
 831     def clear(self):
 832         """Remove all elements from the iterator.
 833         """
 834         self.iterators.clear()
 835     #
 836     def extend(self, iterable):
 837         """append `iterable` to self"""
 838         self.iterators.append(iter(iterable))
 839     #
 840     def extendleft(self, iterable):
 841         """prepend `iterable` to self"""
 842         self.iterators.appendleft(iter(iterable))
 843     #
 844     def peek(self):
 845         """Return the next value without advancing the iterator
 846
 847         Yield next value but push back a copy of the result.
 848         This way you may "peak" at an iterator without loss.
 849
 850         Raises `StopIteration` if the iterator is empty.
 851         """
 852         value = self.next()
 853         self.iterators.appendleft(iter((value,)))
 854         return value
 855     #
 856     def rotate(self, n=1):
 857         """append the next `n` values to the end of the iterator
 858
 859         Similar to `container.deque.rotate`, but
 860          * negative `n` leads to error
 861          * a list of the `n` rotated values is returned
 862         """
 863         result = list(itertools.islice(self, n))
 864         self.iterators.append(result)
 865         return result
 866
 867     #
 868     def __repr__(self):
 869         """Return a string representation"""
 870         return "IQueue(%s)" % repr(self.iterators)
 871     #
 872     def  __nonzero__(self):
 873         """Test for a non-zero length of the iterator"""
 874         if len(self.iterators) > 1:
 875             return True
 876         try:
 877             self.peek()
 878         except StopIteration:
 879             return False
 880         return True
 881
 882 # XIter
 883 # -----
 884 #
 885 # The `XIter` class is an optimised version of the `IQueue` for the
 886 # case when appending of a value is a done less frequently than calling `next`.
 887 # It does so by aliasing next to the underlying iterators `next` method in
 888 # case there is only one iterator in the `iterables` chain.
 889 #
 890 # ::
 891
 892 class XIter:
 893     """'Mutable iterator' class"""
 894     def __init__(self, *iterables):
 895         self.iterators = deque(iter(i) for i in iterables)
 896         if len(self.iterators) is 1:
 897             self.next = self.iterators[0].next
 898         else:
 899             self.next = self._next     # iterate over argument
 900     #
 901     def __iter__(self): return self        # "I am an iterator!"
 902     #
 903     def _next(self):
 904         """get next in turn if there are more than one iterators"""
 905         try:
 906             return self.iterators[0].next()
 907         except StopIteration:
 908             del(self.iterators[0])             # switch to next iterator
 909             assert len(self.iterators) >= 1
 910             if len(self.iterators) is 1:
 911                 self.next = self.iterators[0].next
 912             return self.next()
 913     #
 914     def append(self, element):
 915         """append `element` to self"""
 916         self.iterators.append(iter((element,)))
 917         self.next = self._next        # iterate over cache
 918     #
 919     def appendleft(self, element):
 920         """prepend `element` to self"""
 921         self.iterators.appendleft(iter((element,)))
 922         self.next = self._next        # iterate over cache
 923     #
 924     def extend(self, iterable):
 925         """append `iterable` to self"""
 926         self.iterators.append(iter(iterable))
 927         self.next = self._next        # iterate over cache
 928     #
 929     def extendleft(self, iterable):
 930         """prepend `iterable` to self"""
 931         self.iterators.appendleft(iter(iterable))
 932         self.next = self._next        # iterate over cache
 933
 934     #
 935     def peek(self):
 936         """Return the next value without advancing the iterator
 937
 938         Yield next value but push back a copy of the result.
 939         This way you may "peak" at an iterator without loss.
 940
 941         Raises `StopIteration` if the iterator is empty.
 942         """
 943         value = self.next()
 944         self.appendleft(value)
 945         return value
 946     #
 947     def rotate(self, n=1):
 948         """append the next `n` values to the end of the iterator
 949
 950         Similar to `container.deque.rotate`, but
 951          * negative `n` leads to error
 952          * a list of the `n` rotated values is returned
 953         """
 954         result = list(itertools.islice(self, n))
 955         self.iterators.append(result)
 956         return result
 957
 958     #
 959     def __repr__(self):
 960         return "XIter(%s)" % repr(self.iterators)
 961     #
 962     def  __nonzero__(self):
 963         """Test for a non-zero length of the iterator"""
 964         if len(self.iterators) > 1:
 965             return True
 966         try:
 967             self.peek()
 968         except StopIteration:
 969             return False
 970         return True
 971
 972
 973 # Some optimisation could be done adapting a `round-robin example`__ posted by
 974 # R. Hettinger on 2004-04-30 15:58 in comp.lang.python
 975 #
 976 # __ http://sourceforge.net/tracker/index.php?func=detail&aid=756253&group_id=5470&atid=305470
 977 #
 978 # ::
 979
 980 ##
 981 # For the record, here a simple and efficient roundrobin task
 982 # server based on collections.deque:
 983 #
 984 # def roundrobin(*iterables):
 985 #     pending = deque(iter(i).next for i in iterables)
 986 #     gettask, scheduletask = pending.popleft, pending.append
 987 #     while pending:
 988 #         task = gettask()
 989 #         try:
 990 #             yield task()
 991 #         except StopIteration:
 992 #             continue
 993 #         scheduletask(task)
 994 #
 995 # for value in roundrobin('abc', 'd', 'efgh'):
 996 #     print value
 997
 998
 999 # Do a doctest if the module is run in nosetests::
1000
1001 def test():
1002     import doctest
1003     doctest.testmod()