internal/number: add Decimal type
Decimal is used as an intermediate format of numbers before
formatting or determining the plural form.
This type supports converting a variety of number types
to decimal form. It also supports rounding modes that
are commonly provided for localization purposes.
Change-Id: I8aaa9fcf6a6ad21b885534a75757c03b579a1930
Reviewed-on: https://go-review.googlesource.com/45493
Run-TryBot: Marcel van Lohuizen <mpvl@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Nigel Tao <nigeltao@golang.org>
diff --git a/internal/number/decimal.go b/internal/number/decimal.go
new file mode 100644
index 0000000..4e42ec7
--- /dev/null
+++ b/internal/number/decimal.go
@@ -0,0 +1,430 @@
+// Copyright 2017 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+//go:generate stringer -type RoundingMode
+
+package number
+
+import (
+ "math"
+ "strconv"
+)
+
+// RoundingMode determines how a number is rounded to the desired precision.
+type RoundingMode byte
+
+const (
+ ToNearestEven RoundingMode = iota // towards the nearest integer, or towards an even number if equidistant.
+ ToNearestZero // towards the nearest integer, or towards zero if equidistant.
+ ToNearestAway // towards the nearest integer, or away from zero if equidistant.
+ ToPositiveInf // towards infinity
+ ToNegativeInf // towards negative infinity
+ ToZero // towards zero
+ AwayFromZero // away from zero
+ numModes
+)
+
+// A RoundingContext indicates how a number should be converted to digits.
+type RoundingContext struct {
+ Mode RoundingMode
+ Increment int32 // if > 0, round to Increment * 10^-Scale
+
+ Precision int32 // maximum number of significant digits.
+ Scale int32 // maximum number of decimals after the dot.
+}
+
+// A Decimal represents floating point number represented in digits of the base
+// in which a number is to be displayed. Digits represents a number [0, 1.0),
+// and the absolute value represented by Decimal is Digits * 10^Exp.
+// Leading and trailing zeros may be omitted and Exp may point outside a valid
+// position in Digits.
+//
+// Examples:
+// Number Decimal
+// 12345 Digits: [1, 2, 3, 4, 5], Exp: 5
+// 12.345 Digits: [1, 2, 3, 4, 5], Exp: 2
+// 12000 Digits: [1, 2], Exp: 5
+// 0.00123 Digits: [1, 2, 3], Exp: -2
+type Decimal struct {
+ Digits []byte // mantissa digits, big-endian
+ Exp int32 // exponent
+ Neg bool
+ Inf bool // Takes precedence over Digits and Exp.
+ NaN bool // Takes precedence over Inf.
+
+ buf [10]byte
+}
+
+// normalize retuns a new Decimal with leading and trailing zeros removed.
+func (d *Decimal) normalize() (n Decimal) {
+ n = *d
+ b := n.Digits
+ // Strip leading zeros. Resulting number of digits is significant digits.
+ for len(b) > 0 && b[0] == 0 {
+ b = b[1:]
+ n.Exp--
+ }
+ // Strip trailing zeros
+ for len(b) > 0 && b[len(b)-1] == 0 {
+ b = b[:len(b)-1]
+ }
+ if len(b) == 0 {
+ n.Exp = 0
+ }
+ n.Digits = b
+ return n
+}
+
+func (d *Decimal) clear() {
+ b := d.Digits
+ if b == nil {
+ b = d.buf[:0]
+ }
+ *d = Decimal{}
+ d.Digits = b[:0]
+}
+
+func (x *Decimal) String() string {
+ if x.NaN {
+ return "NaN"
+ }
+ var buf []byte
+ if x.Neg {
+ buf = append(buf, '-')
+ }
+ if x.Inf {
+ buf = append(buf, "Inf"...)
+ return string(buf)
+ }
+ if len(x.Digits) == 0 {
+ return "0"
+ }
+ switch {
+ case x.Exp <= 0:
+ // 0.00ddd
+ buf = append(buf, "0."...)
+ buf = appendZeros(buf, -int(x.Exp))
+ buf = appendDigits(buf, x.Digits)
+
+ case /* 0 < */ int(x.Exp) < len(x.Digits):
+ // dd.ddd
+ buf = appendDigits(buf, x.Digits[:x.Exp])
+ buf = append(buf, '.')
+ buf = appendDigits(buf, x.Digits[x.Exp:])
+
+ default: // len(x.Digits) <= x.Exp
+ // ddd00
+ buf = appendDigits(buf, x.Digits)
+ buf = appendZeros(buf, int(x.Exp)-len(x.Digits))
+ }
+ return string(buf)
+}
+
+func appendDigits(buf []byte, digits []byte) []byte {
+ for _, c := range digits {
+ buf = append(buf, c+'0')
+ }
+ return buf
+}
+
+// appendZeros appends n 0 digits to buf and returns buf.
+func appendZeros(buf []byte, n int) []byte {
+ for ; n > 0; n-- {
+ buf = append(buf, '0')
+ }
+ return buf
+}
+
+func (d *Decimal) round(mode RoundingMode, n int) {
+ if n >= len(d.Digits) {
+ return
+ }
+ // Make rounding decision: The result mantissa is truncated ("rounded down")
+ // by default. Decide if we need to increment, or "round up", the (unsigned)
+ // mantissa.
+ inc := false
+ switch mode {
+ case ToNegativeInf:
+ inc = d.Neg
+ case ToPositiveInf:
+ inc = !d.Neg
+ case ToZero:
+ // nothing to do
+ case AwayFromZero:
+ inc = true
+ case ToNearestEven:
+ inc = d.Digits[n] > 5 || d.Digits[n] == 5 &&
+ (len(d.Digits) > n+1 || n == 0 || d.Digits[n-1]&1 != 0)
+ case ToNearestAway:
+ inc = d.Digits[n] >= 5
+ case ToNearestZero:
+ inc = d.Digits[n] > 5 || d.Digits[n] == 5 && len(d.Digits) > n+1
+ default:
+ panic("unreachable")
+ }
+ if inc {
+ d.roundUp(n)
+ } else {
+ d.roundDown(n)
+ }
+}
+
+// roundFloat rounds a floating point number.
+func (r RoundingMode) roundFloat(x float64) float64 {
+ // Make rounding decision: The result mantissa is truncated ("rounded down")
+ // by default. Decide if we need to increment, or "round up", the (unsigned)
+ // mantissa.
+ abs := x
+ if x < 0 {
+ abs = -x
+ }
+ i, f := math.Modf(abs)
+ if f == 0.0 {
+ return x
+ }
+ inc := false
+ switch r {
+ case ToNegativeInf:
+ inc = x < 0
+ case ToPositiveInf:
+ inc = x >= 0
+ case ToZero:
+ // nothing to do
+ case AwayFromZero:
+ inc = true
+ case ToNearestEven:
+ // TODO: check overflow
+ inc = f > 0.5 || f == 0.5 && int64(i)&1 != 0
+ case ToNearestAway:
+ inc = f >= 0.5
+ case ToNearestZero:
+ inc = f > 0.5
+ default:
+ panic("unreachable")
+ }
+ if inc {
+ i += 1
+ }
+ if abs != x {
+ i = -i
+ }
+ return i
+}
+
+func (x *Decimal) roundUp(n int) {
+ if n < 0 || n >= len(x.Digits) {
+ return // nothing to do
+ }
+ // find first digit < 9
+ for n > 0 && x.Digits[n-1] >= 9 {
+ n--
+ }
+
+ if n == 0 {
+ // all digits are 9s => round up to 1 and update exponent
+ x.Digits[0] = 1 // ok since len(x.Digits) > n
+ x.Digits = x.Digits[:1]
+ x.Exp++
+ return
+ }
+ x.Digits[n-1]++
+ x.Digits = x.Digits[:n]
+ // x already trimmed
+}
+
+func (x *Decimal) roundDown(n int) {
+ if n < 0 || n >= len(x.Digits) {
+ return // nothing to do
+ }
+ x.Digits = x.Digits[:n]
+ trim(x)
+}
+
+// trim cuts off any trailing zeros from x's mantissa;
+// they are meaningless for the value of x.
+func trim(x *Decimal) {
+ i := len(x.Digits)
+ for i > 0 && x.Digits[i-1] == 0 {
+ i--
+ }
+ x.Digits = x.Digits[:i]
+ if i == 0 {
+ x.Exp = 0
+ }
+}
+
+// A Converter converts a number into decimals according to the given rounding
+// criteria.
+type Converter interface {
+ Convert(d *Decimal, r *RoundingContext)
+}
+
+const (
+ signed = true
+ unsigned = false
+)
+
+// Convert converts the given number to the decimal representation using the
+// supplied RoundingContext.
+func (d *Decimal) Convert(r *RoundingContext, number interface{}) {
+ switch f := number.(type) {
+ case Converter:
+ d.clear()
+ f.Convert(d, r)
+ case float32:
+ d.convertFloat64(r, float64(f), 32)
+ case float64:
+ d.convertFloat64(r, f, 64)
+ case int:
+ d.convertInt(r, signed, uint64(f))
+ case int8:
+ d.convertInt(r, signed, uint64(f))
+ case int16:
+ d.convertInt(r, signed, uint64(f))
+ case int32:
+ d.convertInt(r, signed, uint64(f))
+ case int64:
+ d.convertInt(r, signed, uint64(f))
+ case uint:
+ d.convertInt(r, unsigned, uint64(f))
+ case uint8:
+ d.convertInt(r, unsigned, uint64(f))
+ case uint16:
+ d.convertInt(r, unsigned, uint64(f))
+ case uint32:
+ d.convertInt(r, unsigned, uint64(f))
+ case uint64:
+ d.convertInt(r, unsigned, f)
+
+ // TODO:
+ // case string: if produced by strconv, allows for easy arbitrary pos.
+ // case reflect.Value:
+ // case big.Float
+ // case big.Int
+ // case big.Rat?
+ // catch underlyings using reflect or will this already be done by the
+ // message package?
+ }
+}
+
+func (d *Decimal) convertInt(r *RoundingContext, signed bool, x uint64) {
+ if r.Increment > 0 {
+ // TODO: if uint64 is too large, fall back to float64
+ if signed {
+ d.convertFloat64(r, float64(int64(x)), 64)
+ } else {
+ d.convertFloat64(r, float64(x), 64)
+ }
+ return
+ }
+ d.clear()
+ if signed && int64(x) < 0 {
+ x = uint64(-int64(x))
+ d.Neg = true
+ }
+ d.fillIntDigits(x)
+ d.Exp = int32(len(d.Digits))
+}
+
+func (d *Decimal) convertFloat64(r *RoundingContext, x float64, size int) {
+ d.clear()
+ if math.IsNaN(x) {
+ d.NaN = true
+ return
+ }
+ abs := x
+ if x < 0 {
+ d.Neg = true
+ abs = -x
+ }
+ if math.IsInf(abs, 1) {
+ d.Inf = true
+ return
+ }
+ // Simple case: decimal notation
+ if r.Scale > 0 || r.Increment > 0 && r.Scale == 0 {
+ if int(r.Scale) > len(scales) {
+ x *= math.Pow(10, float64(r.Scale))
+ } else {
+ x *= scales[r.Scale]
+ }
+ if r.Increment > 0 {
+ inc := float64(r.Increment)
+ x /= float64(inc)
+ x = r.Mode.roundFloat(x)
+ x *= inc
+ } else {
+ x = r.Mode.roundFloat(x)
+ }
+ d.fillIntDigits(uint64(math.Abs(x)))
+ d.Exp = int32(len(d.Digits)) - r.Scale
+ return
+ }
+
+ // Nasty case (for non-decimal notation).
+ // Asides from being inefficient, this result is also wrong as it will
+ // apply ToNearestEven rounding regardless of the user setting.
+ // TODO: expose functionality in strconv so we can avoid this hack.
+ // Something like this would work:
+ // AppendDigits(dst []byte, x float64, base, size, prec int) (digits []byte, exp, accuracy int)
+
+ prec := int(r.Precision)
+ if prec > 0 {
+ prec--
+ }
+ b := strconv.AppendFloat(d.Digits, abs, 'e', prec, size)
+ i := 0
+ k := 0
+ // No need to check i < len(b) as we always have an 'e'.
+ for {
+ if c := b[i]; '0' <= c && c <= '9' {
+ b[k] = c - '0'
+ k++
+ } else if c != '.' {
+ break
+ }
+ i++
+ }
+ d.Digits = b[:k]
+ i += len("e")
+ pSign := i
+ exp := 0
+ for i++; i < len(b); i++ {
+ exp *= 10
+ exp += int(b[i] - '0')
+ }
+ if b[pSign] == '-' {
+ exp = -exp
+ }
+ d.Exp = int32(exp) + 1
+}
+
+func (d *Decimal) fillIntDigits(x uint64) {
+ const maxUintDigits = 10
+ if cap(d.Digits) < maxUintDigits {
+ d.Digits = d.buf[:]
+ } else {
+ d.Digits = d.buf[:maxUintDigits]
+ }
+ i := 0
+ for ; x > 0; x /= 10 {
+ d.Digits[i] = byte(x % 10)
+ i++
+ }
+ d.Digits = d.Digits[:i]
+ for p := 0; p < i; p++ {
+ i--
+ d.Digits[p], d.Digits[i] = d.Digits[i], d.Digits[p]
+ }
+}
+
+var scales [70]float64
+
+func init() {
+ x := 1.0
+ for i := range scales {
+ scales[i] = x
+ x *= 10
+ }
+}
diff --git a/internal/number/decimal_test.go b/internal/number/decimal_test.go
new file mode 100644
index 0000000..b99fedc
--- /dev/null
+++ b/internal/number/decimal_test.go
@@ -0,0 +1,294 @@
+// Copyright 2017 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package number
+
+import (
+ "fmt"
+ "math"
+ "strconv"
+ "strings"
+ "testing"
+)
+
+func mkfloat(num string) float64 {
+ u, _ := strconv.ParseUint(num, 10, 32)
+ return float64(u)
+}
+
+// mkdec creates a decimal from a string. All ASCII digits are converted to
+// digits in the decimal. The dot is used to indicate the scale by which the
+// digits are shifted. Numbers may have an additional exponent or be the special
+// value NaN, Inf, or -Inf.
+func mkdec(num string) (d Decimal) {
+ if num[0] == '-' {
+ d.Neg = true
+ num = num[1:]
+ }
+ switch num {
+ case "NaN":
+ d.NaN = true
+ return
+ case "Inf":
+ d.Inf = true
+ return
+ }
+ if p := strings.IndexAny(num, "eE"); p != -1 {
+ i64, err := strconv.ParseInt(num[p+1:], 10, 32)
+ if err != nil {
+ panic(err)
+ }
+ d.Exp = int32(i64)
+ num = num[:p]
+ }
+ if p := strings.IndexByte(num, '.'); p != -1 {
+ d.Exp += int32(p)
+ num = num[:p] + num[p+1:]
+ } else {
+ d.Exp += int32(len(num))
+ }
+ d.Digits = []byte(num)
+ for i := range d.Digits {
+ d.Digits[i] -= '0'
+ }
+ return d.normalize()
+}
+
+func byteNum(s string) []byte {
+ b := make([]byte, len(s))
+ for i := 0; i < len(s); i++ {
+ if c := s[i]; '0' <= c && c <= '9' {
+ b[i] = s[i] - '0'
+ } else {
+ b[i] = s[i] - 'a' + 10
+ }
+ }
+ return b
+}
+
+func strNum(s string) string {
+ return string(byteNum(s))
+}
+
+func TestDecimalString(t *testing.T) {
+ for _, test := range []struct {
+ x Decimal
+ want string
+ }{
+ {want: "0"},
+ {Decimal{Digits: nil, Exp: 1000}, "0"}, // exponent of 1000 is ignored
+ {Decimal{Digits: byteNum("12345"), Exp: 0}, "0.12345"},
+ {Decimal{Digits: byteNum("12345"), Exp: -3}, "0.00012345"},
+ {Decimal{Digits: byteNum("12345"), Exp: +3}, "123.45"},
+ {Decimal{Digits: byteNum("12345"), Exp: +10}, "1234500000"},
+ } {
+ if got := test.x.String(); got != test.want {
+ t.Errorf("%v == %q; want %q", test.x, got, test.want)
+ }
+ }
+}
+
+func TestRounding(t *testing.T) {
+ testCases := []struct {
+ x string
+ n int
+ // modes is the result for modes. Signs are left out of the result.
+ // The results are stored in the following order:
+ // zero, negInf
+ // nearZero, nearEven, nearAway
+ // away, posInf
+ modes [numModes]string
+ }{
+ {"0", 1, [numModes]string{
+ "0", "0",
+ "0", "0", "0",
+ "0", "0"}},
+ {"1", 1, [numModes]string{
+ "1", "1",
+ "1", "1", "1",
+ "1", "1"}},
+ {"5", 1, [numModes]string{
+ "5", "5",
+ "5", "5", "5",
+ "5", "5"}},
+ {"15", 1, [numModes]string{
+ "10", "10",
+ "10", "20", "20",
+ "20", "20"}},
+ {"45", 1, [numModes]string{
+ "40", "40",
+ "40", "40", "50",
+ "50", "50"}},
+ {"95", 1, [numModes]string{
+ "90", "90",
+ "90", "100", "100",
+ "100", "100"}},
+
+ {"12344999", 4, [numModes]string{
+ "12340000", "12340000",
+ "12340000", "12340000", "12340000",
+ "12350000", "12350000"}},
+ {"12345000", 4, [numModes]string{
+ "12340000", "12340000",
+ "12340000", "12340000", "12350000",
+ "12350000", "12350000"}},
+ {"12345001", 4, [numModes]string{
+ "12340000", "12340000",
+ "12350000", "12350000", "12350000",
+ "12350000", "12350000"}},
+ {"12345100", 4, [numModes]string{
+ "12340000", "12340000",
+ "12350000", "12350000", "12350000",
+ "12350000", "12350000"}},
+ {"23454999", 4, [numModes]string{
+ "23450000", "23450000",
+ "23450000", "23450000", "23450000",
+ "23460000", "23460000"}},
+ {"23455000", 4, [numModes]string{
+ "23450000", "23450000",
+ "23450000", "23460000", "23460000",
+ "23460000", "23460000"}},
+ {"23455001", 4, [numModes]string{
+ "23450000", "23450000",
+ "23460000", "23460000", "23460000",
+ "23460000", "23460000"}},
+ {"23455100", 4, [numModes]string{
+ "23450000", "23450000",
+ "23460000", "23460000", "23460000",
+ "23460000", "23460000"}},
+
+ {"99994999", 4, [numModes]string{
+ "99990000", "99990000",
+ "99990000", "99990000", "99990000",
+ "100000000", "100000000"}},
+ {"99995000", 4, [numModes]string{
+ "99990000", "99990000",
+ "99990000", "100000000", "100000000",
+ "100000000", "100000000"}},
+ {"99999999", 4, [numModes]string{
+ "99990000", "99990000",
+ "100000000", "100000000", "100000000",
+ "100000000", "100000000"}},
+
+ {"12994999", 4, [numModes]string{
+ "12990000", "12990000",
+ "12990000", "12990000", "12990000",
+ "13000000", "13000000"}},
+ {"12995000", 4, [numModes]string{
+ "12990000", "12990000",
+ "12990000", "13000000", "13000000",
+ "13000000", "13000000"}},
+ {"12999999", 4, [numModes]string{
+ "12990000", "12990000",
+ "13000000", "13000000", "13000000",
+ "13000000", "13000000"}},
+ }
+ modes := []RoundingMode{
+ ToZero, ToNegativeInf,
+ ToNearestZero, ToNearestEven, ToNearestAway,
+ AwayFromZero, ToPositiveInf,
+ }
+ for _, tc := range testCases {
+ // Create negative counterpart tests: the sign is reversed and
+ // ToPositiveInf and ToNegativeInf swapped.
+ negModes := tc.modes
+ negModes[1], negModes[6] = negModes[6], negModes[1]
+ for i, res := range negModes {
+ if res != "0" {
+ negModes[i] = "-" + res
+ }
+ }
+
+ for i, m := range modes {
+ t.Run(fmt.Sprintf("v:%s/n:%d/%s", tc.x, tc.n, m), func(t *testing.T) {
+ d := mkdec(tc.x)
+ d.round(m, tc.n)
+ if got := d.String(); got != tc.modes[i] {
+ t.Errorf("pos decimal: got %q; want %q", d.String(), tc.modes[i])
+ }
+
+ mult := math.Pow(10, float64(len(tc.x)-tc.n))
+ f := mkfloat(tc.x)
+ f = m.roundFloat(f/mult) * mult
+ if got := fmt.Sprintf("%.0f", f); got != tc.modes[i] {
+ t.Errorf("pos float: got %q; want %q", got, tc.modes[i])
+ }
+
+ // Test the negative case. This is the same as the positive
+ // case, but with ToPositiveInf and ToNegativeInf swapped.
+ d = mkdec(tc.x)
+ d.Neg = true
+ d.round(m, tc.n)
+ if got, want := d.String(), negModes[i]; got != want {
+ t.Errorf("neg decimal: got %q; want %q", d.String(), want)
+ }
+
+ if f = mkfloat(tc.x); f != 0 {
+ f = -f // avoid creating -0.0
+ }
+ f = m.roundFloat(f/mult) * mult
+ if got := fmt.Sprintf("%.0f", f); got != negModes[i] {
+ t.Errorf("neg float: got %q; want %q", got, negModes[i])
+ }
+ })
+ }
+ }
+}
+
+func TestConvert(t *testing.T) {
+ scale2 := &RoundingContext{Scale: 2}
+ scale2away := &RoundingContext{Scale: 2, Mode: AwayFromZero}
+ inc0_05 := &RoundingContext{Increment: 5, Scale: 2}
+ inc50 := &RoundingContext{Increment: 50}
+ prec3 := &RoundingContext{Precision: 3}
+ testCases := []struct {
+ x interface{}
+ rc *RoundingContext
+ out string
+ }{
+ {int8(-34), scale2, "-34"},
+ {int16(-234), scale2, "-234"},
+ {int32(-234), scale2, "-234"},
+ {int64(-234), scale2, "-234"},
+ {int(-234), scale2, "-234"},
+ {uint8(234), scale2, "234"},
+ {uint16(234), scale2, "234"},
+ {uint32(234), scale2, "234"},
+ {uint64(234), scale2, "234"},
+ {uint(234), scale2, "234"},
+ {0.234, scale2, "0.23"},
+ {0.234, scale2away, "0.24"},
+ {0.1234, prec3, "0.123"},
+ {1234.0, prec3, "1230"},
+ {1.2345e10, prec3, "12300000000"},
+
+ {0.03, inc0_05, "0.05"},
+ {0.025, inc0_05, "0"},
+ {0.075, inc0_05, "0.10"},
+ {325, inc50, "300"},
+ {375, inc50, "400"},
+
+ {converter(3), scale2, "100"},
+
+ {math.Inf(1), inc50, "Inf"},
+ {math.Inf(-1), inc50, "-Inf"},
+ {math.NaN(), inc50, "NaN"},
+ }
+ for _, tc := range testCases {
+ var d Decimal
+ t.Run(fmt.Sprintf("%T:%v-%v", tc.x, tc.x, tc.rc), func(t *testing.T) {
+ d.Convert(tc.rc, tc.x)
+ if got := d.String(); got != tc.out {
+ t.Errorf("got %q; want %q", got, tc.out)
+ }
+ })
+ }
+}
+
+type converter int
+
+func (c converter) Convert(d *Decimal, r *RoundingContext) {
+ d.Digits = append(d.Digits, 1, 0, 0)
+ d.Exp = 3
+}
diff --git a/internal/number/roundingmode_string.go b/internal/number/roundingmode_string.go
new file mode 100644
index 0000000..f264ea5
--- /dev/null
+++ b/internal/number/roundingmode_string.go
@@ -0,0 +1,16 @@
+// Code generated by "stringer -type RoundingMode"; DO NOT EDIT.
+
+package number
+
+import "fmt"
+
+const _RoundingMode_name = "ToNearestEvenToNearestZeroToNearestAwayToPositiveInfToNegativeInfToZeroAwayFromZeronumModes"
+
+var _RoundingMode_index = [...]uint8{0, 13, 26, 39, 52, 65, 71, 83, 91}
+
+func (i RoundingMode) String() string {
+ if i >= RoundingMode(len(_RoundingMode_index)-1) {
+ return fmt.Sprintf("RoundingMode(%d)", i)
+ }
+ return _RoundingMode_name[_RoundingMode_index[i]:_RoundingMode_index[i+1]]
+}
