vendor/golang.org/x/text/collate/sort.go

   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 }