1package functions23import (4 "cmp"5 "math"6 "slices"78 "src.rest/cat/012/internal/formula"9 "src.rest/cat/012/internal/value"10)1112// Order statistics: MEDIAN, MODE, PERCENTILE, QUARTILE, LARGE and SMALL13// read their numbers once, in ascending order, picking the ones they14// need as they pass. On a sheet the numbers are held and sorted; over a15// linked source's column, computing a StreamCall, the Book sorts them16// on disk (Sorter), so a source of any size takes the memory of a sort17// run rather than of its column. Either way the same code picks, so the18// results are the same.1920// Sorted is numbers read in ascending order, once.21type Sorted interface {22 // Len counts the numbers.23 Len() int24 // Next is the next number, ties in the order they were read, with25 // its position in that order; false at the end, or on an error,26 // which Err says.27 Next() (v float64, pos int64, ok bool)28 Err() error29 Close() error30}3132// Sorter is a Book that sorts the numbers of a range of a paged sheet33// (a linked source's column) on disk: its numbers, skipping the cells34// holding anything else, as a range's are read by SUM, or the first35// error in it.36type Sorter interface {37 SortedNums(sheet string, r Rect) (Sorted, *Value)38}3940// orderFuncs are the functions that read their numbers in order: from41// every argument (true: MEDIAN, MODE) or from the first, the rest being42// what to pick.43var orderFuncs = map[string]bool{44 "MEDIAN": true, "MODE": true, "MODE.SNGL": true, "LARGE": false, "SMALL": false,45 "PERCENTILE": false, "PERCENTILE.INC": false, "PERCENTILE.EXC": false,46 "QUARTILE": false, "QUARTILE.INC": false, "QUARTILE.EXC": false,47}4849// sortsSource reports whether c is an order statistic of one range of a50// source, its other arguments single values: the Book sorts that range51// on disk, so it streams.52func sortsSource(c StreamCall) bool {53 all, ok := orderFuncs[c.Fn]54 if !ok || len(c.Args) == 0 || c.Args[0].Sheet == "" || all && len(c.Args) > 1 {55 return false56 }57 for _, a := range c.Args[1:] {58 if a.Sheet != "" {59 return false60 }61 }62 return true63}6465// held is numbers held in memory, sorted.66type held struct {67 x []posNum68 i int69}7071type posNum struct {72 v float6473 pos int6474}7576func (h *held) Len() int { return len(h.x) }77func (h *held) Err() error { return nil }78func (h *held) Close() error { return nil }79func (h *held) Next() (float64, int64, bool) {80 if h.i >= len(h.x) {81 return 0, 0, false82 }83 h.i++84 return h.x[h.i-1].v, h.x[h.i-1].pos, true85}8687// sortedNums is the numbers of args in ascending order, with aggregate88// semantics (nums): sorted by the Book on disk when computing a89// StreamCall over one range of a source, else held.90func sortedNums(args []Node, get lookup) (Sorted, *Value) {91 if s, ok := get.book.(Sorter); ok && get.stream && len(args) == 1 {92 if r, ok := get.refOf(args[0]).(formula.Range); ok && r.Sheet != "" {93 return s.SortedNums(r.Sheet, r.Rect)94 }95 }96 x, err := nums(args, get)97 if err != nil {98 return nil, err99 }100 h := &held{x: make([]posNum, len(x))}101 for i, v := range x {102 h.x[i] = posNum{v, int64(i)}103 }104 slices.SortFunc(h.x, func(a, b posNum) int { return cmp.Or(cmpFloat(a.v, b.v), cmp.Compare(a.pos, b.pos)) })105 return h, nil106}107108// pickAt reads the numbers at the ascending indexes ks of s, in order.109func pickAt(s Sorted, ks ...int) ([]float64, *Value) {110 out := make([]float64, 0, len(ks))111 for i := 0; len(out) < len(ks); i++ {112 v, _, ok := s.Next()113 if !ok {114 return nil, &value.ErrRef // the source failed as it was read115 }116 for len(out) < len(ks) && ks[len(out)] == i {117 out = append(out, v)118 }119 }120 return out, nil121}122123// withSorted passes the numbers of the first argument, or with all of124// every argument (MEDIAN, MODE), sorted, to f with the rest.125func withSorted(all bool, f func(s Sorted, rest []Node, get lookup) Value) func([]Node, lookup) Value {126 return func(args []Node, get lookup) Value {127 upto := 1128 if all {129 upto = len(args)130 }131 s, err := sortedNums(args[:upto], get)132 if err != nil {133 return *err134 }135 defer s.Close()136 return f(s, args[upto:], get)137 }138}139140func medianOf(s Sorted, _ []Node, _ lookup) Value {141 n := s.Len()142 if n == 0 {143 return value.ErrNum144 }145 if n%2 == 1 {146 x, err := pickAt(s, n/2)147 if err != nil {148 return *err149 }150 return num(x[0])151 }152 x, err := pickAt(s, n/2-1, n/2)153 if err != nil {154 return *err155 }156 return num((x[0] + x[1]) / 2)157}158159// modeOf is the most common number, the one read first on a tie, or160// #N/A when none repeats: one pass over the runs of equal numbers.161func modeOf(s Sorted, _ []Node, _ lookup) Value {162 best, bestN, bestPos := 0.0, 1, int64(math.MaxInt64)163 cur, n, first := 0.0, 0, int64(0)164 end := func() {165 if n > bestN || n == bestN && n > 1 && first < bestPos {166 best, bestN, bestPos = cur, n, first167 }168 }169 for {170 v, pos, ok := s.Next()171 if !ok {172 break173 }174 if n > 0 && v == cur {175 n++176 continue177 }178 end()179 cur, n, first = v, 1, pos180 }181 if s.Err() != nil {182 return value.ErrRef183 }184 end()185 if bestN < 2 {186 return value.ErrNA187 }188 return num(best)189}190191// nthOf builds LARGE and SMALL: the kth largest or smallest number.192func nthOf(largest bool) func(Sorted, []Node, lookup) Value {193 return func(s Sorted, rest []Node, get lookup) Value {194 n, err := numArg(rest[0], get)195 if err != nil {196 return *err197 }198 k := int(math.Ceil(n))199 if k < 1 || k > s.Len() {200 return value.ErrNum201 }202 if largest {203 k = s.Len() - k + 1204 }205 x, err := pickAt(s, k-1)206 if err != nil {207 return *err208 }209 return num(x[0])210 }211}212213// percentileOf builds PERCENTILE.INC (exc false) and PERCENTILE.EXC,214// and with quart QUARTILE.INC and QUARTILE.EXC, whose argument counts215// quarters.216func percentileOf(exc, quart bool) func(Sorted, []Node, lookup) Value {217 return func(s Sorted, rest []Node, get lookup) Value {218 p, err := numArg(rest[0], get)219 if err != nil {220 return *err221 }222 if quart {223 q := math.Trunc(p)224 if q < 0 || q > 4 || exc && (q < 1 || q > 3) {225 return value.ErrNum226 }227 p = q / 4228 }229 return percentile(s, p, exc)230 }231}232233// percentile interpolates between the numbers either side of rank p of234// s: (n-1)p counting from 0, or (n+1)p counting from 1 for the235// exclusive kind, which has no rank before the first or past the last.236func percentile(s Sorted, p float64, exc bool) Value {237 n := s.Len()238 if n == 0 || p < 0 || p > 1 || exc && (p <= 0 || p >= 1) {239 return value.ErrNum240 }241 h := float64(n-1) * p242 if exc {243 h = float64(n+1)*p - 1244 if h < 0 || h > float64(n-1) {245 return value.ErrNum246 }247 }248 lo := int(math.Floor(h))249 if lo >= n-1 {250 x, err := pickAt(s, n-1)251 if err != nil {252 return *err253 }254 return num(x[0])255 }256 x, err := pickAt(s, lo, lo+1)257 if err != nil {258 return *err259 }260 return num(x[0] + (h-float64(lo))*(x[1]-x[0]))261}