# Idiomatic use of \`iterate\`

**URL:** <https://discourse.julialang.org/t/idiomatic-use-of-iterate/28951>\
**Category:** General Usage\
**Created:** [September 19, 2019, 3:29pm UTC](https://discourse.julialang.org/t/idiomatic-use-of-iterate/28951 "2019-09-19T15:29:27Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![krcools](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/krcools/32/10212_2.png) [@krcools](https://discourse.julialang.org/u/krcools)\
**Post date:** [September 19, 2019, 3:29pm UTC](https://discourse.julialang.org/t/idiomatic-use-of-iterate/28951/1 "2019-09-19T15:29:27Z")

</div>

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:

```nohighlight
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.

```julia
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?

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 19, 2019, 4:24pm UTC](https://discourse.julialang.org/t/idiomatic-use-of-iterate/28951/2 "2019-09-19T16:24:19Z")

</div>

If the container is a vector, then

```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).

---

<div class="post-metadata">

**Author:** ![leethargo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/leethargo/32/6004_2.png) [@leethargo](https://discourse.julialang.org/u/leethargo)\
**Post date:** [September 19, 2019, 5:40pm UTC](https://discourse.julialang.org/t/idiomatic-use-of-iterate/28951/3 "2019-09-19T17:40:16Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![ssfrr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ssfrr/32/3736_2.png) [@ssfrr](https://discourse.julialang.org/u/ssfrr)\
**Post date:** [September 19, 2019, 5:51pm UTC](https://discourse.julialang.org/t/idiomatic-use-of-iterate/28951/4 "2019-09-19T17:51:50Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![krcools](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/krcools/32/10212_2.png) [@krcools](https://discourse.julialang.org/u/krcools)\
**Post date:** [September 19, 2019, 6:12pm UTC](https://discourse.julialang.org/t/idiomatic-use-of-iterate/28951/5 "2019-09-19T18:12:18Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [September 19, 2019, 6:15pm UTC](https://discourse.julialang.org/t/idiomatic-use-of-iterate/28951/6 "2019-09-19T18:15:41Z")

</div>

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)`).

---

<div class="post-metadata">

**Author:** ![krcools](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/krcools/32/10212_2.png) [@krcools](https://discourse.julialang.org/u/krcools)\
**Post date:** [September 19, 2019, 6:16pm UTC](https://discourse.julialang.org/t/idiomatic-use-of-iterate/28951/7 "2019-09-19T18:16:31Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![krcools](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/krcools/32/10212_2.png) [@krcools](https://discourse.julialang.org/u/krcools)\
**Post date:** [September 19, 2019, 6:19pm UTC](https://discourse.julialang.org/t/idiomatic-use-of-iterate/28951/8 "2019-09-19T18:19:58Z")

</div>

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

```julia
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.

---

<div class="post-metadata">

**Author:** ![krcools](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/krcools/32/10212_2.png) [@krcools](https://discourse.julialang.org/u/krcools)\
**Post date:** [September 19, 2019, 6:21pm UTC](https://discourse.julialang.org/t/idiomatic-use-of-iterate/28951/9 "2019-09-19T18:21:11Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ssfrr](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ssfrr/32/3736_2.png) [@ssfrr](https://discourse.julialang.org/u/ssfrr)\
**Post date:** [September 19, 2019, 7:08pm UTC](https://discourse.julialang.org/t/idiomatic-use-of-iterate/28951/10 "2019-09-19T19:08:40Z")

</div>

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.

```julia
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([]))

```