--- /dev/null
+// Copyright 2014 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 colltab
+
+import (
+ "unicode"
+ "unicode/utf8"
+)
+
+// NewNumericWeighter wraps w to replace individual digits to sort based on their
+// numeric value.
+//
+// Weighter w must have a free primary weight after the primary weight for 9.
+// If this is not the case, numeric value will sort at the same primary level
+// as the first primary sorting after 9.
+func NewNumericWeighter(w Weighter) Weighter {
+ getElem := func(s string) Elem {
+ elems, _ := w.AppendNextString(nil, s)
+ return elems[0]
+ }
+ nine := getElem("9")
+
+ // Numbers should order before zero, but the DUCET has no room for this.
+ // TODO: move before zero once we use fractional collation elements.
+ ns, _ := MakeElem(nine.Primary()+1, nine.Secondary(), int(nine.Tertiary()), 0)
+
+ return &numericWeighter{
+ Weighter: w,
+
+ // We assume that w sorts digits of different kinds in order of numeric
+ // value and that the tertiary weight order is preserved.
+ //
+ // TODO: evaluate whether it is worth basing the ranges on the Elem
+ // encoding itself once the move to fractional weights is complete.
+ zero: getElem("0"),
+ zeroSpecialLo: getElem("０"), // U+FF10 FULLWIDTH DIGIT ZERO
+ zeroSpecialHi: getElem("₀"), // U+2080 SUBSCRIPT ZERO
+ nine: nine,
+ nineSpecialHi: getElem("₉"), // U+2089 SUBSCRIPT NINE
+ numberStart: ns,
+ }
+}
+
+// A numericWeighter translates a stream of digits into a stream of weights
+// representing the numeric value.
+type numericWeighter struct {
+ Weighter
+
+ // The Elems below all demarcate boundaries of specific ranges. With the
+ // current element encoding digits are in two ranges: normal (default
+ // tertiary value) and special. For most languages, digits have collation
+ // elements in the normal range.
+ //
+ // Note: the range tests are very specific for the element encoding used by
+ // this implementation. The tests in collate_test.go are designed to fail
+ // if this code is not updated when an encoding has changed.
+
+ zero Elem // normal digit zero
+ zeroSpecialLo Elem // special digit zero, low tertiary value
+ zeroSpecialHi Elem // special digit zero, high tertiary value
+ nine Elem // normal digit nine
+ nineSpecialHi Elem // special digit nine
+ numberStart Elem
+}
+
+// AppendNext calls the namesake of the underlying weigher, but replaces single
+// digits with weights representing their value.
+func (nw *numericWeighter) AppendNext(buf []Elem, s []byte) (ce []Elem, n int) {
+ ce, n = nw.Weighter.AppendNext(buf, s)
+ nc := numberConverter{
+ elems: buf,
+ w: nw,
+ b: s,
+ }
+ isZero, ok := nc.checkNextDigit(ce)
+ if !ok {
+ return ce, n
+ }
+ // ce might have been grown already, so take it instead of buf.
+ nc.init(ce, len(buf), isZero)
+ for n < len(s) {
+ ce, sz := nw.Weighter.AppendNext(nc.elems, s[n:])
+ nc.b = s
+ n += sz
+ if !nc.update(ce) {
+ break
+ }
+ }
+ return nc.result(), n
+}
+
+// AppendNextString calls the namesake of the underlying weigher, but replaces
+// single digits with weights representing their value.
+func (nw *numericWeighter) AppendNextString(buf []Elem, s string) (ce []Elem, n int) {
+ ce, n = nw.Weighter.AppendNextString(buf, s)
+ nc := numberConverter{
+ elems: buf,
+ w: nw,
+ s: s,
+ }
+ isZero, ok := nc.checkNextDigit(ce)
+ if !ok {
+ return ce, n
+ }
+ nc.init(ce, len(buf), isZero)
+ for n < len(s) {
+ ce, sz := nw.Weighter.AppendNextString(nc.elems, s[n:])
+ nc.s = s
+ n += sz
+ if !nc.update(ce) {
+ break
+ }
+ }
+ return nc.result(), n
+}
+
+type numberConverter struct {
+ w *numericWeighter
+
+ elems []Elem
+ nDigits int
+ lenIndex int
+
+ s string // set if the input was of type string
+ b []byte // set if the input was of type []byte
+}
+
+// init completes initialization of a numberConverter and prepares it for adding
+// more digits. elems is assumed to have a digit starting at oldLen.
+func (nc *numberConverter) init(elems []Elem, oldLen int, isZero bool) {
+ // Insert a marker indicating the start of a number and a placeholder
+ // for the number of digits.
+ if isZero {
+ elems = append(elems[:oldLen], nc.w.numberStart, 0)
+ } else {
+ elems = append(elems, 0, 0)
+ copy(elems[oldLen+2:], elems[oldLen:])
+ elems[oldLen] = nc.w.numberStart
+ elems[oldLen+1] = 0
+
+ nc.nDigits = 1
+ }
+ nc.elems = elems
+ nc.lenIndex = oldLen + 1
+}
+
+// checkNextDigit reports whether bufNew adds a single digit relative to the old
+// buffer. If it does, it also reports whether this digit is zero.
+func (nc *numberConverter) checkNextDigit(bufNew []Elem) (isZero, ok bool) {
+ if len(nc.elems) >= len(bufNew) {
+ return false, false
+ }
+ e := bufNew[len(nc.elems)]
+ if e < nc.w.zeroSpecialLo || nc.w.nine < e {
+ // Not a number.
+ return false, false
+ }
+ if e < nc.w.zero {
+ if e > nc.w.nineSpecialHi {
+ // Not a number.
+ return false, false
+ }
+ if !nc.isDigit() {
+ return false, false
+ }
+ isZero = e <= nc.w.zeroSpecialHi
+ } else {
+ // This is the common case if we encounter a digit.
+ isZero = e == nc.w.zero
+ }
+ // Test the remaining added collation elements have a zero primary value.
+ if n := len(bufNew) - len(nc.elems); n > 1 {
+ for i := len(nc.elems) + 1; i < len(bufNew); i++ {
+ if bufNew[i].Primary() != 0 {
+ return false, false
+ }
+ }
+ // In some rare cases, collation elements will encode runes in
+ // unicode.No as a digit. For example Ethiopic digits (U+1369 - U+1371)
+ // are not in Nd. Also some digits that clearly belong in unicode.No,
+ // like U+0C78 TELUGU FRACTION DIGIT ZERO FOR ODD POWERS OF FOUR, have
+ // collation elements indistinguishable from normal digits.
+ // Unfortunately, this means we need to make this check for nearly all
+ // non-Latin digits.
+ //
+ // TODO: check the performance impact and find something better if it is
+ // an issue.
+ if !nc.isDigit() {
+ return false, false
+ }
+ }
+ return isZero, true
+}
+
+func (nc *numberConverter) isDigit() bool {
+ if nc.b != nil {
+ r, _ := utf8.DecodeRune(nc.b)
+ return unicode.In(r, unicode.Nd)
+ }
+ r, _ := utf8.DecodeRuneInString(nc.s)
+ return unicode.In(r, unicode.Nd)
+}
+
+// We currently support a maximum of about 2M digits (the number of primary
+// values). Such numbers will compare correctly against small numbers, but their
+// comparison against other large numbers is undefined.
+//
+// TODO: define a proper fallback, such as comparing large numbers textually or
+// actually allowing numbers of unlimited length.
+//
+// TODO: cap this to a lower number (like 100) and maybe allow a larger number
+// in an option?
+const maxDigits = 1<<maxPrimaryBits - 1
+
+func (nc *numberConverter) update(elems []Elem) bool {
+ isZero, ok := nc.checkNextDigit(elems)
+ if nc.nDigits == 0 && isZero {
+ return true
+ }
+ nc.elems = elems
+ if !ok {
+ return false
+ }
+ nc.nDigits++
+ return nc.nDigits < maxDigits
+}
+
+// result fills in the length element for the digit sequence and returns the
+// completed collation elements.
+func (nc *numberConverter) result() []Elem {
+ e, _ := MakeElem(nc.nDigits, defaultSecondary, defaultTertiary, 0)
+ nc.elems[nc.lenIndex] = e
+ return nc.elems
+}
Code Review / barometer.git / blobdiff