[[tags: egg]]
== rope
[[toc:]]
=== Description
Ropes, as described in "Ropes, An Alternative to Strings"
(1995 - H. Boehm, R. Atkinson, M. Plass).
The source for this egg is available at [[http://github.com/evhan/rope]].
=== API
rope
(rope? object) => boolean
(rope-length rope) => integer
(rope-depth rope) => integer
A rope is either a leaf containing a string or a binary tree consisting of such
leaves.
Length and depth are stored on each node, so {{rope-length}} and {{rope-depth}}
are constant time queries.
{{rope?}} simply tests if its argument is a rope.
(rope=? rope1 rope2) => boolean
{{rope=?}} tests whether two ropes represent the same string. Fast paths are
provided on {{eq?}}ity and {{rope-length}}; otherwise, this comparison is O(n).
(current-maximum-leaf-length [n])
{{current-maximum-leaf-length}} specifies the maximum string length for rope
leaf nodes.
The default value is 512, which should be suitable for most purposes. Setting
this value too low will result in frequent rebalancing, adversely affecting
performance.
(rope-null? rope) => boolean
Tests whether the given rope is empty. Equivalent to {{(= 0 (rope-length rope))}}.
(rope [string ...]) => rope
Constructs a rope from the given strings. The resulting rope, while not
guaranteed to be balanced, should be fairly so.
(string->rope string) => rope
Constructs a rope from the given string. The resulting rope is guaranteed to
be balanced.
(rope->string rope) => string
Returns the full contents of the given rope as a string.
(rope-ref rope i) => character
Returns the {{i}}th character of the rope, zero-indexed.
(subrope rope start [end]) => rope
Returns a subrope consisting of the range of characters starting at the
zero-indexed character {{start}} and ending at character {{end}}, or the end of
the rope if no {{end}} is given.
(rope-append [rope ...]) => rope
Appends the given ropes, trying to keep the resulting rope fairly
well-balanced.
(rope-concatenate list) => rope
Constructs a new rope from the the given list of ropes, trying to keep the
resulting rope fairly well-balanced.
(rope-reverse rope)
Constructs a new rope consisting of the characters in the given rope, reversed.
This operation is expensive for large ropes (O(n) in the length of the rope,
best-case).
(rope-balanced? rope) => boolean
Tests whether the given rope is balanced. A rope is balanced if its length is
at least {{F(n+2)}}, where {{F(n)}} is the {{n}}th fibonacci number and {{n}}
is the depth of the given rope.
(rope-balance rope) => rope
Explicitly rebalances a rope.
The rebalancing strategy used is that described in Boehm, Atkinson & Plass'
1995 paper "Ropes, An Alternative to Strings".
(rope-fold f a rope1 [ropen ...]) => object
(rope-for-each f rope1 [ropen ...]) => void
These procedures implement characterwise {{fold}} and {{for-each}} over the
given ropes.
(read-rope [port [length]]) => rope
Reads a rope from the given port, or {{current-input-port}} if no port is specified.
If a numerical length argument is given, at most that many characters are read.
The resulting rope is guaranteed to be balanced.
(make-rope-iterator rope) => procedure
Returns a cursor procedure over the given rope's characters.
The resulting procedure, when invoked, will return the current character in the
rope and advance to the next character. When the characters of the rope are
exhausted, the procedure will yield {{#!eof}}.
(open-input-rope rope) => port
Returns a port from which the contents of the rope can be read. When the end of
the rope is reached, subsequent reads will return {{#!eof}}.
(open-output-rope) => port
(get-output-rope [port]) => rope
{{open-output-rope}} returns a port to which output can be written and
accumulated, until returned as a rope with {{get-output-rope}}.
In reality, {{open-output-rope}} and {{open-output-string}} are the same.
Construction of the rope returned by {{get-output-rope}} is delayed until that
procedure is called, so {{get-output-rope}} may be used to return a rope from
the accumulated output of ports created by either {{open-output-rope}} or
{{open-output-string}}.
=== History
* 0.0.2 - initial
=== Author
Evan Hanson
=== License
Copyright (c) 2012, 3-Clause BSD.