pushback iterator

Discussion in 'Python' started by Matus, May 17, 2009.

  1. Matus

    Matus Guest

    Hallo pylist,

    I searches web and python documentation for implementation of pushback
    iterator but found none in stdlib.

    problem:
    ========
    when you parse a file, often you have to read a line from parsed file
    before you can decide if you want that line it or not. if not, it would
    be a nice feature to be able po push the line back into the iterator, so
    nest time when you pull from iterator you get this 'unused' line.

    solution:
    =========
    I found a nice and fast solution somewhere on the net:

    ---------------------------------------------------------------------
    class Pushback_wrapper( object ):
    def __init__( self, it ):
    self.it = it
    self.pushed_back = [ ]
    self.nextfn = it.next

    def __iter__( self ):
    return self

    def __nonzero__( self ):
    if self.pushed_back:
    return True

    try:
    self.pushback( self.nextfn( ) )
    except StopIteration:
    return False
    else:
    return True

    def popfn( self ):
    lst = self.pushed_back
    res = lst.pop( )
    if not lst:
    self.nextfn = self.it.next
    return res

    def next( self ):
    return self.nextfn( )

    def pushback( self, item ):
    self.pushed_back.append( item )
    self.nextfn = self.popfn
    ---------------------------------------------------------------------

    proposal:
    =========
    as this is (as I suppose) common problem, would it be possible to extend
    the stdlib of python (ie itertools module) with a similar solution so
    one do not have to reinvent the wheel every time pushback is needed?


    thx, Matus
    Matus, May 17, 2009
    #1
    1. Advertising

  2. Matus

    Simon Forman Guest

    On May 17, 10:39 am, Matus <> wrote:
    > Hallo pylist,
    >
    > I searches web and python documentation for implementation of pushback
    > iterator but found none in stdlib.
    >
    > problem:
    > ========
    > when you parse a file, often you have to read a line from parsed file
    > before you can decide if you want that line it or not. if not, it would
    > be a nice feature to be able po push the line back into the iterator, so
    > nest time when you pull from iterator you get this 'unused' line.
    >
    > solution:
    > =========
    > I found a nice and fast solution somewhere on the net:
    >
    > ---------------------------------------------------------------------
    > class Pushback_wrapper( object ):
    >         def __init__( self, it ):
    >                 self.it = it
    >                 self.pushed_back = [ ]
    >                 self.nextfn = it.next
    >
    >         def __iter__( self ):
    >                 return self
    >
    >         def __nonzero__( self ):
    >                 if self.pushed_back:
    >                         return True
    >
    >                 try:
    >                         self.pushback( self.nextfn( ) )
    >                 except StopIteration:
    >                         return False
    >                 else:
    >                         return True
    >
    >         def popfn( self ):
    >                 lst = self.pushed_back
    >                 res = lst.pop( )
    >                 if not lst:
    >                         self.nextfn = self.it.next
    >                 return res
    >
    >         def next( self ):
    >                 return self.nextfn( )
    >
    >         def pushback( self, item ):
    >                 self.pushed_back.append( item )
    >                 self.nextfn = self.popfn
    > ---------------------------------------------------------------------
    >
    > proposal:
    > =========
    > as this is (as I suppose) common problem, would it be possible to extend
    > the stdlib of python (ie itertools module) with a similar solution so
    > one do not have to reinvent the wheel every time pushback is needed?
    >
    > thx, Matus



    By coincidence I had need of just such a pushback iterator just the
    other day. I was playing with queues and generators after reading
    David Beazley's "Generator Tricks For Systems Programmers" [1] and I
    needed an iterator that could be used with this generator function:

    def pushQueueNonblocking(queue, iterator):
    for item in iterator:
    try:
    queue.put(item, False)
    except Queue.Full:
    raise Queue.Full(item)

    If the queue is full I pass item taken from the iterator but not yet
    pushed onto the queue up to the caller in the Full exception so it
    doesn't get lost. I wrote a wrapper function that retried putting
    items on the queue after sleeping for a certain time if the queue is
    full.

    def pushQueueRetry(queue, iterator, retry_delay=1):
    iterator = IteratorWithPushback(iterator)
    while True:
    try:
    pushQueueNonblocking(queue, iterator)
    except Queue.Full, err:
    iterator.pushback(err.args[0])
    if retry_delay >= 0:
    sleep(retry_delay)
    else:
    break

    Originally I used an itertools.chain() solution, but when I tried the
    function with sleep of 0 (the queue was being get() from once a second
    in another thread) I hit a funny error.

    Because the put() thread was running, and retrying, much faster than
    the get() thread, a huge "linked list" of itertools.chain generator
    objects was stored up in memory. When the get() thread finally
    unblocked the queue and the call to put() succeeded, the
    pushQueueNonblocking() would loop and call next() on the chain object,
    which would call next() on the next chain object, which called next()
    on the next next chain object, etc...

    That linked list of chain iterators was longer than
    sys.getrecursionlimit().

    Anyway, FWIW here's the IteratorWithPushback class that I whanged up:


    class IteratorWithPushback:

    def __init__(self, initial_iterator):
    self.iter = iter(initial_iterator)
    self.last = None
    self.has_last = False

    def __iter__(self):
    return self

    def next(self):
    if self.has_last:
    item = self.last
    self.has_last = False
    self.last = None # Don't hang on to it.
    else:
    item = self.iter.next()
    return item

    def pushback(self, item):
    if self.has_last:
    raise Exception("I'm full!")
    self.last = item
    self.has_last = True

    As for putting something like this in the standard library, I'm not
    sure. I've never needed one before and it's easy enough to write.
    *shrug*


    Regards,
    ~Simon

    [1] http://www.dabeaz.com/generators/Generators.pdf
    Simon Forman, May 23, 2009
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chandrashekar

    Pushback

    Chandrashekar, Jul 14, 2003, in forum: C++
    Replies:
    4
    Views:
    595
    Victor Bazarov
    Jul 14, 2003
  2. john isaac

    vector pushback compilation error

    john isaac, Mar 9, 2006, in forum: C++
    Replies:
    4
    Views:
    351
    Chris Theis
    Mar 9, 2006
  3. Replies:
    6
    Views:
    418
    Jim Langston
    Jul 26, 2007
  4. Replies:
    7
    Views:
    638
    John B. Matthews
    Sep 21, 2008
  5. Matus

    Re: pushback iterator

    Matus, May 17, 2009, in forum: Python
    Replies:
    0
    Views:
    481
    Matus
    May 17, 2009
Loading...

Share This Page