Idiomatic use of `iterate`

I want to insert item in a linked list containing balls before the first red ball. The precise implementation of the list is not too important. I in particular did not use the list provided by Datastructures.jl, but my own, which uses a Vector as memory storage.

Using the C++ iteration protocol this works as follows:

auto state = list.begin();
while(state != list.end()) {
    if(color(*state) == RED)  break;
list.insert(state, item);

I can’t seem to be able to get something like this using the iterate protocol.

vs = iterate(list)
while vs != nothing
    value, state = vs
    color(value) == RED && break
    vs = iterate(list, state)
insert!(list, item, position)

No idea what to put for position. Clearly not state, since it is not defined outside of the loop. Even if it were, it would point one position too far in the list. Also the case where the list does not contain red balls seems hard; there is no equivalent to the c++ idea of an end iterator or position in the sens of one past the last item.

What is the best manner to accomplish this in Julia?

If the container is a vector, then

julia> a = [:blue, :blue, :red]
3-element Array{Symbol,1}:

julia> i = something(findfirst(isequal(:red), a), length(a) + 1)

julia> insert!(a, i, :green)
4-element Array{Symbol,1}:

When there is no :red, i will be nothing, so this will put the :green in the last position (it was not clear to me whether you want this, customize accordingly).

I think for general containers (that you did not implement), you can not rely on the iterate protocol to get a position where something can be inserted later.

But if you use your own implementation of a list, with your own implementation of iterate, you could store that position as part of the state, and extract it from there. Of course, that would be relying on an implementation detail, not something provided by iterate itself.

In general you can’t assume that iterables can have items inserted in them. For instance, an iterable might represent values coming in real-time from a sensor, or data coming in over a network stream.

You could however create your own iterator that wraps another iterator, does a 1-item lookahead, and if the next item is RED then it returns the item you want to “insert” before continuing on. Would that do what you want?

Yes, you are right; I want to green ball in the rear if no red balls are present.

No, the container is not a vector. So findfirst (which is built on top of pairs and limited to arrays and dicts) is not an options, nor is using length(v)+1 as end-state.

As others have pointed out, there is no API for doing this for general iterables. For example, they may be immutable (eg (:blue, :blue, :red)).

You are right that insertion cannot be supported for all iterables. This is why iterators in c++ come in flavours such as input and output iterators. I think however this is unrelated to the problem here.

The idea to wrap a look ahead iterator around the original one might work. I don’t see however how to get a state pointing to the first element out of this. iterate produces the first state as a default value for its second argument. Outside users cannot get their hands on it.

I fear you are correct. With the old API I can get close:

state = start(list)
while !done(list, state)
    value, _ = next(list, state)
    color(value) == RED && break
    _, state = next(list, state)
insert!(list, item, state)

The only awkward thing being that next is called twice.

I understand, and this would make it impossible to implement insert!, but is up to some extent unrelated to the positioning problem.

I just realized I misunderstood your problem slightly, but maybe this is useful - here’s an iterator that inserts :purple before each incidence of :red. It should work regardless of the inner iterator.

struct Inserter{T}

# `state` is a tuple: (queued, [queuedval,] nextstate)
# which only has a `queuedval` if `queued` is true
function Base.iterate(i::Inserter, state=nothing)
    if state !== nothing && state[1]
        # we had a value queued up
        state[2], (false, state[3])
        next = if state === nothing
            iterate(i.iter, state[2])

        if next === nothing
            # at the end of the iterable
            nextval, nextstate = next
            if nextval != :red
                nextval, (false, nextstate)
                # we don't strictly need to save `nextval` because it's always
                # `:red`, but this way it would work if you had some more complicated
                # triggering criteria
                :purple, (true, nextval, nextstate)

Base.IteratorSize(::Type{<:Inserter}) = Base.SizeUnknown()

# to test it out:
collect(Inserter([:green, :red, :blue, :red]))