1package sheet23import (4 "cmp"5 "slices"6)78// rangeIndex finds the formulas whose range references contain a cell.9// Recalculation asks it about every changed cell; scanning every range10// user instead made a change cost O(changed x range users), so filling a11// column of 8192 running totals checked 67 million ranges.12//13// Ranges up to wideCols columns are indexed under each column they cover,14// wider ones (whole rows) once; within each, an interval tree over rows15// finds the ranges holding a row in O(log n + found), and formulas with16// the same range (a thousand SUM(A:A)) share one entry. Only the columns17// that ranges cover take memory.18type rangeIndex struct {19 byCol map[int]*intervals20 wide intervals21}2223// wideCols is the widest range indexed column by column.24const wideCols = 322526// add indexes the formula at a under the ranges it reads.27func (x *rangeIndex) add(a Addr, ranges []Rect) {28 for _, r := range ranges {29 if r.To.Col-r.From.Col >= wideCols {30 x.wide.add(r, a)31 continue32 }33 if x.byCol == nil {34 x.byCol = make(map[int]*intervals)35 }36 for c := max(r.From.Col, 0); c <= min(r.To.Col, MaxCols-1); c++ {37 iv := x.byCol[c]38 if iv == nil {39 iv = &intervals{}40 x.byCol[c] = iv41 }42 iv.add(r, a)43 }44 }45}4647// remove undoes add for the same ranges.48func (x *rangeIndex) remove(a Addr, ranges []Rect) {49 for _, r := range ranges {50 if r.To.Col-r.From.Col >= wideCols {51 x.wide.remove(r, a)52 continue53 }54 for c := max(r.From.Col, 0); c <= min(r.To.Col, MaxCols-1); c++ {55 if iv := x.byCol[c]; iv != nil {56 iv.remove(r, a)57 if len(iv.users) == 0 {58 delete(x.byCol, c)59 }60 }61 }62 }63}6465// readers calls fn with each formula one of whose ranges contains a; a66// formula with two such ranges may come twice.67func (x *rangeIndex) readers(a Addr, fn func(Addr)) {68 if iv := x.byCol[a.Col]; iv != nil {69 iv.stab(a, fn)70 }71 x.wide.stab(a, fn)72}7374// intervals holds ranges and the formulas reading each, with a tree over75// their rows built when first asked after a change.76type intervals struct {77 users map[Rect]map[Addr]struct{}78 sorted []Rect // by first row; nil when stale79 maxEnd []int // the last row of any range in the subtree rooted at each index80}8182func (iv *intervals) add(r Rect, a Addr) {83 if iv.users == nil {84 iv.users = make(map[Rect]map[Addr]struct{})85 }86 u := iv.users[r]87 if u == nil {88 u = make(map[Addr]struct{})89 iv.users[r] = u90 iv.sorted = nil91 }92 u[a] = struct{}{}93}9495func (iv *intervals) remove(r Rect, a Addr) {96 u := iv.users[r]97 if u == nil {98 return99 }100 delete(u, a)101 if len(u) == 0 {102 delete(iv.users, r)103 iv.sorted = nil104 }105}106107// stab calls fn with the users of every range containing a.108func (iv *intervals) stab(a Addr, fn func(Addr)) {109 if len(iv.users) == 0 {110 return111 }112 if iv.sorted == nil {113 iv.build()114 }115 iv.query(0, len(iv.sorted), a, fn)116}117118func (iv *intervals) build() {119 iv.sorted = iv.sorted[:0]120 for r := range iv.users {121 iv.sorted = append(iv.sorted, r)122 }123 slices.SortFunc(iv.sorted, func(p, q Rect) int {124 if c := cmp.Compare(p.From.Row, q.From.Row); c != 0 {125 return c126 }127 if c := cmp.Compare(p.To.Row, q.To.Row); c != 0 {128 return c129 }130 if c := cmp.Compare(p.From.Col, q.From.Col); c != 0 {131 return c132 }133 return cmp.Compare(p.To.Col, q.To.Col)134 })135 iv.maxEnd = slices.Grow(iv.maxEnd[:0], len(iv.sorted))[:len(iv.sorted)]136 iv.fill(0, len(iv.sorted))137}138139// fill computes maxEnd for the implicit tree over sorted[lo:hi], whose140// root is its middle element, and returns it.141func (iv *intervals) fill(lo, hi int) int {142 if lo >= hi {143 return -1144 }145 mid := (lo + hi) / 2146 m := max(iv.sorted[mid].To.Row, iv.fill(lo, mid), iv.fill(mid+1, hi))147 iv.maxEnd[mid] = m148 return m149}150151func (iv *intervals) query(lo, hi int, a Addr, fn func(Addr)) {152 for lo < hi {153 mid := (lo + hi) / 2154 if iv.maxEnd[mid] < a.Row {155 return // nothing below reaches the row156 }157 iv.query(lo, mid, a, fn)158 r := iv.sorted[mid]159 if r.From.Row > a.Row {160 return // this and everything after start below the row161 }162 if r.Contains(a) {163 for u := range iv.users[r] {164 fn(u)165 }166 }167 lo = mid + 1168 }169}