--- /dev/null
+// Copyright 2012 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.
+
+// TODO: remove hard-coded versions when we have implemented fractional weights.
+// The current implementation is incompatible with later CLDR versions.
+//go:generate go run maketables.go -cldr=23 -unicode=6.2.0
+
+// Package collate contains types for comparing and sorting Unicode strings
+// according to a given collation order.
+package collate // import "golang.org/x/text/collate"
+
+import (
+ "bytes"
+ "strings"
+
+ "golang.org/x/text/internal/colltab"
+ "golang.org/x/text/language"
+)
+
+// Collator provides functionality for comparing strings for a given
+// collation order.
+type Collator struct {
+ options
+
+ sorter sorter
+
+ _iter [2]iter
+}
+
+func (c *Collator) iter(i int) *iter {
+ // TODO: evaluate performance for making the second iterator optional.
+ return &c._iter[i]
+}
+
+// Supported returns the list of languages for which collating differs from its parent.
+func Supported() []language.Tag {
+ // TODO: use language.Coverage instead.
+
+ t := make([]language.Tag, len(tags))
+ copy(t, tags)
+ return t
+}
+
+func init() {
+ ids := strings.Split(availableLocales, ",")
+ tags = make([]language.Tag, len(ids))
+ for i, s := range ids {
+ tags[i] = language.Raw.MustParse(s)
+ }
+}
+
+var tags []language.Tag
+
+// New returns a new Collator initialized for the given locale.
+func New(t language.Tag, o ...Option) *Collator {
+ index := colltab.MatchLang(t, tags)
+ c := newCollator(getTable(locales[index]))
+
+ // Set options from the user-supplied tag.
+ c.setFromTag(t)
+
+ // Set the user-supplied options.
+ c.setOptions(o)
+
+ c.init()
+ return c
+}
+
+// NewFromTable returns a new Collator for the given Weighter.
+func NewFromTable(w colltab.Weighter, o ...Option) *Collator {
+ c := newCollator(w)
+ c.setOptions(o)
+ c.init()
+ return c
+}
+
+func (c *Collator) init() {
+ if c.numeric {
+ c.t = colltab.NewNumericWeighter(c.t)
+ }
+ c._iter[0].init(c)
+ c._iter[1].init(c)
+}
+
+// Buffer holds keys generated by Key and KeyString.
+type Buffer struct {
+ buf [4096]byte
+ key []byte
+}
+
+func (b *Buffer) init() {
+ if b.key == nil {
+ b.key = b.buf[:0]
+ }
+}
+
+// Reset clears the buffer from previous results generated by Key and KeyString.
+func (b *Buffer) Reset() {
+ b.key = b.key[:0]
+}
+
+// Compare returns an integer comparing the two byte slices.
+// The result will be 0 if a==b, -1 if a < b, and +1 if a > b.
+func (c *Collator) Compare(a, b []byte) int {
+ // TODO: skip identical prefixes once we have a fast way to detect if a rune is
+ // part of a contraction. This would lead to roughly a 10% speedup for the colcmp regtest.
+ c.iter(0).SetInput(a)
+ c.iter(1).SetInput(b)
+ if res := c.compare(); res != 0 {
+ return res
+ }
+ if !c.ignore[colltab.Identity] {
+ return bytes.Compare(a, b)
+ }
+ return 0
+}
+
+// CompareString returns an integer comparing the two strings.
+// The result will be 0 if a==b, -1 if a < b, and +1 if a > b.
+func (c *Collator) CompareString(a, b string) int {
+ // TODO: skip identical prefixes once we have a fast way to detect if a rune is
+ // part of a contraction. This would lead to roughly a 10% speedup for the colcmp regtest.
+ c.iter(0).SetInputString(a)
+ c.iter(1).SetInputString(b)
+ if res := c.compare(); res != 0 {
+ return res
+ }
+ if !c.ignore[colltab.Identity] {
+ if a < b {
+ return -1
+ } else if a > b {
+ return 1
+ }
+ }
+ return 0
+}
+
+func compareLevel(f func(i *iter) int, a, b *iter) int {
+ a.pce = 0
+ b.pce = 0
+ for {
+ va := f(a)
+ vb := f(b)
+ if va != vb {
+ if va < vb {
+ return -1
+ }
+ return 1
+ } else if va == 0 {
+ break
+ }
+ }
+ return 0
+}
+
+func (c *Collator) compare() int {
+ ia, ib := c.iter(0), c.iter(1)
+ // Process primary level
+ if c.alternate != altShifted {
+ // TODO: implement script reordering
+ if res := compareLevel((*iter).nextPrimary, ia, ib); res != 0 {
+ return res
+ }
+ } else {
+ // TODO: handle shifted
+ }
+ if !c.ignore[colltab.Secondary] {
+ f := (*iter).nextSecondary
+ if c.backwards {
+ f = (*iter).prevSecondary
+ }
+ if res := compareLevel(f, ia, ib); res != 0 {
+ return res
+ }
+ }
+ // TODO: special case handling (Danish?)
+ if !c.ignore[colltab.Tertiary] || c.caseLevel {
+ if res := compareLevel((*iter).nextTertiary, ia, ib); res != 0 {
+ return res
+ }
+ if !c.ignore[colltab.Quaternary] {
+ if res := compareLevel((*iter).nextQuaternary, ia, ib); res != 0 {
+ return res
+ }
+ }
+ }
+ return 0
+}
+
+// Key returns the collation key for str.
+// Passing the buffer buf may avoid memory allocations.
+// The returned slice will point to an allocation in Buffer and will remain
+// valid until the next call to buf.Reset().
+func (c *Collator) Key(buf *Buffer, str []byte) []byte {
+ // See http://www.unicode.org/reports/tr10/#Main_Algorithm for more details.
+ buf.init()
+ return c.key(buf, c.getColElems(str))
+}
+
+// KeyFromString returns the collation key for str.
+// Passing the buffer buf may avoid memory allocations.
+// The returned slice will point to an allocation in Buffer and will retain
+// valid until the next call to buf.ResetKeys().
+func (c *Collator) KeyFromString(buf *Buffer, str string) []byte {
+ // See http://www.unicode.org/reports/tr10/#Main_Algorithm for more details.
+ buf.init()
+ return c.key(buf, c.getColElemsString(str))
+}
+
+func (c *Collator) key(buf *Buffer, w []colltab.Elem) []byte {
+ processWeights(c.alternate, c.t.Top(), w)
+ kn := len(buf.key)
+ c.keyFromElems(buf, w)
+ return buf.key[kn:]
+}
+
+func (c *Collator) getColElems(str []byte) []colltab.Elem {
+ i := c.iter(0)
+ i.SetInput(str)
+ for i.Next() {
+ }
+ return i.Elems
+}
+
+func (c *Collator) getColElemsString(str string) []colltab.Elem {
+ i := c.iter(0)
+ i.SetInputString(str)
+ for i.Next() {
+ }
+ return i.Elems
+}
+
+type iter struct {
+ wa [512]colltab.Elem
+
+ colltab.Iter
+ pce int
+}
+
+func (i *iter) init(c *Collator) {
+ i.Weighter = c.t
+ i.Elems = i.wa[:0]
+}
+
+func (i *iter) nextPrimary() int {
+ for {
+ for ; i.pce < i.N; i.pce++ {
+ if v := i.Elems[i.pce].Primary(); v != 0 {
+ i.pce++
+ return v
+ }
+ }
+ if !i.Next() {
+ return 0
+ }
+ }
+ panic("should not reach here")
+}
+
+func (i *iter) nextSecondary() int {
+ for ; i.pce < len(i.Elems); i.pce++ {
+ if v := i.Elems[i.pce].Secondary(); v != 0 {
+ i.pce++
+ return v
+ }
+ }
+ return 0
+}
+
+func (i *iter) prevSecondary() int {
+ for ; i.pce < len(i.Elems); i.pce++ {
+ if v := i.Elems[len(i.Elems)-i.pce-1].Secondary(); v != 0 {
+ i.pce++
+ return v
+ }
+ }
+ return 0
+}
+
+func (i *iter) nextTertiary() int {
+ for ; i.pce < len(i.Elems); i.pce++ {
+ if v := i.Elems[i.pce].Tertiary(); v != 0 {
+ i.pce++
+ return int(v)
+ }
+ }
+ return 0
+}
+
+func (i *iter) nextQuaternary() int {
+ for ; i.pce < len(i.Elems); i.pce++ {
+ if v := i.Elems[i.pce].Quaternary(); v != 0 {
+ i.pce++
+ return v
+ }
+ }
+ return 0
+}
+
+func appendPrimary(key []byte, p int) []byte {
+ // Convert to variable length encoding; supports up to 23 bits.
+ if p <= 0x7FFF {
+ key = append(key, uint8(p>>8), uint8(p))
+ } else {
+ key = append(key, uint8(p>>16)|0x80, uint8(p>>8), uint8(p))
+ }
+ return key
+}
+
+// keyFromElems converts the weights ws to a compact sequence of bytes.
+// The result will be appended to the byte buffer in buf.
+func (c *Collator) keyFromElems(buf *Buffer, ws []colltab.Elem) {
+ for _, v := range ws {
+ if w := v.Primary(); w > 0 {
+ buf.key = appendPrimary(buf.key, w)
+ }
+ }
+ if !c.ignore[colltab.Secondary] {
+ buf.key = append(buf.key, 0, 0)
+ // TODO: we can use one 0 if we can guarantee that all non-zero weights are > 0xFF.
+ if !c.backwards {
+ for _, v := range ws {
+ if w := v.Secondary(); w > 0 {
+ buf.key = append(buf.key, uint8(w>>8), uint8(w))
+ }
+ }
+ } else {
+ for i := len(ws) - 1; i >= 0; i-- {
+ if w := ws[i].Secondary(); w > 0 {
+ buf.key = append(buf.key, uint8(w>>8), uint8(w))
+ }
+ }
+ }
+ } else if c.caseLevel {
+ buf.key = append(buf.key, 0, 0)
+ }
+ if !c.ignore[colltab.Tertiary] || c.caseLevel {
+ buf.key = append(buf.key, 0, 0)
+ for _, v := range ws {
+ if w := v.Tertiary(); w > 0 {
+ buf.key = append(buf.key, uint8(w))
+ }
+ }
+ // Derive the quaternary weights from the options and other levels.
+ // Note that we represent MaxQuaternary as 0xFF. The first byte of the
+ // representation of a primary weight is always smaller than 0xFF,
+ // so using this single byte value will compare correctly.
+ if !c.ignore[colltab.Quaternary] && c.alternate >= altShifted {
+ if c.alternate == altShiftTrimmed {
+ lastNonFFFF := len(buf.key)
+ buf.key = append(buf.key, 0)
+ for _, v := range ws {
+ if w := v.Quaternary(); w == colltab.MaxQuaternary {
+ buf.key = append(buf.key, 0xFF)
+ } else if w > 0 {
+ buf.key = appendPrimary(buf.key, w)
+ lastNonFFFF = len(buf.key)
+ }
+ }
+ buf.key = buf.key[:lastNonFFFF]
+ } else {
+ buf.key = append(buf.key, 0)
+ for _, v := range ws {
+ if w := v.Quaternary(); w == colltab.MaxQuaternary {
+ buf.key = append(buf.key, 0xFF)
+ } else if w > 0 {
+ buf.key = appendPrimary(buf.key, w)
+ }
+ }
+ }
+ }
+ }
+}
+
+func processWeights(vw alternateHandling, top uint32, wa []colltab.Elem) {
+ ignore := false
+ vtop := int(top)
+ switch vw {
+ case altShifted, altShiftTrimmed:
+ for i := range wa {
+ if p := wa[i].Primary(); p <= vtop && p != 0 {
+ wa[i] = colltab.MakeQuaternary(p)
+ ignore = true
+ } else if p == 0 {
+ if ignore {
+ wa[i] = colltab.Ignore
+ }
+ } else {
+ ignore = false
+ }
+ }
+ case altBlanked:
+ for i := range wa {
+ if p := wa[i].Primary(); p <= vtop && (ignore || p != 0) {
+ wa[i] = colltab.Ignore
+ ignore = true
+ } else {
+ ignore = false
+ }
+ }
+ }
+}
OSDN Git Service
