zsortanyfunc.go

     1  // Code generated by gen_sort_variants.go; DO NOT EDIT.
     2  
     3  // Copyright 2022 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 slices
     8  
     9  // insertionSortCmpFunc sorts data[a:b] using insertion sort.
    10  func insertionSortCmpFunc[E any](data []E, a, b int, cmp func(a, b E) int) {
    11  	for i := a + 1; i < b; i++ {
    12  		for j := i; j > a && (cmp(data[j], data[j-1]) < 0); j-- {
    13  			data[j], data[j-1] = data[j-1], data[j]
    14  		}
    15  	}
    16  }
    17  
    18  // siftDownCmpFunc implements the heap property on data[lo:hi].
    19  // first is an offset into the array where the root of the heap lies.
    20  func siftDownCmpFunc[E any](data []E, lo, hi, first int, cmp func(a, b E) int) {
    21  	root := lo
    22  	for {
    23  		child := 2*root + 1
    24  		if child >= hi {
    25  			break
    26  		}
    27  		if child+1 < hi && (cmp(data[first+child], data[first+child+1]) < 0) {
    28  			child++
    29  		}
    30  		if !(cmp(data[first+root], data[first+child]) < 0) {
    31  			return
    32  		}
    33  		data[first+root], data[first+child] = data[first+child], data[first+root]
    34  		root = child
    35  	}
    36  }
    37  
    38  func heapSortCmpFunc[E any](data []E, a, b int, cmp func(a, b E) int) {
    39  	first := a
    40  	lo := 0
    41  	hi := b - a
    42  
    43  	// Build heap with greatest element at top.
    44  	for i := (hi - 1) / 2; i >= 0; i-- {
    45  		siftDownCmpFunc(data, i, hi, first, cmp)
    46  	}
    47  
    48  	// Pop elements, largest first, into end of data.
    49  	for i := hi - 1; i >= 0; i-- {
    50  		data[first], data[first+i] = data[first+i], data[first]
    51  		siftDownCmpFunc(data, lo, i, first, cmp)
    52  	}
    53  }
    54  
    55  // pdqsortCmpFunc sorts data[a:b].
    56  // The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort.
    57  // pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf
    58  // C++ implementation: https://github.com/orlp/pdqsort
    59  // Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/
    60  // limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.
    61  func pdqsortCmpFunc[E any](data []E, a, b, limit int, cmp func(a, b E) int) {
    62  	const maxInsertion = 12
    63  
    64  	var (
    65  		wasBalanced    = true // whether the last partitioning was reasonably balanced
    66  		wasPartitioned = true // whether the slice was already partitioned
    67  	)
    68  
    69  	for {
    70  		length := b - a
    71  
    72  		if length <= maxInsertion {
    73  			insertionSortCmpFunc(data, a, b, cmp)
    74  			return
    75  		}
    76  
    77  		// Fall back to heapsort if too many bad choices were made.
    78  		if limit == 0 {
    79  			heapSortCmpFunc(data, a, b, cmp)
    80  			return
    81  		}
    82  
    83  		// If the last partitioning was imbalanced, we need to breaking patterns.
    84  		if !wasBalanced {
    85  			breakPatternsCmpFunc(data, a, b, cmp)
    86  			limit--
    87  		}
    88  
    89  		pivot, hint := choosePivotCmpFunc(data, a, b, cmp)
    90  		if hint == decreasingHint {
    91  			reverseRangeCmpFunc(data, a, b, cmp)
    92  			// The chosen pivot was pivot-a elements after the start of the array.
    93  			// After reversing it is pivot-a elements before the end of the array.
    94  			// The idea came from Rust's implementation.
    95  			pivot = (b - 1) - (pivot - a)
    96  			hint = increasingHint
    97  		}
    98  
    99  		// The slice is likely already sorted.
   100  		if wasBalanced && wasPartitioned && hint == increasingHint {
   101  			if partialInsertionSortCmpFunc(data, a, b, cmp) {
   102  				return
   103  			}
   104  		}
   105  
   106  		// Probably the slice contains many duplicate elements, partition the slice into
   107  		// elements equal to and elements greater than the pivot.
   108  		if a > 0 && !(cmp(data[a-1], data[pivot]) < 0) {
   109  			mid := partitionEqualCmpFunc(data, a, b, pivot, cmp)
   110  			a = mid
   111  			continue
   112  		}
   113  
   114  		mid, alreadyPartitioned := partitionCmpFunc(data, a, b, pivot, cmp)
   115  		wasPartitioned = alreadyPartitioned
   116  
   117  		leftLen, rightLen := mid-a, b-mid
   118  		balanceThreshold := length / 8
   119  		if leftLen < rightLen {
   120  			wasBalanced = leftLen >= balanceThreshold
   121  			pdqsortCmpFunc(data, a, mid, limit, cmp)
   122  			a = mid + 1
   123  		} else {
   124  			wasBalanced = rightLen >= balanceThreshold
   125  			pdqsortCmpFunc(data, mid+1, b, limit, cmp)
   126  			b = mid
   127  		}
   128  	}
   129  }
   130  
   131  // partitionCmpFunc does one quicksort partition.
   132  // Let p = data[pivot]
   133  // Moves elements in data[a:b] around, so that data[i]<p and data[j]>=p for i<newpivot and j>newpivot.
   134  // On return, data[newpivot] = p
   135  func partitionCmpFunc[E any](data []E, a, b, pivot int, cmp func(a, b E) int) (newpivot int, alreadyPartitioned bool) {
   136  	data[a], data[pivot] = data[pivot], data[a]
   137  	i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned
   138  
   139  	for i <= j && (cmp(data[i], data[a]) < 0) {
   140  		i++
   141  	}
   142  	for i <= j && !(cmp(data[j], data[a]) < 0) {
   143  		j--
   144  	}
   145  	if i > j {
   146  		data[j], data[a] = data[a], data[j]
   147  		return j, true
   148  	}
   149  	data[i], data[j] = data[j], data[i]
   150  	i++
   151  	j--
   152  
   153  	for {
   154  		for i <= j && (cmp(data[i], data[a]) < 0) {
   155  			i++
   156  		}
   157  		for i <= j && !(cmp(data[j], data[a]) < 0) {
   158  			j--
   159  		}
   160  		if i > j {
   161  			break
   162  		}
   163  		data[i], data[j] = data[j], data[i]
   164  		i++
   165  		j--
   166  	}
   167  	data[j], data[a] = data[a], data[j]
   168  	return j, false
   169  }
   170  
   171  // partitionEqualCmpFunc partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot].
   172  // It assumed that data[a:b] does not contain elements smaller than the data[pivot].
   173  func partitionEqualCmpFunc[E any](data []E, a, b, pivot int, cmp func(a, b E) int) (newpivot int) {
   174  	data[a], data[pivot] = data[pivot], data[a]
   175  	i, j := a+1, b-1 // i and j are inclusive of the elements remaining to be partitioned
   176  
   177  	for {
   178  		for i <= j && !(cmp(data[a], data[i]) < 0) {
   179  			i++
   180  		}
   181  		for i <= j && (cmp(data[a], data[j]) < 0) {
   182  			j--
   183  		}
   184  		if i > j {
   185  			break
   186  		}
   187  		data[i], data[j] = data[j], data[i]
   188  		i++
   189  		j--
   190  	}
   191  	return i
   192  }
   193  
   194  // partialInsertionSortCmpFunc partially sorts a slice, returns true if the slice is sorted at the end.
   195  func partialInsertionSortCmpFunc[E any](data []E, a, b int, cmp func(a, b E) int) bool {
   196  	const (
   197  		maxSteps         = 5  // maximum number of adjacent out-of-order pairs that will get shifted
   198  		shortestShifting = 50 // don't shift any elements on short arrays
   199  	)
   200  	i := a + 1
   201  	for j := 0; j < maxSteps; j++ {
   202  		for i < b && !(cmp(data[i], data[i-1]) < 0) {
   203  			i++
   204  		}
   205  
   206  		if i == b {
   207  			return true
   208  		}
   209  
   210  		if b-a < shortestShifting {
   211  			return false
   212  		}
   213  
   214  		data[i], data[i-1] = data[i-1], data[i]
   215  
   216  		// Shift the smaller one to the left.
   217  		if i-a >= 2 {
   218  			for j := i - 1; j >= 1; j-- {
   219  				if !(cmp(data[j], data[j-1]) < 0) {
   220  					break
   221  				}
   222  				data[j], data[j-1] = data[j-1], data[j]
   223  			}
   224  		}
   225  		// Shift the greater one to the right.
   226  		if b-i >= 2 {
   227  			for j := i + 1; j < b; j++ {
   228  				if !(cmp(data[j], data[j-1]) < 0) {
   229  					break
   230  				}
   231  				data[j], data[j-1] = data[j-1], data[j]
   232  			}
   233  		}
   234  	}
   235  	return false
   236  }
   237  
   238  // breakPatternsCmpFunc scatters some elements around in an attempt to break some patterns
   239  // that might cause imbalanced partitions in quicksort.
   240  func breakPatternsCmpFunc[E any](data []E, a, b int, cmp func(a, b E) int) {
   241  	length := b - a
   242  	if length >= 8 {
   243  		random := xorshift(length)
   244  		modulus := nextPowerOfTwo(length)
   245  
   246  		for idx := a + (length/4)*2 - 1; idx <= a+(length/4)*2+1; idx++ {
   247  			other := int(uint(random.Next()) & (modulus - 1))
   248  			if other >= length {
   249  				other -= length
   250  			}
   251  			data[idx], data[a+other] = data[a+other], data[idx]
   252  		}
   253  	}
   254  }
   255  
   256  // choosePivotCmpFunc chooses a pivot in data[a:b].
   257  //
   258  // [0,8): chooses a static pivot.
   259  // [8,shortestNinther): uses the simple median-of-three method.
   260  // [shortestNinther,∞): uses the Tukey ninther method.
   261  func choosePivotCmpFunc[E any](data []E, a, b int, cmp func(a, b E) int) (pivot int, hint sortedHint) {
   262  	const (
   263  		shortestNinther = 50
   264  		maxSwaps        = 4 * 3
   265  	)
   266  
   267  	l := b - a
   268  
   269  	var (
   270  		swaps int
   271  		i     = a + l/4*1
   272  		j     = a + l/4*2
   273  		k     = a + l/4*3
   274  	)
   275  
   276  	if l >= 8 {
   277  		if l >= shortestNinther {
   278  			// Tukey ninther method, the idea came from Rust's implementation.
   279  			i = medianAdjacentCmpFunc(data, i, &swaps, cmp)
   280  			j = medianAdjacentCmpFunc(data, j, &swaps, cmp)
   281  			k = medianAdjacentCmpFunc(data, k, &swaps, cmp)
   282  		}
   283  		// Find the median among i, j, k and stores it into j.
   284  		j = medianCmpFunc(data, i, j, k, &swaps, cmp)
   285  	}
   286  
   287  	switch swaps {
   288  	case 0:
   289  		return j, increasingHint
   290  	case maxSwaps:
   291  		return j, decreasingHint
   292  	default:
   293  		return j, unknownHint
   294  	}
   295  }
   296  
   297  // order2CmpFunc returns x,y where data[x] <= data[y], where x,y=a,b or x,y=b,a.
   298  func order2CmpFunc[E any](data []E, a, b int, swaps *int, cmp func(a, b E) int) (int, int) {
   299  	if cmp(data[b], data[a]) < 0 {
   300  		*swaps++
   301  		return b, a
   302  	}
   303  	return a, b
   304  }
   305  
   306  // medianCmpFunc returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.
   307  func medianCmpFunc[E any](data []E, a, b, c int, swaps *int, cmp func(a, b E) int) int {
   308  	a, b = order2CmpFunc(data, a, b, swaps, cmp)
   309  	b, c = order2CmpFunc(data, b, c, swaps, cmp)
   310  	a, b = order2CmpFunc(data, a, b, swaps, cmp)
   311  	return b
   312  }
   313  
   314  // medianAdjacentCmpFunc finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.
   315  func medianAdjacentCmpFunc[E any](data []E, a int, swaps *int, cmp func(a, b E) int) int {
   316  	return medianCmpFunc(data, a-1, a, a+1, swaps, cmp)
   317  }
   318  
   319  func reverseRangeCmpFunc[E any](data []E, a, b int, cmp func(a, b E) int) {
   320  	i := a
   321  	j := b - 1
   322  	for i < j {
   323  		data[i], data[j] = data[j], data[i]
   324  		i++
   325  		j--
   326  	}
   327  }
   328  
   329  func swapRangeCmpFunc[E any](data []E, a, b, n int, cmp func(a, b E) int) {
   330  	for i := 0; i < n; i++ {
   331  		data[a+i], data[b+i] = data[b+i], data[a+i]
   332  	}
   333  }
   334  
   335  func stableCmpFunc[E any](data []E, n int, cmp func(a, b E) int) {
   336  	blockSize := 20 // must be > 0
   337  	a, b := 0, blockSize
   338  	for b <= n {
   339  		insertionSortCmpFunc(data, a, b, cmp)
   340  		a = b
   341  		b += blockSize
   342  	}
   343  	insertionSortCmpFunc(data, a, n, cmp)
   344  
   345  	for blockSize < n {
   346  		a, b = 0, 2*blockSize
   347  		for b <= n {
   348  			symMergeCmpFunc(data, a, a+blockSize, b, cmp)
   349  			a = b
   350  			b += 2 * blockSize
   351  		}
   352  		if m := a + blockSize; m < n {
   353  			symMergeCmpFunc(data, a, m, n, cmp)
   354  		}
   355  		blockSize *= 2
   356  	}
   357  }
   358  
   359  // symMergeCmpFunc merges the two sorted subsequences data[a:m] and data[m:b] using
   360  // the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum
   361  // Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz
   362  // Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in
   363  // Computer Science, pages 714-723. Springer, 2004.
   364  //
   365  // Let M = m-a and N = b-n. Wolog M < N.
   366  // The recursion depth is bound by ceil(log(N+M)).
   367  // The algorithm needs O(M*log(N/M + 1)) calls to data.Less.
   368  // The algorithm needs O((M+N)*log(M)) calls to data.Swap.
   369  //
   370  // The paper gives O((M+N)*log(M)) as the number of assignments assuming a
   371  // rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation
   372  // in the paper carries through for Swap operations, especially as the block
   373  // swapping rotate uses only O(M+N) Swaps.
   374  //
   375  // symMerge assumes non-degenerate arguments: a < m && m < b.
   376  // Having the caller check this condition eliminates many leaf recursion calls,
   377  // which improves performance.
   378  func symMergeCmpFunc[E any](data []E, a, m, b int, cmp func(a, b E) int) {
   379  	// Avoid unnecessary recursions of symMerge
   380  	// by direct insertion of data[a] into data[m:b]
   381  	// if data[a:m] only contains one element.
   382  	if m-a == 1 {
   383  		// Use binary search to find the lowest index i
   384  		// such that data[i] >= data[a] for m <= i < b.
   385  		// Exit the search loop with i == b in case no such index exists.
   386  		i := m
   387  		j := b
   388  		for i < j {
   389  			h := int(uint(i+j) >> 1)
   390  			if cmp(data[h], data[a]) < 0 {
   391  				i = h + 1
   392  			} else {
   393  				j = h
   394  			}
   395  		}
   396  		// Swap values until data[a] reaches the position before i.
   397  		for k := a; k < i-1; k++ {
   398  			data[k], data[k+1] = data[k+1], data[k]
   399  		}
   400  		return
   401  	}
   402  
   403  	// Avoid unnecessary recursions of symMerge
   404  	// by direct insertion of data[m] into data[a:m]
   405  	// if data[m:b] only contains one element.
   406  	if b-m == 1 {
   407  		// Use binary search to find the lowest index i
   408  		// such that data[i] > data[m] for a <= i < m.
   409  		// Exit the search loop with i == m in case no such index exists.
   410  		i := a
   411  		j := m
   412  		for i < j {
   413  			h := int(uint(i+j) >> 1)
   414  			if !(cmp(data[m], data[h]) < 0) {
   415  				i = h + 1
   416  			} else {
   417  				j = h
   418  			}
   419  		}
   420  		// Swap values until data[m] reaches the position i.
   421  		for k := m; k > i; k-- {
   422  			data[k], data[k-1] = data[k-1], data[k]
   423  		}
   424  		return
   425  	}
   426  
   427  	mid := int(uint(a+b) >> 1)
   428  	n := mid + m
   429  	var start, r int
   430  	if m > mid {
   431  		start = n - b
   432  		r = mid
   433  	} else {
   434  		start = a
   435  		r = m
   436  	}
   437  	p := n - 1
   438  
   439  	for start < r {
   440  		c := int(uint(start+r) >> 1)
   441  		if !(cmp(data[p-c], data[c]) < 0) {
   442  			start = c + 1
   443  		} else {
   444  			r = c
   445  		}
   446  	}
   447  
   448  	end := n - start
   449  	if start < m && m < end {
   450  		rotateCmpFunc(data, start, m, end, cmp)
   451  	}
   452  	if a < start && start < mid {
   453  		symMergeCmpFunc(data, a, start, mid, cmp)
   454  	}
   455  	if mid < end && end < b {
   456  		symMergeCmpFunc(data, mid, end, b, cmp)
   457  	}
   458  }
   459  
   460  // rotateCmpFunc rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data:
   461  // Data of the form 'x u v y' is changed to 'x v u y'.
   462  // rotate performs at most b-a many calls to data.Swap,
   463  // and it assumes non-degenerate arguments: a < m && m < b.
   464  func rotateCmpFunc[E any](data []E, a, m, b int, cmp func(a, b E) int) {
   465  	i := m - a
   466  	j := b - m
   467  
   468  	for i != j {
   469  		if i > j {
   470  			swapRangeCmpFunc(data, m-i, m, j, cmp)
   471  			i -= j
   472  		} else {
   473  			swapRangeCmpFunc(data, m-i, m+j-i, i, cmp)
   474  			j -= i
   475  		}
   476  	}
   477  	// i == j
   478  	swapRangeCmpFunc(data, m-i, m, i, cmp)
   479  }
   480
View as plain text