← Back to branch summary

~ubuntu-branches/ubuntu/wily/julia/wily

« back to all changes in this revision

Viewing changes to base/sort.jl

  • Committer: Package Import Robot
  • Author(s): Sébastien Villemot
  • Date: 2013-01-16 12:29:42 UTC
  • mfrom: (1.1.2)
  • Revision ID: package-import@ubuntu.com-20130116122942-x86e42akjq31repw
Tags: 0.0.0+20130107.gitd9656f41-1
* New upstream snashot
* No longer try to rebuild helpdb.jl.
   + debian/rules: remove helpdb.jl from build-arch rule
   + debian/control: move back python-sphinx to Build-Depends-Indep
* debian/copyright: reflect upstream changes
* Add Build-Conflicts on libatlas3-base (makes linalg tests fail)
* debian/rules: replace obsolete USE_DEBIAN makeflag by a list of
  USE_SYSTEM_* flags
* debian/rules: on non-x86 systems, use libm instead of openlibm
* dpkg-buildflags.patch: remove patch, applied upstream
* Refreshed other patches

Show diffs side-by-side

added added

removed removed

Lines of Context:
base/sort.jl
1
1
## standard sort comparisons ##
2
2
 
3
 
_jl_fp_pos_lt(x::Float32, y::Float32) = slt_int(unbox(Float32,x),unbox(Float32,y))
4
 
_jl_fp_pos_lt(x::Float64, y::Float64) = slt_int(unbox(Float64,x),unbox(Float64,y))
5
 
_jl_fp_pos_le(x::Float32, y::Float32) = sle_int(unbox(Float32,x),unbox(Float32,y))
6
 
_jl_fp_pos_le(x::Float64, y::Float64) = sle_int(unbox(Float64,x),unbox(Float64,y))
7
 
 
8
 
_jl_fp_neg_lt(x::Float32, y::Float32) = slt_int(unbox(Float32,y),unbox(Float32,x))
9
 
_jl_fp_neg_lt(x::Float64, y::Float64) = slt_int(unbox(Float64,y),unbox(Float64,x))
10
 
_jl_fp_neg_le(x::Float32, y::Float32) = sle_int(unbox(Float32,y),unbox(Float32,x))
11
 
_jl_fp_neg_le(x::Float64, y::Float64) = sle_int(unbox(Float64,y),unbox(Float64,x))
 
3
module Sort
 
4
 
 
5
export 
 
6
    @in_place_matrix_op,
 
7
    issorted,
 
8
    issorted_r,
 
9
    issorted_by,
 
10
    order,
 
11
    search_sorted,
 
12
    search_sorted_r,
 
13
    search_sorted_by,
 
14
    search_sorted_first,
 
15
    search_sorted_first_r,
 
16
    search_sorted_first_by,
 
17
    search_sorted_last,
 
18
    search_sorted_last_r,
 
19
    search_sorted_last_by,
 
20
    select,
 
21
    select!,
 
22
    select_r,
 
23
    select_r!,
 
24
    select_by,
 
25
    select_by!,
 
26
    sort,
 
27
    sort!,
 
28
    sort_by,
 
29
    sort_by!,
 
30
    sortr,
 
31
    sortr!,
 
32
    sortperm,
 
33
    sortperm!,
 
34
    sortperm_r,
 
35
    sortperm_r!,
 
36
    sortperm_by,
 
37
    sortperm_by!,
 
38
 
 
39
    insertionsort,
 
40
    insertionsort!,
 
41
    insertionsort_r,
 
42
    insertionsort_r!,
 
43
    insertionsort_by,
 
44
    insertionsort_by!,
 
45
    insertionsort_perm,
 
46
    insertionsort_perm!,
 
47
    insertionsort_perm_r,
 
48
    insertionsort_perm_r!,
 
49
    insertionsort_perm_by,
 
50
    insertionsort_perm_by!,
 
51
    mergesort,
 
52
    mergesort!,
 
53
    mergesort_r,
 
54
    mergesort_r!,
 
55
    mergesort_by,
 
56
    mergesort_by!,
 
57
    mergesort_perm,
 
58
    mergesort_perm!,
 
59
    mergesort_perm_r,
 
60
    mergesort_perm_r!,
 
61
    mergesort_perm_by,
 
62
    mergesort_perm_by!,
 
63
    quicksort,
 
64
    quicksort!,
 
65
    quicksort_r,
 
66
    quicksort_r!,
 
67
    quicksort_by,
 
68
    quicksort_by!,
 
69
    timsort,
 
70
    timsort!,
 
71
    timsort_r,
 
72
    timsort_r!,
 
73
    timsort_by,
 
74
    timsort_by!,
 
75
    timsort_perm,
 
76
    timsort_perm!,
 
77
    timsort_perm_r,
 
78
    timsort_perm_r!,
 
79
    timsort_perm_by,
 
80
    timsort_perm_by!
 
81
 
 
82
import Base.sort, Base.issorted, Base.sort, Base.sort!, Base.sortperm, Base.slt_int,
 
83
       Base.unbox, Base.sle_int, Base.length
 
84
 
 
85
fp_pos_lt(x::Float32, y::Float32) = slt_int(unbox(Float32,x),unbox(Float32,y))
 
86
fp_pos_lt(x::Float64, y::Float64) = slt_int(unbox(Float64,x),unbox(Float64,y))
 
87
fp_pos_le(x::Float32, y::Float32) = sle_int(unbox(Float32,x),unbox(Float32,y))
 
88
fp_pos_le(x::Float64, y::Float64) = sle_int(unbox(Float64,x),unbox(Float64,y))
 
89
 
 
90
fp_neg_lt(x::Float32, y::Float32) = slt_int(unbox(Float32,y),unbox(Float32,x))
 
91
fp_neg_lt(x::Float64, y::Float64) = slt_int(unbox(Float64,y),unbox(Float64,x))
 
92
fp_neg_le(x::Float32, y::Float32) = sle_int(unbox(Float32,y),unbox(Float32,x))
 
93
fp_neg_le(x::Float64, y::Float64) = sle_int(unbox(Float64,y),unbox(Float64,x))
12
94
 
13
95
## internal sorting functionality ##
14
96
 
15
 
macro _jl_sort_functions(suffix, lt, args...)
16
 
insertionsort = esc(symbol("_jl_insertionsort$suffix"))
17
 
quicksort = esc(symbol("_jl_quicksort$suffix"))
18
 
mergesort = esc(symbol("_jl_mergesort$suffix"))
19
 
pivot_middle = esc(symbol("_jl_pivot_middle$suffix"))
20
 
lt = @eval (a,b)->$lt
21
 
quote
 
97
include("timsort.jl")
 
98
 
 
99
for (suffix, lt, args) in (("",    (a,b)->:(isless($a,$b)), ()),
 
100
                           ("_r",  (a,b)->:(isless($b,$a)), ()),
 
101
                           ("",    (a,b)->:(lt($a,$b)), (:(lt::Function),)),
 
102
                           ("_by", (a,b)->:(isless(by($a),by($b))), (:(by::Function),)),
 
103
                           ## special sorting for floating-point arrays ##
 
104
                           ("_fp_pos", (a,b)->:(fp_pos_lt($a,$b)), ()),
 
105
                           ("_fp_neg", (a,b)->:(fp_neg_lt($a,$b)), ()))
 
106
    insertionsort = symbol("insertionsort$(suffix)")
 
107
    insertionsort! = symbol("insertionsort$(suffix)!")
 
108
    insertionsort_perm = symbol("insertionsort_perm$(suffix)")
 
109
    insertionsort_perm! = symbol("insertionsort_perm$(suffix)!")
 
110
    quicksort = symbol("quicksort$(suffix)")
 
111
    quicksort! = symbol("quicksort$(suffix)!")
 
112
    quicksort_perm = symbol("quicksort_perm$(suffix)")
 
113
    quicksort_perm! = symbol("quicksort_perm$(suffix)!")
 
114
    mergesort = symbol("mergesort$(suffix)")
 
115
    mergesort! = symbol("mergesort$(suffix)!")
 
116
    mergesort_perm = symbol("mergesort_perm$(suffix)")
 
117
    mergesort_perm! = symbol("mergesort_perm$(suffix)!")
 
118
    pivot_middle = symbol("pivot_middle$(suffix)")
 
119
    issorted = symbol("issorted$(suffix)")
 
120
    quickselect = symbol("quickselect$(suffix)")
 
121
    select = symbol("select$(suffix)")
 
122
    select! = symbol("select$(suffix)!")
 
123
    search_sorted = symbol("search_sorted$(suffix)")
 
124
    search_sorted_first = symbol("search_sorted_first$(suffix)")
 
125
    search_sorted_last = symbol("search_sorted_last$(suffix)")
 
126
    sortperm = symbol("sortperm$(suffix)")
 
127
    sortperm! = symbol("sortperm$(suffix)!")
 
128
@eval begin
22
129
 
23
130
# sorting should be stable
24
131
# Thus, if a permutation is required, or records are being sorted
26
133
# If only numbers are being sorted, a faster quicksort can be used.
27
134
 
28
135
# fast sort for small arrays
29
 
function ($insertionsort)($(args...), a::AbstractVector, lo::Int, hi::Int)
 
136
function ($insertionsort!)($(args...), a::AbstractVector, lo::Int, hi::Int)
30
137
    for i = lo+1:hi
31
138
        j = i
32
139
        x = a[i]
43
150
    return a
44
151
end
45
152
 
 
153
($insertionsort!)($(args...), a::AbstractVector) = ($insertionsort!)($(args...), a, 1, length(a))
 
154
($insertionsort)($(args...), a::AbstractVector, args2...) = ($insertionsort!)($(args...), copy(a), args2...)
 
155
 
46
156
# permutes an auxilliary array mirroring the sort
47
 
function ($insertionsort)($(args...), a::AbstractVector, p::AbstractVector{Int}, lo::Int, hi::Int)
 
157
function ($insertionsort_perm!)($(args...), a::AbstractVector, p::AbstractVector{Int}, lo::Int, hi::Int)
48
158
    for i = lo+1:hi
49
159
        j = i
50
160
        x = a[i]
64
174
    return a, p
65
175
end
66
176
 
67
 
($pivot_middle)(a,b,c) = $(lt(:a,:b)) ? ($(lt(:b,:c)) ? b : c) : ($(lt(:a,:c)) ? a : c)
 
177
($insertionsort_perm!){T}($(args...), a::AbstractVector{T}, p::AbstractVector{Int}) =
 
178
    ($insertionsort_perm!)($(args...), a, p, 1, length(a))
 
179
($insertionsort_perm!){T}($(args...), a::AbstractVector{T}) =
 
180
    ($insertionsort_perm!)($(args...), a, [1:length(a)])
 
181
($insertionsort_perm){T}($(args...), a::AbstractVector{T}, args2...) =
 
182
    ($insertionsort_perm!)($(args...), copy(a), [1:length(a)], args2...)
 
183
 
 
184
 
 
185
($pivot_middle)($(args...),a,b,c) = $(lt(:a,:b)) ? ($(lt(:b,:c)) ? b : c) : ($(lt(:a,:c)) ? a : c)
68
186
 
69
187
# very fast but unstable
70
 
function ($quicksort)($(args...), a::AbstractVector, lo::Int, hi::Int)
 
188
function ($quicksort!)($(args...), a::AbstractVector, lo::Int, hi::Int)
71
189
    while hi > lo
72
190
        if hi-lo <= 20
73
 
            return $(expr(:call, insertionsort, args..., :a, :lo, :hi))
 
191
            return $(expr(:call, insertionsort!, args..., :a, :lo, :hi))
74
192
        end
75
193
        i, j = lo, hi
76
 
        # pivot = (a[lo]+a[hi])/2                                   # 1.14x
77
 
          pivot = a[(lo+hi)>>>1]                                    # 1.15x
78
 
        # pivot = (a[lo]+a[hi]+a[(lo+hi)>>>1])/3                    # 1.16x
79
 
        # pivot = _jl_pivot_middle(a[lo], a[hi], a[(lo+hi)>>>1])    # 1.23x
80
 
        # pivot = a[randival(lo,hi)]                                # 1.28x
 
194
        # pivot = (a[lo]+a[hi])/2                                               # 1.14x
 
195
          pivot = a[(lo+hi)>>>1]                                                # 1.15x
 
196
        # pivot = (a[lo]+a[hi]+a[(lo+hi)>>>1])/3                                # 1.16x
 
197
        # pivot = pivot_middle($(args...), a[lo], a[hi], a[(lo+hi)>>>1])    # 1.23x
 
198
        # pivot = a[randival(lo,hi)]                                            # 1.28x
81
199
        while i <= j
82
200
            while $(lt(:(a[i]), :pivot)); i += 1; end
83
201
            while $(lt(:pivot, :(a[j]))); j -= 1; end
88
206
            end
89
207
        end
90
208
        if lo < j
91
 
            $(expr(:call, quicksort, args..., :a, :lo, :j))
 
209
            $(expr(:call, quicksort!, args..., :a, :lo, :j))
92
210
        end
93
211
        lo = i
94
212
    end
95
213
    return a
96
214
end
97
215
 
 
216
($quicksort!)($(args...), a::AbstractVector) = ($quicksort!)($(args...), a, 1, length(a))
 
217
($quicksort)($(args...), a::AbstractVector) = ($quicksort!)($(args...), copy(a), 1, length(a))
 
218
 
98
219
# less fast & not in-place, but stable
99
 
function ($mergesort)($(args...), a::AbstractVector, lo::Int, hi::Int, b::AbstractVector)
 
220
function ($mergesort!)($(args...), a::AbstractVector, lo::Int, hi::Int, b::AbstractVector)
100
221
    if lo < hi
101
222
        if hi-lo <= 20
102
 
            return ($insertionsort)($(args...), a, lo, hi)
 
223
            return ($insertionsort!)($(args...), a, lo, hi)
103
224
        end
104
225
 
105
226
        m = (lo+hi)>>>1
106
 
        ($mergesort)($(args...), a, lo, m, b)
107
 
        ($mergesort)($(args...), a, m+1, hi, b)
 
227
        ($mergesort!)($(args...), a, lo, m, b)
 
228
        ($mergesort!)($(args...), a, m+1, hi, b)
108
229
 
109
230
        # merge(lo,m,hi)
110
231
        i = 1
136
257
    return a
137
258
end
138
259
 
 
260
($mergesort!){T}($(args...), a::AbstractVector{T}) = ($mergesort!)($(args...), a, 1, length(a), Array(T,length(a)))
 
261
($mergesort){T}($(args...), a::AbstractVector{T}) = 
 
262
    ($mergesort!)($(args...), copy(a), 1, length(a), Array(T,length(a)))
 
263
 
139
264
# permutes auxilliary arrays mirroring the sort
140
 
function ($mergesort)($(args...),
141
 
                      a::AbstractVector, p::AbstractVector{Int}, lo::Int, hi::Int,
142
 
                      b::AbstractVector, pb::AbstractVector{Int})
 
265
function ($mergesort_perm!)($(args...),
 
266
                            a::AbstractVector, p::AbstractVector{Int}, lo::Int, hi::Int,
 
267
                            b::AbstractVector, pb::AbstractVector{Int})
143
268
    if lo < hi
144
269
        if hi-lo <= 20
145
 
            return ($insertionsort)($(args...), a, p, lo, hi)
 
270
            return ($insertionsort_perm!)($(args...), a, p, lo, hi)
146
271
        end
147
272
 
148
273
        m = (lo+hi)>>>1
149
 
        ($mergesort)($(args...), a, p, lo, m, b, pb)
150
 
        ($mergesort)($(args...), a, p, m+1, hi, b, pb)
 
274
        ($mergesort_perm!)($(args...), a, p, lo, m, b, pb)
 
275
        ($mergesort_perm!)($(args...), a, p, m+1, hi, b, pb)
151
276
 
152
277
        # merge(lo,m,hi)
153
278
        i = 1
183
308
    return a, p
184
309
end
185
310
 
186
 
end; end # quote / macro
187
 
 
188
 
@_jl_sort_functions ""    :(isless($a,$b))
189
 
@_jl_sort_functions "_r"  :(isless($b,$a))
190
 
@_jl_sort_functions "_lt" :(lt($a,$b)) lt::Function
191
 
@_jl_sort_functions "_by" :(isless(by($a),by($b))) by::Function
 
311
($mergesort_perm!){T}($(args...), a::AbstractVector{T}, p::AbstractVector{Int}) = 
 
312
    ($mergesort_perm!)($(args...), a, p, 1, length(a), Array(T,length(a)), Array(Int,length(a)))
 
313
($mergesort_perm!){T}($(args...), a::AbstractVector{T}) = 
 
314
    ($mergesort_perm!)($(args...), a, [1:length(a)])
 
315
($mergesort_perm){T}($(args...), a::AbstractVector{T}, args2...) = 
 
316
    ($mergesort_perm!)($(args...), copy(a), [1:length(a)], args2...)
 
317
 
 
318
 
 
319
function ($issorted)($(args...), v::AbstractVector)
 
320
  for i = 1:length(v)-1
 
321
      if $(lt(:(v[i+1]), :(v[i])))
 
322
          return false
 
323
      end
 
324
  end
 
325
  return true
 
326
end
 
327
 
 
328
function ($quickselect)($(args...), a::AbstractArray, k::Int, lo::Int, hi::Int)
 
329
    if k < lo || k > hi; error("k is out of bounds"); end
 
330
 
 
331
    while true
 
332
 
 
333
        if lo == hi; return a[lo]; end
 
334
 
 
335
        i, j = lo, hi
 
336
        pivot = ($pivot_middle)($(args...), a[lo], a[hi], a[(lo+hi)>>>1])
 
337
        while i < j
 
338
            while $(lt(:(a[i]), :(pivot))); i += 1; end
 
339
            while $(lt(:(pivot), :(a[j]))); j -= 1; end
 
340
            #if isequal(a[i], a[j])
 
341
            if !$(lt(:(a[i]), :(a[j]))) && !$(lt(:(a[j]), :(a[i])))
 
342
                i += 1
 
343
            elseif i < j
 
344
                a[i], a[j] = a[j], a[i]
 
345
            end
 
346
        end
 
347
        pivot_ind = j
 
348
 
 
349
        len = pivot_ind - lo + 1
 
350
        if k == len
 
351
            return a[pivot_ind]
 
352
        elseif k <  len
 
353
            hi = pivot_ind - 1
 
354
        else
 
355
            lo = pivot_ind + 1
 
356
            k = k - len
 
357
        end
 
358
 
 
359
    end # while true...
 
360
 
 
361
end
 
362
 
 
363
($select!)($(args...), a::AbstractArray, k::Int) = ($quickselect)($(args...), a, k, 1, length(a))
 
364
($select)($(args...), a::AbstractArray, k::Int) = ($quickselect)($(args...), copy(a), k, 1, length(a))
 
365
 
 
366
($search_sorted)($(args...), a::Vector, x) = ($search_sorted_first)($(args...), a, x, 1, length(a))
 
367
 
 
368
($search_sorted_last)($(args...), a::Vector, x) = ($search_sorted_last)($(args...), a, x, 1, length(a))
 
369
 
 
370
function ($search_sorted_last)($(args...), a::Vector, x, lo::Int, hi::Int)
 
371
    ## Index of the last value of vector a that is less than or equal to x.
 
372
    ## Returns 0 if x is less than all values of a.
 
373
    ## 
 
374
    ## Good reference: http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary 
 
375
    lo = lo-1
 
376
    hi = hi+1
 
377
    while lo < hi-1
 
378
        i = (lo+hi)>>>1
 
379
        if $(lt(:(x), :(a[i])))
 
380
            hi = i
 
381
        else
 
382
            lo = i
 
383
        end
 
384
    end
 
385
    lo
 
386
end
 
387
 
 
388
($search_sorted_first)($(args...), a::Vector, x) = ($search_sorted_first)($(args...), a, x, 1, length(a))
 
389
 
 
390
function ($search_sorted_first)($(args...), a::Vector, x, lo::Int, hi::Int)
 
391
    ## Index of the first value of vector a that is greater than or equal to x.
 
392
    ## Returns length(a) + 1 if x is greater than all values in a.
 
393
    ## 
 
394
    ## Good reference: http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary 
 
395
    lo = lo-1
 
396
    hi = hi+1
 
397
    while lo < hi-1
 
398
        i = (lo+hi)>>>1
 
399
        if $(lt(:(a[i]), :(x)))
 
400
            lo = i
 
401
        else
 
402
            hi = i
 
403
        end
 
404
    end
 
405
    hi
 
406
end
 
407
 
 
408
($sortperm){T}($(args...), a::AbstractVector{T}, args2...) = ($mergesort_perm)($(args...), a, args2...)
 
409
($sortperm!){T}($(args...), a::AbstractVector{T}, args2...) = ($mergesort_perm!)($(args...), a, args2...)
 
410
 
 
411
end; end # @eval / for
 
412
 
 
413
search_sorted_last_r(a::Ranges, x::Real) = search_sorted_last(a, x)
 
414
search_sorted_first_r(a::Ranges, x::Real) = search_sorted_first(a, x)
 
415
search_sorted_r(a::Ranges, x::Real) = search_sorted(a, x)
 
416
search_sorted(a::Ranges, x::Real) = search_sorted_first(a, x)
 
417
 
 
418
search_sorted_last(a::Ranges, x::Real) =
 
419
    max(min(int(fld(x - a[1], step(a))) + 1, length(a)), 0)
 
420
 
 
421
function search_sorted_first(a::Ranges, x::Real)
 
422
    n = x - a[1]
 
423
    s = step(a)
 
424
    max(min(int(fld(n, s)) + (rem(n, s) != 0), length(a)), 0) + 1
 
425
end
192
426
 
193
427
## external sorting functions ##
194
428
 
195
 
sort!{T<:Real}(a::AbstractVector{T})  = _jl_quicksort(a, 1, length(a))
196
 
sortr!{T<:Real}(a::AbstractVector{T}) = _jl_quicksort_r(a, 1, length(a))
197
 
sort!{T}(a::AbstractVector{T})  = _jl_mergesort(a, 1, length(a), Array(T,length(a)))
198
 
sortr!{T}(a::AbstractVector{T}) = _jl_mergesort_r(a, 1, length(a), Array(T,length(a)))
 
429
sort!{T<:Real}(a::AbstractVector{T})  = quicksort!(a, 1, length(a))
 
430
sortr!{T<:Real}(a::AbstractVector{T}) = quicksort_r!(a, 1, length(a))
 
431
sort!{T}(a::AbstractVector{T})  = mergesort!(a, 1, length(a), Array(T,length(a)))
 
432
sortr!{T}(a::AbstractVector{T}) = mergesort_r!(a, 1, length(a), Array(T,length(a)))
199
433
 
200
434
sort!{T}(lt::Function, a::AbstractVector{T}) =
201
 
    _jl_mergesort_lt(lt, a, 1, length(a), Array(T,length(a)))
 
435
    mergesort!(lt, a, 1, length(a), Array(T,length(a)))
202
436
sort_by!{T}(by::Function, a::AbstractVector{T}) =
203
 
    _jl_mergesort_by(by, a, 1, length(a), Array(T,length(a)))
204
 
 
205
 
## special sorting for floating-point arrays ##
206
 
 
207
 
@_jl_sort_functions "_fp_pos" :(_jl_fp_pos_lt($a,$b))
208
 
@_jl_sort_functions "_fp_neg" :(_jl_fp_neg_lt($a,$b))
 
437
    mergesort_by!(by, a, 1, length(a), Array(T,length(a)))
209
438
 
210
439
# push NaNs to the end of a, returning # of non-NaNs
211
 
function _jl_nans_to_end{T<:FloatingPoint}(a::AbstractVector{T})
 
440
function nans_to_end{T<:FloatingPoint}(a::AbstractVector{T})
212
441
    n = length(a)
213
442
    if n <= 1
214
443
        return n
235
464
end
236
465
 
237
466
function sort!{T<:FloatingPoint}(a::AbstractVector{T})
238
 
    n = _jl_nans_to_end(a)
 
467
    n = nans_to_end(a)
239
468
    i, j = 1, n
240
469
    while true
241
470
        # TODO: faster positive negative int check?
242
 
        while i <= j && _jl_fp_pos_lt(a[i],zero(T)); i += 1; end
243
 
        while i <= j && _jl_fp_pos_le(zero(T),a[j]); j -= 1; end
 
471
        while i <= j && fp_pos_lt(a[i],zero(T)); i += 1; end
 
472
        while i <= j && fp_pos_le(zero(T),a[j]); j -= 1; end
244
473
        if i <= j
245
474
            a[i], a[j] = a[j], a[i]
246
475
            i += 1
249
478
            break
250
479
        end
251
480
    end
252
 
    _jl_quicksort_fp_neg(a, 1, j)
253
 
    _jl_quicksort_fp_pos(a, i, n)
254
 
    return a
255
 
end
256
 
 
257
 
# TODO: something sensible should happen when each_col et. al. are used with a
258
 
# pure function argument
259
 
function each_col!(f::Function, a::AbstractMatrix)
260
 
    m = size(a,1)
261
 
    for i = 1:m:numel(a)
262
 
        f(sub(a, i:(i+m-1)))
263
 
    end
264
 
    return a
265
 
end
266
 
 
267
 
function each_row!(f::Function, a::AbstractMatrix)
268
 
    m = size(a,1)
269
 
    for i = 1:m
270
 
        f(sub(a, i:m:numel(a)))
271
 
    end
272
 
    return a
273
 
end
274
 
 
275
 
function each_vec!(f::Function, a::AbstractMatrix, dim::Integer)
276
 
    if dim == 1; return each_col!(f,a); end
277
 
    if dim == 2; return each_row!(f,a); end
278
 
    error("invalid matrix dimensions: $dim")
279
 
end
280
 
 
281
 
each_col(f::Function, a::AbstractMatrix) = each_col!(f,copy(a))
282
 
each_row(f::Function, a::AbstractMatrix) = each_row!(f,copy(a))
283
 
each_vec(f::Function, a::AbstractMatrix, d::Integer) = each_vec!(f,copy(a),d)
 
481
    quicksort_fp_neg!(a, 1, j)
 
482
    quicksort_fp_pos!(a, i, n)
 
483
    return a
 
484
end
 
485
 
284
486
 
285
487
## other sorting functions defined in terms of sort! ##
286
488
 
315
517
@in_place_matrix_op sortr
316
518
@in_place_matrix_op sort_by by::Function
317
519
 
 
520
@in_place_matrix_op insertionsort
 
521
@in_place_matrix_op insertionsort lt::Function
 
522
@in_place_matrix_op insertionsort_r
 
523
@in_place_matrix_op insertionsort_by by::Function
 
524
 
 
525
@in_place_matrix_op quicksort
 
526
@in_place_matrix_op quicksort lt::Function
 
527
@in_place_matrix_op quicksort_r
 
528
@in_place_matrix_op quicksort_by by::Function
 
529
 
 
530
@in_place_matrix_op mergesort
 
531
@in_place_matrix_op mergesort lt::Function
 
532
@in_place_matrix_op mergesortr
 
533
@in_place_matrix_op mergesort_by by::Function
 
534
 
 
535
@in_place_matrix_op timsort
 
536
@in_place_matrix_op timsort lt::Function
 
537
@in_place_matrix_op timsortr
 
538
@in_place_matrix_op timsort_by by::Function
 
539
 
318
540
# TODO: implement generalized in-place, ditch this
319
541
function sort(a::AbstractArray, dim::Int)
320
542
    X = similar(a)
332
554
    return X
333
555
end
334
556
 
335
 
sortperm{T}(a::AbstractVector{T}) =
336
 
    _jl_mergesort(copy(a), [1:length(a)], 1, length(a),
337
 
                  Array(T, length(a)), Array(Int, length(a)))
338
 
 
339
 
function issorted(v::AbstractVector)
340
 
  for i = 1:length(v)-1
341
 
      if isless(v[i+1], v[i])
342
 
          return false
343
 
      end
344
 
  end
345
 
  return true
346
 
end
347
 
 
348
 
function _jl_quickselect(a::AbstractArray, k::Int, lo::Int, hi::Int)
349
 
    if k < lo || k > hi; error("k is out of bounds"); end
350
 
 
351
 
    while true
352
 
 
353
 
        if lo == hi; return a[lo]; end
354
 
 
355
 
        i, j = lo, hi
356
 
        pivot = _jl_pivot_middle(a[lo], a[hi], a[(lo+hi)>>>1])
357
 
        while i < j
358
 
            while isless(a[i], pivot); i += 1; end
359
 
            while isless(pivot, a[j]); j -= 1; end
360
 
            if isequal(a[i], a[j])
361
 
                i += 1
362
 
            elseif i < j
363
 
                a[i], a[j] = a[j], a[i]
364
 
            end
365
 
        end
366
 
        pivot_ind = j
367
 
 
368
 
        length = pivot_ind - lo + 1
369
 
        if k == length
370
 
            return a[pivot_ind]
371
 
        elseif k <  length
372
 
            hi = pivot_ind - 1
373
 
        else
374
 
            lo = pivot_ind + 1
375
 
            k = k - length
376
 
        end
377
 
 
378
 
    end # while true...
379
 
 
380
 
end
381
 
 
382
 
select(a::AbstractArray, k::Int) = _jl_quickselect(copy(a), k, 1, length(a))
383
 
select!(a::AbstractArray, k::Int) = _jl_quickselect(a, k, 1, length(a))
384
 
 
385
 
search_sorted(a::Vector, x) = search_sorted(a, x, 1, length(a))
386
 
 
387
 
function search_sorted(a::Vector, x, lo::Int, hi::Int)
388
 
    if isless(a[hi], x)
389
 
        return hi+1
390
 
    end
391
 
    while lo < hi-1
392
 
        i = (lo+hi)>>>1
393
 
        if isless(x,a[i])
394
 
            hi = i
395
 
        else
396
 
            lo = i
397
 
        end
398
 
    end
399
 
    return isless(a[lo],x) ? hi : lo
400
 
end
401
 
 
402
 
search_sorted_last(a::Vector, x) = search_sorted_last(a, x, 0, length(a)+1)
403
 
 
404
 
function search_sorted_last(a::Vector, x, lo::Int, hi::Int)
405
 
    ## Index of the last value of vector a that is less than or equal to x.
406
 
    ## Returns 0 if x is less than all values of a.
407
 
    ## 
408
 
    ## Good reference: http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary 
409
 
    while lo < hi-1
410
 
        i = (lo+hi)>>>1
411
 
        if isless(x,a[i])
412
 
            hi = i
413
 
        else
414
 
            lo = i
415
 
        end
416
 
    end
417
 
    lo
418
 
end
419
 
 
420
 
search_sorted_first(a::Vector, x) = search_sorted_first(a, x, 0, length(a)+1)
421
 
 
422
 
function search_sorted_first(a::Vector, x, lo::Int, hi::Int)
423
 
    ## Index of the first value of vector a that is greater than or equal to x.
424
 
    ## Returns length(a) + 1 if x is greater than all values in a.
425
 
    ## 
426
 
    ## Good reference: http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary 
427
 
    while lo < hi-1
428
 
        i = (lo+hi)>>>1
429
 
        if isless(a[i],x)
430
 
            lo = i
431
 
        else
432
 
            hi = i
433
 
        end
434
 
    end
435
 
    hi
436
 
end
437
 
 
438
557
order(a::AbstractVector) = sortperm(a)[2]
 
558
 
 
559
end # module Sort