From fe122c32160517a25d469f697019947f9ea15ddc Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Mon, 13 Nov 2017 21:15:44 -0500 Subject: [PATCH] fleshed out tests for rope module --- docs/Buf.Cursor.html | 2 +- docs/Buf.html | 4 +- docs/Cfg.Color.Syntax.html | 2 +- docs/Cfg.Color.html | 4 +- docs/Cfg.html | 4 +- docs/Draw.Cursor.html | 2 +- docs/Draw.html | 4 +- docs/Misc.html | 2 +- docs/Rope.html | 5 +- docs/Scrollmap.html | 2 +- docs/View.html | 2 +- docs/X11.GlyphMap.html | 2 +- docs/X11.Rune.html | 2 +- docs/X11.html | 6 +-- docs/index.html | 7 +-- docs/index_exceptions.html | 4 +- docs/index_modules.html | 18 +++---- docs/index_types.html | 16 +++---- docs/index_values.html | 46 +++++++++--------- docs/type_X11.GlyphMap.html | 1 + lib/rope.ml | 37 +++----------- lib/rope.mli | 2 +- tests/rope_tests.ml | 96 ++++++++++++++++++++++++++++--------- 23 files changed, 148 insertions(+), 122 deletions(-) diff --git a/docs/Buf.Cursor.html b/docs/Buf.Cursor.html index f55b43b..2952d51 100644 --- a/docs/Buf.Cursor.html +++ b/docs/Buf.Cursor.html @@ -24,7 +24,7 @@

Module Buf.Cursor

module Cursor: sig .. end

module Cursor: sig .. end

type csr = {

diff --git a/docs/Buf.html b/docs/Buf.html index fef0b39..2b5147f 100644 --- a/docs/Buf.html +++ b/docs/Buf.html @@ -28,7 +28,7 @@

Module Buf

module Buf: sig .. end

module Buf: sig .. end

type buf = {

@@ -104,7 +104,7 @@

val length : buf -> int

val iteri : (int -> Rope.rune -> bool) -> buf -> int -> unit

val iter : (Rope.rune -> bool) -> buf -> int -> unit

module Cursor: sig .. end

module Cursor: sig .. end

val move_to : dest -> buf -> int -> int

val nextc : buf -> int -> int

val prevc : buf -> int -> int

diff --git a/docs/Cfg.Color.Syntax.html b/docs/Cfg.Color.Syntax.html index 4e24f31..1d69c7a 100644 --- a/docs/Cfg.Color.Syntax.html +++ b/docs/Cfg.Color.Syntax.html @@ -24,7 +24,7 @@

Module Cfg.Color.Syntax

module Syntax: sig .. end

module Syntax: sig .. end

val normal : int

val comment : int

diff --git a/docs/Cfg.Color.html b/docs/Cfg.Color.html index 71da952..0ae0ac9 100644 --- a/docs/Cfg.Color.html +++ b/docs/Cfg.Color.html @@ -24,7 +24,7 @@

Module Cfg.Color

module Color: sig .. end

module Color: sig .. end

val palette : int array

val scroll_nor : int * int

@@ -39,4 +39,4 @@

val edit_csr : int

val edit_rul : int

val borders : int * int

module Syntax: sig .. end

\ No newline at end of file +

module Syntax: sig .. end

\ No newline at end of file diff --git a/docs/Cfg.html b/docs/Cfg.html index 6a81cb1..b566741 100644 --- a/docs/Cfg.html +++ b/docs/Cfg.html @@ -28,7 +28,7 @@

Module Cfg

module Cfg: sig .. end

module Cfg: sig .. end

val boolvar : string -> bool -> bool

val intvar : string -> int -> int

@@ -51,4 +51,4 @@

val scroll_lines : int

val dbl_click_time : int

val max_scan_dist : int

module Color: sig .. end

\ No newline at end of file +

module Color: sig .. end

\ No newline at end of file diff --git a/docs/Draw.Cursor.html b/docs/Draw.Cursor.html index 6dd4c39..425675f 100644 --- a/docs/Draw.Cursor.html +++ b/docs/Draw.Cursor.html @@ -24,7 +24,7 @@

Module Draw.Cursor

module Cursor: sig .. end

module Cursor: sig .. end

type t = {

diff --git a/docs/Draw.html b/docs/Draw.html index 92f03a4..409af29 100644 --- a/docs/Draw.html +++ b/docs/Draw.html @@ -28,14 +28,14 @@

Module Draw

module Draw: sig .. end

module Draw: sig .. end

val font : X11.font

val font_height : int

val tabglyph : int

val tabwidth : int

val glyph_width : X11.glyph -> int

module Cursor: sig .. end

module Cursor: sig .. end

val rectangle : int -> int -> int -> Cursor.t -> unit

val dark_bkg : int -> int -> Cursor.t -> unit

val light_bkg : int -> int -> Cursor.t -> unit

diff --git a/docs/Misc.html b/docs/Misc.html index 3f975b4..287bd85 100644 --- a/docs/Misc.html +++ b/docs/Misc.html @@ -26,6 +26,6 @@

Module Misc

module Misc: sig .. end

module Misc: sig .. end

val load_file : string -> string

\ No newline at end of file diff --git a/docs/Rope.html b/docs/Rope.html index 1dafc57..6b235d1 100644 --- a/docs/Rope.html +++ b/docs/Rope.html @@ -28,7 +28,7 @@

Module Rope

module Rope: sig .. end

module Rope: sig .. end

exception Out_of_bounds of string

@@ -65,11 +65,10 @@

val is_leaf : t -> bool

val limit_index : t -> int -> int

val last : t -> int

val check_index : t -> int -> unit

val getb : t -> int -> char

val getc : t -> int -> int

val iteri : (int -> int -> bool) -> t -> int -> unit

val gets : t -> int -> int -> string

val to_string : t -> string

val flatten : t -> t

val join : t -> t -> t

val join_special : t -> t -> t -> t

diff --git a/docs/Scrollmap.html b/docs/Scrollmap.html index be5b11d..36b4e01 100644 --- a/docs/Scrollmap.html +++ b/docs/Scrollmap.html @@ -28,7 +28,7 @@

Module Scrollmap

module Scrollmap: sig .. end

module Scrollmap: sig .. end

type t = {

diff --git a/docs/View.html b/docs/View.html index 2d6e1fa..2ad94d5 100644 --- a/docs/View.html +++ b/docs/View.html @@ -26,7 +26,7 @@

Module View

module View: sig .. end

module View: sig .. end

type t = {

diff --git a/docs/X11.GlyphMap.html b/docs/X11.GlyphMap.html index e94cdda..a603a14 100644 --- a/docs/X11.GlyphMap.html +++ b/docs/X11.GlyphMap.html @@ -26,5 +26,5 @@

Module X11.GlyphMap

module GlyphMap: Map.Make(Rune)

module GlyphMap: Map.Make(Rune)

\ No newline at end of file diff --git a/docs/X11.Rune.html b/docs/X11.Rune.html index 2a9f928..38c5d18 100644 --- a/docs/X11.Rune.html +++ b/docs/X11.Rune.html @@ -26,7 +26,7 @@

Module X11.Rune

module Rune: sig .. end

module Rune: sig .. end

type t = int

diff --git a/docs/X11.html b/docs/X11.html index 6271273..dc39ef4 100644 --- a/docs/X11.html +++ b/docs/X11.html @@ -28,7 +28,7 @@

Module X11

module X11: sig .. end

module X11: sig .. end

type xatom

@@ -456,8 +456,8 @@ -

module Rune: sig .. end

module GlyphMap: Map.Make(Rune)

module Rune: sig .. end

module GlyphMap: Map.Make(Rune)

val connect : unit -> unit

val disconnect : unit -> unit

val make_window : int -> int -> xwin

diff --git a/docs/index.html b/docs/index.html index d21b245..6cfc26c 100644 --- a/docs/index.html +++ b/docs/index.html @@ -19,15 +19,16 @@ -

-

-

+ + +

diff --git a/docs/index_exceptions.html b/docs/index_exceptions.html index b674928..6356339 100644 --- a/docs/index_exceptions.html +++ b/docs/index_exceptions.html @@ -22,10 +22,10 @@

Index of exceptions

Misc
X11
Cfg

- + - +

B
B
Bad_rotation [Rope]
O
O
Out_of_bounds [Rope]

diff --git a/docs/index_modules.html b/docs/index_modules.html index 1407eb6..d23f065 100644 --- a/docs/index_modules.html +++ b/docs/index_modules.html @@ -22,10 +22,10 @@

Index of modules

- + - + @@ -34,29 +34,29 @@ - + - + - + - + - + - + - +

B
B
Buf
C
C
Cfg
Color [Cfg]
Cursor [Buf]
D
D
Draw
G
G
GlyphMap [X11]
M
M
Misc
R
R
Rope
Rune [X11]
S
S
Scrollmap
Syntax [Cfg.Color]
V
V
View
X
X
X11

diff --git a/docs/index_types.html b/docs/index_types.html index c9e1ebc..8e00052 100644 --- a/docs/index_types.html +++ b/docs/index_types.html @@ -22,27 +22,27 @@

Index of types

- + - + - + - + - + - + - + @@ -57,7 +57,7 @@ - + diff --git a/docs/index_values.html b/docs/index_values.html index 7e34b42..9bd4278 100644 --- a/docs/index_values.html +++ b/docs/index_values.html @@ -22,7 +22,7 @@

Index of values

B
B
buf [Buf]
C
C
csr [Buf.Cursor]
D
D
dest [Buf]
F
F
font [X11]
G
G
glyph [X11]
R
R
rope [Rope]
rune [Rope]
T
T
t [View]
t [Scrollmap]
t [X11.Rune]
X
X
xatom [X11]
xcfgvar [X11]

- + @@ -35,13 +35,11 @@ - + - - @@ -60,7 +58,7 @@ - + @@ -87,7 +85,7 @@ - + @@ -116,7 +114,7 @@ - + @@ -139,11 +137,9 @@ - + - - @@ -160,14 +156,14 @@ - + - + @@ -198,15 +194,15 @@ - + - + - + @@ -225,7 +221,7 @@ - + @@ -252,7 +248,7 @@ - + @@ -273,12 +269,12 @@ - + - + @@ -311,7 +307,7 @@ - + @@ -324,7 +320,7 @@ - + @@ -361,7 +357,7 @@ - + @@ -380,18 +376,20 @@ + + - + - + diff --git a/docs/type_X11.GlyphMap.html b/docs/type_X11.GlyphMap.html index 80ee296..b388f49 100644 --- a/docs/type_X11.GlyphMap.html +++ b/docs/type_X11.GlyphMap.html @@ -24,6 +24,7 @@   val is_empty : 'a t -> bool
  val mem : key -> 'a t -> bool
  val add : key -> 'a -> 'a t -> 'a t
+  val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
  val singleton : key -> 'a -> 'a t
  val remove : key -> 'a t -> 'a t
  val merge :
diff --git a/lib/rope.ml b/lib/rope.ml index 873c114..86ff9ef 100644 --- a/lib/rope.ml +++ b/lib/rope.ml @@ -33,36 +33,10 @@ let limit_index rope i = let last rope = limit_index rope ((length rope) - 1) -let check_index rope i = - if i < 0 || i >= (length rope) then begin - raise (Out_of_bounds "Rope.check_index") - end - -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 - | Leaf (s,off,_) -> (Char.code s.[off + i]) -(* - let c = (Char.code s.[off + i]) in - let len = (length rope) in - let next = (i + 1) in - if (c == 0x0D && next < len && (getc rope next) == 0x0A) then - 0x0A - else - c -*) + | Leaf (s,off,_) -> + Char.code s.[off + i] | Node (l,r,h,len) -> let left_len = (length l) in if i < left_len then @@ -72,7 +46,7 @@ let rec getc rope i = (* inefficient form of iteri *) let rec iteri fn rope pos = - if pos < (length rope) && (fn pos (Char.code (getb rope pos))) then + if pos < (length rope) && (fn pos (getc rope pos)) then iteri fn rope (pos + 1) (* More efficient form of iteri? @@ -104,6 +78,9 @@ let gets rope i j = rope i; Bytes.unsafe_to_string buf +let to_string rope = + gets rope 0 (length rope) + (* Rebalancing Algorithm from the original paper on ropes: * Height of leaf is 0 @@ -176,8 +153,6 @@ and join_special left right node = | _ -> node let rec split rope i = - if i < 0 || i > (length rope) then - raise (Out_of_bounds "Rope.split"); match rope with | Leaf (s,off,len) -> (Leaf (s, off, i), Leaf (s, (off + i), len - (i))) diff --git a/lib/rope.mli b/lib/rope.mli index fd9e545..17c7948 100644 --- a/lib/rope.mli +++ b/lib/rope.mli @@ -9,6 +9,7 @@ type rune = int val empty : rope val from_string : string -> rope +val to_string : rope -> string val length : rope -> int val height : rope -> int @@ -22,7 +23,6 @@ val del : rope -> int -> int -> rope val iteri : (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 64115bd..5cec045 100644 --- a/tests/rope_tests.ml +++ b/tests/rope_tests.ml @@ -1,8 +1,16 @@ open Test open Rope -let () = - (* length() tests *) +let () = (* empty tests *) + test "empty : should be an empty rope" (fun () -> + let rope = Rope.empty in + assert( length rope == 0 ); + assert( height rope == 0 ); + assert( to_string rope = "" ) + ); + () + +let () = (* length() tests *) test "length : 0 for empty string" (fun () -> let rope = Leaf("", 0, 0) in assert( length rope == 0 ) @@ -15,8 +23,28 @@ let () = let rope = (join (Leaf("a", 0, 1)) (Leaf("a", 0, 1))) in assert( length rope == 2 ) ); + () + +let () = (* last() tests *) + test "last() : should return 0" (fun () -> + let rope = from_string "" in + assert( last rope == 0 ); + ); + test "last() : should return 0" (fun () -> + let rope = from_string "a" in + assert( last rope == 0 ); + ); + test "last() : should return 1" (fun () -> + let rope = from_string "ab" in + assert( last rope == 1 ); + ); + test "last() : should return 2" (fun () -> + let rope = from_string "abc" in + assert( last rope == 2 ); + ); + () - (* flatten() tests *) +let () = (* flatten() tests *) test "flatten : flatten a tree to a leaf" (fun () -> let tree = Node (Leaf("a", 0, 1), Leaf("b", 0, 1), 2, 2) in let leaf = (flatten tree) in @@ -24,8 +52,9 @@ let () = | Leaf ("ab",0,2) -> true | _ -> false) ); + () - (* join() tests *) +let () = (* join() tests *) test "join : join two leaves into rope" (fun () -> let left = Leaf("a", 0, 1) in let right = Leaf("b", 0, 1) in @@ -50,17 +79,36 @@ let () = | Leaf ("abc",0,3) -> true | _ -> false) ); + () - (* getc() tests *) +let () = (* split() tests *) + test "split : split string into two parts" (fun () -> + let left, right = split (from_string "ab") 1 in + assert (to_string left = "a"); + assert (to_string right = "b") + ); + test "split : split string into empty left and full right" (fun () -> + let left, right = split (from_string "ab") 0 in + assert (to_string left = ""); + assert (to_string right = "ab") + ); + test "split : split string into empty right and full left" (fun () -> + let left, right = split (from_string "ab") 2 in + assert (to_string left = "ab"); + assert (to_string right = "") + ); + () + +let () = (* getc() tests *) test "getc : raise Out_of_bounds on negative index" (fun () -> let rope = Leaf("a", 0, 1) in try let _ = getc rope (-1) in assert false - with Out_of_bounds _ -> assert true + with Invalid_argument _ -> assert true ); test "getc : raise Out_of_bounds on out of bounds index" (fun () -> let rope = Leaf("a", 0, 1) in try let _ = getc rope (2) in assert false - with Out_of_bounds _ -> assert true + with Invalid_argument _ -> assert true ); test "getc : return index 0 of leaf" (fun () -> let rope = Leaf("abc", 0, 3) in @@ -82,11 +130,6 @@ let () = 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 () -> - let rope = from_string "\r\n" in - assert( (getc rope (0)) == Char.code '\n' ); - ); -*) test "getc : return \\r for \\r at end of string" (fun () -> let rope = from_string "\r" in assert( (getc rope (0)) == Char.code '\r' ); @@ -95,8 +138,9 @@ let () = let rope = from_string "\ra" in assert( (getc rope (0)) == Char.code '\r' ); ); + () - (* puts() tests *) +let () = (* puts() tests *) test "puts : insert at index 0" (fun () -> let rope = Leaf("bc", 0, 2) in let rope = (puts rope "a" 0) in @@ -124,8 +168,9 @@ let () = assert( (getc rope (1)) == Char.code 'b' ); assert( (getc rope (2)) == Char.code 'c' ); ); + () - (* nextc() tests *) +let () = (* nextc() tests *) test "nextc : should return pos if at end of buffer" (fun () -> let rope = Leaf("abc", 0, 3) in assert( 2 == (nextc rope 2) ); @@ -134,8 +179,9 @@ let () = let rope = Leaf("a\na", 0, 3) in assert( 2 == (nextc rope 1) ); ); + () - (* prevc() tests *) +let () = (* prevc() tests *) test "prevc : should return pos if at start of buffer" (fun () -> let rope = Leaf("abc", 0, 3) in assert( 0 == (prevc rope 0) ); @@ -144,8 +190,9 @@ let () = let rope = Leaf("a\na", 0, 3) in assert( 1 == (prevc rope 2) ); ); + () - (* is_bol() tests *) +let () = (* is_bol() tests *) test "is_bol : should return true if pos is 0" (fun () -> let rope = Leaf("abc", 0, 3) in assert( is_bol rope 0 ); @@ -162,8 +209,9 @@ let () = let rope = Leaf("\rabc", 0, 3) in assert( (is_bol rope 1) == false ); ); + () - (* is_eol() tests *) +let () = (* is_eol() tests *) test "is_eol : should return true if pos is Rope.last" (fun () -> let rope = Leaf("abc", 0, 3) in assert( is_eol rope 2 ); @@ -172,18 +220,22 @@ let () = let rope = Leaf("abc\n", 0, 4) in assert( is_eol rope 3 ); ); -(* test "is_eol : should return true if pos is last char of line with \\r\\n ending" (fun () -> - let rope = Leaf("abc\r\n", 0, 5) in - assert( is_eol rope 3 ); - );*) test "is_eol : should return false if pos is not last char of line" (fun () -> let rope = Leaf("abcd\n", 0, 5) in assert( (is_eol rope 2) == false ); ); + () - (* to_bol() tests *) +let () = (* to_bol() tests *) test "to_bol : should return index of first char on the line" (fun () -> let rope = Leaf("\nabc\n", 0, 5) in assert( (to_bol rope 2) == 1 ); ); () + +let () = (* to_eol() tests *) + test "to_bol : should return index of last char on the line" (fun () -> + let rope = Leaf("\nabc\n", 0, 5) in + assert( (to_eol rope 1) == 4 ); + ); + () -- 2.52.0

B
B
bol [Buf.Cursor]
bol [Buf]
buffer [Draw]
C
C
cache_update [X11]
char [Cfg.Color.Syntax]
check_index [Rope]
clone [Draw.Cursor]
clone [Buf.Cursor]
copy_indent [Cfg]
D
D
dark_bkg [Draw]
dbl_click_time [Cfg]
draw_tab [Draw.Cursor]
E
E
edit [Draw]
edit_csr [Cfg.Color]
expand_tabs [Cfg]
F
F
find_line [Scrollmap]
first [Scrollmap]
from_string [Rope]
G
G
get_glyph [X11]
getb [Rope]
getc [Buf.Cursor]
getc [Rope]
gutter_sel [Cfg.Color]
H
H
has_next_line [Draw.Cursor]
height [Rope]
hrule [Draw]
I
I
intern [X11]
intvar [Cfg]
iteri [Rope]
J
J
join [Rope]
join_special [Rope]
K
K
keyword [Cfg.Color.Syntax]
L
L
last [Rope]
length [Buf]
load_file [Misc]
M
M
make [View]
make [Scrollmap]
move_x [Draw.Cursor]
N
N
next_glyph [Draw.Cursor]
next_line [Draw.Cursor]
number [Cfg.Color.Syntax]
O
O
offset [Buf.Cursor]
operator [Cfg.Color.Syntax]
P
P
palette [Cfg.Color]
path [View]
puts [Rope]
R
R
rectangle [Draw]
resize [View]
ruler_column [Cfg]
S
S
scroll [Draw]
scroll_dn [View]
syntax_enabled [Cfg]
T
T
tab_width [Cfg]
tabglyph [Draw]
to_eol [Rope]
to_string [Rope]
trim_on_save [Cfg]
typedef [Cfg.Color.Syntax]
V
V
var_get [X11]
variable [Cfg.Color.Syntax]
vrule [Draw]
W
W
winheight [Cfg]
winwidth [Cfg]