...
Run Format

Source file src/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	}
   266	

View as plain text