StatProfilerHTML.jl report
Generated on Thu, 26 Mar 2020 19:09:01
File source code
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 (42 %) samples spent in #1
348 (100 %) (incl.) when called from lt line 60
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