Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > pushback iterator

Reply
Thread Tools

pushback iterator

 
 
Matus
Guest
Posts: n/a
 
      05-17-2009
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
 
Reply With Quote
 
 
 
 
Simon Forman
Guest
Posts: n/a
 
      05-22-2009
On May 17, 10:39*am, Matus <(E-Mail Removed)> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: pushback iterator Matus Python 0 05-17-2009 08:17 PM
Does StreamTokenizer.pushBack correctly update TT_EOF ? enokacorea@gmail.com Java 7 09-21-2008 03:48 PM
Problem with pushback function - "An Access Violation.. " hadad.yaniv@gmail.com C++ 6 07-26-2007 10:48 PM
vector pushback compilation error john isaac C++ 4 03-09-2006 09:37 AM
Pushback Chandrashekar C++ 4 07-14-2003 07:37 PM



Advertisments