numeric.go

Documentation: golang.org/x/text/internal/colltab

     1  // Copyright 2014 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package colltab
     6  
     7  import (
     8  	"unicode"
     9  	"unicode/utf8"
    10  )
    11  
    12  // NewNumericWeighter wraps w to replace individual digits to sort based on their
    13  // numeric value.
    14  //
    15  // Weighter w must have a free primary weight after the primary weight for 9.
    16  // If this is not the case, numeric value will sort at the same primary level
    17  // as the first primary sorting after 9.
    18  func NewNumericWeighter(w Weighter) Weighter {
    19  	getElem := func(s string) Elem {
    20  		elems, _ := w.AppendNextString(nil, s)
    21  		return elems[0]
    22  	}
    23  	nine := getElem("9")
    24  
    25  	// Numbers should order before zero, but the DUCET has no room for this.
    26  	// TODO: move before zero once we use fractional collation elements.
    27  	ns, _ := MakeElem(nine.Primary()+1, nine.Secondary(), int(nine.Tertiary()), 0)
    28  
    29  	return &numericWeighter{
    30  		Weighter: w,
    31  
    32  		// We assume that w sorts digits of different kinds in order of numeric
    33  		// value and that the tertiary weight order is preserved.
    34  		//
    35  		// TODO: evaluate whether it is worth basing the ranges on the Elem
    36  		// encoding itself once the move to fractional weights is complete.
    37  		zero:          getElem("0"),
    38  		zeroSpecialLo: getElem("０"), // U+FF10 FULLWIDTH DIGIT ZERO
    39  		zeroSpecialHi: getElem("₀"), // U+2080 SUBSCRIPT ZERO
    40  		nine:          nine,
    41  		nineSpecialHi: getElem("₉"), // U+2089 SUBSCRIPT NINE
    42  		numberStart:   ns,
    43  	}
    44  }
    45  
    46  // A numericWeighter translates a stream of digits into a stream of weights
    47  // representing the numeric value.
    48  type numericWeighter struct {
    49  	Weighter
    50  
    51  	// The Elems below all demarcate boundaries of specific ranges. With the
    52  	// current element encoding digits are in two ranges: normal (default
    53  	// tertiary value) and special. For most languages, digits have collation
    54  	// elements in the normal range.
    55  	//
    56  	// Note: the range tests are very specific for the element encoding used by
    57  	// this implementation. The tests in collate_test.go are designed to fail
    58  	// if this code is not updated when an encoding has changed.
    59  
    60  	zero          Elem // normal digit zero
    61  	zeroSpecialLo Elem // special digit zero, low tertiary value
    62  	zeroSpecialHi Elem // special digit zero, high tertiary value
    63  	nine          Elem // normal digit nine
    64  	nineSpecialHi Elem // special digit nine
    65  	numberStart   Elem
    66  }
    67  
    68  // AppendNext calls the namesake of the underlying weigher, but replaces single
    69  // digits with weights representing their value.
    70  func (nw *numericWeighter) AppendNext(buf []Elem, s []byte) (ce []Elem, n int) {
    71  	ce, n = nw.Weighter.AppendNext(buf, s)
    72  	nc := numberConverter{
    73  		elems: buf,
    74  		w:     nw,
    75  		b:     s,
    76  	}
    77  	isZero, ok := nc.checkNextDigit(ce)
    78  	if !ok {
    79  		return ce, n
    80  	}
    81  	// ce might have been grown already, so take it instead of buf.
    82  	nc.init(ce, len(buf), isZero)
    83  	for n < len(s) {
    84  		ce, sz := nw.Weighter.AppendNext(nc.elems, s[n:])
    85  		nc.b = s
    86  		n += sz
    87  		if !nc.update(ce) {
    88  			break
    89  		}
    90  	}
    91  	return nc.result(), n
    92  }
    93  
    94  // AppendNextString calls the namesake of the underlying weigher, but replaces
    95  // single digits with weights representing their value.
    96  func (nw *numericWeighter) AppendNextString(buf []Elem, s string) (ce []Elem, n int) {
    97  	ce, n = nw.Weighter.AppendNextString(buf, s)
    98  	nc := numberConverter{
    99  		elems: buf,
   100  		w:     nw,
   101  		s:     s,
   102  	}
   103  	isZero, ok := nc.checkNextDigit(ce)
   104  	if !ok {
   105  		return ce, n
   106  	}
   107  	nc.init(ce, len(buf), isZero)
   108  	for n < len(s) {
   109  		ce, sz := nw.Weighter.AppendNextString(nc.elems, s[n:])
   110  		nc.s = s
   111  		n += sz
   112  		if !nc.update(ce) {
   113  			break
   114  		}
   115  	}
   116  	return nc.result(), n
   117  }
   118  
   119  type numberConverter struct {
   120  	w *numericWeighter
   121  
   122  	elems    []Elem
   123  	nDigits  int
   124  	lenIndex int
   125  
   126  	s string // set if the input was of type string
   127  	b []byte // set if the input was of type []byte
   128  }
   129  
   130  // init completes initialization of a numberConverter and prepares it for adding
   131  // more digits. elems is assumed to have a digit starting at oldLen.
   132  func (nc *numberConverter) init(elems []Elem, oldLen int, isZero bool) {
   133  	// Insert a marker indicating the start of a number and a placeholder
   134  	// for the number of digits.
   135  	if isZero {
   136  		elems = append(elems[:oldLen], nc.w.numberStart, 0)
   137  	} else {
   138  		elems = append(elems, 0, 0)
   139  		copy(elems[oldLen+2:], elems[oldLen:])
   140  		elems[oldLen] = nc.w.numberStart
   141  		elems[oldLen+1] = 0
   142  
   143  		nc.nDigits = 1
   144  	}
   145  	nc.elems = elems
   146  	nc.lenIndex = oldLen + 1
   147  }
   148  
   149  // checkNextDigit reports whether bufNew adds a single digit relative to the old
   150  // buffer. If it does, it also reports whether this digit is zero.
   151  func (nc *numberConverter) checkNextDigit(bufNew []Elem) (isZero, ok bool) {
   152  	if len(nc.elems) >= len(bufNew) {
   153  		return false, false
   154  	}
   155  	e := bufNew[len(nc.elems)]
   156  	if e < nc.w.zeroSpecialLo || nc.w.nine < e {
   157  		// Not a number.
   158  		return false, false
   159  	}
   160  	if e < nc.w.zero {
   161  		if e > nc.w.nineSpecialHi {
   162  			// Not a number.
   163  			return false, false
   164  		}
   165  		if !nc.isDigit() {
   166  			return false, false
   167  		}
   168  		isZero = e <= nc.w.zeroSpecialHi
   169  	} else {
   170  		// This is the common case if we encounter a digit.
   171  		isZero = e == nc.w.zero
   172  	}
   173  	// Test the remaining added collation elements have a zero primary value.
   174  	if n := len(bufNew) - len(nc.elems); n > 1 {
   175  		for i := len(nc.elems) + 1; i < len(bufNew); i++ {
   176  			if bufNew[i].Primary() != 0 {
   177  				return false, false
   178  			}
   179  		}
   180  		// In some rare cases, collation elements will encode runes in
   181  		// unicode.No as a digit. For example Ethiopic digits (U+1369 - U+1371)
   182  		// are not in Nd. Also some digits that clearly belong in unicode.No,
   183  		// like U+0C78 TELUGU FRACTION DIGIT ZERO FOR ODD POWERS OF FOUR, have
   184  		// collation elements indistinguishable from normal digits.
   185  		// Unfortunately, this means we need to make this check for nearly all
   186  		// non-Latin digits.
   187  		//
   188  		// TODO: check the performance impact and find something better if it is
   189  		// an issue.
   190  		if !nc.isDigit() {
   191  			return false, false
   192  		}
   193  	}
   194  	return isZero, true
   195  }
   196  
   197  func (nc *numberConverter) isDigit() bool {
   198  	if nc.b != nil {
   199  		r, _ := utf8.DecodeRune(nc.b)
   200  		return unicode.In(r, unicode.Nd)
   201  	}
   202  	r, _ := utf8.DecodeRuneInString(nc.s)
   203  	return unicode.In(r, unicode.Nd)
   204  }
   205  
   206  // We currently support a maximum of about 2M digits (the number of primary
   207  // values). Such numbers will compare correctly against small numbers, but their
   208  // comparison against other large numbers is undefined.
   209  //
   210  // TODO: define a proper fallback, such as comparing large numbers textually or
   211  // actually allowing numbers of unlimited length.
   212  //
   213  // TODO: cap this to a lower number (like 100) and maybe allow a larger number
   214  // in an option?
   215  const maxDigits = 1<<maxPrimaryBits - 1
   216  
   217  func (nc *numberConverter) update(elems []Elem) bool {
   218  	isZero, ok := nc.checkNextDigit(elems)
   219  	if nc.nDigits == 0 && isZero {
   220  		return true
   221  	}
   222  	nc.elems = elems
   223  	if !ok {
   224  		return false
   225  	}
   226  	nc.nDigits++
   227  	return nc.nDigits < maxDigits
   228  }
   229  
   230  // result fills in the length element for the digit sequence and returns the
   231  // completed collation elements.
   232  func (nc *numberConverter) result() []Elem {
   233  	e, _ := MakeElem(nc.nDigits, defaultSecondary, defaultTertiary, 0)
   234  	nc.elems[nc.lenIndex] = e
   235  	return nc.elems
   236  }
   237
View as plain text