William Kurkian | ea86948 | 2019-04-09 15:16:11 -0400 | [diff] [blame] | 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 | } |