Structs with custom ordering in a heap

New to Julia
, ,
1

I have a collection of structs that I want to maintain with a heap.

The comparison rules for this struct are defined by a custom ordering.

I managed to get sorting working for an array of these structs, but it seems like some code changes are needed to enable feeding a custom ordering into a heap. I’m about to dive into making those changes, but figured it would be wise to check here first too see if those changes are necessary to enable this functionality.

Here’s the array sorting example for reference, in case anyone is trying to accomplish what’s described in the related Sorting arrays of structures post, but with multiple fields.

Also welcoming any critiques on improving efficiency of my Base.lt function. Two thoughts I had are:

  • Is it possible to improve performance if the size of field_orderings is known to the compiler? In this snippet, the size should be known, and the loop should be unrolled, but will this still be the case in a more dynamic situation where the orderings array is generated? In my use case, I’m planning on always matching the number of struct fields.
  • Is it possible to destructure structs? I’m thinking of something like this:
    • for {sym,ord} in struct_ordering.field_orderings.
struct MyStruct
    a::Int64
    b::Int64
    c::Int64
end

struct FieldOrder
    sym::Symbol
    ord::Base.Ordering
end

struct MyStructOrdering <: Base.Ordering
    field_orderings::AbstractVector{FieldOrder}
end

function Base.lt(struct_ordering::MyStructOrdering, a, b)
    for field_ordering in struct_ordering.field_orderings
        sym = field_ordering.sym
        ord = field_ordering.ord
        va = getproperty(a, sym)
        vb = getproperty(b, sym)
        Base.lt(ord, va, vb) && return true
        Base.lt(ord, vb, va) && return false
    end
    false # a and b are equal
end

mystruct_ordering = MyStructOrdering([
    FieldOrder(:a, Base.Reverse),
    FieldOrder(:b, Base.Forward),
    FieldOrder(:c, Base.Reverse)
    ])

mystructs = collect(MyStruct(rand(-1:1, 3)...) for x=1:9)
    
sorted = sort(mystructs, order=mystruct_ordering)

julia> mystructs
9-element Array{MyStruct,1}:
 MyStruct(-1, 0, 1) 
 MyStruct(-1, 0, 0) 
 MyStruct(0, 1, 1)  
 MyStruct(-1, -1, 1)
 MyStruct(0, -1, 0) 
 MyStruct(0, 1, 0)  
 MyStruct(1, 1, 0)  
 MyStruct(0, 0, 1)  
 MyStruct(-1, 1, 0) 

julia> sorted
9-element Array{MyStruct,1}:
 MyStruct(1, 1, 0)  
 MyStruct(0, -1, 0) 
 MyStruct(0, 0, 1)  
 MyStruct(0, 1, 1)  
 MyStruct(0, 1, 0)  
 MyStruct(-1, -1, 1)
 MyStruct(-1, 0, 1) 
 MyStruct(-1, 0, 0) 
 MyStruct(-1, 1, 0)
1 Like
2

The changes to get this working were not as involved as I expected. Here’s how this works for heaps now. Note that this depends on the code in my previous post.

Still wondering why I can’t just assign a function to another function with something like: DataStructures.compare = Base.lt.

using DataStructures

#DataStructures.compare = Base.lt # Why won't this shorthand work?
function DataStructures.compare(comp::MyStructOrdering, a, b)
    Base.lt(comp, a, b)
end

# create heap
h = BinaryHeap{MyStruct,MyStructOrdering}(comparer=mystruct_ordering)

# fill heap from previous input array
for s in mystructs push!(h,s) end

# unload heap in sorted order
heapsorted = []
while !isempty(h) push!(heapsorted,pop!(h)) end

# ensure same results as previous sort(array) technique
sorted == heapsorted
1 Like
3

I don’t quite know the details of why DataStructures.compare = Base.lt doesn’t work, but one important thing to see is that that line is doing something different than

function DataStructures.compare(comp::MyStructOrdering, a, b)
    Base.lt(comp, a, b)
end

In the first case, you are trying to rebind DataStructures’s compare to point at something new. In the latter case, you are adding a method to the existing DataStructures.compare function. And adding methods to existing functions is a key part of how Julia packages interoperate, while on the other hand, rebinding existing functions seems a bit strange.

1 Like