Getting a specific item from a Set

General Usage
, ,
1

Hi,

I have a set filled with custom objects.
How can I get a specific item from the set equal to another object?

For example, I have a set of points. Then, I add a new point pp1. If pp1 already exists in the set, I want a way to obtain the stored object. This is because the stored point is the one required and may have references elsewhere.

mutable struct Pt
    x::Float64
    y::Float64
end

Base.hash(p::Pt) = hash((p.x+p.y,))
Base.:(==)(p1::Pt, p2::Pt) = hash(p1)==hash(p2)

p1 = Pt(1,0)
p2 = Pt(2,0)
S = OrderedSet([p1, p2])

# a new point
pp1 = Pt(1,0)

# Since pp1 is equal to p1, how to get p1 from the set?

I got a solution for OrderedSets as follows, but I might be missing some standard procedure to do that.

using DataStructures

mutable struct Pt
    x::Float64
    y::Float64
end

Base.hash(p::Pt) = hash((p.x+p.y,))
Base.:(==)(p1::Pt, p2::Pt) = hash(p1)==hash(p2)

# function to get an item from a Set (based on the ht_keyindex function from DataStructures
function getitem(s::OrderedSet{K}, key) where K
    h = s.dict
    slots = h.slots
    sz = length(slots)
    iter = 0
    maxprobe = h.maxprobe
    index = Base.hashindex(key, sz)
    keys = h.keys

    @inbounds while iter <= maxprobe
        si = slots[index]
        si==0 && break # slot empty
        if si>0 && isequal(key, keys[si])
            return keys[si] # it returns the key instead of the index
        end

        index = (index & (sz-1)) + 1
        iter += 1
    end

    error("key not found")
end

p1 = Pt(1,0)
p2 = Pt(2,0)

S = OrderedSet([p1, p2])

# the objectid obtained from getitem(S,pp1) is the one from p1 (as desired)
@show objectid( getitem(S,pp1) ) == objectid(p1)
2

Pt is immutable; there’s no difference bweteen p1 and pp1, just use pp1

julia> struct Pt
           x::Float64
           y::Float64
       end

julia> pp1 = Pt(1,0)
Pt(1.0, 0.0)

julia> p1 = Pt(1,0)
Pt(1.0, 0.0)

# no program should be able to distinguish p1 and pp1
julia> objectid(pp1)
0xb7c8b5259ebb4388

julia> objectid(p1)
0xb7c8b5259ebb4388
3

Thanks for the answer. I just edited the question. Pt is intended to be mutable.

4

you probably want to just use a custom search function

julia> Base.:(==)(a::Pt, b::Pt) = (a.x == b.x) && (a.y==b.y)

julia> p1 = Pt(1,0); p2 = Pt(2,0); pp1 = Pt(1,0);

julia> S = Set([p1, p2]);

julia> function setfindfirst(s, target)
           for v in s
               v==target && return v
           end
           return nothing
       end
setfindfirst (generic function with 1 method)

julia> p1_another = setfindfirst(S, pp1)
Pt(1.0, 0.0)

julia> p1_another.x = 10;

julia> S
Set{Pt} with 2 elements:
  Pt(10.0, 0.0)
  Pt(2.0, 0.0)
5

Thanks @jling. That’s why I implemented the getitem function based on the ht_keyindex function from DataStructures, which performs, I believe, binary search or another kind of fast search.

I wonder if this functionality could be available in Julia’s set structures. It is not the first time I stumbled upon this problem.

6

open an issue

7

getkey?

https://docs.julialang.org/en/v1/base/collections/#Base.getkey

8

Thanks @cjdoris. getkey functions are defined for dictionaries and not for sets.
However, each set instance has an internal dictionary, thus the following works:

using DataStructures

mutable struct Pt
    x::Float64
    y::Float64
end

Base.hash(p::Pt) = hash((p.x+p.y,))
Base.:(==)(p1::Pt, p2::Pt) = hash(p1)==hash(p2)

p1 = Pt(1,0)
p2 = Pt(2,0)
S = OrderedSet([p1, p2])

pp1 = Pt(1,0)
@show objectid( getkey(S.dict, pp1, nothing) ) == objectid(p1)  # shows true