Wrapping iterator, caching intermediate transformation

General Usage
1

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}
end

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

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

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.

2

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

1 Like
3

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.

4

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?

5

@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
        empty!(sortedkeys)
        append!(sortedkeys, keys(stmts))
        sort!(sortedkeys)
    end
    if i in eachindex(sortedkeys)
        return stmts[sortedkeys[i]], (i+1, sortedkeys)
    else
        return nothing
    end
end

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

6

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
7

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.