1
package rope
2

3
const leafMaxLen = 512 // 叶子节点最大长度
4

5
type Rope struct {
6
    weight int    // 左子树字符数（叶子节点为自身长度）
7
    left   *Rope
8
    right  *Rope
9
    leaf   string // 仅叶子节点有值
10
}
11

12
// 从字符串创建 Rope
13
func New(s string) *Rope {
14
    if len(s) <= leafMaxLen {
15
        return &Rope{weight: len(s), leaf: s}
16
    }
17
    mid := len(s) / 2
18
    left, right := New(s[:mid]), New(s[mid:])
19
    return &Rope{weight: left.Len(), left: left, right: right}
20
}
21

22
// 返回 Rope 的总字符数
23
func (r *Rope) Len() int {
24
    if r == nil {
25
        return 0
26
    }
27
    if r.leaf != "" {
28
        return len(r.leaf)
29
    }
30
    return r.weight + r.right.Len()
31
}
32

33
// 拼接两个 Rope，O(1)
34
func Concat(a, b *Rope) *Rope {
35
    if a == nil { return b }
36
    if b == nil { return a }
37
    return &Rope{weight: a.Len(), left: a, right: b}
38
}
39

40
// 索引第 i 个字符，O(log n)
41
func (r *Rope) Index(i int) byte {
42
    if r.leaf != "" {
43
        return r.leaf[i] // 叶子节点直接索引
44
    }
45
    if i < r.weight {
46
        return r.left.Index(i)
47
    }
48
    return r.right.Index(i - r.weight)
49
}
50

51
// 在位置 i 插入字符串，O(log n)
52
func (r *Rope) Insert(i int, s string) *Rope {
53
    left, right := r.Split(i)
54
    return Concat(Concat(left, New(s)), right)
55
}
56

57
// 在位置 i 分裂为两棵 Rope
58
func (r *Rope) Split(i int) (*Rope, *Rope) {
59
    if r.leaf != "" {
60
        return New(r.leaf[:i]), New(r.leaf[i:])
61
    }
62
    if i < r.weight {
63
        l, lr := r.left.Split(i)
64
        return l, Concat(lr, r.right)
65
    }
66
    rl, rr := r.right.Split(i - r.weight)
67
    return Concat(r.left, rl), rr
68
}

1
const LEAF_MAX = 512;
2

3
class Rope {
4
  constructor(
5
    public weight: number,
6
    public left: Rope | null = null,
7
    public right: Rope | null = null,
8
    public leaf: string = ""
9
  ) {}
10

11
  static from(s: string): Rope {
12
    if (s.length <= LEAF_MAX) {
13
      return new Rope(s.length, null, null, s);
14
    }
15
    const mid = Math.floor(s.length / 2);
16
    const left = Rope.from(s.slice(0, mid));
17
    const right = Rope.from(s.slice(mid));
18
    return new Rope(left.len(), left, right);
19
  }
20

21
  len(): number {
22
    if (this.leaf) return this.leaf.length;
23
    return this.weight + (this.right?.len() ?? 0);
24
  }
25

26
  static concat(a: Rope | null, b: Rope | null): Rope {
27
    if (!a) return b!;
28
    if (!b) return a;
29
    return new Rope(a.len(), a, b);
30
  }
31

32
  index(i: number): string {
33
    if (this.leaf) return this.leaf[i]; // 叶子节点直接索引
34
    if (i < this.weight) return this.left!.index(i);
35
    return this.right!.index(i - this.weight);
36
  }
37

38
  insert(i: number, s: string): Rope {
39
    const [left, right] = this.split(i);
40
    return Rope.concat(Rope.concat(left, Rope.from(s)), right);
41
  }
42

43
  split(i: number): [Rope, Rope] {
44
    if (this.leaf) {
45
      return [Rope.from(this.leaf.slice(0, i)), Rope.from(this.leaf.slice(i))];
46
    }
47
    if (i < this.weight) {
48
      const [l, lr] = this.left!.split(i);
49
      return [l, Rope.concat(lr, this.right)];
50
    }
51
    const [rl, rr] = this.right!.split(i - this.weight);
52
    return [Rope.concat(this.left, rl), rr];
53
  }
54
}