Tree arranges a sequence of chunks produced by a Splitter into a "hashsplit tree." The result is an iterator of TreeNode/level pairs in a particular order; see details below. The final pair in the sequence is the root of the tree. A hashsplit tree provides another level of space-and-bandwidth savin
(inp iter.Seq2[[]byte, int])
| 265 | // |
| 266 | // (See https://pkg.go.dev/github.com/bobg/seqs#Map2 for an explanation of the Map2 function used here.) |
| 267 | func Tree(inp iter.Seq2[[]byte, int]) iter.Seq2[*TreeNode, int] { |
| 268 | return func(yield func(*TreeNode, int) bool) { |
| 269 | levels := []*TreeNode{{}} // One empty level-0 node. |
| 270 | for chunk, level := range inp { |
| 271 | levels[0].Chunks = append(levels[0].Chunks, chunk) |
| 272 | for _, n := range levels { |
| 273 | n.Size += uint64(len(chunk)) |
| 274 | } |
| 275 | for i := 0; i < level; i++ { |
| 276 | if i == len(levels)-1 { |
| 277 | levels = append(levels, &TreeNode{ |
| 278 | Size: levels[i].Size, |
| 279 | }) |
| 280 | } |
| 281 | |
| 282 | n := levels[i] |
| 283 | levels[i+1].Children = append(levels[i+1].Children, n) |
| 284 | |
| 285 | if !yield(n, i) { |
| 286 | return |
| 287 | } |
| 288 | |
| 289 | levels[i] = &TreeNode{ |
| 290 | Offset: levels[i+1].Offset + levels[i+1].Size, |
| 291 | } |
| 292 | } |
| 293 | } |
| 294 | |
| 295 | if len(levels[0].Chunks) == 0 { |
| 296 | return |
| 297 | } |
| 298 | |
| 299 | for i := 0; i < len(levels)-1; i++ { |
| 300 | levels[i+1].Children = append(levels[i+1].Children, levels[i]) |
| 301 | } |
| 302 | |
| 303 | top := len(levels) - 1 |
| 304 | for top > 0 && len(levels[top].Children) == 1 { |
| 305 | top-- |
| 306 | } |
| 307 | for i := 0; i <= top; i++ { |
| 308 | if !yield(levels[i], i) { |
| 309 | return |
| 310 | } |
| 311 | } |
| 312 | } |
| 313 | } |
| 314 | |
| 315 | // Root takes the output of [Tree] and returns the root of the tree. |
| 316 | // It does this by consuming the iterator and returning the last node, |