rope.ss: Ropes for fast string concatenation and subsequencing
_rope.ss_: Ropes for fast string concatenation and subsequencing
Danny Yoo (email@example.com / firstname.lastname@example.org)
Index terms: _ropes_
This presents a _rope_ data structure which is very much like a
string, except that it provides constant-time concatenation, as well
as inexpensive subsequencing. It's pretty much what's described in
the paper "Ropes: an Alternative to Strings" by Boehm, Atkinson, and
Plauss. This library also allows special values to be part of a rope.
> (require (planet "rope.ss" ("dyoo" "rope.plt" 3)))
> (define a-rope
"hello, this is a test of the emergency broadcast")
(string->rope "system; this is only a test")))
> (rope-length a-rope)
> (subrope a-rope 5)
> (rope->string (subrope a-rope 5 10))
> (rope-ref (subrope a-rope 20) 0)
;; Example with specials
> (define rope-with-specials
(rope-append (string->rope "hello")
(rope-append (special->rope (box " "))
> (reverse (rope-fold/leaves cons '() rope-with-specials))
("hello" #&" " "world")
> (reverse (rope-fold cons '() rope-with-specials))
(#\h #\e #\l #\l #\o #&" " #\w #\o #\r #\l #\d)
A rope is defined to be either:
* A string node,
* A special node, or
* A concatenation node made of a left rope and a right rope.
Use string->rope and special->rope to convert those types to their
respective ropes. Concatenation nodes are built with rope-append.
> string->rope: string -> rope
Given a long string, breaks it up into smaller rope fragments and
appends them all together. The resulting rope is balanced.
> special->rope: (not string?) -> rope
Creates a rope element of length one whose content is the given
Caveat: The special should not be a string. If it's necessary to
construct and distinguish such a special, one workaround is to wrap
with a box. Rationale: the behavior of rope-fold/leaves becomes
ambiguous and otherwise wouldn't let a client distinguish between a
string and a special-as-a-string.
> rope-append: rope rope -> rope
Joins two ropes.
> rope-append*: rope* -> rope
Joins multiple ropes together. The result tries to maintain some
> rope?: any -> boolean
Returns true if the input is a rope.
> rope-has-special?: rope -> boolean
Returns true if the rope contains a special node.
> rope-length: rope -> natural-number
Returns the length of a rope. Cost is constant time.
> rope-depth: rope -> natural-number
Returns the depth of the rope data structure. Constant time
> rope-ref: rope natural-number -> char-or-special
Returns the nth character or special in a rope. Cost is proportional
to the rope-depth of the rope.
> subrope: rope start [end] -> rope
Returns a subsequence of the rope containing all the character from
start up to (but not including) the end. If the end is not provided,
then the subrope extends to the end of the rope. Cost is proportional
to the rope-depth of the rope.
> rope=?: rope rope -> boolean
Returns true if the given ropes have the same content. Specials are
compared with eq?.
> rope->string: rope -> string
Creates a string from the content in the rope.
Note: if the rope has a special, this function will raise an error.
> rope->vector: rope -> (vectorof char-or-special)
Creates a vector of characters and specials from the content in the
> vector->rope: (vectorof char-or-special) -> rope
Creates a rope from the content of the vector.
> rope-for-each: (char-or-special -> void) rope -> void
Applies the input function on every character or special in the rope.
> rope-fold: (char-or-special X) X rope -> X
Folds an accumulating function across every character or special in
> rope-fold/leaves: (rope:string-or-rope:special X) X rope -> X
Folds an accumulating function across every rope:string or
rope:special node in the rope.
Note: in version 3, the node leaf structure itself is passed to the
accumulator function. In previous versions, the library did an
automatic unboxing of the value.
> open-input-rope: rope -> input-port
Returns an input port whose byte content comes from the rope.
Specials can be read with read-byte-or-special.
Other API functions and parameters
> rope-node-count: rope -> natural-number
Returns the number of nodes in the rope.
> rope-balance: rope -> rope
Returns a balanced version of the rope whose rope-depth is roughly
logarithmic to its rope-node-count.
> current-optimize-flat-ropes: (parameterof boolean)
If true, then rope-append calls will try to optimize appends against
rope:strings if it seems worthwhile. Default is #t.
> current-max-depth-before-rebalancing: (parameterof number)
The maximum depth of a rope before the rope is automatically
rebalanced. Default value is 32.
The following structure definitions are provided for those who need to
do structured traversal over the nodes of a rope.
> (define-struct rope ())
> (define-struct (rope:string rope) (s))
where s is a string.
> (define-struct (rope:special rope) (s))
where s is not a string.
> (define-struct (rope:concat rope) (l r len depth))
where l and r are ropes, and len and depth are natural numbers.
rope-append will automatically rebalance if the depth of the rope data
structure crosses a threshold value. See the
current-max-depth-before-rebalancing parameter for details.
Version 3.0: major API changes.
* rope-fold/leaves does not automatically unbox the leaf
* added rope-depth, rope-append*, rope=?, rope->vector,
* rope:concat has an additional field 'depth'.
* rope-append automatically rebalances a rope if it is too deep.
Version 2.3: improved implementation of open-input-rope. Fixed silly
bug involving subrope and specials.
Version 2.2: exposed structure definitions, although most users won't
touch these directly.
Version 2.1: library API extended to support "special" objects. Also,
strings must be explicitly converted into strings now.
Hans-Juergen Boehm and Russell R. Atkinson and Michael F. Plass.
"Ropes: an Alternative to Strings." Software - Practice and
Experience, Volume 25, No. 12. pp 1315--1330. (1995).