rope 0.5 · OCaml Package

Ropes ("heavyweight strings") are a scalable string implementation: they are designed for efficient operation that involve the string as a whole. Operations such as concatenation, and substring take time that is nearly independent of the length of the string. Unlike strings, ropes are a reasonable representation for very long strings such as edit buffers or mail messages.

Advantages:

No length limitation (contrarily to strings)
Immutability (use Rope.Buffer instead)
Efficient concatenation (Rope.concat2) and taking a range (Rope.sub), and sharing memory whenever possible.

Disadvantages:

get is not O(1) -- but it is amortized O(1) if you use an iterator (see the Rope.Iterator module). get is 2 to 3 times slower than for a string so it should not be your main operation. However, as soon as in addition you have a few concatenations (especially with sharing) or splice operations, ropes will usually outperform strings.

You can say module String = Rope to use ropes instead of strings and, in particular, so that r.[i] gets the ith char of the rope r. This module has most operations of String but not all: it does not have set because ropes are immutable, not make because it is basically useless in this context (the Rope.Buffer is more powerful),...

To use this library in the toploop, issue #use "rope_top.ml";;

author Christophe Troestler

type t

Immutable rope.

type rope = t

Alias for type Rope.t

exception Out_of_bounds of string

Raised by various functions to indicate out-of-bounds access. The string argument is the name of the function that raised it.

val empty : t

The empty rope.

val of_string : string -> t

of_string s creates a rope from the string s. Because ropes are immutable while strings are not, a copy of s is made.

val of_substring : string -> int -> int -> t

of_substring s start len create a new rope from the substring s.[start .. start+len-1].

raises Invalid_argument
if start and len do not designate a valid sbstring of s.

val of_char : char -> t

of_char c returns a rope consisting of the unique character c. It may be useful to append a char to a given rope.

val to_string : t -> string

to_string r return a string with the same content as the rope. The rope and the string share no data.

raises Failure
if the rope is too long to fit into a string.

val is_empty : t -> bool

is_empty r tells whether the rope r is empty.

val length : t -> int

length r returns the length of the rope. O(1) time.

val get : t -> int -> char

get r i returns the ith char of the rope. Takes O(log(length r)).

val sub : t -> int -> int -> t

sub r i start len returns the sub-rope consisting of characters from position start to start+len-1 (included) of the rope r. O(log(length r)) time.

raises Invalid_argument
if i < 0, len < 0 or i + len > Rope.length r.

val concat2 : t -> t -> t

concat2 r1 r2 concatenates the ropes r1 and r2.

val concat : t -> t list -> t

concat sep rl concatenates the list of ropes rl, inserting the separator string sep between each.

val iter : (char -> unit) -> t -> unit

iter f r execute f c for c going through every character of rope r from left to right.

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

iter f r execute f i c for c going through every character of rope r from left to right and i the index of c.

val escaped : t -> t

Return a copy of the argument, with special characters represented by escape sequences, following the lexical conventions of Objective Caml.

val index : t -> char -> int

index r c returns the position of the leftmost occurrence of character c in rope r.

raises Not_found
if c does not occur in r.

val rindex : t -> char -> int

rindex r c returns the position of the rightmost occurrence of character c in rope r.

raises Not_found
if c does not occur in r.

val index_from : t -> int -> char -> int

Same as Rope.index, but start searching at the character position given as second argument. Rope.index r c is equivalent to Rope.index_from r 0 c.

val rindex_from : t -> int -> char -> int

Same as Rope.rindex, but start searching at the character position given as second argument. Rope.rindex r c is equivalent to Rope.rindex_from s (Rope.length r - 1) c.

val contains : t -> char -> bool

contains r c tests if character c appears in the rope r.

val contains_from : t -> int -> char -> bool

contains_from r start c tests if character c appears in the subrope of r starting from start to the end of s.

raises Invalid_argument
if start is not a valid index of r.

val rcontains_from : t -> int -> char -> bool

rcontains_from r stop c tests if character c appears in the subrope of r starting from the beginning of r to index stop.

raises Invalid_argument
if stop is not a valid index of r.

val uppercase : t -> t

Return a copy of the argument, with all lowercase letters translated to uppercase, including accented letters of the ISO Latin-1 (8859-1) character set.

val lowercase : t -> t

Return a copy of the argument, with all uppercase letters translated to lowercase, including accented letters of the ISO Latin-1 (8859-1) character set.

val capitalize : t -> t

Return a copy of the argument, with the first character set to uppercase.

val uncapitalize : t -> t

Return a copy of the argument, with the first character set to lowercase.

val compare : t -> t -> int

The comparison function for ropes, with the same specification as Pervasives.compare. Along with the type t, this function compare allows the module Rope to be passed as argument to the functors Set.Make and Map.Make.

val equal : t -> t -> bool

equal r1 r2 tells whether the two ropes r1 and r2 are equal. (It is equivalent to compare r1 r2 = 0, just slightly faster.)

Search

val search_forward_string : string -> t -> int -> int

search_forward_string p is a search function that, given a rope r and a start index i0, will return the position of p in r or raise Not_found if no occurrence of p in r exists. let search = search_forward_string p takes O(length�p) and search r i0 takes O(length r - i0).

Input/output

Input and output functions for ropes modelled on the standard library Pervasives.

val input_line : ?leaf_length:int -> Pervasives.in_channel -> t

Read characters from the given input channel, until a newline character is encountered. Return the rope of all characters read, without the newline character at the end.

raises End_of_file
if the end of the file is reached at the beginning of line.

val read_line : unit -> t

Flush standard output, then read characters from standard input until a newline character is encountered. Return the rope of all characters read, without the newline character at the end.

val print_string : t -> unit

Print a rope on standard output.

val print_endline : t -> unit

Print a rope, followed by a newline character, on standard output and flush standard output.

val prerr_string : t -> unit

Print a rope on standard error.

val prerr_endline : t -> unit

Print a rope, followed by a newline character on standard error and flush standard error.

val output_string : Pervasives.out_channel -> t -> unit

output_string oc r outputs the rope r to the output channel oc. May also be used with a %a directive of printf.

val output_rope : Pervasives.out_channel -> t -> unit

Alias for Rope.output_string.

Balancing

val balance : t -> t

balance r return a balanced copy of the rope r. Implicit rebalancing is done by some of the above functions to avoid gross inefficiencies but you may want to call this function explicitely to try to improve your running times.

val height : t -> int

depth r returns the depth of the rope r. This information may be useful to decide whether you want to re-balance.

val rebalancing_height : int

The rope will be rebalanced by some functions it its height is greater or equal to rebalancing_height.

Submodules

module Iterator : sig ... end

Iterators for ropes. It is more efficient to use an iterator to perform small steps and get the characters than to use Rope.get repeatedly.

module Buffer : sig ... end

This is similar to the Buffer module in the standard library except that it constructs ropes. It is recommended to use this module instead of repeatedly concatenating chars.

module Regexp : sig ... end

TBD: Regular expressions for ropes.

module Rope_toploop : sig ... end

Toploop printer and its configuration.

package rope

Search

Input/output

Balancing

Submodules