| // Copyright 2016 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. |
| |
| package table |
| |
| import ( |
| "sort" |
| |
| "github.com/aclements/go-gg/generic/slice" |
| ) |
| |
| // SortBy sorts each group of g by the named columns. If a column's |
| // type implements sort.Interface, rows will be sorted according to |
| // that order. Otherwise, the values in the column must be naturally |
| // ordered (their types must be orderable by the Go specification). If |
| // neither is true, SortBy panics with a *generic.TypeError. If more |
| // than one column is given, SortBy sorts by the tuple of the columns; |
| // that is, if two values in the first column are equal, they are |
| // sorted by the second column, and so on. |
| func SortBy(g Grouping, cols ...string) Grouping { |
| // Sort each group. |
| sorters := make([]sort.Interface, len(cols)) |
| return MapTables(g, func(_ GroupID, t *Table) *Table { |
| // Create sorters for each column. |
| sorters = sorters[:0] |
| for _, col := range cols { |
| if _, ok := t.Const(col); ok { |
| continue |
| } |
| seq := t.MustColumn(col) |
| sorter := slice.Sorter(seq) |
| if sort.IsSorted(sorter) { |
| continue |
| } |
| sorters = append(sorters, sorter) |
| } |
| |
| if len(sorters) == 0 { |
| // Avoid shuffling everything by the identity |
| // permutation. |
| return t |
| } |
| |
| // Generate an initial permutation sequence. |
| perm := make([]int, t.Len()) |
| for i := range perm { |
| perm[i] = i |
| } |
| |
| // Sort the permutation sequence. |
| sort.Stable(&permSort{perm, sorters}) |
| |
| // Permute all columns. |
| var nt Builder |
| for _, name := range t.Columns() { |
| if cv, ok := t.Const(name); ok { |
| nt.AddConst(name, cv) |
| continue |
| } |
| seq := t.Column(name) |
| seq = slice.Select(seq, perm) |
| nt.Add(name, seq) |
| } |
| return nt.Done() |
| }) |
| } |
| |
| type permSort struct { |
| perm []int |
| keys []sort.Interface |
| } |
| |
| func (s *permSort) Len() int { |
| return len(s.perm) |
| } |
| |
| func (s *permSort) Less(i, j int) bool { |
| // Since there's no way to ask about equality, we have to do |
| // extra work for all of the keys except the last. |
| for _, key := range s.keys[:len(s.keys)-1] { |
| if key.Less(s.perm[i], s.perm[j]) { |
| return true |
| } else if key.Less(s.perm[j], s.perm[i]) { |
| return false |
| } |
| } |
| return s.keys[len(s.keys)-1].Less(s.perm[i], s.perm[j]) |
| } |
| |
| func (s *permSort) Swap(i, j int) { |
| s.perm[i], s.perm[j] = s.perm[j], s.perm[i] |
| } |