README
¶
go-natural
go-natural is a small library for performing "natural" string comparison in Go and on the beach.
Installation
go get github.com/halleknast/go-natural
or (preferrably)
glide get github.com/halleknast/go-natural
Function
The library contains a single function Natural with signature:
Natural(left, right string) int
Like any comparator, Natural evaluates to
- zero if
left = right, - a negative value if
left < right, and - a positive value if
left > right.
Natural comparison is similar to "ordinary" (i.e. character by character) string comparison.
The main difference is that numbers are compared in their entirety even if they span multiple charcters.
For example, "2" < "10" even though "1" < "2".
See the tests for a complete set of examples and the next section for a formal definition.
Natural comparison is useful whenever strings are sorted for readability.
It also allows correct comparison of e.g. semantic version strings.
For instance, "v1.2.3" < "v1.10.1" as one would expect.
Formal definition
The precise definition of natural order is the following:
Strings are equal if and only if they consist of the same bytes in the same order. If they are different, the order is determined using the following rule:
Write the compared strings left and right as their longest common prefix
concatenated by different (non-empty) suffixes:
left = <prefix><suffix1>
right = <prefix><suffix2>
Extract any prefix number from the suffixes into a separate group, such that none of the suffixes start with a number character:
left = <prefix><number1><suffix1>
right = <prefix><number2><suffix2>
If both number groups are non-empty, the string with the greater number is "greater". If the numbers are equal but have a different number of leading zeros, the number with the most leading zeros is "greater".
If either of the number groups are empty, the order is determined by single byte (character) comparison: Numbers characters are always larger than non-numbers. Other characters are simply compared by their byte values. The reason for this rule is that it allows a slightly faster implementation without sacrificing the ordering intent (the only order that matters is the one within the groups of upper-/lowercase letters and numbers - not between them).
Sorting
For sorting a string slice in natural order,
Naturally is provided as a convenience implementation of sort.Interface.
For example, the program
package main
import (
"sort"
"github.com/halleknast/go-natural"
)
func main() {
ss := []string{
"1.2.3",
"0.2.3",
"1.10.3",
"1.2.10",
}
sort.Sort(strcmp.Naturally(ss))
for _, s := range ss {
println(s)
}
}
prints
0.2.3
1.2.3
1.2.10
1.10.3
Limitations
Negative and fractional numbers are not supported since it isn't clear in which cases (and with what semantics) one would want that.
Documentation
¶
Overview ¶
Package strcmp contains a comparator function and a companion sort.Interface implementation for sorting strings according to "natural order".
Natural order is defined as follows:
Strings are equal if and only if they consist of the same bytes in the same order. If they are different, the order is determined using the following rule:
Write the compared strings left and right as the longest common prefix followed by (non-empty) suffixes:
left = <prefix><suffix1> right = <prefix><suffix2>
Extract any prefix number from the suffixes into a separate group, such that none of the suffixes start with a number character:
left = <prefix><number1><suffix1> right = <prefix><number2><suffix2>
If both number groups are non-empty, the string with the greater number is "larger". If the numbers are equal but have a different number of leading zeros, the number with the most leading zeros is "larger".
If either of the number groups are empty, the order is simply defined according to the usual definition (i.e. byte comparison).
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Source Files