Include custom less-than in AVL Tree

[chubbc]

Allows one to pass a custom isless function to the AVLTree constructor, which is necessary when simply overloading isless is not possible due to scope issues.

[StephenVavasis]

Just noting that the sorted containers take an order argument.

From: Christopher T. Chubb @.*** Sent: Sunday, March 21, 2021 5:06 PM To: JuliaCollections/DataStructures.jl @.> Cc: Subscribed @.> Subject: Re: [JuliaCollections/DataStructures.jl] Include custom less-than in AVL Tree (#729)

@chubbc commented on this pull request.

---

In src/avl_tree.jlhttps://github.com/JuliaCollections/DataStructures.jl/pull/729#discussion_r598337808:

@@ -19,8 +19,9 @@ AVLTreeNode_or_null{T} = Union{AVLTreeNode{T}, Nothing}

mutable struct AVLTree{T}

 root::AVLTreeNode_or_null{T}

 count::Int

• lt::Function

In isolation I agree, but I went with lt for consistency with sort and all the other sorting functions, which were the only other Julia functions could think of which take a comparison as an optional parameter. If you still prefer comp I can switch it over though.

You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://github.com/JuliaCollections/DataStructures.jl/pull/729#discussion_r598337808, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AB4EJB3F6XEGIRXVCSPAX6LTEZNSXANCNFSM4ZLFGOSA.

[chubbc]

Just noting that the sorted containers take an order argument. From: Christopher T. Chubb @.*** Sent: Sunday, March 21, 2021 5:06 PM To: JuliaCollections/DataStructures.jl @.> Cc: Subscribed @.> Subject: Re: [JuliaCollections/DataStructures.jl] Include custom less-than in AVL Tree (#729) @chubbc commented on this pull request. ________________________________ In src/avl_tree.jl<#729 (comment)>: @@ -19,8 +19,9 @@ AVLTreeNode_or_null{T} = Union{AVLTreeNode{T}, Nothing} mutable struct AVLTree{T} root::AVLTreeNode_or_null{T} count::Int + lt::Function In isolation I agree, but I went with lt for consistency with sort and all the other sorting functions, which were the only other Julia functions could think of which take a comparison as an optional parameter. If you still prefer comp I can switch it over though. - You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub<#729 (comment)>, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AB4EJB3F6XEGIRXVCSPAX6LTEZNSXANCNFSM4ZLFGOSA.

I had thought of something like this, but I think it is strictly less powerful. I was trying to use the AVLTree in a situation in which my isless was defined as a nested function. It needed to be nested because it depended on the function input (essentially it was a closure). To my knowledge, there is no way of promoting this information up to a function in the global scope, so the only way of making this work is to explicitly pass the function. Correct me if I'm wrong about this (I am far from a Julia expert), but it seems in this case the ability to explicitly pass a comparison function is the only solution.

[StephenVavasis]

It is possible to define an order object that takes a non-global function. Suppose the nonglobal function is my_lt, such that my_lt(x,y) checks whether x<y. Here is how this can be done with SortedDict (not tested):

struct MyCompare{T} <: Ordering
   comparison_function::T
end

lt(o::MyCompare{T} where T, x, y) = o.comparison_function(x,y);

function uses_sorted_dict()
    my_lt = ## some complicated closure goes here
    s = SortedDict{MyKeyType, MyValueType, MyCompare(my_lt)}()

end

[StephenVavasis]

Sorry, I forgot that the struct denoted MyCompare in my previous post is already available in Base under the name Lt in ordering.jl. So using this is even easier than what I said.

[chubbc]

Right okay, yea that would be an alternative. I'm not sure I see the point of using Lt over this though, because it seems to just wrap a function being passed in anyway, no? I might be missing something though

[StephenVavasis]

The point of using Ordering and Lt for this purpose rather than a placeholder for a function is to give the user access to all the tools in ordering.jl, not just Lt.

Since the user right now is only you, and the only tool you want is a function place-holder, I won't insist on the point too much.

However, now that I look at the PR again, I see a more pressing issue with your code, which is that lt as a member function has an undeclared type, i.e., its type is Any. This means that the compiler will not be able to deduce the type of lt at compile time, and all the AVL tree functions will need run-time dispatch for lt invocations, which is a significant performance hit.

If you do not want to implement the Ordering infrastructure but would prefer to stick to a placeholder for a function, then the solution to the performance issue is to have a second type parameter for AVLTreeNode, say C, and declare the type of lt to be C.

From: Christopher T. Chubb @.*** Sent: Sunday, March 21, 2021 10:40 PM To: JuliaCollections/DataStructures.jl @.> Cc: Stephen Vavasis @.>; Comment @.***> Subject: Re: [JuliaCollections/DataStructures.jl] Include custom less-than in AVL Tree (#729)

Right okay, yea that would be an alternative. I'm not sure I see the point of using Lt over this though, because it seems to just wrap a function being passed in anyway, no? I might be missing something though

You are receiving this because you commented. Reply to this email directly, view it on GitHubhttps://github.com/JuliaCollections/DataStructures.jl/pull/729#issuecomment-803723025, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AB4EJB5V7ZPGALJEQVNGV23TE2UZPANCNFSM4ZLFGOSA.

[oxinabox]

Cool, thanks. :+1: Needs docstrings and tests added. Looks like we might currently be missing a docstring for the constuctor/type entirely right now (though i might be missing it). Which is probably OK when it only has 1 argument/field, but less so once it has a second