libgo/go/sort/zfuncversion.go

   1 // DO NOT EDIT; AUTO-GENERATED from sort.go using genzfunc.go
   2
   3 // Copyright 2016 The Go Authors. All rights reserved.
   4 // Use of this source code is governed by a BSD-style
   5 // license that can be found in the LICENSE file.
   6
   7 package sort
   8
   9 // Auto-generated variant of sort.go:insertionSort
  10 func insertionSort_func(data lessSwap, a, b int) {
  11         for i := a + 1; i < b; i++ {
  12                 for j := i; j > a && data.Less(j, j-1); j-- {
  13                         data.Swap(j, j-1)
  14                 }
  15         }
  16 }
  17
  18 // Auto-generated variant of sort.go:siftDown
  19 func siftDown_func(data lessSwap, lo, hi, first int) {
  20         root := lo
  21         for {
  22                 child := 2*root + 1
  23                 if child >= hi {
  24                         break
  25                 }
  26                 if child+1 < hi && data.Less(first+child, first+child+1) {
  27                         child++
  28                 }
  29                 if !data.Less(first+root, first+child) {
  30                         return
  31                 }
  32                 data.Swap(first+root, first+child)
  33                 root = child
  34         }
  35 }
  36
  37 // Auto-generated variant of sort.go:heapSort
  38 func heapSort_func(data lessSwap, a, b int) {
  39         first := a
  40         lo := 0
  41         hi := b - a
  42         for i := (hi - 1) / 2; i >= 0; i-- {
  43                 siftDown_func(data, i, hi, first)
  44         }
  45         for i := hi - 1; i >= 0; i-- {
  46                 data.Swap(first, first+i)
  47                 siftDown_func(data, lo, i, first)
  48         }
  49 }
  50
  51 // Auto-generated variant of sort.go:medianOfThree
  52 func medianOfThree_func(data lessSwap, m1, m0, m2 int) {
  53         if data.Less(m1, m0) {
  54                 data.Swap(m1, m0)
  55         }
  56         if data.Less(m2, m1) {
  57                 data.Swap(m2, m1)
  58                 if data.Less(m1, m0) {
  59                         data.Swap(m1, m0)
  60                 }
  61         }
  62 }
  63
  64 // Auto-generated variant of sort.go:swapRange
  65 func swapRange_func(data lessSwap, a, b, n int) {
  66         for i := 0; i < n; i++ {
  67                 data.Swap(a+i, b+i)
  68         }
  69 }
  70
  71 // Auto-generated variant of sort.go:doPivot
  72 func doPivot_func(data lessSwap, lo, hi int) (midlo, midhi int) {
  73         m := lo + (hi-lo)/2
  74         if hi-lo > 40 {
  75                 s := (hi - lo) / 8
  76                 medianOfThree_func(data, lo, lo+s, lo+2*s)
  77                 medianOfThree_func(data, m, m-s, m+s)
  78                 medianOfThree_func(data, hi-1, hi-1-s, hi-1-2*s)
  79         }
  80         medianOfThree_func(data, lo, m, hi-1)
  81         pivot := lo
  82         a, c := lo+1, hi-1
  83         for ; a < c && data.Less(a, pivot); a++ {
  84         }
  85         b := a
  86         for {
  87                 for ; b < c && !data.Less(pivot, b); b++ {
  88                 }
  89                 for ; b < c && data.Less(pivot, c-1); c-- {
  90                 }
  91                 if b >= c {
  92                         break
  93                 }
  94                 data.Swap(b, c-1)
  95                 b++
  96                 c--
  97         }
  98         protect := hi-c < 5
  99         if !protect && hi-c < (hi-lo)/4 {
 100                 dups := 0
 101                 if !data.Less(pivot, hi-1) {
 102                         data.Swap(c, hi-1)
 103                         c++
 104                         dups++
 105                 }
 106                 if !data.Less(b-1, pivot) {
 107                         b--
 108                         dups++
 109                 }
 110                 if !data.Less(m, pivot) {
 111                         data.Swap(m, b-1)
 112                         b--
 113                         dups++
 114                 }
 115                 protect = dups > 1
 116         }
 117         if protect {
 118                 for {
 119                         for ; a < b && !data.Less(b-1, pivot); b-- {
 120                         }
 121                         for ; a < b && data.Less(a, pivot); a++ {
 122                         }
 123                         if a >= b {
 124                                 break
 125                         }
 126                         data.Swap(a, b-1)
 127                         a++
 128                         b--
 129                 }
 130         }
 131         data.Swap(pivot, b-1)
 132         return b - 1, c
 133 }
 134
 135 // Auto-generated variant of sort.go:quickSort
 136 func quickSort_func(data lessSwap, a, b, maxDepth int) {
 137         for b-a > 12 {
 138                 if maxDepth == 0 {
 139                         heapSort_func(data, a, b)
 140                         return
 141                 }
 142                 maxDepth--
 143                 mlo, mhi := doPivot_func(data, a, b)
 144                 if mlo-a < b-mhi {
 145                         quickSort_func(data, a, mlo, maxDepth)
 146                         a = mhi
 147                 } else {
 148                         quickSort_func(data, mhi, b, maxDepth)
 149                         b = mlo
 150                 }
 151         }
 152         if b-a > 1 {
 153                 for i := a + 6; i < b; i++ {
 154                         if data.Less(i, i-6) {
 155                                 data.Swap(i, i-6)
 156                         }
 157                 }
 158                 insertionSort_func(data, a, b)
 159         }
 160 }
 161
 162 // Auto-generated variant of sort.go:stable
 163 func stable_func(data lessSwap, n int) {
 164         blockSize := 20
 165         a, b := 0, blockSize
 166         for b <= n {
 167                 insertionSort_func(data, a, b)
 168                 a = b
 169                 b += blockSize
 170         }
 171         insertionSort_func(data, a, n)
 172         for blockSize < n {
 173                 a, b = 0, 2*blockSize
 174                 for b <= n {
 175                         symMerge_func(data, a, a+blockSize, b)
 176                         a = b
 177                         b += 2 * blockSize
 178                 }
 179                 if m := a + blockSize; m < n {
 180                         symMerge_func(data, a, m, n)
 181                 }
 182                 blockSize *= 2
 183         }
 184 }
 185
 186 // Auto-generated variant of sort.go:symMerge
 187 func symMerge_func(data lessSwap, a, m, b int) {
 188         if m-a == 1 {
 189                 i := m
 190                 j := b
 191                 for i < j {
 192                         h := i + (j-i)/2
 193                         if data.Less(h, a) {
 194                                 i = h + 1
 195                         } else {
 196                                 j = h
 197                         }
 198                 }
 199                 for k := a; k < i-1; k++ {
 200                         data.Swap(k, k+1)
 201                 }
 202                 return
 203         }
 204         if b-m == 1 {
 205                 i := a
 206                 j := m
 207                 for i < j {
 208                         h := i + (j-i)/2
 209                         if !data.Less(m, h) {
 210                                 i = h + 1
 211                         } else {
 212                                 j = h
 213                         }
 214                 }
 215                 for k := m; k > i; k-- {
 216                         data.Swap(k, k-1)
 217                 }
 218                 return
 219         }
 220         mid := a + (b-a)/2
 221         n := mid + m
 222         var start, r int
 223         if m > mid {
 224                 start = n - b
 225                 r = mid
 226         } else {
 227                 start = a
 228                 r = m
 229         }
 230         p := n - 1
 231         for start < r {
 232                 c := start + (r-start)/2
 233                 if !data.Less(p-c, c) {
 234                         start = c + 1
 235                 } else {
 236                         r = c
 237                 }
 238         }
 239         end := n - start
 240         if start < m && m < end {
 241                 rotate_func(data, start, m, end)
 242         }
 243         if a < start && start < mid {
 244                 symMerge_func(data, a, start, mid)
 245         }
 246         if mid < end && end < b {
 247                 symMerge_func(data, mid, end, b)
 248         }
 249 }
 250
 251 // Auto-generated variant of sort.go:rotate
 252 func rotate_func(data lessSwap, a, m, b int) {
 253         i := m - a
 254         j := b - m
 255         for i != j {
 256                 if i > j {
 257                         swapRange_func(data, m-i, m, j)
 258                         i -= j
 259                 } else {
 260                         swapRange_func(data, m-i, m+j-i, i)
 261                         j -= i
 262                 }
 263         }
 264         swapRange_func(data, m-i, m, i)
 265 }