huffman_sortByLiteral.go 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201
  1. // Copyright 2009 The Go Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style
  3. // license that can be found in the LICENSE file.
  4. package flate
  5. // Sort sorts data.
  6. // It makes one call to data.Len to determine n, and O(n*log(n)) calls to
  7. // data.Less and data.Swap. The sort is not guaranteed to be stable.
  8. func sortByLiteral(data []literalNode) {
  9. n := len(data)
  10. quickSort(data, 0, n, maxDepth(n))
  11. }
  12. func quickSort(data []literalNode, a, b, maxDepth int) {
  13. for b-a > 12 { // Use ShellSort for slices <= 12 elements
  14. if maxDepth == 0 {
  15. heapSort(data, a, b)
  16. return
  17. }
  18. maxDepth--
  19. mlo, mhi := doPivot(data, a, b)
  20. // Avoiding recursion on the larger subproblem guarantees
  21. // a stack depth of at most lg(b-a).
  22. if mlo-a < b-mhi {
  23. quickSort(data, a, mlo, maxDepth)
  24. a = mhi // i.e., quickSort(data, mhi, b)
  25. } else {
  26. quickSort(data, mhi, b, maxDepth)
  27. b = mlo // i.e., quickSort(data, a, mlo)
  28. }
  29. }
  30. if b-a > 1 {
  31. // Do ShellSort pass with gap 6
  32. // It could be written in this simplified form cause b-a <= 12
  33. for i := a + 6; i < b; i++ {
  34. if data[i].literal < data[i-6].literal {
  35. data[i], data[i-6] = data[i-6], data[i]
  36. }
  37. }
  38. insertionSort(data, a, b)
  39. }
  40. }
  41. func heapSort(data []literalNode, a, b int) {
  42. first := a
  43. lo := 0
  44. hi := b - a
  45. // Build heap with greatest element at top.
  46. for i := (hi - 1) / 2; i >= 0; i-- {
  47. siftDown(data, i, hi, first)
  48. }
  49. // Pop elements, largest first, into end of data.
  50. for i := hi - 1; i >= 0; i-- {
  51. data[first], data[first+i] = data[first+i], data[first]
  52. siftDown(data, lo, i, first)
  53. }
  54. }
  55. // siftDown implements the heap property on data[lo, hi).
  56. // first is an offset into the array where the root of the heap lies.
  57. func siftDown(data []literalNode, lo, hi, first int) {
  58. root := lo
  59. for {
  60. child := 2*root + 1
  61. if child >= hi {
  62. break
  63. }
  64. if child+1 < hi && data[first+child].literal < data[first+child+1].literal {
  65. child++
  66. }
  67. if data[first+root].literal > data[first+child].literal {
  68. return
  69. }
  70. data[first+root], data[first+child] = data[first+child], data[first+root]
  71. root = child
  72. }
  73. }
  74. func doPivot(data []literalNode, lo, hi int) (midlo, midhi int) {
  75. m := int(uint(lo+hi) >> 1) // Written like this to avoid integer overflow.
  76. if hi-lo > 40 {
  77. // Tukey's ``Ninther,'' median of three medians of three.
  78. s := (hi - lo) / 8
  79. medianOfThree(data, lo, lo+s, lo+2*s)
  80. medianOfThree(data, m, m-s, m+s)
  81. medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
  82. }
  83. medianOfThree(data, lo, m, hi-1)
  84. // Invariants are:
  85. // data[lo] = pivot (set up by ChoosePivot)
  86. // data[lo < i < a] < pivot
  87. // data[a <= i < b] <= pivot
  88. // data[b <= i < c] unexamined
  89. // data[c <= i < hi-1] > pivot
  90. // data[hi-1] >= pivot
  91. pivot := lo
  92. a, c := lo+1, hi-1
  93. for ; a < c && data[a].literal < data[pivot].literal; a++ {
  94. }
  95. b := a
  96. for {
  97. for ; b < c && data[pivot].literal > data[b].literal; b++ { // data[b] <= pivot
  98. }
  99. for ; b < c && data[pivot].literal < data[c-1].literal; c-- { // data[c-1] > pivot
  100. }
  101. if b >= c {
  102. break
  103. }
  104. // data[b] > pivot; data[c-1] <= pivot
  105. data[b], data[c-1] = data[c-1], data[b]
  106. b++
  107. c--
  108. }
  109. // If hi-c<3 then there are duplicates (by property of median of nine).
  110. // Let's be a bit more conservative, and set border to 5.
  111. protect := hi-c < 5
  112. if !protect && hi-c < (hi-lo)/4 {
  113. // Lets test some points for equality to pivot
  114. dups := 0
  115. if data[pivot].literal > data[hi-1].literal { // data[hi-1] = pivot
  116. data[c], data[hi-1] = data[hi-1], data[c]
  117. c++
  118. dups++
  119. }
  120. if data[b-1].literal > data[pivot].literal { // data[b-1] = pivot
  121. b--
  122. dups++
  123. }
  124. // m-lo = (hi-lo)/2 > 6
  125. // b-lo > (hi-lo)*3/4-1 > 8
  126. // ==> m < b ==> data[m] <= pivot
  127. if data[m].literal > data[pivot].literal { // data[m] = pivot
  128. data[m], data[b-1] = data[b-1], data[m]
  129. b--
  130. dups++
  131. }
  132. // if at least 2 points are equal to pivot, assume skewed distribution
  133. protect = dups > 1
  134. }
  135. if protect {
  136. // Protect against a lot of duplicates
  137. // Add invariant:
  138. // data[a <= i < b] unexamined
  139. // data[b <= i < c] = pivot
  140. for {
  141. for ; a < b && data[b-1].literal > data[pivot].literal; b-- { // data[b] == pivot
  142. }
  143. for ; a < b && data[a].literal < data[pivot].literal; a++ { // data[a] < pivot
  144. }
  145. if a >= b {
  146. break
  147. }
  148. // data[a] == pivot; data[b-1] < pivot
  149. data[a], data[b-1] = data[b-1], data[a]
  150. a++
  151. b--
  152. }
  153. }
  154. // Swap pivot into middle
  155. data[pivot], data[b-1] = data[b-1], data[pivot]
  156. return b - 1, c
  157. }
  158. // Insertion sort
  159. func insertionSort(data []literalNode, a, b int) {
  160. for i := a + 1; i < b; i++ {
  161. for j := i; j > a && data[j].literal < data[j-1].literal; j-- {
  162. data[j], data[j-1] = data[j-1], data[j]
  163. }
  164. }
  165. }
  166. // maxDepth returns a threshold at which quicksort should switch
  167. // to heapsort. It returns 2*ceil(lg(n+1)).
  168. func maxDepth(n int) int {
  169. var depth int
  170. for i := n; i > 0; i >>= 1 {
  171. depth++
  172. }
  173. return depth * 2
  174. }
  175. // medianOfThree moves the median of the three values data[m0], data[m1], data[m2] into data[m1].
  176. func medianOfThree(data []literalNode, m1, m0, m2 int) {
  177. // sort 3 elements
  178. if data[m1].literal < data[m0].literal {
  179. data[m1], data[m0] = data[m0], data[m1]
  180. }
  181. // data[m0] <= data[m1]
  182. if data[m2].literal < data[m1].literal {
  183. data[m2], data[m1] = data[m1], data[m2]
  184. // data[m0] <= data[m2] && data[m1] < data[m2]
  185. if data[m1].literal < data[m0].literal {
  186. data[m1], data[m0] = data[m0], data[m1]
  187. }
  188. }
  189. // now data[m0] <= data[m1] <= data[m2]
  190. }