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 |