source: project/wiki/eggref/5/rope @ 36452

Last change on this file since 36452 was 36452, checked in by evhan, 10 months ago

release/5/egg-locations: Add optimism and schematic

File size: 5.1 KB
Line 
1[[tags: egg]]
2
3== rope
4
5[[toc:]]
6
7== Description
8
9Ropes, as described in "Ropes, An Alternative to Strings" (1995 - H. Boehm, R. Atkinson, M. Plass).
10
11The source for this egg is available [[http://git.foldling.org/rope.git|here]].
12
13== API
14
15<record>rope</record>
16<procedure>(rope? object) => boolean</procedure>
17<procedure>(rope-length rope) => integer</procedure>
18<procedure>(rope-depth rope) => integer</procedure>
19
20A rope is either a leaf containing a string or a binary tree consisting of such leaves.
21
22Length and depth are stored on each node, so {{rope-length}} and {{rope-depth}} are constant time queries.
23
24{{rope?}} simply tests if its argument is a rope.
25
26<procedure>(rope=? rope1 rope2) => boolean</procedure>
27
28{{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).
29
30<parameter>(current-maximum-leaf-length [n])</parameter>
31
32{{current-maximum-leaf-length}} specifies the maximum string length for rope leaf nodes.
33
34The default value is 512, which should be suitable for most purposes. Setting this value too low will result in frequent rebalancing, adversely affecting performance.
35
36<procedure>(rope-null? rope) => boolean</procedure>
37
38Tests whether the given rope is empty. Equivalent to {{(= 0 (rope-length rope))}}.
39
40<procedure>(rope [string ...]) => rope</procedure>
41
42Constructs a rope from the given strings. The resulting rope, while not guaranteed to be balanced, should be fairly so.
43
44<procedure>(string->rope string [start [end]]) => rope</procedure>
45
46Constructs a rope from the given string. The resulting rope is guaranteed to be balanced. If {{start}} and {{end}} indices are given, the resulting rope will consist of only the characters in that range of the string.
47
48<procedure>(rope->string rope [start [end]]) => string</procedure>
49
50Returns the contents of the given rope as a string. If {{start}} and {{end}} indices are given, the resulting string will consist of only the characters in that range of the rope.
51
52<procedure>(rope-ref rope i) => character</procedure>
53
54Returns the {{i}}th character of the rope, zero-indexed.
55
56<procedure>(rope-set! rope i char) => void</procedure>
57
58Sets the {{i}}th character of the rope, zero-indexed, to the given {{char}}. The rope is destructively modified.
59
60<procedure>(subrope rope start [end]) => rope</procedure>
61
62Returns 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.
63
64<procedure>(rope-append [rope ...]) => rope</procedure>
65
66Appends the given ropes, trying to keep the resulting rope fairly well-balanced.
67
68<procedure>(rope-concatenate list) => rope</procedure>
69
70Constructs a new rope from the the given list of ropes, trying to keep the resulting rope fairly well-balanced.
71
72<procedure>(rope-reverse rope)</procedure>
73
74Constructs 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).
75
76<procedure>(rope-balanced? rope) => boolean</procedure>
77
78Tests 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.
79
80<procedure>(rope-balance rope) => rope</procedure>
81
82Explicitly rebalances a rope.
83
84The rebalancing strategy used is that described in Boehm, Atkinson & Plass' 1995 paper "Ropes, An Alternative to Strings".
85
86<procedure>(rope-fold f a rope1 [ropen ...]) => object</procedure> <procedure>(rope-for-each f rope1 [ropen ...]) => void</procedure>
87
88These procedures implement characterwise {{fold}} and {{for-each}} over the given ropes.
89
90<procedure>(read-rope [port [length]]) => rope</procedure>
91
92Reads a rope from the given port, or {{current-input-port}} if no port is specified.
93
94If a numerical length argument is given, at most that many characters are read.
95
96The resulting rope is guaranteed to be balanced.
97
98<procedure>(make-rope-iterator rope) => procedure</procedure>
99
100Returns a cursor procedure over the given rope's characters.
101
102The 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}}.
103
104<procedure>(open-input-rope rope) => port</procedure>
105
106Returns 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}}.
107
108<procedure>(open-output-rope) => port</procedure> <procedure>(get-output-rope [port]) => rope</procedure>
109
110{{open-output-rope}} returns a port to which output can be written and accumulated, until returned as a rope with {{get-output-rope}}.
111
112In 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}}.
113
114== Author
115
116Evan Hanson
117
118== License
119
120Copyright (c) 2012-2018, 3-Clause BSD.
Note: See TracBrowser for help on using the repository browser.