Pythonic equivalent of unshift or redo?

Question

I'm learning Python, and I have a situation where I want to consume items from an iterator. The tricky part is that under certain conditions, I want to "un-iterate." That is, put an item back onto the front of the iterator before I loop.

For example, suppose I'm picking apples from a tree. My fruit basket can only hold 10kg before it needs to be emptied. But I have to pick each apple before I can weigh it and determine if this apple would exceed the capacity of the basket.

In a language like Perl, I could unshift() the apple back onto the tree, and then let the loop expression re-pick the apple:

while ($apple = shift(@tree)) {
  $wt = weight($apple);
  if ($wt + weight(@basket) > 10) {
    send(@basket);
    @basket = ();
    unshift(@tree, $apple);
  } else {
    push(@basket, $element);
  }
}

Or else I can also use redo, which resumes processing at the top of block, without evaluating the loop expression. So the same apple can be re-processed, after the basket has been emptied.

while ($apple = shift(@tree)) {
  $wt = weight($apple);
  if ($wt + weight(@basket) > 10) {
    send(@basket);
    @basket = ();
    redo;
  } else {
    push(@basket, $apple);
  }
}

What would be the most pythonic solution for this kind of problem?

Gatias

if $wt > 10 then there is an infinite loop (the first example eats all memory, the second one just never halts). – Overly

@J.F.: You're right, but in this case it's safe to assume no single apple will exceed 10kg. – Gatias

Answer 1

Why bother with unshifting when the else clause should always occur?

for apple in tree:
    if (apple.weight + basket.weight) > 10:
       send(basket)
       basket.clear()
    basket.add(apple)

Anyway, I'm fairly certain that Python doesn't have the sort of behavior you're looking for.

Dichromatic

Just to clarify: Python's builtin iterators don't have the sort of behavior he's looking for. – Lindquist

This appears to be the most straightforward solution. Thanks! – Gatias

Answer 2

I'm learning Python, and I have a situation where I want to consume items from an iterator. The tricky part is that under certain conditions, I want to "un-iterate." That is, put an item back onto the front of the iterator before I loop.

Here's a simple solution:

class MyIterator(object):   # undo-able iterator wrapper
    def __init__(self, iterable):
        super(MyIterator, self).__init__()
        self.iterator = iter(iterable)
        self.stack = []

    def __iter__(self):
        return self

    def next(self):
        if self.stack:
            return self.stack.pop()
        return self.iterator.next()  # Raises StopIteration eventually

    def undo(self, item):
        self.stack.append(item)

for i in  MyIterator(xrange(5)): print i
0
1
2
3
4

rng = MyIterator(xrange(5))
rng.next()
0
rng.next()
1
rng.undo(1)
rng.next()
1

Edh

Thanks, this answers my original question about how one could implement an unshift-like operation. – Gatias

Answer 3

I'd say that the most Pythonic solution is the simplest one. Instead of trying to wrap an iterator in a generator expression that allows you to "backtrack" or something similarly complex, use a while loop, as you have in Perl! Iterators don't mix very nicely with mutation, anywho.

Simple translation of your implementation (ignoring @Patrick's optimization):

while tree:
    apple = tree.pop(0)
    if apple.weight + basket.weight > 10:
        basket.send()
        basket.clear()
        tree.insert(0, apple) # Put it back.
    else:
        basket.append(apple)

Or, you could use a peek-like functionality with ordered sequence indices:

while tree:
    apple = tree[0] # Take a peek at it.
    if apple.weight + basket.weight > 10:
        basket.send()
        basket.clear()
    else:
        basket.append(tree.pop(0))

If you don't like the "simple" argument, check out the collections.deque iterators mentioned in the above (linked) thread.

Lindquist

Thanks, it's good to remember to step back from the problem. Instead of focusing on a mechanism like unshift, it's best to solve the true problem in a more simple way. – Gatias

Answer 4

If you don't want to follow the other's suggestion of just removing the else clause, you can write your own unshift function that will work in a way similar to perl's with any iterable:

class UnshiftableIterable(object):
    def __init__(self, iterable):
        self._iter = iter(iterable)
        self._unshifted = [] # empty list of unshifted stuff
    def __iter__(self):
        while True:
            if self._unshifted:
                yield self._unshifted.pop()
            else:
                yield self._iter.next()
    def unshift(self, item):
        self._unshifted.append(item)

Then in your code:

it = UnshiftableIterable(tree)
for apple in tree:
    if weigth(basket) + weight(apple) > MAX_WEIGHT:
        send(basket)
        basket = []
        it.unshift(apple)
    else:
        basket.append(apple)

Some testing of the UnshiftableIterable:

it = UnshiftableIterable(xrange(5))

for i in it:
    print '*',
    if i == 2:
        it.unshift(10)
    else:
        print i,
# output: * 0 * 1 * * 10 * 3 * 4

Isoagglutination

Your UnshiftableIterator is not an iterator (it has no next() method). It is iterable (it has __iter__() method). – Overly

@J.F.Sebastian: True. Changed name to reflect that. – Isoagglutination

for apple in tree: -> for apple in it:. Otherwise unshifted values are never used. – Overly

Thanks for the example. It's good to see how to create an iterable class, even if I don't use this solution in this particular case. – Gatias

Answer 5

You're looking for a generator, an iterator that can receive modifications to its internal state via the send() method

https://docs.python.org/howto/functional.html#passing-values-into-a-generator

Vulnerary

Thanks for this tip about send()! I'm not sure I'll use it in this case, but it's great to know for the future. – Gatias

Answer 6

By the way, what you really want is list.insert(0,yourObject)

Babbittry

Answer 7

While I was writing this @Patrick already suggested the same thing. But since I have written it I will paste the code anyways, with comments in code marking methods from Patrick.

import random

apples=[random.randint(1,3) for j in range(10)]
print 'apples',apples

basket=[]
y=6
baskets=[]

for i in range(len(apples)):
    if sum(basket+[apples[i]])>y:
        #basket is full                                                                                                                                     
        baskets.append(basket)#basket.send()                                                                                                                
        basket=[]#basket.empty()                                                                                                                            
    basket.append(apples[i])#add apple to basket                                                                                                            

print 'baskets',baskets

though this does not pop() the apples from the original iterator. Please remark if that's a desired behavior too.

the output

apples [1, 1, 3, 3, 1, 1, 3, 3, 2, 3]
baskets [[1, 1, 3], [3, 1, 1], [3, 3]]

Citizenship

Answer 8

Currently my upgraded version of pythonizer doesn't handle redo but if I added it, I would probably implement it like this:

while (apple:=(tree.pop(0) if tree else None)):
    while True:
        wt = weight(apple)
        if wt+weight(*basket) > 10:
            sendit(basket)
            basket = []
            continue
        else:
            basket.append(apple)
        break

(Note: I had to change send to sendit because send is predefined in perl.)

Alboin

Thanks for the answer! – Gatias

Answer 9

Back to the original question about impementing unshift, operator.delitem can be used to implement a simple non-OO function:

from operator import delitem

def unshift(l,idx):
    retval = l[0]
    delitem(l,0)
    return retval

x = [2,4,6,8]

firstval = unshift(x,0)

print firstval,x

2 [4, 6, 8]

Oppilate

That's not unshift -- that's shift. – Gatias

Answer 10

There is no way general way to push a value into an iterator in python. A stack or linked list is better suited to that.

If you're iterating over a list or something, of course you can add the item manually back to the list. But you can also iterate over objects which can't be manipulated in such a way.

If you want to use python to implement that algorithm, you'll have to choose a data structure that allows the operations you want to use. I suggest the .push() and .pop() methods which let you treat lists as stacks.

Allonge