compare_natural.go

     1  // Copyright 2026 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  
     5  package sgutil
     6  
     7  import (
     8  	"strconv"
     9  	"strings"
    10  )
    11  
    12  // isDigit returns true if the byte is an ASCII digit.
    13  func isDigit(b byte) bool {
    14  	return b >= '0' && b <= '9'
    15  }
    16  
    17  // CompareNatural performs a "natural sort" comparison of two strings.
    18  // It compares non-digit sections lexicographically and digit sections
    19  // numerically.  In the case of string-unequal "equal" strings like
    20  // "a01b" and "a1b", strings.Compare breaks the tie.
    21  //
    22  // It returns:
    23  //
    24  //	-1 if s1 < s2
    25  //	 0 if s1 == s2
    26  //	+1 if s1 > s2
    27  func CompareNatural(s1, s2 string) int {
    28  	i, j := 0, 0
    29  	len1, len2 := len(s1), len(s2)
    30  
    31  	for i < len1 && j < len2 {
    32  		// Find a non-digit segment or a number segment in both strings.
    33  		if isDigit(s1[i]) && isDigit(s2[j]) {
    34  			// Number segment comparison.
    35  			numStart1 := i
    36  			for i < len1 && isDigit(s1[i]) {
    37  				i++
    38  			}
    39  			num1, _ := strconv.Atoi(s1[numStart1:i])
    40  
    41  			numStart2 := j
    42  			for j < len2 && isDigit(s2[j]) {
    43  				j++
    44  			}
    45  			num2, _ := strconv.Atoi(s2[numStart2:j])
    46  
    47  			if num1 < num2 {
    48  				return -1
    49  			}
    50  			if num1 > num2 {
    51  				return 1
    52  			}
    53  			// "1" < "01".  Don't expect it in simdgen, but just in case.
    54  			if ln1, ln2 := i-numStart1, j-numStart2; ln1 != ln2 {
    55  				return ln1 - ln2
    56  			}
    57  			// If numbers are equal, continue to the next segment.
    58  		} else {
    59  			// Non-digit comparison.
    60  			if s1[i] < s2[j] {
    61  				return -1
    62  			}
    63  			if s1[i] > s2[j] {
    64  				return 1
    65  			}
    66  			i++
    67  			j++
    68  		}
    69  	}
    70  
    71  	// deal with a01b vs a1b; there needs to be an order.
    72  	return strings.Compare(s1, s2)
    73  }
    74
View as plain text