(**************************************************************************) (* *) (* Copyright (C) Jean-Christophe Filliatre *) (* *) (* This software is free software; you can redistribute it and/or *) (* modify it under the terms of the GNU Library General Public *) (* License version 2.1, with the special exception on linking *) (* described in file LICENSE. *) (* *) (* This software is distributed in the hope that it will be useful, *) (* but WITHOUT ANY WARRANTY; without even the implied warranty of *) (* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *) (* *) (**************************************************************************) (** Ropes are persistent data structures for long sequences. Elements are of any type. When elements are characters, ropes thus implement strings (with an interface identical to that of [String]) but with far better performances w.r.t. concatenation of substring extraction, especially on very large strings. *) (** Ropes are naturally implemented as a functor turning a (possibly inefficient) data structure of ``strings'' into another (more efficient) data structure with the same signature. *) exception Out_of_bounds (** Input signature for the functor *) module type STRING = sig type t type char val length : t -> int val empty : t val singleton : char -> t val append : t -> t -> t val get : t -> int -> char val sub : t -> int -> int -> t (** [sub t ofs len] extracts the substring of length [len] at offset [ofs], that is [t[ofs..ofs+len-1]]. Will always be called with a valid range. *) val iter_range : (char -> unit) -> t -> int -> int -> unit (** [iter_range f t ofs len] successively iterates [f] over characters of [t] at offsets [ofs], [ofs+1], ..., [ofs+len-1], in this order. Will always be called with a valid range. *) val print : Format.formatter -> t -> unit end (** Output signature of the functor. Note that it extends signature [STRING] and thus functor [Make] below can be iterated several times. *) module type ROPE = sig include STRING val is_empty : t -> bool (** [is_empty t] returns [true] if the given rope is empty. *) val set : t -> int -> char -> t (** [set t i c] returns a new rope identical to [t], apart character [i] which is set to [c]. Raises [Out_of_bounds] if [i < 0 || i >= length t]. It is more equivalent to (but more efficient than) [sub t 0 i ++ singleton c ++ sub t (i+1) (length t-i-1)] *) val delete : t -> int -> t (** [delete t i] returns a new rope obtained by removing character [i] in [t]. Raises [Out_of_bounds] if [i < 0 || i >= length t]. It is more equivalent to (but more efficient than) [sub t 0 i ++ sub t (i + 1) (length t - i - 1)] *) val insert_char : t -> int -> char -> t (** [insert t i c] returns a new rope resulting from the insertion of character [c] at position [i] in [t], that right before character [i]. Raises [Out_of_bounds] if [i < 0 || i > length t]. It is more equivalent to (but more efficient than) [sub t 0 i ++ singleton c ++ sub t i (length t - i)] *) val insert : t -> int -> t -> t (** [insert t i r] returns a new rope resulting from the insertion of rope [r] at position [i] in [t]. Raises [Out_of_bounds] if [i < 0 || i > length t]. It is more equivalent to (but more efficient than) [sub t 0 i ++ r ++ sub t i (length t - i)] *) (** Cursors are persistent data structures to navigate within ropes. When several operations are to be performed locally on a rope (such as local deletions, insertions or even simple accesses), then the use of cursors can be more efficient than the use of rope operations. It is convenient to see the cursor as placed between two characters, so that a rope of length [n] has [n+1] cursor positions. *) module Cursor : sig type cursor val empty : cursor (** [empty] is a cursor for an empty rope. *) val create : t -> int -> cursor (** [create t i] returns a cursor placed before character [i] of rope [t]. Raises [Out_of_bounds] is [i < 0 || i > length t]. Note that [i = length t] is a valid argument, resulting in a cursor placed right after the last character of the rope (i.e. at the end of the rope). *) val position : cursor -> int (** [position c] returns the position of cursor [c] in its rope. *) val to_rope : cursor -> t (** [to_rope c] returns the rope corresponding to cursor [c]. *) val move_forward : cursor -> int -> cursor (** [move_forward c n] moves cursor [c] [n] characters forward. Raises [Invalid_argument] if [n < 0]. Raises [Out_of_bounds] if it moves the cursor beyond the end of the rope. *) val move_backward : cursor -> int -> cursor (** [move_backward c n] moves cursor [c] [n] characters backward. Raises [Invalid_argument] if [n < 0]. Raises [Out_of_bounds] if it moves the cursor beyond the start of the rope. *) val move : cursor -> int -> cursor (** [move c n] moves cursor [c] [n] characters away from its current location, relatively to the sign of [n] (i.e. forward if [n > 0] and backward if [n < 0]). Raises [Out_of_bounds] if it moves the cursor beyond the start or the end of the rope. *) val get : cursor -> char (** [get c] returns the character right after cursor [c]. Raises [Out_of_bounds] if the cursor is located at the end of the rope. *) val set : cursor -> char -> cursor (** [set c x] returns a new cursor identical to [c] apart from the character right after the cursor position, which is set to [x]. Raises [Out_of_bounds] if the cursor is located at the end of the rope. *) val insert_char : cursor -> char -> cursor (** [insert_char c x] returns a new cursor obtained from [c] by inserting character [x] at the cursor position. The new cursor is located right before the newly inserted character (i.e. at the same absolute position in the rope). *) val insert : cursor -> t -> cursor (** [insert c r] is similar to [insert_char] but inserts a rope [r] at the cursor point instead of a character. *) val delete : cursor -> cursor (** [delete c] deletes the character right after the cursor location. Raises [Out_of_bounds] if the cursor is located at the end of the rope. *) val print : Format.formatter -> cursor -> unit (** [print fmt c] prints cursor [c] on formatter [fmt], as a string ["abc...|def..."] where ["abc..."] is the portion of the rope before the cursor position and ["def..."] the portion after. *) end end (** The functor to build ropes, turning an implemention of strings [S] into an implemention of ropes. It is controlled by two parameters: - [small_length] is the maximal length under which we perform concatenation of flat strings, i.e. when two ropes of length at most [small_length] are concatenated, then the corresponding flat string is built. - [maximal_height] is the threshold for rebalancing: when a rope has height at least [maximal_height] it is then rebalanced; setting [small_length] to [max_int] will result in ropes that are never rebalanced (which is perfectly fine in many applications). *) module type CONTROL = sig val small_length : int val maximal_height : int end module Make (S : STRING) (C : CONTROL) : sig include ROPE with type char = S.char val of_string : S.t -> t end (** Instance: usual strings (i.e. with [type char = Char.t]) is a particular instance of functor [Make] above, which is directly provided here as module [S] *) module String : sig include ROPE with type char = Char.t val of_string : string -> t end (** Elements of ropes can be of any type, of course. In that case, they must rather be seen as arrays instead of strings. The following functor builds ropes for a given (printable) type of elements (using arrays internally for flat strings). *) module type Print = sig type t val print : Format.formatter -> t -> unit end module Make_array (X : Print) : sig include ROPE with type char = X.t val of_array : X.t array -> t val create : int -> X.t -> t val init : int -> (int -> X.t) -> t end