rope.go

   1 package main
   2
   3 import (
   4         "math"
   5         "unicode/utf8"
   6 )
   7
   8 const (
   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
  12         RopeJoinLength = 500
  13         // RopeRebalanceRatio = 1.2
  14 )
  15
  16 // Min takes the min of two ints
  17 func Min(a, b int) int {
  18         if a > b {
  19                 return b
  20         }
  21         return a
  22 }
  23
  24 // Max takes the max of two ints
  25 func Max(a, b int) int {
  26         if a > b {
  27                 return a
  28         }
  29         return b
  30 }
  31
  32 // A Rope is a data structure for efficiently manipulating large strings
  33 type Rope struct {
  34         left     *Rope
  35         right    *Rope
  36         value    string
  37         valueNil bool
  38
  39         len int
  40 }
  41
  42 // NewRope returns a new rope from a given string
  43 func NewRope(str string) *Rope {
  44         r := new(Rope)
  45         r.value = str
  46         r.valueNil = false
  47         r.len = utf8.RuneCountInString(r.value)
  48
  49         r.Adjust()
  50
  51         return r
  52 }
  53
  54 // Adjust modifies the rope so it is more balanced
  55 func (r *Rope) Adjust() {
  56         if !r.valueNil {
  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:])
  61                         r.valueNil = true
  62                 }
  63         } else {
  64                 if r.len < RopeJoinLength {
  65                         r.value = r.left.String() + r.right.String()
  66                         r.valueNil = false
  67                         r.left = nil
  68                         r.right = nil
  69                 }
  70         }
  71 }
  72
  73 // String returns the string representation of the rope
  74 func (r *Rope) String() string {
  75         if !r.valueNil {
  76                 return r.value
  77         }
  78         return r.left.String() + r.right.String()
  79 }
  80
  81 // Remove deletes a slice of the rope from start the to end (exclusive)
  82 func (r *Rope) Remove(start, end int) {
  83         if !r.valueNil {
  84                 r.value = string(append([]rune(r.value)[:start], []rune(r.value)[end:]...))
  85                 r.valueNil = false
  86                 r.len = utf8.RuneCountInString(r.value)
  87         } else {
  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)
  94                 }
  95                 if rightEnd > 0 {
  96                         r.right.Remove(rightStart, rightEnd)
  97                 }
  98                 r.len = r.left.len + r.right.len
  99         }
 100
 101         r.Adjust()
 102 }
 103
 104 // Insert inserts a string into the rope at a specified position
 105 func (r *Rope) Insert(pos int, value string) {
 106         if !r.valueNil {
 107                 first := append([]rune(r.value)[:pos], []rune(value)...)
 108                 r.value = string(append(first, []rune(r.value)[pos:]...))
 109                 r.valueNil = false
 110                 r.len = utf8.RuneCountInString(r.value)
 111         } else {
 112                 if pos < r.left.len {
 113                         r.left.Insert(pos, value)
 114                         r.len = r.left.len + r.right.len
 115                 } else {
 116                         r.right.Insert(pos-r.left.len, value)
 117                 }
 118         }
 119
 120         r.Adjust()
 121 }