You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
A custom comparator may be provided at initialization via the :comparator
option.
For example, let's say we want to store maps containing order information,
sorted by the revenue generated and unique by id. We'll use the
RedBlackTree.compare_terms function for comparisions since it takes care of
weird cases (see note below.)
order_revenue=RedBlackTree.new([],comparator: fn(value1,value2)-># If the ids are the same, they are the sameifvalue1.id===value2.iddo0elsecaseRedBlackTree.compare_terms(value1.revenue,value2.revenue)do# If the revenues are the same but the ids are different, fall back to id comparison for ordering0->RedBlackTree.compare_terms(value1.id,value2.id)# otherwise return the comparisonrevenue_comparison->revenue_comparisonendendend)updated_tree=order_revenue|>RedBlackTree.insert(%{id: 3,revenue: 40},40)|>RedBlackTree.insert(%{id: 50,revenue: 10},10)|>RedBlackTree.insert(%{id: 1,revenue: 50},50)|>RedBlackTree.insert(%{id: 2,revenue: 40},40)# => #RedBlackTree<[{%{id: 50, revenue: 10}, 10}, {%{id: 2, revenue: 40}, 40},{%{id: 3,revenue: 40},40},{%{id: 1,revenue: 50},50}]># Notice how changing the revenue of order 2 bumps it all the way to the end,# since its revenue now equals order 1 but it loses the tie-breakerRedBlackTree.insert(updated_tree,%{id: 2,revenue: 50},50)# #RedBlackTree<[{%{id: 50, revenue: 10}, 10}, {%{id: 2, revenue: 40}, 40},{%{id: 3,revenue: 40},40},{%{id: 1,revenue: 50},50},{%{id: 2,revenue: 50},50}]>
Note
Due to the way Erlang, and therefore Elixir, implement comparisons for floats
and integers, it is possible for a two keys to be equal (key == other_key)
but not strictly equal (key !== other_key).
To guarantee consistent ordering, the default :comparator function must
fallback to hashing keys that exhibit this property on comparison. In these rare
cases, there will be a small performance penalty.
Example:
tree=RedBlackTree.new([1=>:bubbles])# Hashing necessary since 1 != 1.0 and 1 == 1.0updated=RedBlackTree.insert(tree,1.0,:walrus)# No hashing necessary, no performance impactRedBlackTree.insert(updated,0.5,:frank)|>RedBlackTree.insert(1.5,:suzie)
