|
0
|
1 import { cleanUpLine } from "../line/line_data.js"
|
|
|
2 import { indexOf } from "../util/misc.js"
|
|
|
3 import { signalLater } from "../util/operation_group.js"
|
|
|
4
|
|
|
5 // The document is represented as a BTree consisting of leaves, with
|
|
|
6 // chunk of lines in them, and branches, with up to ten leaves or
|
|
|
7 // other branch nodes below them. The top node is always a branch
|
|
|
8 // node, and is the document object itself (meaning it has
|
|
|
9 // additional methods and properties).
|
|
|
10 //
|
|
|
11 // All nodes have parent links. The tree is used both to go from
|
|
|
12 // line numbers to line objects, and to go from objects to numbers.
|
|
|
13 // It also indexes by height, and is used to convert between height
|
|
|
14 // and line object, and to find the total height of the document.
|
|
|
15 //
|
|
|
16 // See also http://marijnhaverbeke.nl/blog/codemirror-line-tree.html
|
|
|
17
|
|
|
18 export function LeafChunk(lines) {
|
|
|
19 this.lines = lines
|
|
|
20 this.parent = null
|
|
|
21 let height = 0
|
|
|
22 for (let i = 0; i < lines.length; ++i) {
|
|
|
23 lines[i].parent = this
|
|
|
24 height += lines[i].height
|
|
|
25 }
|
|
|
26 this.height = height
|
|
|
27 }
|
|
|
28
|
|
|
29 LeafChunk.prototype = {
|
|
|
30 chunkSize() { return this.lines.length },
|
|
|
31
|
|
|
32 // Remove the n lines at offset 'at'.
|
|
|
33 removeInner(at, n) {
|
|
|
34 for (let i = at, e = at + n; i < e; ++i) {
|
|
|
35 let line = this.lines[i]
|
|
|
36 this.height -= line.height
|
|
|
37 cleanUpLine(line)
|
|
|
38 signalLater(line, "delete")
|
|
|
39 }
|
|
|
40 this.lines.splice(at, n)
|
|
|
41 },
|
|
|
42
|
|
|
43 // Helper used to collapse a small branch into a single leaf.
|
|
|
44 collapse(lines) {
|
|
|
45 lines.push.apply(lines, this.lines)
|
|
|
46 },
|
|
|
47
|
|
|
48 // Insert the given array of lines at offset 'at', count them as
|
|
|
49 // having the given height.
|
|
|
50 insertInner(at, lines, height) {
|
|
|
51 this.height += height
|
|
|
52 this.lines = this.lines.slice(0, at).concat(lines).concat(this.lines.slice(at))
|
|
|
53 for (let i = 0; i < lines.length; ++i) lines[i].parent = this
|
|
|
54 },
|
|
|
55
|
|
|
56 // Used to iterate over a part of the tree.
|
|
|
57 iterN(at, n, op) {
|
|
|
58 for (let e = at + n; at < e; ++at)
|
|
|
59 if (op(this.lines[at])) return true
|
|
|
60 }
|
|
|
61 }
|
|
|
62
|
|
|
63 export function BranchChunk(children) {
|
|
|
64 this.children = children
|
|
|
65 let size = 0, height = 0
|
|
|
66 for (let i = 0; i < children.length; ++i) {
|
|
|
67 let ch = children[i]
|
|
|
68 size += ch.chunkSize(); height += ch.height
|
|
|
69 ch.parent = this
|
|
|
70 }
|
|
|
71 this.size = size
|
|
|
72 this.height = height
|
|
|
73 this.parent = null
|
|
|
74 }
|
|
|
75
|
|
|
76 BranchChunk.prototype = {
|
|
|
77 chunkSize() { return this.size },
|
|
|
78
|
|
|
79 removeInner(at, n) {
|
|
|
80 this.size -= n
|
|
|
81 for (let i = 0; i < this.children.length; ++i) {
|
|
|
82 let child = this.children[i], sz = child.chunkSize()
|
|
|
83 if (at < sz) {
|
|
|
84 let rm = Math.min(n, sz - at), oldHeight = child.height
|
|
|
85 child.removeInner(at, rm)
|
|
|
86 this.height -= oldHeight - child.height
|
|
|
87 if (sz == rm) { this.children.splice(i--, 1); child.parent = null }
|
|
|
88 if ((n -= rm) == 0) break
|
|
|
89 at = 0
|
|
|
90 } else at -= sz
|
|
|
91 }
|
|
|
92 // If the result is smaller than 25 lines, ensure that it is a
|
|
|
93 // single leaf node.
|
|
|
94 if (this.size - n < 25 &&
|
|
|
95 (this.children.length > 1 || !(this.children[0] instanceof LeafChunk))) {
|
|
|
96 let lines = []
|
|
|
97 this.collapse(lines)
|
|
|
98 this.children = [new LeafChunk(lines)]
|
|
|
99 this.children[0].parent = this
|
|
|
100 }
|
|
|
101 },
|
|
|
102
|
|
|
103 collapse(lines) {
|
|
|
104 for (let i = 0; i < this.children.length; ++i) this.children[i].collapse(lines)
|
|
|
105 },
|
|
|
106
|
|
|
107 insertInner(at, lines, height) {
|
|
|
108 this.size += lines.length
|
|
|
109 this.height += height
|
|
|
110 for (let i = 0; i < this.children.length; ++i) {
|
|
|
111 let child = this.children[i], sz = child.chunkSize()
|
|
|
112 if (at <= sz) {
|
|
|
113 child.insertInner(at, lines, height)
|
|
|
114 if (child.lines && child.lines.length > 50) {
|
|
|
115 // To avoid memory thrashing when child.lines is huge (e.g. first view of a large file), it's never spliced.
|
|
|
116 // Instead, small slices are taken. They're taken in order because sequential memory accesses are fastest.
|
|
|
117 let remaining = child.lines.length % 25 + 25
|
|
|
118 for (let pos = remaining; pos < child.lines.length;) {
|
|
|
119 let leaf = new LeafChunk(child.lines.slice(pos, pos += 25))
|
|
|
120 child.height -= leaf.height
|
|
|
121 this.children.splice(++i, 0, leaf)
|
|
|
122 leaf.parent = this
|
|
|
123 }
|
|
|
124 child.lines = child.lines.slice(0, remaining)
|
|
|
125 this.maybeSpill()
|
|
|
126 }
|
|
|
127 break
|
|
|
128 }
|
|
|
129 at -= sz
|
|
|
130 }
|
|
|
131 },
|
|
|
132
|
|
|
133 // When a node has grown, check whether it should be split.
|
|
|
134 maybeSpill() {
|
|
|
135 if (this.children.length <= 10) return
|
|
|
136 let me = this
|
|
|
137 do {
|
|
|
138 let spilled = me.children.splice(me.children.length - 5, 5)
|
|
|
139 let sibling = new BranchChunk(spilled)
|
|
|
140 if (!me.parent) { // Become the parent node
|
|
|
141 let copy = new BranchChunk(me.children)
|
|
|
142 copy.parent = me
|
|
|
143 me.children = [copy, sibling]
|
|
|
144 me = copy
|
|
|
145 } else {
|
|
|
146 me.size -= sibling.size
|
|
|
147 me.height -= sibling.height
|
|
|
148 let myIndex = indexOf(me.parent.children, me)
|
|
|
149 me.parent.children.splice(myIndex + 1, 0, sibling)
|
|
|
150 }
|
|
|
151 sibling.parent = me.parent
|
|
|
152 } while (me.children.length > 10)
|
|
|
153 me.parent.maybeSpill()
|
|
|
154 },
|
|
|
155
|
|
|
156 iterN(at, n, op) {
|
|
|
157 for (let i = 0; i < this.children.length; ++i) {
|
|
|
158 let child = this.children[i], sz = child.chunkSize()
|
|
|
159 if (at < sz) {
|
|
|
160 let used = Math.min(n, sz - at)
|
|
|
161 if (child.iterN(at, used, op)) return true
|
|
|
162 if ((n -= used) == 0) break
|
|
|
163 at = 0
|
|
|
164 } else at -= sz
|
|
|
165 }
|
|
|
166 }
|
|
|
167 }
|
