9 // RopeSplitLength defines how large can a string be before it is split into two nodes
10 RopeSplitLength = 1000
11 // RopeJoinLength defines how short can a string be before it is joined
13 // RopeRebalanceRatio = 1.2
16 // Min takes the min of two ints
17 func Min(a, b int) int {
24 // Max takes the max of two ints
25 func Max(a, b int) int {
32 // A Rope is a data structure for efficiently manipulating large strings
42 // NewRope returns a new rope from a given string
43 func NewRope(str string) *Rope {
47 r.len = utf8.RuneCountInString(r.value)
54 // Adjust modifies the rope so it is more balanced
55 func (r *Rope) Adjust() {
57 if r.len > RopeSplitLength {
58 divide := int(math.Floor(float64(r.len) / 2))
59 r.left = NewRope(r.value[:divide])
60 r.right = NewRope(r.value[divide:])
64 if r.len < RopeJoinLength {
65 r.value = r.left.String() + r.right.String()
73 // String returns the string representation of the rope
74 func (r *Rope) String() string {
78 return r.left.String() + r.right.String()
81 // Remove deletes a slice of the rope from start the to end (exclusive)
82 func (r *Rope) Remove(start, end int) {
84 r.value = string(append([]rune(r.value)[:start], []rune(r.value)[end:]...))
86 r.len = utf8.RuneCountInString(r.value)
88 leftStart := Min(start, r.left.len)
89 leftEnd := Min(end, r.left.len)
90 rightStart := Max(0, Min(start-r.left.len, r.right.len))
91 rightEnd := Max(0, Min(end-r.left.len, r.right.len))
92 if leftStart < r.left.len {
93 r.left.Remove(leftStart, leftEnd)
96 r.right.Remove(rightStart, rightEnd)
98 r.len = r.left.len + r.right.len
104 // Insert inserts a string into the rope at a specified position
105 func (r *Rope) Insert(pos int, value string) {
107 first := append([]rune(r.value)[:pos], []rune(value)...)
108 r.value = string(append(first, []rune(r.value)[pos:]...))
110 r.len = utf8.RuneCountInString(r.value)
112 if pos < r.left.len {
113 r.left.Insert(pos, value)
114 r.len = r.left.len + r.right.len
116 r.right.Insert(pos-r.left.len, value)