| Line | Exclusive | Inclusive | Code |
|---|---|---|---|
| 1 | # This file is a part of Julia. License is MIT: https://julialang.org/license | ||
| 2 | |||
| 3 | module Order | ||
| 4 | |||
| 5 | |||
| 6 | import ..@__MODULE__, ..parentmodule | ||
| 7 | const Base = parentmodule(@__MODULE__) | ||
| 8 | import .Base: | ||
| 9 | AbstractVector, @propagate_inbounds, isless, identity, getindex, | ||
| 10 | +, -, !, &, <, | | ||
| 11 | |||
| 12 | ## notions of element ordering ## | ||
| 13 | |||
| 14 | export # not exported by Base | ||
| 15 | Ordering, Forward, Reverse, | ||
| 16 | By, Lt, Perm, | ||
| 17 | ReverseOrdering, ForwardOrdering, | ||
| 18 | DirectOrdering, | ||
| 19 | lt, ord, ordtype | ||
| 20 | |||
| 21 | abstract type Ordering end | ||
| 22 | |||
| 23 | struct ForwardOrdering <: Ordering end | ||
| 24 | struct ReverseOrdering{Fwd<:Ordering} <: Ordering | ||
| 25 | fwd::Fwd | ||
| 26 | end | ||
| 27 | |||
| 28 | ReverseOrdering(rev::ReverseOrdering) = rev.fwd | ||
| 29 | ReverseOrdering(fwd::Fwd) where {Fwd} = ReverseOrdering{Fwd}(fwd) | ||
| 30 | ReverseOrdering() = ReverseOrdering(ForwardOrdering()) | ||
| 31 | |||
| 32 | const DirectOrdering = Union{ForwardOrdering,ReverseOrdering{ForwardOrdering}} | ||
| 33 | |||
| 34 | const Forward = ForwardOrdering() | ||
| 35 | const Reverse = ReverseOrdering() | ||
| 36 | |||
| 37 | struct By{T, O} <: Ordering | ||
| 38 | by::T | ||
| 39 | order::O | ||
| 40 | end | ||
| 41 | |||
| 42 | # backwards compatibility with VERSION < v"1.5-" | ||
| 43 | By(by) = By(by, Forward) | ||
| 44 | |||
| 45 | struct Lt{T} <: Ordering | ||
| 46 | lt::T | ||
| 47 | end | ||
| 48 | |||
| 49 | struct Perm{O<:Ordering,V<:AbstractVector} <: Ordering | ||
| 50 | order::O | ||
| 51 | data::V | ||
| 52 | end | ||
| 53 | |||
| 54 | ReverseOrdering(by::By) = By(by.by, ReverseOrdering(by.order)) | ||
| 55 | ReverseOrdering(perm::Perm) = Perm(ReverseOrdering(perm.order), perm.data) | ||
| 56 | |||
| 57 | lt(o::ForwardOrdering, a, b) = isless(a,b) | ||
| 58 | lt(o::ReverseOrdering, a, b) = lt(o.fwd,b,a) | ||
| 59 | lt(o::By, a, b) = lt(o.order,o.by(a),o.by(b)) | ||
| 60 | 348 (42 %) |
348 (42 %)
samples spent in lt
338 (97 %) (incl.) when called from sort! line 592 10 (3 %) (incl.) when called from sort! line 490
348 (100 %)
samples spent calling
#1
lt(o::Lt, a, b) = o.lt(a,b)
|
|
| 61 | |||
| 62 | @propagate_inbounds function lt(p::Perm, a::Integer, b::Integer) | ||
| 63 | da = p.data[a] | ||
| 64 | db = p.data[b] | ||
| 65 | lt(p.order, da, db) | (!lt(p.order, db, da) & (a < b)) | ||
| 66 | end | ||
| 67 | |||
| 68 | _ord(lt::typeof(isless), by::typeof(identity), order::Ordering) = order | ||
| 69 | _ord(lt::typeof(isless), by, order::Ordering) = By(by, order) | ||
| 70 | |||
| 71 | function _ord(lt, by, order::Ordering) | ||
| 72 | if order === Forward | ||
| 73 | 348 (42 %) |
348 (100 %)
samples spent calling
>
return Lt((x, y) -> lt(by(x), by(y)))
|
|
| 74 | elseif order === Reverse | ||
| 75 | return Lt((x, y) -> lt(by(y), by(x))) | ||
| 76 | else | ||
| 77 | error("Passing both lt= and order= arguments is ambiguous; please pass order=Forward or order=Reverse (or leave default)") | ||
| 78 | end | ||
| 79 | end | ||
| 80 | |||
| 81 | ord(lt, by, rev::Nothing, order::Ordering=Forward) = _ord(lt, by, order) | ||
| 82 | |||
| 83 | function ord(lt, by, rev::Bool, order::Ordering=Forward) | ||
| 84 | o = _ord(lt, by, order) | ||
| 85 | return rev ? ReverseOrdering(o) : o | ||
| 86 | end | ||
| 87 | |||
| 88 | |||
| 89 | # This function is not in use anywhere in Base but we observed | ||
| 90 | # use in sorting-related packages (#34719). It's probably best to move | ||
| 91 | # this functionality to those packages in the future; let's remind/force | ||
| 92 | # ourselves to deprecate this in v2.0. | ||
| 93 | # The following clause means `if VERSION < v"2.0-"` but it also works during | ||
| 94 | # bootstrap. For the same reason, we need to write `Int32` instead of `Cint`. | ||
| 95 | if ccall(:jl_ver_major, Int32, ()) < 2 | ||
| 96 | ordtype(o::ReverseOrdering, vs::AbstractArray) = ordtype(o.fwd, vs) | ||
| 97 | ordtype(o::Perm, vs::AbstractArray) = ordtype(o.order, o.data) | ||
| 98 | # TODO: here, we really want the return type of o.by, without calling it | ||
| 99 | ordtype(o::By, vs::AbstractArray) = try typeof(o.by(vs[1])) catch; Any end | ||
| 100 | ordtype(o::Ordering, vs::AbstractArray) = eltype(vs) | ||
| 101 | end | ||
| 102 | |||
| 103 | end |