summaryrefslogtreecommitdiffstats
path: root/modules/base/natural_sort.go
diff options
context:
space:
mode:
Diffstat (limited to 'modules/base/natural_sort.go')
-rw-r--r--modules/base/natural_sort.go90
1 files changed, 90 insertions, 0 deletions
diff --git a/modules/base/natural_sort.go b/modules/base/natural_sort.go
new file mode 100644
index 0000000..5b5febb
--- /dev/null
+++ b/modules/base/natural_sort.go
@@ -0,0 +1,90 @@
+// Copyright 2017 The Gitea Authors. All rights reserved.
+// SPDX-License-Identifier: MIT
+
+package base
+
+import (
+ "math/big"
+ "strings"
+ "unicode/utf8"
+)
+
+// NaturalSortLess compares two strings so that they could be sorted in natural order
+func NaturalSortLess(s1, s2 string) bool {
+ s1, s2 = strings.ToLower(s1), strings.ToLower(s2)
+ 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) {
+ d1, d2 := 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
+}