Wrapping iterator, caching intermediate transformation

I want to wrap a dictionary in a data structure that lets you iterate over it in sorted order. Is there any more elegant solution than the following?

struct Graph
    # For example's sake
    statements::Dict{Int, Int}

function _makewrappediter(graph::Graph)
    stmts = sort(graph.statements)
    return stmts, iterate(stmts)

function Base.iterate(graph::Graph, (stmts, iter)=_makewrappediter(graph))
    if !isnothing(iter)
        el, state = iter
        return el, (stmts, iterate(stmts, state))
        return nothing

By “more elegant” I mean some (syntactic?) trickery that let’s one get rid of the helper function and manual repetition of the nothing check.

Maybe SortedDict from DataStructures.jl (Sorted Containers · DataStructures.jl) is a more appropriate choice for your task?

1 Like

That’s a good suggestion, but in this case the struct is merely a container for several dicts that get updated often, and one of them is iterated over only rarely (i.e., once at the end of processing).

But the semantics are not really in question, it is the iterator implementation I seek improvement for.

Should this code even work? There is not method sort for Dict{Int, Int}.

> d = Dict{Int, Int}(1 => 100, 2 => -200);
> sort(d)
ERROR: MethodError: no method matching sort(::Dict{Int64,Int64})

Your sort(graph.statements) should be doing what?

@phg Is there a reason to not just iterate over sort(graph.statements)? I don’t see a way to avoid an additional check for nothing in a wrapped iterator. I would probably go with a sorted array of keys instead of a sorted dictionary, like that

function Base.iterate(graph::Graph, (i, sortedkeys)=(1, Int[]))
    stmts = graph.statements
    isempty(stmts) && return nothing
    if i == 1
        append!(sortedkeys, keys(stmts))
    if i in eachindex(sortedkeys)
        return stmts[sortedkeys[i]], (i+1, sortedkeys)
        return nothing

But the nothing check is just replaced by in eachindex() check.
@Henrique_Becker OrderedCollections.jl overloads sort for dictionaries, returning OrderedDict.

FYI, it looks like sort(::Dict) will be gone at some point (to avoid type-piracy) https://github.com/JuliaCollections/OrderedCollections.jl/issues/25. It’s better to write sort!(collect(graph.statements)).

1 Like

Ha! I didn’t realize at all that sort(::Dict) is from OrderedCollections! I thought that’s in Base. Maybe I’ll just stick with the SortedDict suggestion, then.

But it still bothers me that there’s no nice equivalent to the short

def iterate(self):
    yield from sort_dict_by_key(self.statements)

or similar in Python.