1package functions23import (4 "slices"56 "src.rest/cat/012/internal/value"7)89// Sorting and comparing the rows of arrays, for SORT, SORTN and UNIQUE10// (dynamic.go).1112// sortKey is a column to sort by and its direction.13type sortKey struct {14 col *Array // one column, aligned with the rows15 desc bool16}1718// sortKeys reads SORT's (sort_column, is_ascending) pairs from args[i]19// on: a column by position in a, or a range of its own, aligned with it.20// With none, the first column goes up.21func sortKeys(a *Array, args []Node, i int, get lookup) ([]sortKey, *Value) {22 if !given(args, i) && len(args) <= i+1 {23 return []sortKey{{col: a.column(0)}}, nil24 }25 var keys []sortKey26 for ; i < len(args); i += 2 {27 k, err := sortKeyArg(a, args[i], get)28 if err != nil {29 return nil, err30 }31 asc, err := boolArg(args, i+1, true, get)32 if err != nil {33 return nil, err34 }35 k.desc = !asc36 keys = append(keys, k)37 }38 return keys, nil39}4041func sortKeyArg(a *Array, n Node, get lookup) (sortKey, *Value) {42 col, err := arrayArg(n, get)43 switch {44 case err != nil:45 return sortKey{}, err46 case col.Rows == 1 && col.Cols == 1:47 i, err := toNum(col.At(0, 0))48 if err != nil {49 return sortKey{}, err50 }51 if i < 1 || int(i) > a.Cols {52 return sortKey{}, &value.ErrValue53 }54 return sortKey{col: a.column(int(i) - 1)}, nil55 case col.Cols != 1 || col.Rows != a.Rows:56 return sortKey{}, &value.ErrValue57 }58 return sortKey{col: col}, nil59}6061// column is column c of a, as an array of one column.62func (a *Array) column(c int) *Array {63 out := &Array{Rows: a.Rows, Cols: 1, Fill: a.Fill}64 if c < a.DCols {65 out.DRows, out.DCols = a.DRows, 166 out.V = make([]Value, a.DRows)67 for r := range a.DRows {68 out.V[r] = a.At(r, c)69 }70 }71 return out72}7374// sortOrder orders rows 0..n-1 by keys, stably: numbers, then text, then75// booleans, ascending or not, and blanks last either way, as Sheets76// sorts.77func sortOrder(n int, keys []sortKey) []int {78 order := make([]int, n)79 for i := range order {80 order[i] = i81 }82 slices.SortStableFunc(order, func(x, y int) int {83 for _, k := range keys {84 if d := sortCompare(k.col.At(x, 0), k.col.At(y, 0), k.desc); d != 0 {85 return d86 }87 }88 return 089 })90 return order91}9293// sortCompare orders two values for sorting, blanks last.94func sortCompare(a, b Value, desc bool) int {95 ab, bb := a.Kind == value.Empty, b.Kind == value.Empty96 switch {97 case ab || bb:98 return boolOrder(ab) - boolOrder(bb)99 case a.Kind == value.Error || b.Kind == value.Error:100 return boolOrder(a.Kind == value.Error) - boolOrder(b.Kind == value.Error)101 }102 d := compare(a, b)103 if desc {104 d = -d105 }106 return d107}108109func boolOrder(b bool) int {110 if b {111 return 1112 }113 return 0114}115116// sortedData sorts a's rows that hold data (every row past them is117// blank, and blanks sort last), keeping the blank rows as its fill.118func sortedData(a *Array, keys []sortKey) *Array {119 data := a.DRows120 for _, k := range keys {121 data = max(data, k.col.DRows)122 }123 data = min(data, a.Rows)124 out := a.rows(sortOrder(data, keys))125 out.Rows, out.Fill = a.Rows, a.Fill126 return out127}128129// topRows picks SORTN's rows of sorted, by its display_ties_mode: 0 the130// first n; 1 the first n and any tied with the last; 2 the first n131// distinct rows; 3 the rows of the first n distinct keys.132func topRows(sorted *Array, keys []sortKey, n, mode int) []int {133 keyed := sortedKeys(sorted, keys)134 var out []int135 distinct := 0136 for r := range sorted.Rows {137 switch mode {138 case 0:139 if len(out) == n {140 return out141 }142 case 1:143 if len(out) >= n && !sameRow(keyed, r, out[len(out)-1]) {144 return out145 }146 case 2:147 if slices.ContainsFunc(out, func(p int) bool { return sameRow(sorted, r, p) }) {148 continue149 }150 if len(out) == n {151 return out152 }153 case 3:154 if len(out) == 0 || !sameRow(keyed, r, out[len(out)-1]) {155 distinct++156 }157 if distinct > n {158 return out159 }160 }161 out = append(out, r)162 }163 return out164}165166// sortedKeys is the sort key columns of sorted's rows side by side, for167// comparing rows by their keys.168func sortedKeys(sorted *Array, keys []sortKey) *Array {169 out := NewArray(sorted.Rows, len(keys))170 for i, k := range keys {171 for r := range sorted.Rows {172 out.Set(r, i, k.col.At(r, 0))173 }174 }175 return out176}177178// sameRow reports whether rows x and y of a hold the same values: text179// compared exactly, as UNIQUE does.180func sameRow(a *Array, x, y int) bool {181 for c := range a.Cols {182 if !sameValue(a.At(x, c), a.At(y, c)) {183 return false184 }185 }186 return true187}188189// sameValue reports whether two values are the same for UNIQUE: of one190// kind and equal, text case included, as Sheets compares them.191func sameValue(a, b Value) bool {192 if a.Kind != b.Kind {193 return false194 }195 if a.Kind == value.Text || a.Kind == value.Error {196 return a.Str == b.Str197 }198 return a.Num == b.Num199}