Legend:
Library
Module
Module type
Parameter
Class
Class type
Heavyweight strings ("ropes")
This module implements ropes as described in Boehm, H., Atkinson, R., and Plass, M. 1995. Ropes: an alternative to strings. Softw. Pract. Exper. 25, 12 (Dec. 1995), 1315-1330.
Ropes are an alternative to strings which support efficient operations:
determining the length of a rope in constant time
appending or prepending a small rope to an arbitrarily large one in amortized constant time
concat, substring, insert, remove operations in amortized logarithmic time
access to and modification of ropes in logarithmic time
Functional nature and persistence
All operations are non-destructive: the original rope is never modified. When a new rope is returned as the result of an operation, it will share as much data as possible with its "parent". For instance, if a rope of length n undergoes m operations (assume n >> m) like set, append or prepend, the modified rope will only require O(m) space in addition to that taken by the original one.
However, Rope is an amortized data structure, and its use in a persistent setting can easily degrade its amortized time bounds. It is thus mainly intended to be used ephemerally. In some cases, it is possible to use Rope persistently with the same amortized bounds by explicitly rebalancing ropes to be reused using balance. Special care must be taken to avoid calling balance too frequently; in the limit, calling balance after each modification would defeat the purpose of amortization.
Limitations
The length of ropes is limited to approximately 700 Mb on 32-bit architectures, 220 Gb on 64 bit architectures.
author Mauricio Fernandez, Yoriyuki Yamagata, The Batteries Included Team
type t
The type of the rope.
exceptionOut_of_bounds
Raised when an operation violates the bounds of the rope.
val max_length : int
Maximum length of the rope (number of UTF-8 characters).
balance r returns a balanced copy of the r rope. Note that ropes are automatically rebalanced when their height exceeds a given threshold, but balance allows to invoke that operation explicitly.
append r u concatenates the r and u ropes. In general, it operates in O(log(min n1 n2)) amortized time. Small ropes are treated specially and can be appended/prepended in amortized O(1) time.
sub r m n returns a sub-rope of r containing all characters whose indexes range from m to m + n - 1 (included). Operates in worst-case O(log size) time.
insert n r u returns a copy of the u rope where r has been inserted between the characters with index n and n + 1 in the original rope. The length of the new rope is length u + length r. Operates in amortized O(log(size r) + log(size u)) time.
remove m n r returns the rope resulting from deleting the characters with indexes ranging from m to m + n - 1 (included) from the original rope r. The length of the new rope is length r - n. Operates in amortized O(log(size r)) time.
iter f r applies f to all the characters in the r rope, in order.
val iteri : ?base:int ->(int ->BatUChar.t-> unit)->t-> unit
Operates like iter, but also passes the index of the character to the given function.
val range_iter : (BatUChar.t-> unit)->int ->int ->t-> unit
range_iter f m n r applies f to all the characters whose indices k satisfy m <= k < m + n. It is thus equivalent to iter f (sub m n r), but does not create an intermediary rope. range_iter operates in worst-case O(n + log m) time, which improves on the O(n log m) bound from an explicit loop using get.
filter_map f l calls (f a0) (f a1).... (f an) where a0..an are the characters of l. It returns the list of elements bi such as f ai = Some bi (when f returns None, the corresponding element of l is discarded).
index_from r i c returns the character number of the first occurrence of character c in rope r after position i. index s c is equivalent to index_from s 0 c.
slice ?first ?last s returns a "slice" of the rope which corresponds to the characters s.[first], s.[first+1], ..., s[last-1]. Note that the character at index last is not included! If first is omitted it defaults to the start of the rope, i.e. index 0, and if last is omitted is defaults to point just past the end of s, i.e. length s. Thus, slice s is equivalent to copy s.
Negative indexes are interpreted as counting from the end of the rope. For example, slice ~last:-2 s will return the rope s, but without the last two characters.
This function never raises any exceptions. If the indexes are out of bounds they are automatically clipped.
blit src srcoff dst dstoff len returns a copy of dst in which len characters have been copied from rope src, starting at character number srcoff, to rope dst, starting at character number dstoff. It works correctly even if src and dst are the same rope, and the source and destination chunks overlap.
replace ~str ~sub ~by returns a tuple constisting of a boolean and a rope where the first occurrence of the rope sub within str has been replaced by the rope by. The boolean is true if a substitution has taken place, false otherwise.
nsplit s sep splits the rope s into a list of ropes which are separated by sep. nsplit "" _ returns the empty list. If the separator is not found, it returns a list of the rope s. If two occurrences of the separator are consecutive (with nothing in between), the empty rope is added in the sequence. For example, nsplit "a//b/" "/" is "a"; ""; "b"; "".
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.