CODEWITHSUNDEEP
julia
user888379
user888379

Reputation: 1467

custom ordering in Julia SortedSet

In the Julia documentation for SortedSet, there is a reference to "ordering objects", which can be used in the constructor. I'm working on a project where I need to implement a custom sort on a set of structs. I'd like to use a functor for this, since there is additional state I need for my comparisons. Here is a somewhat simplified version of the problem I want to solve. I have two structs, Point and Edge:

struct Point{T<:Real}
    x::T
    y::T
end
struct Edge{T<:Real}
    first::Point{T}
    second::Point{T}
end

I have a Point called 'vantage', and I want to order Edges by their distance from 'vantage'. Conceptually:

function edge_ordering(vantage::Point, e1::Edge, e2::Edge)
    d1 = distance(vantage, e1)
    d2 = distance(vantage, e2)
    return d1 < d2
end

Are "ordering objects" functors (or functor-ish)? Is there some other conventional way of doing this sort of ordering in Julia?

Upvotes: 2

Views: 602

Answers (2)

张实唯
张实唯

Reputation: 2862

An Ordering object can contain fields, you can store your state there. This is an example of a Remainder Ordering which sort integers by it's remainder:

using DataStructures

struct RemainderOrdering <: Base.Order.Ordering
    r::Int
end

import Base.Order.lt
lt(o::RemainderOrdering, a, b) = isless(a % o.r, b % o.r)

SortedSet(RemainderOrdering(3), [1,2,3]) # 3, 1, 2

I'm not sure how it is related to functors, so I may misunderstand your question. This is an alternative implementation that defines an Ordering functor. I made explanations in comments.

using DataStructures
import Base: isless, map

struct Foo # this is your structure
    x::Int
end

struct PrimaryOrdered{T, F} # this is the functor, F is the additional state.
    x::T
end

map(f::Base.Callable, x::T) where {T <: PrimaryOrdered} = T(f(x.x)) # this makes it a functor?
isless(x::PrimaryOrdered{T, F}, y::PrimaryOrdered{T, F}) where {T, F} =
    F(x.x) < F(y.x) # do comparison with your additional state, here I assume it is a closure

const OrderR3 = PrimaryOrdered{Foo, x -> x.x % 3} # a order that order by the remainder by 3

a = OrderR3(Foo(2))
f(x::Foo) = Foo(x.x + 1) # this is a Foo -> Foo
a = map(f, a) # you can map f on a OrderR3 object
a == OrderR3(Foo(33)) # true

a = map(OrderR3 ∘ Foo, [1, 2, 3])

s = SortedSet(a)

map(x->x.x, s) # Foo[3, 1, 2]

As always, an MWE is important for a question to be understood better. You can include a piece of code to show how you want to construct and use your SortedSet, instead of the vague "state" and "functor".

Upvotes: 4

dberge
dberge

Reputation: 331

The sorting is based on the method isless for the type. So for instance if you have a type in which you want to sort on the b field. For instance you can do

struct Foo{T}
        a::T
        b::T
end

Base.:isless(x::T,y::T) where {T<:Foo} = isless(x.b,y.b)

s=[Foo(1,2),Foo(2,-1)]

res=SortedSet(s)
#SortedSet(Foo[Foo(2, -1), Foo(1, 2)],
#Base.Order.ForwardOrdering())

Tuples are also sorted in order, so you can also use sort(s,by=x->(x.b,x.a)) to sort by b,thena without having to define isless for the type.

Upvotes: 3

Related Questions