1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73
74. 74
75. 75
76. 76
77. 77
78. 78
79. 79
80. 80
81. 81
82. 82
83. 83
84. 84
85. 85
86. 86
87. 87
88. 88
89. 89

// Copyright 2017 The Gitea Authors. All rights reserved.
// Use of this source code is governed by a MIT-style
// license that can be found in the LICENSE file.

package base

import (
	"math/big"
	"unicode/utf8"
)

// NaturalSortLess compares two strings so that they could be sorted in natural order
func NaturalSortLess(s1, s2 string) bool {
	var i1, i2 int
	for {
		rune1, j1, end1 := getNextRune(s1, i1)
		rune2, j2, end2 := getNextRune(s2, i2)
		if end1 || end2 {
			return end1 != end2 && end1
		}
		dec1 := isDecimal(rune1)
		dec2 := isDecimal(rune2)
		var less, equal bool
		if dec1 && dec2 {
			i1, i2, less, equal = compareByNumbers(s1, i1, s2, i2)
		} else if !dec1 && !dec2 {
			equal = rune1 == rune2
			less = rune1 < rune2
			i1 = j1
			i2 = j2
		} else {
			return rune1 < rune2
		}
		if !equal {
			return less
		}
	}
}

func getNextRune(str string, pos int) (rune, int, bool) {
	if pos < len(str) {
		r, w := utf8.DecodeRuneInString(str[pos:])
		// Fallback to ascii
		if r == utf8.RuneError {
			r = rune(str[pos])
			w = 1
		}
		return r, pos + w, false
	}
	return 0, pos, true
}

func isDecimal(r rune) bool {
	return '0' <= r && r <= '9'
}

func compareByNumbers(str1 string, pos1 int, str2 string, pos2 int) (i1, i2 int, less, equal bool) {
	var d1, d2 bool = true, true
	var dec1, dec2 string
	for d1 || d2 {
		if d1 {
			r, j, end := getNextRune(str1, pos1)
			if !end && isDecimal(r) {
				dec1 += string(r)
				pos1 = j
			} else {
				d1 = false
			}
		}
		if d2 {
			r, j, end := getNextRune(str2, pos2)
			if !end && isDecimal(r) {
				dec2 += string(r)
				pos2 = j
			} else {
				d2 = false
			}
		}
	}
	less, equal = compareBigNumbers(dec1, dec2)
	return pos1, pos2, less, equal
}

func compareBigNumbers(dec1, dec2 string) (less, equal bool) {
	d1, _ := big.NewInt(0).SetString(dec1, 10)
	d2, _ := big.NewInt(0).SetString(dec2, 10)
	cmp := d1.Cmp(d2)
	return cmp < 0, cmp == 0
}