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;
++state;
}
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)
end
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?
julia> a = [:blue, :blue, :red]
3-element Array{Symbol,1}:
:blue
:blue
:red
julia> i = something(findfirst(isequal(:red), a), length(a) + 1)
3
julia> insert!(a, i, :green)
4-element Array{Symbol,1}:
:blue
:blue
:green
:red
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.
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)
end
insert!(list, item, state)
The only awkward thing being that next is called twice.
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}
iter::T
end
# `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])
else
next = if state === nothing
iterate(i.iter)
else
iterate(i.iter, state[2])
end
if next === nothing
# at the end of the iterable
nothing
else
nextval, nextstate = next
if nextval != :red
nextval, (false, nextstate)
else
# 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)
end
end
end
end
Base.IteratorSize(::Type{<:Inserter}) = Base.SizeUnknown()
# to test it out:
collect(Inserter([:green, :red, :blue, :red]))
collect(Inserter([:red]))
collect(Inserter([:green]))
collect(Inserter([]))