"Fossies" - the Fresh Open Source Software Archive

Member "julia-1.1.1/share/julia/test/sorting.jl" (16 May 2019, 13306 Bytes) of package /linux/misc/julia-1.1.1-linux-i686.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Julia source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

    1 # This file is a part of Julia. License is MIT: https://julialang.org/license
    2 
    3 using Base.Order: Forward
    4 using Random
    5 
    6 @test sort([2,3,1]) == [1,2,3]
    7 @test sort([2,3,1], rev=true) == [3,2,1]
    8 @test sort(['z':-1:'a';]) == ['a':'z';]
    9 @test sort(['a':'z';], rev=true) == ['z':-1:'a';]
   10 @test sortperm([2,3,1]) == [3,1,2]
   11 @test sortperm!([1,2,3], [2,3,1]) == [3,1,2]
   12 let s = view([1,2,3,4], 1:3),
   13     r = sortperm!(s, [2,3,1])
   14     @test r == [3,1,2]
   15     @test r === s
   16 end
   17 @test_throws ArgumentError sortperm!(view([1,2,3,4], 1:4), [2,3,1])
   18 @test !issorted([2,3,1])
   19 @test issorted([1,2,3])
   20 @test reverse([2,3,1]) == [1,3,2]
   21 @test partialsort([3,6,30,1,9],3) == 6
   22 @test partialsort([3,6,30,1,9],3:4) == [6,9]
   23 @test partialsortperm([3,6,30,1,9], 3:4) == [2,5]
   24 @test partialsortperm!(Vector(1:5), [3,6,30,1,9], 3:4) == [2,5]
   25 let a=[1:10;]
   26     for r in Any[2:4, 1:2, 10:10, 4:2, 2:1, 4:-1:2, 2:-1:1, 10:-1:10, 4:1:3, 1:2:8, 10:-3:1]
   27         @test partialsort(a, r) == [r;]
   28         @test partialsortperm(a, r) == [r;]
   29         @test partialsort(a, r, rev=true) == (11 .- [r;])
   30         @test partialsortperm(a, r, rev=true) == (11 .- [r;])
   31     end
   32 end
   33 @test sum(randperm(6)) == 21
   34 
   35 @testset "searchsorted" begin
   36     numTypes = [ Int8,  Int16,  Int32,  Int64,  Int128,
   37                 UInt8, UInt16, UInt32, UInt64, UInt128,
   38                 Float16, Float32, Float64, BigInt, BigFloat]
   39 
   40     @test searchsorted([1:10;], 1, by=(x -> x >= 5)) == 1:4
   41     @test searchsorted([1:10;], 10, by=(x -> x >= 5)) == 5:10
   42     @test searchsorted([1:5; 1:5; 1:5], 1, 6, 10, Forward) == 6:6
   43     @test searchsorted(fill(1, 15), 1, 6, 10, Forward) == 6:10
   44 
   45     for R in numTypes, T in numTypes
   46         @test searchsorted(R[1, 1, 2, 2, 3, 3], T(0)) == 1:0
   47         @test searchsorted(R[1, 1, 2, 2, 3, 3], T(1)) == 1:2
   48         @test searchsorted(R[1, 1, 2, 2, 3, 3], T(2)) == 3:4
   49         @test searchsorted(R[1, 1, 2, 2, 3, 3], T(4)) == 7:6
   50         @test searchsorted(R[1, 1, 2, 2, 3, 3], 2.5) == 5:4
   51 
   52         @test searchsorted(1:3, T(0)) == 1:0
   53         @test searchsorted(1:3, T(1)) == 1:1
   54         @test searchsorted(1:3, T(2)) == 2:2
   55         @test searchsorted(1:3, T(4)) == 4:3
   56 
   57         @test searchsorted(R[1:10;], T(1), by=(x -> x >= 5)) == 1:4
   58         @test searchsorted(R[1:10;], T(10), by=(x -> x >= 5)) == 5:10
   59         @test searchsorted(R[1:5; 1:5; 1:5], T(1), 6, 10, Forward) == 6:6
   60         @test searchsorted(fill(R(1), 15), T(1), 6, 10, Forward) == 6:10
   61     end
   62 
   63     for (rg,I) in [(49:57,47:59), (1:2:17,-1:19), (-3:0.5:2,-5:.5:4)]
   64         rg_r = reverse(rg)
   65         rgv, rgv_r = [rg;], [rg_r;]
   66         for i = I
   67             @test searchsorted(rg,i) == searchsorted(rgv,i)
   68             @test searchsorted(rg_r,i,rev=true) == searchsorted(rgv_r,i,rev=true)
   69         end
   70     end
   71 
   72     rg = 0.0:0.01:1.0
   73     for i = 2:101
   74         @test searchsorted(rg, rg[i]) == i:i
   75         @test searchsorted(rg, prevfloat(rg[i])) == i:i-1
   76         @test searchsorted(rg, nextfloat(rg[i])) == i+1:i
   77     end
   78 
   79     rg_r = reverse(rg)
   80     for i = 1:100
   81         @test searchsorted(rg_r, rg_r[i], rev=true) == i:i
   82         @test searchsorted(rg_r, prevfloat(rg_r[i]), rev=true) == i+1:i
   83         @test searchsorted(rg_r, nextfloat(rg_r[i]), rev=true) == i:i-1
   84     end
   85 
   86     @test searchsorted(1:10, 1, by=(x -> x >= 5)) == searchsorted([1:10;], 1, by=(x -> x >= 5))
   87     @test searchsorted(1:10, 10, by=(x -> x >= 5)) == searchsorted([1:10;], 10, by=(x -> x >= 5))
   88 
   89     @test searchsorted([], 0) == 1:0
   90     @test searchsorted([1,2,3], 0) == 1:0
   91     @test searchsorted([1,2,3], 4) == 4:3
   92 
   93     @testset "issue 8866" begin
   94         @test searchsortedfirst(500:1.0:600, -1.0e20) == 1
   95         @test searchsortedfirst(500:1.0:600, 1.0e20) == 102
   96         @test searchsortedlast(500:1.0:600, -1.0e20) == 0
   97         @test searchsortedlast(500:1.0:600, 1.0e20) == 101
   98     end
   99 end
  100 # exercise the codepath in searchsorted* methods for ranges that check for zero step range
  101 struct ConstantRange{T} <: AbstractRange{T}
  102    val::T
  103    len::Int
  104 end
  105 
  106 Base.length(r::ConstantRange) = r.len
  107 Base.getindex(r::ConstantRange, i::Int) = (1 <= i <= r.len || throw(BoundsError(r,i)); r.val)
  108 Base.step(r::ConstantRange) = 0
  109 
  110 @testset "searchsorted method with ranges which check for zero step range" begin
  111     r = ConstantRange(1, 5)
  112 
  113     @test searchsortedfirst(r, 1.0, Forward) == 1
  114     @test searchsortedfirst(r, 1, Forward) == 1
  115     @test searchsortedfirst(r, UInt(1), Forward) == 1
  116 
  117     @test searchsortedlast(r, 1.0, Forward) == 5
  118     @test searchsortedlast(r, 1, Forward) == 5
  119     @test searchsortedlast(r, UInt(1), Forward) == 5
  120 
  121     a = rand(1:10000, 1000)
  122     for alg in [InsertionSort, MergeSort]
  123         b = sort(a, alg=alg)
  124         @test issorted(b)
  125 
  126         ix = sortperm(a, alg=alg)
  127         b = a[ix]
  128         @test issorted(b)
  129         @test a[ix] == b
  130 
  131         sortperm!(view(ix, 1:100), view(a, 1:100), alg=alg)
  132         b = a[ix][1:100]
  133         @test issorted(b)
  134 
  135         sortperm!(ix, a, alg=alg)
  136         b = a[ix]
  137         @test issorted(b)
  138         @test a[ix] == b
  139 
  140         b = sort(a, alg=alg, rev=true)
  141         @test issorted(b, rev=true)
  142         ix = sortperm(a, alg=alg, rev=true)
  143         b = a[ix]
  144         @test issorted(b, rev=true)
  145         @test a[ix] == b
  146 
  147         sortperm!(view(ix, 1:100), view(a, 1:100), alg=alg, rev=true)
  148         b = a[ix][1:100]
  149         @test issorted(b, rev=true)
  150 
  151         sortperm!(ix, a, alg=alg, rev=true)
  152         b = a[ix]
  153         @test issorted(b, rev=true)
  154         @test a[ix] == b
  155 
  156         b = sort(a, alg=alg, by=x->1/x)
  157         @test issorted(b, by=x->1/x)
  158         ix = sortperm(a, alg=alg, by=x->1/x)
  159         b = a[ix]
  160         @test issorted(b, by=x->1/x)
  161         @test a[ix] == b
  162 
  163         sortperm!(view(ix, 1:100), view(a, 1:100), by=x->1/x)
  164         b = a[ix][1:100]
  165         @test issorted(b, by=x->1/x)
  166 
  167         sortperm!(ix, a, alg=alg, by=x->1/x)
  168         b = a[ix]
  169         @test issorted(b, by=x->1/x)
  170         @test a[ix] == b
  171 
  172         c = copy(a)
  173         permute!(c, ix)
  174         @test c == b
  175 
  176         invpermute!(c, ix)
  177         @test c == a
  178 
  179         c = sort(a, alg=alg, lt=(>))
  180         @test b == c
  181 
  182         c = sort(a, alg=alg, by=x->1/x)
  183         @test b == c
  184     end
  185 
  186     @testset "unstable algorithms" begin
  187         for alg in [QuickSort, PartialQuickSort(length(a))]
  188             b = sort(a, alg=alg)
  189             @test issorted(b)
  190             b = sort(a, alg=alg, rev=true)
  191             @test issorted(b, rev=true)
  192             b = sort(a, alg=alg, by=x->1/x)
  193             @test issorted(b, by=x->1/x)
  194         end
  195     end
  196 end
  197 @testset "PartialQuickSort" begin
  198     a = rand(1:10000, 1000)
  199     # test PartialQuickSort only does a partial sort
  200     let alg = PartialQuickSort(div(length(a), 10))
  201         k = alg.k
  202         b = sort(a, alg=alg)
  203         c = sort(a, alg=alg, by=x->1/x)
  204         d = sort(a, alg=alg, rev=true)
  205         @test issorted(b[1:k])
  206         @test issorted(c[1:k], by=x->1/x)
  207         @test issorted(d[1:k], rev=true)
  208         @test !issorted(b)
  209         @test !issorted(c, by=x->1/x)
  210         @test !issorted(d, rev=true)
  211     end
  212 
  213     @test partialsort([3,6,30,1,9], 2, rev=true) == 9
  214     @test partialsort([3,6,30,1,9], 2, by=x->1/x) == 9
  215     @test partialsortperm([3,6,30,1,9], 2, rev=true) == 5
  216     @test partialsortperm([3,6,30,1,9], 2, by=x->1/x) == 5
  217 end
  218 ## more advanced sorting tests ##
  219 
  220 randnans(n) = reinterpret(Float64,[rand(UInt64)|0x7ff8000000000000 for i=1:n])
  221 
  222 function randn_with_nans(n,p)
  223     v = randn(n)
  224     x = findall(rand(n).<p)
  225     v[x] = randnans(length(x))
  226     return v
  227 end
  228 
  229 @testset "advanced sorting" begin
  230     Random.seed!(0xdeadbeef)
  231     for n in [0:10; 100; 101; 1000; 1001]
  232         local r
  233         r = -5:5
  234         v = rand(r,n)
  235         h = [sum(v .== x) for x in r]
  236 
  237         for rev in [false,true]
  238             # insertion sort (stable) as reference
  239             pi = sortperm(v, alg=InsertionSort, rev=rev)
  240             @test pi == sortperm(float(v), alg=InsertionSort, rev=rev)
  241             @test isperm(pi)
  242             si = v[pi]
  243             @test [sum(si .== x) for x in r] == h
  244             @test issorted(si, rev=rev)
  245             @test all(issorted,[pi[si.==x] for x in r])
  246             c = copy(v)
  247             permute!(c, pi)
  248             @test c == si
  249             invpermute!(c, pi)
  250             @test c == v
  251 
  252             # stable algorithms
  253             for alg in [MergeSort]
  254                 p = sortperm(v, alg=alg, rev=rev)
  255                 @test p == sortperm(float(v), alg=alg, rev=rev)
  256                 @test p == pi
  257                 s = copy(v)
  258                 permute!(s, p)
  259                 @test s == si
  260                 invpermute!(s, p)
  261                 @test s == v
  262             end
  263 
  264             # unstable algorithms
  265             for alg in [QuickSort, PartialQuickSort(n)]
  266                 p = sortperm(v, alg=alg, rev=rev)
  267                 @test p == sortperm(float(v), alg=alg, rev=rev)
  268                 @test isperm(p)
  269                 @test v[p] == si
  270                 s = copy(v)
  271                 permute!(s, p)
  272                 @test s == si
  273                 invpermute!(s, p)
  274                 @test s == v
  275             end
  276         end
  277 
  278         v = randn_with_nans(n,0.1)
  279         # TODO: alg = PartialQuickSort(n) fails here
  280         for alg in [InsertionSort, QuickSort, MergeSort],
  281             rev in [false,true]
  282             # test float sorting with NaNs
  283             s = sort(v, alg=alg, rev=rev)
  284             @test issorted(s, rev=rev)
  285             @test reinterpret(UInt64,v[isnan.(v)]) == reinterpret(UInt64,s[isnan.(s)])
  286 
  287             # test float permutation with NaNs
  288             p = sortperm(v, alg=alg, rev=rev)
  289             @test isperm(p)
  290             vp = v[p]
  291             @test isequal(vp,s)
  292             @test reinterpret(UInt64,vp) == reinterpret(UInt64,s)
  293         end
  294     end
  295 end
  296 
  297 @testset "sortperm" begin
  298     inds = [
  299         1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9,10,
  300         10,10,11,11,11,12,12,12,13,13,13,14,14,14,15,15,15,16,16,
  301         16,17,17,17,18,18,18,19,19,19,20,20,20,21,21,22,22,22,23,
  302         23,24,24,24,25,25,25,26,26,26,27,27,27,28,28,28,29,29,29,
  303         30,30,30,31,31,32,32,32,33,33,33,34,34,34,35,35,35,36,36,
  304         36,37,37,37,38,38,38,39,39,39,40,40,40,41,41,41,42,42,42,
  305         43,43,43,44,44,44,45,45,45,46,46,46,47,47,47,48,48,48,49,
  306         49,49,50,50,50,51,51,52,52,52,53,53,53,54,54,54,55,55,55,
  307         56,56,56,57,57,57,58,58,58,59,60,60,60,61,61,61,62,62,63,
  308         64,64,64,65,65,65,66,66,66,67,67,67,68,68,69,69,69,70,70,
  309         70,71,71,71,72,72,72,73,73,73,74,75,75,75,76,76,76,77,77,
  310         77,78,78,78,79,79,79,80,80,80,81,81,82,82,82,83,83,83,84,
  311         84,84,85,85,85,86,86,86,87,87,87,88,88,88,89,89,89,90,90,
  312         90,91,91,91,92,92,93,93,93,94,94,94,95,95,95,96,96,96,97,
  313         97,98,98,98,99,99,99,100,100,100,101,101,101,102,102,102,
  314         103,103,103,104,105,105,105,106,106,106,107,107,107,108,
  315         108,108,109,109,109,110,110,110,111,111,111,112,112,112,
  316         113,113,113,114,114,115,115,115,116,116,116,117,117,117,
  317         118,118,118,119,119,119,120,120,120,121,121,121,122,122,
  318         122,123,123,123,124,124,124,125,125,125,126,126,126,127,
  319         127,127,128,128,128,129,129,129,130,130,130,131,131,131,
  320         132,132,132,133,133,133,134,134,134,135,135,135,136,136,
  321         136,137,137,137,138,138,138,139,139,139,140,140,140,141,
  322         141,142,142,142,143,143,143,144,144,144,145,145,145,146,
  323         146,146,147,147,147,148,148,148,149,149,149,150,150,150,
  324         151,151,151,152,152,152,153,153,153,154,154,154,155,155,
  325         155,156,156,156,157,157,157,158,158,158,159,159,159,160,
  326         160,160,161,161,161,162,162,162,163,163,163,164,164,164,
  327         165,165,165,166,166,166,167,167,167,168,168,168,169,169,
  328         169,170,170,170,171,171,171,172,172,172,173,173,173,174,
  329         174,174,175,175,175,176,176,176,177,177,177,178,178,178,
  330         179,179,179,180,180,180,181,181,181,182,182,182,183,183,
  331         183,184,184,184,185,185,185,186,186,186,187,187,187,188,
  332         188,188,189,189,189,190,190,190,191,191,191,192,192,192,
  333         193,193,193,194,194,194,195,195,195,196,196,197,197,197,
  334         198,198,198,199,199,199,200,200,200
  335     ]
  336 
  337     let sp = sortperm(inds)
  338         @test all(issorted, [sp[inds.==x] for x in 1:200])
  339     end
  340 
  341     for alg in [InsertionSort, MergeSort]
  342         sp = sortperm(inds, alg=alg)
  343         @test all(issorted, [sp[inds.==x] for x in 1:200])
  344     end
  345 end
  346 @testset "issue #6177" begin
  347     @test sortperm([ 0.0, 1.0, 1.0], rev=true) == [2, 3, 1]
  348     @test sortperm([-0.0, 1.0, 1.0], rev=true) == [2, 3, 1]
  349     @test sortperm([-1.0, 1.0, 1.0], rev=true) == [2, 3, 1]
  350 end
  351 # issue #8825 - stability of min/max
  352 mutable struct Twain
  353     a :: Int
  354     b :: Int
  355 end
  356 Base.isless(x :: Twain, y :: Twain) = x.a < y.a
  357 let x = Twain(2,3), y = Twain(2,4)
  358     @test (min(x,y), max(x,y)) == (x,y) == minmax(x,y)
  359 end
  360 
  361 # issue #12833 - type stability of sort
  362 @test Base.return_types(sort, (Vector{Int},)) == [Vector{Int}]
  363 
  364 @testset "PR #18791" begin
  365     @test sort([typemax(Int),typemin(Int)]) == [typemin(Int),typemax(Int)]
  366     @test sort([typemax(UInt),0]) == [0,typemax(UInt)]
  367 end
  368 @testset "issue #19005" begin
  369     @test searchsortedfirst(0:256, 0x80) == 129
  370     @test searchsortedlast(0:256, 0x80) == 129
  371 end
  372 # https://discourse.julialang.org/t/sorting-big-int-with-v-0-6/1241
  373 @test sort([big(3), big(2)]) == [big(2), big(3)]