1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
package rope
import "io"
// A node representing the concatenation of two smaller nodes.
type concat struct {
// Subtrees. Neither may be nil or length zero.
Left, Right node
// Length of Left subtree. (relative index where the substrings meet)
Split int64
// Cached length of Right subtree, or 0 if out of range.
RLen rLenT
// Cached depth of the tree.
TreeDepth depthT
}
type rLenT uint32
func (c *concat) depth() depthT { return c.TreeDepth }
func (c *concat) length() int64 {
return c.Split + c.rLength()
}
func (c *concat) at(idx int64) byte {
if idx < c.Split {
return c.Left.at(idx)
}
return c.Right.at(idx - c.Split)
}
func (c *concat) rLength() int64 {
if c.RLen > 0 {
return int64(c.RLen)
}
return c.Right.length()
}
func (c *concat) WriteTo(w io.Writer) (n int64, err error) {
n, err = c.Left.WriteTo(w)
if err != nil {
return
}
m, err := c.Right.WriteTo(w)
return n + m, err
}
// Precondition: start < end
func (c *concat) slice(start, end int64) node {
// If only slicing into one side, recurse to that side.
if end <= c.Split {
return c.Left.slice(start, end)
}
if start >= c.Split {
return c.Right.slice(start-c.Split, end-c.Split)
}
clength := c.Split + c.rLength()
if start <= 0 && end >= clength {
return c
}
Left := c.Left
LeftLen := c.Split
if start > 0 || end < c.Split {
Left = Left.slice(start, end)
LeftLen = -1 // Recompute if needed.
}
Right := c.Right
RightLen := int64(c.RLen)
if start > c.Split || end < clength {
Right = c.Right.slice(start-c.Split, end-c.Split)
RightLen = -1 // Recompute if needed.
}
return conc(Left, Right, LeftLen, RightLen)
}
func (c *concat) dropPrefix(start int64) node {
switch {
case start <= 0:
return c
case start < c.Split:
return conc(c.Left.dropPrefix(start), c.Right,
c.Split-start, int64(c.RLen))
default: // start >= c.Split
return c.Right.dropPrefix(start - c.Split)
}
}
func (c *concat) dropPostfix(end int64) node {
switch {
case end <= 0:
return emptyNode
case end <= c.Split:
return c.Left.dropPostfix(end)
case end >= c.Split+c.rLength():
return c
default: // c.Split < end < c.length()
end -= c.Split
return conc(c.Left, c.Right.dropPostfix(end), c.Split, end)
}
}
func (c *concat) walkLeaves(f func(string) error) (err error) {
err = c.Left.walkLeaves(f)
if err == nil {
err = c.Right.walkLeaves(f)
}
return
}
func (c *concat) readAt(p []byte, start int64) (n int) {
if start < c.Split {
n = c.Left.readAt(p, start)
if int64(n) < c.Split-start && n != len(p) {
panic("incomplete readAt")
}
if n == len(p) {
return
}
}
m := c.Right.readAt(p[n:], start+int64(n)-c.Split)
return m + n
}
|
