1package sheet23import (4 "math/bits"5 "slices"6)78// occupancy records which rows of each column hold a cell, as bitmaps of9// blockRows rows, so the cells of a range are found in row order at the10// cost of what it holds, not its area: a whole column of a million rows11// with ten cells is ten visits.12//13// Columns and their blocks are found by index in slices grown to the14// last one used, so marking a cell costs no hashing.15type occupancy struct {16 cols []*colIndex // by column; nil for none17 colIDs []int // the columns holding cells, ascending18 n int // the cells marked19}2021// Rows of a column are indexed in blocks of blockRows, one bit each.22const (23 blockShift = 1024 blockRows = 1 << blockShift25 blockWords = blockRows / 6426)2728type rowBlock struct {29 bits [blockWords]uint6430 // rank counts the rows set in the words before each, so a row's31 // position among the block's is a popcount away (index).32 rank [blockWords]uint1633 n int34 stats *blockStats // the filled index's statistics, made on first use; see stats.go35 vals []slot // the stored index's cells, one per set row in order; see slot.go36}3738// index is the position of row bit of the block among its set rows, and39// whether it is set.40func (b *rowBlock) index(bit int) (int, bool) {41 w, m := bit>>6, uint64(1)<<(bit&63)42 x := b.bits[w]43 return int(b.rank[w]) + bits.OnesCount64(x&(m-1)), x&m != 044}4546// count adds d to the rank of the words after word w.47func (b *rowBlock) count(w, d int) {48 for j := w + 1; j < blockWords; j++ {49 b.rank[j] = uint16(int(b.rank[j]) + d)50 }51}5253// colIndex is the occupancy of one column: its blocks by number (nil54// for none), and the numbers in order.55type colIndex struct {56 blocks []*rowBlock57 ids []int58 n int59}6061// col is column c's index, or nil.62func (o *occupancy) col(c int) *colIndex {63 if c < 0 || c >= len(o.cols) {64 return nil65 }66 return o.cols[c]67}6869// block is block id of the column, or nil.70func (ci *colIndex) block(id int) *rowBlock {71 if ci == nil || id < 0 || id >= len(ci.blocks) {72 return nil73 }74 return ci.blocks[id]75}7677// has reports whether a holds a cell.78func (o *occupancy) has(a Addr) bool {79 b := o.col(a.Col).block(a.Row >> blockShift)80 bit := a.Row & (blockRows - 1)81 return b != nil && b.bits[bit>>6]&(1<<(bit&63)) != 082}8384// mark records a cell at a, which had none, and returns its block.85func (o *occupancy) mark(a Addr) *rowBlock {86 ci := o.col(a.Col)87 if ci == nil {88 ci = &colIndex{}89 if a.Col >= len(o.cols) {90 o.cols = slices.Grow(o.cols, a.Col+1-len(o.cols))[:a.Col+1]91 }92 o.cols[a.Col] = ci93 o.colIDs = insertSorted(o.colIDs, a.Col)94 }95 id := a.Row >> blockShift96 b := ci.block(id)97 if b == nil {98 b = &rowBlock{}99 if id >= len(ci.blocks) {100 ci.blocks = slices.Grow(ci.blocks, id+1-len(ci.blocks))[:id+1]101 }102 ci.blocks[id] = b103 ci.ids = insertSorted(ci.ids, id)104 }105 bit := a.Row & (blockRows - 1)106 b.bits[bit>>6] |= 1 << (bit & 63)107 b.count(bit>>6, 1)108 b.n++109 ci.n++110 o.n++111 return b112}113114// unmark records that a no longer holds a cell.115func (o *occupancy) unmark(a Addr) {116 ci := o.cols[a.Col]117 id := a.Row >> blockShift118 b := ci.blocks[id]119 bit := a.Row & (blockRows - 1)120 b.bits[bit>>6] &^= 1 << (bit & 63)121 b.count(bit>>6, -1)122 b.n--123 ci.n--124 o.n--125 if b.n == 0 {126 ci.blocks[id] = nil127 ci.ids = removeSorted(ci.ids, id)128 }129 if ci.n == 0 {130 o.cols[a.Col] = nil131 o.colIDs = removeSorted(o.colIDs, a.Col)132 }133}134135func insertSorted(s []int, v int) []int {136 i, found := slices.BinarySearch(s, v)137 if found {138 return s139 }140 return slices.Insert(s, i, v)141}142143func removeSorted(s []int, v int) []int {144 if i, found := slices.BinarySearch(s, v); found {145 return slices.Delete(s, i, i+1)146 }147 return s148}149150// colsIn returns the stored columns from c0 to c1, ascending. The slice151// is shared: callers mustn't keep it across changes.152func (o *occupancy) colsIn(c0, c1 int) []int {153 i, _ := slices.BinarySearch(o.colIDs, c0)154 j, _ := slices.BinarySearch(o.colIDs, c1+1)155 return o.colIDs[i:j]156}157158// blockIDs returns the numbers from b0 to b1 of the blocks that any of159// cols has, ascending.160func (o *occupancy) blockIDs(cols []int, b0, b1 int) []int {161 if len(cols) == 1 {162 ids := o.cols[cols[0]].ids163 i, _ := slices.BinarySearch(ids, b0)164 j, _ := slices.BinarySearch(ids, b1+1)165 return slices.Clone(ids[i:j])166 }167 var out []int168 for _, c := range cols {169 ids := o.cols[c].ids170 i, _ := slices.BinarySearch(ids, b0)171 j, _ := slices.BinarySearch(ids, b1+1)172 out = append(out, ids[i:j]...)173 }174 slices.Sort(out)175 return slices.Compact(out)176}177178// wordMask keeps the bits of word w that fall in rows lo..hi of a block.179func wordMask(w, lo, hi int) uint64 {180 m := ^uint64(0)181 if first := w << 6; lo > first {182 m &= ^uint64(0) << (lo - first)183 }184 if last := w<<6 + 63; hi < last {185 m &= ^uint64(0) >> (last - hi)186 }187 return m188}189190// colScan calls fn with each row from r0 to r1 of column c that holds a191// cell, in order, until fn returns false, and reports whether it went to192// the end. It allocates nothing; the column's cells must not be added193// or removed meanwhile.194func (o *occupancy) colScan(c, r0, r1 int, fn func(row int) bool) bool {195 ci := o.col(c)196 if ci == nil || r0 > r1 {197 return true198 }199 i, _ := slices.BinarySearch(ci.ids, r0>>blockShift)200 for ; i < len(ci.ids) && ci.ids[i] <= r1>>blockShift; i++ {201 id := ci.ids[i]202 b, base := ci.blocks[id], id<<blockShift203 lo, hi := max(r0-base, 0), min(r1-base, blockRows-1)204 for w := lo >> 6; w <= hi>>6; w++ {205 x := b.bits[w] & wordMask(w, lo, hi)206 for x != 0 {207 bit := bits.TrailingZeros64(x)208 x &^= 1 << bit209 if !fn(base + w<<6 + bit) {210 return false211 }212 }213 }214 }215 return true216}217218// colFill writes the cells of column c from row r0 to r1 that hold a219// cell into dst, in order, until dst is full, and returns how many it220// wrote: colScan without a call per cell, for reading a column in221// chunks.222func (o *occupancy) colFill(c, r0, r1 int, dst []Addr) int {223 ci := o.col(c)224 if ci == nil || r0 > r1 || len(dst) == 0 {225 return 0226 }227 n := 0228 i, _ := slices.BinarySearch(ci.ids, r0>>blockShift)229 for ; i < len(ci.ids) && ci.ids[i] <= r1>>blockShift; i++ {230 id := ci.ids[i]231 b, base := ci.blocks[id], id<<blockShift232 lo, hi := max(r0-base, 0), min(r1-base, blockRows-1)233 for w := lo >> 6; w <= hi>>6; w++ {234 x := b.bits[w] & wordMask(w, lo, hi)235 for x != 0 {236 bit := bits.TrailingZeros64(x)237 x &^= 1 << bit238 dst[n] = Addr{Col: c, Row: base + w<<6 + bit}239 if n++; n == len(dst) {240 return n241 }242 }243 }244 }245 return n246}247248// nextRow returns the first row of column c at or after row (dir 1), or249// at or before it (dir -1), that holds a cell.250func (o *occupancy) nextRow(c, row, dir int) (int, bool) {251 ci := o.col(c)252 if ci == nil || row < 0 {253 return 0, false254 }255 id := row >> blockShift256 i, _ := slices.BinarySearch(ci.ids, id)257 if dir > 0 {258 for ; i < len(ci.ids); i++ {259 b := ci.ids[i]260 from := 0261 if b == id {262 from = row & (blockRows - 1)263 }264 if r, ok := ci.blocks[b].first(from); ok {265 return b<<blockShift + r, true266 }267 }268 return 0, false269 }270 if i == len(ci.ids) || ci.ids[i] != id {271 i--272 }273 for ; i >= 0; i-- {274 b := ci.ids[i]275 to := blockRows - 1276 if b == id {277 to = row & (blockRows - 1)278 }279 if r, ok := ci.blocks[b].last(to); ok {280 return b<<blockShift + r, true281 }282 }283 return 0, false284}285286// first is the lowest set row at or after from.287func (b *rowBlock) first(from int) (int, bool) {288 for w := from >> 6; w < blockWords; w++ {289 x := b.bits[w]290 if w == from>>6 {291 x &= ^uint64(0) << (from & 63)292 }293 if x != 0 {294 return w<<6 + bits.TrailingZeros64(x), true295 }296 }297 return 0, false298}299300// last is the highest set row at or before to.301func (b *rowBlock) last(to int) (int, bool) {302 for w := to >> 6; w >= 0; w-- {303 x := b.bits[w]304 if w == to>>6 {305 x &= ^uint64(0) >> (63 - to&63)306 }307 if x != 0 {308 return w<<6 + 63 - bits.LeadingZeros64(x), true309 }310 }311 return 0, false312}313314// bounds returns the smallest range holding every stored cell of r, and315// false if r holds none. It costs a few steps per stored column of r.316func (o *occupancy) bounds(r Rect) (Rect, bool) {317 out, found := Rect{}, false318 for _, c := range o.colsIn(r.From.Col, r.To.Col) {319 top, ok := o.nextRow(c, r.From.Row, 1)320 if !ok || top > r.To.Row {321 continue322 }323 bottom, _ := o.nextRow(c, r.To.Row, -1)324 if !found {325 out, found = Rect{From: Addr{Col: c, Row: top}, To: Addr{Col: c, Row: bottom}}, true326 continue327 }328 out.From.Row, out.To.Row = min(out.From.Row, top), max(out.To.Row, bottom)329 out.To.Col = c330 }331 return out, found332}333334// countIn is the number of cells in rows r0 to r1 of column c, counted335// by block: whole blocks by their count, the ends by popcount.336func (o *occupancy) countIn(c, r0, r1 int) int {337 ci := o.col(c)338 if ci == nil || r0 > r1 {339 return 0340 }341 n := 0342 i, _ := slices.BinarySearch(ci.ids, r0>>blockShift)343 for ; i < len(ci.ids) && ci.ids[i] <= r1>>blockShift; i++ {344 id := ci.ids[i]345 b, base := ci.blocks[id], id<<blockShift346 lo, hi := max(r0-base, 0), min(r1-base, blockRows-1)347 if lo == 0 && hi == blockRows-1 {348 n += b.n349 continue350 }351 for w := lo >> 6; w <= hi>>6; w++ {352 n += bits.OnesCount64(b.bits[w] & wordMask(w, lo, hi))353 }354 }355 return n356}