# Retrieve element from a set

Hi,

I want to do something that may be impossible to do. It is not very important (I have possible workarounds), but I am curious…

I have a struct that represents an edge, defined as:

``````struct Edge{I<Integer}
e::Tuple{I,I}
p::I
r::Bool
end
``````

The idea is that the actual edge is represented by the tuple `e`, whereas `p` and `r` are some attributes of the edge that are only relevant in some particular situations. I want to store Edges in a `Set`, but I want to be able to check set membership using only the tuple `e`. For this I redefine `Base.hash`, `Base.isequal` and `Base.==`:

``````    import Base: hash, isequal, ==
hash(edge::Edge) = hash(edge.e)
isequal(e1::Edge,e2::Edge) = isequal(e1.e,e2.e)
==(e1::Edge,e2::Edge) = ==(e1.e,e2.e)
``````

With this, I can do something like:

``````    a = Edge((1,2),2,true); b = Edge((1,2),3,false); c = Edge((1,3),1,true);
S = Set([a,b,c])
(1,3) in S
``````

and I get what I want. Namely: when constructing `S`, `b` replaces `a` since they are the same edge, and the answer to `(1,3) in S` is `true`. So far, so good.

However, in this way the attributes of the edges are inaccesible: I can check if the edge belongs to `S` but not what attributes are attached to it. Essentially, I cannot extract and `Edge` as it is stored in `S`. I can, for example, use `pop!(S,m)` where `m` is either a tuple or an `Edge` build from the tuple and default values for `p` and `r`. This removes the corresponding `Edge` from `S`, but the output is the same `m` that I used as key for popping, so the attributes of the previously stored edge are lost.

A simple solution is to use a dictionary instead of a set. In particular, a `Dict{Tuple{I,I},Tuple{I,Bool}}`, with the tuples as keys and the attributes as values. But in this way I essentially drop the data type `Edge` that is useful in other parts of the code.
It is not a great deal: I can keep `Edge` for the things it is useful, and just store my set of edges as a `Dict` instead of a real `Set` of `Edge`s. But I wonder if there is some trick that I can apply for having my cake and eating it. In other words: Given a set where the `hash` applies not the whole element but only to a part, is it possible to retrieve the complete element?

Thanks!

1 Like

This is not possible using only stable API and with the existing `Set` type. I would advice you use the Dict approach.
For fun, it’s possible to do this by relying on the internal implementation of `Set`:

``````julia> s = Set([1,2,3]);

julia> function get_element(s::Set, v)
i = Base.ht_keyindex2!(s.dict, v)
i < 1 ? nothing : s.dict.keys[i]
end
get_element (generic function with 1 method)

julia> get_element(s, 0x02)
2
``````

Note that this implementation may break in any future Julia release.

Hunh. Is this a bug? What why wouldn’t we return the value as it appears in the set?

#### `pop!(collection, key[, default])`

Delete and return the mapping for `key` if it exists in `collection`

I suppose it’s not quite clear what “the mapping for `key`” would be in a Set, but it seems defensible that it should be the value in the set itself.

``````julia> s = Set((1,2,3))
Set{Int64} with 3 elements:
2
3
1

julia> pop!(s, 1.0)
1.0
``````
2 Likes

the expression

``````julia>     m=(1,3)
(1, 3)

julia>     pop!(S,m)
``````

gives me an error

Maybe this might be for you

``````[e for e in S if e.e==(1,3)]
[e for e in S if e==Edge{Int64}((1, 3), 991, true)]
``````

Aha!
Nice trick. I had not noticed that a `Set` is actually a `Dict` with values set to `nothing`. Following your approach, it is possible to use `getkey`:

``````julia> S = Set([1,2,3]);

julia> getkey(S.dict,0x02,nothing)
2
``````

Thanks!

Indeed! My reasoning was that `pop!` should return the value as stored in the `Set`. That’s why I though that my approach was more or less acceptable.
Thanks!

You are right. In order to use `pop!(S,(1,3))` it is necessary to define a method for comparing tuples and edges:

``````import Base.==
==(t::Tuple{I,I},e::Edge) where I<:Integer = ==(t,e.e)
``````

The problem with `[e for e in S if e.e==(1,3)]` is that you actually check the whole set, which is something I want to avoid.
Thanks!

You could also define a personal ‘Set’ with `values` equal to the `keys` instead of `nothing` as follows

``````julia> D=Dict([(k,k) for k in (a,b,c)])
Dict{Edge{Int64}, Edge{Int64}} with 2 entries:
Edge{Int64}((1, 2), … => Edge{Int64}((1, 2), 3, false)
Edge{Int64}((1, 3), … => Edge{Int64}((1, 3), 1, true)

julia> D[a]
Edge{Int64}((1, 2), 3, false)

julia> D[b]
Edge{Int64}((1, 2), 3, false)

julia> D[c]
Edge{Int64}((1, 3), 1, true)

julia> D[(1,2)]
Edge{Int64}((1, 2), 3, false)
``````

Should it be nothing!?

Or is nothing the S.dict mapping!?

Thanks to @jakobnissen, `pop!` on a Set will begin returning the element removed in v1.11!