From fe5256d1b90257f31bd30df78ac5a7a62cd6ddc4 Mon Sep 17 00:00:00 2001
From: "Michael D. Lowis" <mike@mdlowis.com>
Date: Thu, 2 Nov 2017 22:02:17 -0400
Subject: [PATCH] added getb function and height tracking to rope

---
 lib/rope.ml         | 45 ++++++++++++++++++++++++++++++++++-----------
 lib/rope.mli        |  5 ++++-
 tests/rope_tests.ml | 10 +++++-----
 3 files changed, 43 insertions(+), 17 deletions(-)

diff --git a/lib/rope.ml b/lib/rope.ml
index 62221bb..9956d51 100644
--- a/lib/rope.ml
+++ b/lib/rope.ml
@@ -1,8 +1,9 @@
 exception Out_of_bounds of string
+exception Bad_rotation
 
 type t =
   | Leaf of string * int * int
-  | Node of t * t * int
+  | Node of t * t * int * int
 type rope = t
 type rune = int
 
@@ -12,8 +13,12 @@ let from_string s =
   Leaf (s, 0, (String.length s))
 
 let length = function
-  | Leaf (_,_,l) -> l
-  | Node (_,_,l) -> l
+  | Leaf (_,_,l)   -> l
+  | Node (_,_,_,l) -> l
+
+let height = function
+  | Leaf (_,_,_)   -> 0
+  | Node (_,_,h,_) -> h
 
 let limit_index rope i =
   if i < 0 then 0
@@ -29,11 +34,17 @@ let check_index rope i =
     raise (Out_of_bounds "Rope.check_index")
 
 let join left right =
-  let left_len = (length left) in
-  let right_len = (length right) in
-  if left_len == 0 then right
-  else if right_len == 0 then left
-  else Node (left, right, (length left) + (length right))
+  let llen = (length left) and rlen = (length right) in
+  if llen == 0 then right
+  else if rlen == 0 then left
+  else
+    let lh = (height left) and rh = (height right) in
+    let nh = 1 + lh + rh in
+    let n = Node (left, right, nh, llen + rlen) in
+    match (lh - rh) with
+    | 0  -> n
+    | 1  -> n
+    | -1 -> n
 
 let rec split rope i =
   if i < 0 || i > (length rope) then
@@ -41,7 +52,7 @@ let rec split rope i =
   match rope with
   | Leaf (s,off,len) ->
       (Leaf (s, off,  i), Leaf (s, (off + i), len - (i)))
-  | Node (l,r,len) ->
+  | Node (l,r,h,len) ->
       let left_len = (length l) in
       if i < left_len then
         let (sl,sr) = (split l i) in
@@ -55,6 +66,18 @@ let del rope i j =
   let (r_left,r_right) = split l_right (j - i) in
   (join l_left r_right)
 
+let rec getb rope i =
+  check_index rope i;
+  match rope with
+  | Leaf (s,off,_) ->
+      s.[off + i]
+  | Node (l,r,h,len) ->
+      let left_len = (length l) in
+      if i < left_len then
+        getb l i
+      else
+        getb r (i - left_len)
+
 let rec getc rope i =
   check_index rope i;
   match rope with
@@ -66,7 +89,7 @@ let rec getc rope i =
         0x0A
       else
         c
-  | Node (l,r,len) ->
+  | Node (l,r,h,len) ->
       let left_len = (length l) in
       if i < left_len then
         getc l i
@@ -87,7 +110,7 @@ let gets rope i j =
   let buf = Bytes.create (j - i) in
   iteri_from
     (fun n c ->
-      Bytes.set buf (n - i) (Char.chr (getc rope i));
+      Bytes.set buf (n - i) (getb rope i);
       (n <= j))
     rope i;
   Bytes.unsafe_to_string buf
diff --git a/lib/rope.mli b/lib/rope.mli
index 900084a..0f7e63f 100644
--- a/lib/rope.mli
+++ b/lib/rope.mli
@@ -1,8 +1,9 @@
 exception Out_of_bounds of string
+exception Bad_rotation
 
 type t =
   | Leaf of string * int * int
-  | Node of t * t * int
+  | Node of t * t * int * int
 type rope = t
 type rune = int
 
@@ -10,6 +11,7 @@ val empty : rope
 val from_string : string -> rope
 
 val length : rope -> int
+val height : rope -> int
 val limit_index : rope -> int -> int
 val last : rope -> int
 
@@ -20,6 +22,7 @@ val del : rope -> int -> int -> rope
 val iter_from : (rune -> bool) -> rope -> int -> unit
 val iteri_from : (int -> rune -> bool) -> rope -> int -> unit
 
+val getb : rope -> int -> char
 val getc : rope -> int -> rune
 val putc : rope -> int -> rune -> rope
 val gets : rope -> int -> int -> string
diff --git a/tests/rope_tests.ml b/tests/rope_tests.ml
index 93303cf..5ec2bbf 100644
--- a/tests/rope_tests.ml
+++ b/tests/rope_tests.ml
@@ -22,7 +22,7 @@ let  () =
     let right =  Leaf("a", 0, 1) in
     let rope  = (join left right) in
     assert( match rope with
-    | Node (l,r,2) -> (l == left && r == right)
+    | Node (l,r,h,2) -> (l == left && r == right)
     | _ -> false)
   );
   test "join : join a rope with a leaf (l to r)" (fun () ->
@@ -30,7 +30,7 @@ let  () =
     let right =  Leaf("a", 0, 1) in
     let rope  = (join left right) in
     assert( match rope with
-    | Node (l,r,3) -> (l == left && r == right)
+    | Node (l,r,h,3) -> (l == left && r == right)
     | _ -> false)
   );
   test "join : join a rope with a leaf (r to l)" (fun () ->
@@ -38,7 +38,7 @@ let  () =
     let right = join (Leaf("a", 0, 1)) (Leaf("a", 0, 1)) in
     let rope  = (join left right) in
     assert( match rope with
-    | Node (l,r,3) -> (l == left && r == right)
+    | Node (l,r,h,3) -> (l == left && r == right)
     | _ -> false)
   );
 
@@ -66,11 +66,11 @@ let  () =
     assert( (getc rope (2)) == Char.code 'c' );
   );
   test "getc : return index 0 of rope" (fun () ->
-    let rope = Node((Leaf("a", 0, 1)), (Leaf("b", 0, 1)), 2) in
+    let rope = Node((Leaf("a", 0, 1)), (Leaf("b", 0, 1)), 0, 2) in
     assert( (getc rope (0)) == Char.code 'a' );
   );
   test "getc : return index 1 of rope" (fun () ->
-    let rope = Node((Leaf("a", 0, 1)), (Leaf("b", 0, 1)), 2) in
+    let rope = Node((Leaf("a", 0, 1)), (Leaf("b", 0, 1)), 0, 2) in
     assert( (getc rope (1)) == Char.code 'b' );
   );
   test "getc : return \\n for \\r\\n" (fun () ->
-- 
2.52.0