1# buffer - growing buffers of text and bytes.2#3# Concatenating with + copies the whole string every time, so building a4# string piece by piece costs O(n^2). A buffer keeps the pieces apart and5# joins them once.67# Builder accumulates strings.8#9# b = buffer.Builder()10# b.Write("hello ")11# b.Write("world")12# b.String()13Builder = fn() {14 b = new()15 b.parts = []16 b.size = 01718 # Write appends s to the buffer and returns the number of bytes written.19 b.Write = fn(s) {20 if type(s) != "string" {21 s = string(s)22 }23 b.parts = append(b.parts, s)24 b.size = b.size + len(s)25 return len(s)26 }2728 # WriteByte appends a single byte given as its integer value.29 b.WriteByte = fn(c) { b.Write(string(bytes([c]))) }3031 # Len returns the number of bytes accumulated so far.32 b.Len = fn() { b.size }3334 # String returns the concatenation of everything written.35 #36 # The pieces are joined in pairs, and the pairs in pairs, until one is37 # left. Adding them up one at a time would copy everything accumulated so38 # far at every step, which is the O(n^2) this type exists to avoid - and39 # was what it did. Halving the count each round makes it O(n log n) of40 # copying, all of it done by the concatenation itself rather than a byte41 # at a time here.42 b.String = fn() {43 parts = b.parts4445 for len(parts) > 1 {46 merged = []47 for i = 0; i < len(parts); i += 2 {48 if i + 1 < len(parts) {49 merged = append(merged, parts[i] + parts[i + 1])50 } else {51 merged = append(merged, parts[i])52 }53 }54 parts = merged55 }5657 out = ""58 if len(parts) == 1 {59 out = parts[0]60 }61 # Collapse the pieces, further writes start from here.62 b.parts = [out]63 return out64 }6566 # Reset empties the buffer.67 b.Reset = fn() {68 b.parts = []69 b.size = 070 }7172 return b73}7475# Buffer accumulates bytes. Read and Write make it usable wherever a stream76# of bytes is expected.77Buffer = fn() {78 b = new()79 b.data = []80 b.off = 08182 # Write appends bytes, a string or a list of byte values.83 b.Write = fn(x) {84 t = type(x)85 if t == "string" {86 x = bytes(x)87 t = "bytes"88 }89 if t != "bytes" && t != "list" {90 return error("buffer: cannot write {t}")91 }9293 for i = 0; i < len(x); ++i {94 b.data = append(b.data, x[i])95 }96 return len(x)97 }9899 b.WriteByte = fn(c) {100 b.data = append(b.data, c)101 return 1102 }103104 # Len returns the number of bytes still to be read.105 b.Len = fn() { len(b.data) - b.off }106107 # Read returns up to n bytes and consumes them, or all of them if n is null.108 b.Read = fn(n) {109 if n == null || n > b.Len() {110 n = b.Len()111 }112 if n <= 0 {113 return bytes([])114 }115116 out = slice(b.data, b.off, b.off + n)117 b.off = b.off + n118 return bytes(out)119 }120121 # Bytes returns everything that hasn't been read, without consuming it.122 b.Bytes = fn() { bytes(slice(b.data, b.off, len(b.data))) }123124 b.String = fn() { string(b.Bytes()) }125126 b.Reset = fn() {127 b.data = []128 b.off = 0129 }130131 return b132}