1package sheet23import (4 "slices"5 "strings"67 "src.rest/cat/012/internal/formula"8)910// SortKey is one column to sort by.11type SortKey struct {12 Col int13 Desc bool // Z to A14}1516// sortRank orders kinds as Sheets sorts them A to Z: numbers (dates are17// numbers), then text, then booleans, then errors. Blanks always go last,18// in either direction.19func sortRank(v Value) int {20 switch v.Kind {21 case Number:22 return 023 case Text:24 return 125 case Bool:26 return 227 case Error:28 return 329 }30 return 431}3233// sortCompare orders two values A to Z: by kind, then numerically, or34// alphabetically ignoring case.35func sortCompare(a, b Value) int {36 if d := sortRank(a) - sortRank(b); d != 0 {37 return d38 }39 switch a.Kind {40 case Number, Bool:41 switch {42 case a.Num < b.Num:43 return -144 case a.Num > b.Num:45 return 146 }47 case Text, Error:48 return strings.Compare(strings.ToLower(a.Str), strings.ToLower(b.Str))49 }50 return 051}5253// compareRows orders rows i and j by keys, first key first. Blanks go54// last in either direction.55func (s *Sheet) compareRows(keys []SortKey, i, j int) int {56 for _, k := range keys {57 a, b := s.Value(Addr{Col: k.Col, Row: i}), s.Value(Addr{Col: k.Col, Row: j})58 if (a.Kind == Empty) != (b.Kind == Empty) {59 if a.Kind == Empty {60 return 161 }62 return -163 }64 d := sortCompare(a, b)65 if k.Desc {66 d = -d67 }68 if d != 0 {69 return d70 }71 }72 return 073}7475// SortRange sorts the rows of r by keys, first key first, as Sheets' Data76// > Sort range does (r excludes any header row). The sort is stable, so77// rows that tie keep their order. Only the cells inside r move. Formulas78// move with their rows and their relative references shift by the79// distance moved, as if copied there; references to the sorted cells80// from elsewhere are left alone. The whole sort is one undo step.81//82// Only rows holding cells are sorted: rows whose keys are all blank go83// last in their order, as blank rows do, so the cost is the rows with84// data, however tall r is.85func (s *Sheet) SortRange(r Rect, keys []SortKey) {86 if used, ok := s.UsedRange(); ok {87 r.To.Row, r.To.Col = min(r.To.Row, used.To.Row), min(r.To.Col, used.To.Col)88 }89 if len(keys) == 0 || r.To.Row <= r.From.Row || r.To.Col < r.From.Col || len(s.MergesIn(r)) > 0 {90 return91 }92 old := map[Addr]*Cell{}93 var rows []int // rows of r with cells, in order94 for a, c := range s.cells.inRange(r) {95 old[a] = c96 if len(rows) == 0 || rows[len(rows)-1] != a.Row {97 rows = append(rows, a.Row)98 }99 }100 dst := s.sortedRows(r, rows, keys)101 src := make(map[int]int, len(dst)) // where each row's new contents come from102 for from, to := range dst {103 src[to] = from104 }105 s.change("sort "+r.String(), r, func() {106 for a := range old {107 if from, ok := src[a.Row]; !ok || old[Addr{Col: a.Col, Row: from}] == nil {108 s.place(a, nil) // nothing moves here109 }110 }111 for a, c := range old {112 if to := dst[a.Row]; to != a.Row {113 s.place(Addr{Col: a.Col, Row: to}, c.rewritten(formula.Shift(0, to-a.Row)))114 }115 }116 })117}118119// sortedRows maps each of rows, the rows of r with cells, to where the120// sort puts it. Rows with a key sort to the top; the others (blank keys,121// and blank rows) keep their order below them.122func (s *Sheet) sortedRows(r Rect, rows []int, keys []SortKey) map[int]int {123 var keyed, rest []int124 for _, row := range rows {125 if s.keysBlank(keys, row) {126 rest = append(rest, row)127 } else {128 keyed = append(keyed, row)129 }130 }131 before := slices.Clone(keyed) // in their original order132 slices.SortStableFunc(keyed, func(i, j int) int { return s.compareRows(keys, i, j) })133 dst := make(map[int]int, len(rows))134 for i, row := range keyed {135 dst[row] = r.From.Row + i136 }137 // The other rows close up below: each moves down past the keyed rows138 // that were below it and up past those that were above it.139 n := 0140 for _, row := range rest {141 for n < len(before) && before[n] < row {142 n++143 }144 dst[row] = row + len(keyed) - n145 }146 return dst147}148149// keysBlank reports whether every key of row is blank.150func (s *Sheet) keysBlank(keys []SortKey, row int) bool {151 for _, k := range keys {152 if s.Value(Addr{Col: k.Col, Row: row}).Kind != Empty {153 return false154 }155 }156 return true157}