1package functions23import "slices"45// seq is the entries of a row or column searched by a lookup: n of them,6// of which only the first data may hold data. With sparse, only the7// entries holding cells (entries, positions) hold anything; every other8// entry is blank.9type seq struct {10 n, data int11 line matrix // the row or column12 blank Value13 sparse bool1415 get lookup16 r Rect // the line's cells, when it is a range17 vertical bool18}1920// lineSeq is the first column (vertical) or row of m, as a lookup21// searches it: through the cells it holds, when it is a range.22func lineSeq(m matrix, get lookup, vertical bool) seq {23 line := m24 switch {25 case !m.ref && vertical && m.cols > 1:26 line = m.part(m.rows, 1)27 case !m.ref && !vertical && m.rows > 1:28 line = m.part(1, m.cols)29 case m.ref:30 to := Addr{Col: m.origin.Col, Row: m.origin.Row + m.rows - 1}31 if !vertical {32 to = Addr{Col: m.origin.Col + m.cols - 1, Row: m.origin.Row}33 }34 line = rectMatrix(m.sheet, Rect{From: m.origin, To: to}, get)35 }36 return seq{37 n: line.size(), data: min(line.dataLen(), line.size()), line: line, blank: line.blank,38 sparse: line.ref && !get.dense, // a single value is one entry, searched as data39 get: get, vertical: vertical,40 r: Rect{From: line.origin, To: Addr{Col: line.origin.Col + line.cols - 1, Row: line.origin.Row + line.rows - 1}},41 }42}4344// at is entry i's value.45func (q *seq) at(i int) Value { return q.line.at(i) }4647// value is the value of the entry whose cell is at a.48func (q *seq) value(a Addr) Value { return q.get.cell(q.line.sheet, a) }4950// index is the entry of the line's cell at a.51func (q *seq) index(a Addr) int {52 if q.vertical {53 return a.Row - q.r.From.Row54 }55 return a.Col - q.r.From.Col56}5758// walk walks the cells of a sparse line's entries, in order. It59// evaluates nothing: a search reads the value of each entry it reaches60// (q.value), and no more, as reading one at a time did.61func (q *seq) walk() cursor { return q.get.walk(q.line.sheet, q.r) }6263// positions is the sparse line's entries holding cells, in order.64func (q *seq) positions() []int {65 var out []int66 q.get.stored(q.line.sheet, q.r, func(a Addr) bool {67 out = append(out, q.index(a))68 return true69 })70 return out71}7273// findExact returns the first index whose value equals key, or -1.74func (q *seq) findExact(key Value, wild bool) int {75 if q.sparse {76 blank := lookupEqual(key, q.blank, wild)77 next := 0 // the first entry not looked at78 c := q.walk()79 defer c.close()80 for a, ok := c.next(); ok; a, ok = c.next() {81 i := q.index(a)82 switch {83 case i > next && blank:84 return next // a blank before this cell85 case lookupEqual(key, q.value(a), wild):86 return i87 }88 next = i + 189 }90 if blank && next < q.n {91 return next92 }93 return -194 }95 for i := range q.data {96 if lookupEqual(key, q.at(i), wild) {97 return i98 }99 }100 if q.data < q.n && lookupEqual(key, q.blank, wild) {101 return q.data102 }103 return -1104}105106// findSorted is the approximate match of sorted lookups: with dir 1 the107// last value <= key in ascending data, with dir -1 the last value >= key108// in descending data. Values of another kind are skipped.109func (q *seq) findSorted(key Value, dir int) int {110 found := -1111 if q.sparse && key.Kind != q.blank.Kind { // blanks are skipped: only the cells count112 c := q.walk()113 defer c.close()114 for a, ok := c.next(); ok; a, ok = c.next() {115 v := q.value(a)116 if v.Kind != key.Kind {117 continue118 }119 if compare(v, key)*dir > 0 {120 return found121 }122 found = q.index(a)123 }124 return found125 }126 for i := range q.data {127 v := q.at(i)128 if v.Kind != key.Kind {129 continue130 }131 if c := compare(v, key) * dir; c > 0 {132 return found133 }134 found = i135 }136 if v := q.blank; q.data < q.n && v.Kind == key.Kind && compare(v, key)*dir <= 0 {137 found = q.n - 1 // the blanks past the data all match; the last wins138 }139 return found140}141142// order is the entries a search visits, first to last (last to first143// with reverse): those that hold cells, and of the blanks, which are all144// the same, only the first met.145func (q *seq) order(reverse bool) []int {146 var out []int147 if !q.sparse {148 for i := range q.data {149 out = append(out, i)150 }151 if q.data < q.n {152 out = append(out, q.data)153 }154 if reverse {155 slices.Reverse(out)156 if q.data < q.n {157 out[0] = q.n - 1158 }159 }160 return out161 }162 out = q.positions()163 gap := -1 // the first blank in search order164 if !reverse {165 for gap = 0; gap < len(out) && out[gap] == gap; gap++ {166 }167 } else {168 for gap = q.n - 1; len(out) > 0 && q.n-1-gap < len(out) && out[len(out)-1-(q.n-1-gap)] == gap; gap-- {169 }170 }171 if gap >= 0 && gap < q.n {172 i, _ := slices.BinarySearch(out, gap)173 out = slices.Insert(out, i, gap)174 }175 if reverse {176 slices.Reverse(out)177 }178 return out179}