sort.test 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160
  1. ;;;; sort.test --- tests Guile's sort functions -*- scheme -*-
  2. ;;;; Copyright (C) 2003, 2006, 2007, 2009, 2011, 2017
  3. ;;;; Free Software Foundation, Inc.
  4. ;;;;
  5. ;;;; This library is free software; you can redistribute it and/or
  6. ;;;; modify it under the terms of the GNU Lesser General Public
  7. ;;;; License as published by the Free Software Foundation; either
  8. ;;;; version 3 of the License, or (at your option) any later version.
  9. ;;;;
  10. ;;;; This library is distributed in the hope that it will be useful,
  11. ;;;; but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. ;;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  13. ;;;; Lesser General Public License for more details.
  14. ;;;;
  15. ;;;; You should have received a copy of the GNU Lesser General Public
  16. ;;;; License along with this library; if not, write to the Free Software
  17. ;;;; Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  18. (use-modules (test-suite lib)
  19. (ice-9 arrays))
  20. (set! *random-state* (seed->random-state 2017))
  21. ; Randomly shuffle u in place, using Fisher-Yates algorithm.
  22. (define (array-shuffle! v)
  23. (unless (= 1 (array-rank v)) (throw 'bad-rank (array-rank v)))
  24. (let* ((dims (car (array-shape v)))
  25. (lo (car dims)))
  26. (let loop ((i (cadr dims)))
  27. (if (> i lo)
  28. (let* ((j (+ lo (random (- (1+ i) lo))))
  29. (t (array-ref v j)))
  30. (array-set! v (array-ref v i) j)
  31. (array-set! v t i)
  32. (loop (- i 1)))
  33. v))))
  34. (define* (test-sort! v #:optional (sort sort))
  35. (array-index-map! v (lambda (i) i))
  36. (let ((before (array-copy v)))
  37. (array-shuffle! v)
  38. (let ((after (array-copy v)))
  39. (and
  40. (equal? before (sort v <))
  41. (equal? after v)))))
  42. (define* (test-sort-inplace! v #:optional (sort! sort!))
  43. (array-index-map! v (lambda (i) i))
  44. (let ((before (array-copy v)))
  45. (array-shuffle! v)
  46. (and (equal? before (sort! v <))
  47. (equal? before v)
  48. (sorted? v <))))
  49. (with-test-prefix "sort"
  50. (pass-if-exception "less function taking less than two arguments"
  51. exception:wrong-num-args
  52. (sort '(1 2) (lambda (x) #t)))
  53. (pass-if-exception "less function taking more than two arguments"
  54. exception:wrong-num-args
  55. (sort '(1 2) (lambda (x y z) z)))
  56. (pass-if "sort of vector"
  57. (test-sort! (make-vector 100)))
  58. (pass-if "sort of typed vector"
  59. (test-sort! (make-f64vector 100))))
  60. (with-test-prefix "sort!"
  61. (pass-if "sort of empty vector"
  62. (test-sort-inplace! (vector)))
  63. (pass-if "sort of vector"
  64. (test-sort-inplace! (make-vector 100)))
  65. (pass-if "sort of empty typed vector"
  66. (test-sort-inplace! (f64vector)))
  67. (pass-if "sort! of typed vector"
  68. (test-sort-inplace! (make-f64vector 100)))
  69. (pass-if "sort! of non-contigous array"
  70. (let* ((a (make-array 0 100 3))
  71. (v (make-shared-array a (lambda (i) (list i 0)) 100)))
  72. (test-sort-inplace! v)))
  73. (pass-if "sort! of non-contigous typed array"
  74. (let* ((a (make-typed-array 'f64 0 99 3))
  75. (v (make-shared-array a (lambda (i) (list i 0)) 99)))
  76. (test-sort-inplace! v)))
  77. (pass-if "sort! of negative-increment array"
  78. (let* ((a (make-array 0 100 3))
  79. (v (make-shared-array a (lambda (i) (list (- 99 i) 0)) 100)))
  80. (test-sort-inplace! v)))
  81. (pass-if "sort! of non-zero base index array"
  82. (test-sort-inplace! (make-array 0 '(-99 0))))
  83. (pass-if "sort! of non-zero base index typed array"
  84. (test-sort-inplace! (make-typed-array 'f64 0 '(-99 0))))
  85. (pass-if "sort! of negative-increment typed array"
  86. (let* ((a (make-typed-array 'f64 0 99 3))
  87. (v (make-shared-array a (lambda (i) (list (- 98 i) 0)) 99)))
  88. (test-sort-inplace! v))))
  89. (with-test-prefix "stable-sort!"
  90. (pass-if "stable-sort!"
  91. (let ((v (make-vector 100)))
  92. (test-sort-inplace! v stable-sort!)))
  93. (pass-if "stable-sort! of non-contigous array"
  94. (let* ((a (make-array 0 100 3))
  95. (v (make-shared-array a (lambda (i) (list i 0)) 100)))
  96. (test-sort-inplace! v stable-sort!)))
  97. (pass-if "stable-sort! of negative-increment array"
  98. (let* ((a (make-array 0 100 3))
  99. (v (make-shared-array a (lambda (i) (list (- 99 i) 0)) 100)))
  100. (test-sort-inplace! v stable-sort!)))
  101. (pass-if "stable-sort! of non-zero base index array"
  102. (test-sort-inplace! (make-array 0 '(-99 0)) stable-sort!)))
  103. (with-test-prefix "stable-sort"
  104. ;; in guile 1.8.0 and 1.8.1 this test failed, an empty list provoked a
  105. ;; wrong-type-arg exception (where it shouldn't)
  106. (pass-if "empty list"
  107. (eq? '() (stable-sort '() <)))
  108. ;; Ditto here, but up to 2.0.1 and 2.1.0 and invoking undefined
  109. ;; behavior (integer underflow) leading to crashes.
  110. (pass-if "empty vector"
  111. (equal? '#() (stable-sort '#() <))))
  112. (with-test-prefix "mutable/immutable arguments"
  113. (with-test-prefix/c&e "immutable arguments"
  114. (pass-if "sort! of empty vector"
  115. (equal? #() (sort! (vector) <)))
  116. (pass-if "sort of immutable vector"
  117. (equal? #(0 1) (sort #(1 0) <))))
  118. (pass-if-exception "sort! of mutable vector (compile)"
  119. exception:wrong-type-arg
  120. (compile '(sort! #(0) <) #:to 'value #:env (current-module))))