1package sheet23import (4 "math/bits"5 "slices"6)78// Stats summarizes the values in r, as shown in the status line for a9// selection. Count is non-blank cells, Nums is numeric cells.10type Stats struct {11 Sum float6412 Count, Nums int13}1415// add counts a cell with contents whose value is v.16func (st *Stats) add(v Value) {17 st.Count++18 if v.Kind == Number {19 st.Nums++20 st.Sum += v.Num21 }22}2324// statsCache is the last RangeStats result: the status line asks for the25// selection's statistics on every frame.26type statsCache struct {27 r Rect28 version uint6429 st Stats30 ok bool31}3233// RangeStats computes Stats over r. The result is kept until a cell or34// value changes. A selection over a large, well-filled sheet is summed35// from the cells' statistics index (see rangeStats), so changing it costs36// a block per column plus the rows at its ends, not a read of every cell.37func (s *Sheet) RangeStats(r Rect) Stats {38 if c := s.stats; c.ok && c.r == r && c.version == s.version {39 return c.st40 }41 var st Stats42 area := (r.To.Col - r.From.Col + 1) * (r.To.Row - r.From.Row + 1)43 if area <= statsDirect || s.cells.len() <= statsSparse {44 for a := range s.cells.anyKeysIn(r) {45 if s.cells.filledAt(a) {46 st.add(s.cells.value(a))47 }48 }49 } else {50 st = s.cells.rangeStats(r)51 }52 s.stats = statsCache{r: r, version: s.version, st: st, ok: true}53 return st54}5556const (57 // statsDirect: selections of at most this many cells are summed cell58 // by cell.59 statsDirect = 409660 // statsSparse: sheets of at most this many cells are summed by61 // visiting their cells, which is cheaper than the index.62 statsSparse = 1638463)6465// The statistics index keeps Stats for every 64 rows of every column66// that has contents, on the blocks of the index of filled cells67// (occupancy.go): one entry per word of a block's bitmap, so it takes68// memory only where there is data, whatever the grid's size. Entries are69// computed when a selection first covers them; storing or deleting a70// cell, or recalculating its value, marks its entry stale, and a stale71// entry is summed again (a lookup per cell it holds) when next needed.72// Entries are recomputed rather than adjusted, so sums don't drift with73// rounding.7475// wordStats is Stats over the 64 rows of one word of a block.76type wordStats struct {77 sum float6478 count, nums int3279}8081// blockStats is the statistics of a block of the filled index, made on82// first use.83type blockStats struct {84 words [blockWords]wordStats85 ok uint16 // a bit per word: its entry is current86 total wordStats87 totalOK bool // total is the sum of the words' entries, all current88}8990// touch marks the entry holding a stale.91func (st *cellStore) touch(a Addr) {92 if b := st.filled.col(a.Col).block(a.Row >> blockShift); b != nil && b.stats != nil {93 b.stats.ok &^= 1 << ((a.Row & (blockRows - 1)) >> 6)94 b.stats.totalOK = false95 }96}9798// changed notes that the value of the cell at a was recalculated.99func (st *cellStore) changed(a Addr) { st.touch(a) }100101// word returns the statistics of word w of block id of column col, summing102// it again if it's stale.103func (st *cellStore) word(col, id int, b *rowBlock, w int) wordStats {104 if b.stats == nil {105 b.stats = &blockStats{}106 }107 x := b.stats108 if x.ok&(1<<w) == 0 {109 var s Stats110 st.scanWord(col, id, b, w, ^uint64(0), &s)111 x.words[w] = wordStats{sum: s.Sum, count: int32(s.Count), nums: int32(s.Nums)}112 x.ok |= 1 << w113 }114 return x.words[w]115}116117// blockTotal returns the statistics of the whole block id of column col.118func (st *cellStore) blockTotal(col, id int, b *rowBlock) wordStats {119 if b.stats != nil && b.stats.totalOK {120 return b.stats.total121 }122 var t wordStats123 for w := range blockWords {124 ws := st.word(col, id, b, w)125 t.sum += ws.sum126 t.count += ws.count127 t.nums += ws.nums128 }129 b.stats.total, b.stats.totalOK = t, true130 return t131}132133// scanWord adds the filled cells of word w of block id, among the rows134// mask keeps, into s.135func (st *cellStore) scanWord(col, id int, b *rowBlock, w int, mask uint64, s *Stats) {136 base := id<<blockShift + w<<6137 for x := b.bits[w] & mask; x != 0; x &= x - 1 {138 s.add(st.value(Addr{Col: col, Row: base + bits.TrailingZeros64(x)}))139 }140}141142// rangeStats sums r from the index: in each column with contents, the143// whole words r covers from their entries, and the rows at its ends144// outside them cell by cell.145func (st *cellStore) rangeStats(r Rect) Stats {146 st.statsUsed = true147 var s Stats148 b0, b1 := r.From.Row>>blockShift, r.To.Row>>blockShift149 for _, col := range st.filled.colsIn(r.From.Col, r.To.Col) {150 ci := st.filled.col(col)151 i, _ := slices.BinarySearch(ci.ids, b0)152 for ; i < len(ci.ids) && ci.ids[i] <= b1; i++ {153 id := ci.ids[i]154 b := ci.blocks[id]155 base := id << blockShift156 lo, hi := max(r.From.Row-base, 0), min(r.To.Row-base, blockRows-1)157 if lo == 0 && hi == blockRows-1 {158 t := st.blockTotal(col, id, b)159 s.Sum += t.sum160 s.Count += int(t.count)161 s.Nums += int(t.nums)162 continue163 }164 for w := lo >> 6; w <= hi>>6; w++ {165 if mask := wordMask(w, lo, hi); mask != ^uint64(0) {166 st.scanWord(col, id, b, w, mask, &s)167 continue168 }169 ws := st.word(col, id, b, w)170 s.Sum += ws.sum171 s.Count += int(ws.count)172 s.Nums += int(ws.nums)173 }174 }175 }176 return s177}