+package main
+
+import (
+ "fmt"
+ "math"
+ "math/bits"
+ "strconv"
+ "strings"
+)
+
+const (
+ // chatHigh and chatLow are the limits of the chat view in bytes.
+ chatHigh = 128000
+ chatLow = 64000
+
+ // pending is the text of a line that is not built yet.
+ pending = "(not summarized yet: zoom it)"
+)
+
+// nodeReader gives the built nodes of a tree.
+type nodeReader interface {
+ Node(level, index int) (Node, bool)
+}
+
+// View is a list of tree nodes that covers messages 0 to end-1 without a gap,
+// oldest first. Each new message appends its leaf as a line. Once the size of
+// the view goes above high, one batch merges the most due sibling pairs until
+// the size is at most low. A batch merges only pairs whose parent is built. If
+// the batch cannot get to low, it continues at each new message until it does.
+//
+// The size of a line is the size of its node text, or the size of the pending
+// text when the node is not built.
+//
+// For the sibling pair (l, i) and (l, i+1), due is (T - last) / 2^l, with T the
+// number of messages and last the ID of the last message of the pair. That is
+// how long ago the pair ended, measured in its own line size. With a budget of
+// the length of Taelin's rollback push list, this order makes the same merges
+// as the push. The oldest pair wins a tie.
+type View struct {
+ high int
+ low int
+ lines []nodeKey
+ end int
+ merging bool
+}
+
+// viewState is the saved form of a View. The limits are not part of it.
+type viewState struct {
+ Lines [][2]int `json:"lines"`
+ Merging bool `json:"merging"`
+}
+
+// newView returns an empty view with the limits high and low.
+func newView(high, low int) *View {
+ return &View{
+ high: high,
+ low: low,
+ }
+}
+
+// restoreView returns the view of state with the limits high and low. Each line
+// must continue the one before it, and each line above level 0 must be built.
+func restoreView(state viewState, high, low int, tree nodeReader) (*View, error) {
+ v := newView(high, low)
+ v.merging = state.Merging
+ for _, pair := range state.Lines {
+ line := nodeKey{pair[0], pair[1]}
+ if line.level < 0 || line.level >= bits.UintSize-2 || line.index < 0 || line.index<<line.level != v.end {
+ return nil, fmt.Errorf("view line (%d, %d) does not start at message %d", line.level, line.index, v.end)
+ }
+
+ _, built := tree.Node(line.level, line.index)
+ if line.level > 0 && !built {
+ return nil, fmt.Errorf("view line (%d, %d) is not built", line.level, line.index)
+ }
+
+ v.lines = append(v.lines, line)
+ v.end = nodeEnd(line.level, line.index)
+ }
+
+ return v, nil
+}
+
+// State returns the saved form of the view.
+func (v *View) State() viewState {
+ state := viewState{
+ Lines: make([][2]int, len(v.lines)),
+ Merging: v.merging,
+ }
+
+ for n, line := range v.lines {
+ state.Lines[n] = [2]int{line.level, line.index}
+ }
+
+ return state
+}
+
+// Append adds the leaf of the next message as a line and merges when the view
+// is too large.
+func (v *View) Append(tree nodeReader) {
+ v.lines = append(v.lines, nodeKey{0, v.end})
+ v.end++
+ v.fit(tree)
+}
+
+func (v *View) fit(tree nodeReader) {
+ size := v.Size(tree)
+ if size > v.high {
+ v.merging = true
+ }
+
+ for v.merging && size > v.low {
+ best := v.mostDue(tree)
+ if best < 0 {
+ return
+ }
+
+ left, right := v.lines[best], v.lines[best+1]
+ parent := nodeKey{left.level + 1, left.index / 2}
+ size += lineSize(tree, parent) - lineSize(tree, left) - lineSize(tree, right)
+ v.lines[best] = parent
+ v.lines = append(v.lines[:best+1], v.lines[best+2:]...)
+ }
+
+ v.merging = false
+}
+
+// mostDue returns the position of the left line of the most due sibling pair
+// whose parent is built, or -1 when there is no such pair.
+func (v *View) mostDue(tree nodeReader) int {
+ best := -1
+ bestDue := 0.0
+ for n := 0; n+1 < len(v.lines); n++ {
+ left, right := v.lines[n], v.lines[n+1]
+ if left.index%2 != 0 || right.level != left.level || right.index != left.index+1 {
+ continue
+ }
+
+ _, built := tree.Node(left.level+1, left.index/2)
+ if !built {
+ continue
+ }
+
+ last := nodeEnd(right.level, right.index) - 1
+ due := math.Ldexp(float64(v.end-last), -left.level)
+ if best < 0 || due > bestDue {
+ best = n
+ bestDue = due
+ }
+ }
+
+ return best
+}
+
+// Size returns the sum of the line sizes.
+func (v *View) Size(tree nodeReader) int {
+ size := 0
+ for _, line := range v.lines {
+ size += lineSize(tree, line)
+ }
+
+ return size
+}
+
+// Render returns the view as the model reads it: one line "id+n|text" for each
+// node inside <chat> tags, with the newlines of the text as spaces.
+func (v *View) Render(tree nodeReader) string {
+ var text strings.Builder
+ text.WriteString("<chat>\n")
+ for _, line := range v.lines {
+ renderLine(&text, tree, line)
+ }
+
+ text.WriteString("</chat>")
+
+ return text.String()
+}
+
+// lineSize returns the size of a view line.
+func lineSize(tree nodeReader, line nodeKey) int {
+ node, built := tree.Node(line.level, line.index)
+ if !built {
+ return len(pending)
+ }
+
+ return node.Size
+}
+
+// renderLine writes one view line, "id+n|text", and a newline.
+func renderLine(text *strings.Builder, tree nodeReader, line nodeKey) {
+ body := pending
+ node, built := tree.Node(line.level, line.index)
+ if built {
+ body = strings.ReplaceAll(node.Text, "\n", " ")
+ }
+
+ text.WriteString(strconv.Itoa(line.index << line.level))
+ text.WriteByte('+')
+ text.WriteString(strconv.Itoa(1 << line.level))
+ text.WriteByte('|')
+ text.WriteString(body)
+ text.WriteByte('\n')
+}
projects / onechat / commitdiff