sort.go

Documentation: golang.org/x/text/collate

     1  // Copyright 2013 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 collate
     6  
     7  import (
     8  	"bytes"
     9  	"sort"
    10  )
    11  
    12  const (
    13  	maxSortBuffer  = 40960
    14  	maxSortEntries = 4096
    15  )
    16  
    17  type swapper interface {
    18  	Swap(i, j int)
    19  }
    20  
    21  type sorter struct {
    22  	buf  *Buffer
    23  	keys [][]byte
    24  	src  swapper
    25  }
    26  
    27  func (s *sorter) init(n int) {
    28  	if s.buf == nil {
    29  		s.buf = &Buffer{}
    30  		s.buf.init()
    31  	}
    32  	if cap(s.keys) < n {
    33  		s.keys = make([][]byte, n)
    34  	}
    35  	s.keys = s.keys[0:n]
    36  }
    37  
    38  func (s *sorter) sort(src swapper) {
    39  	s.src = src
    40  	sort.Sort(s)
    41  }
    42  
    43  func (s sorter) Len() int {
    44  	return len(s.keys)
    45  }
    46  
    47  func (s sorter) Less(i, j int) bool {
    48  	return bytes.Compare(s.keys[i], s.keys[j]) == -1
    49  }
    50  
    51  func (s sorter) Swap(i, j int) {
    52  	s.keys[i], s.keys[j] = s.keys[j], s.keys[i]
    53  	s.src.Swap(i, j)
    54  }
    55  
    56  // A Lister can be sorted by Collator's Sort method.
    57  type Lister interface {
    58  	Len() int
    59  	Swap(i, j int)
    60  	// Bytes returns the bytes of the text at index i.
    61  	Bytes(i int) []byte
    62  }
    63  
    64  // Sort uses sort.Sort to sort the strings represented by x using the rules of c.
    65  func (c *Collator) Sort(x Lister) {
    66  	n := x.Len()
    67  	c.sorter.init(n)
    68  	for i := 0; i < n; i++ {
    69  		c.sorter.keys[i] = c.Key(c.sorter.buf, x.Bytes(i))
    70  	}
    71  	c.sorter.sort(x)
    72  }
    73  
    74  // SortStrings uses sort.Sort to sort the strings in x using the rules of c.
    75  func (c *Collator) SortStrings(x []string) {
    76  	c.sorter.init(len(x))
    77  	for i, s := range x {
    78  		c.sorter.keys[i] = c.KeyFromString(c.sorter.buf, s)
    79  	}
    80  	c.sorter.sort(sort.StringSlice(x))
    81  }
    82
View as plain text