Thomas Lord wrote:
By which I take you to mean I should show you uses for random
access into strings? You are talking about using
markers instead of integer string indexes, right?
Right.
Fast pattern matching. Fast search of texts displaying
various kinds of sorting. Fast fingerprinting. Quite
a few more, I'm sure, even though those already broad
categories.
True, though those are pretty esoteric, written as
specialized low-level libraries.
More importantly note that in most cases you don't need to
move by N "characters" - you need to move by N *code
units*, which would be an O(1) operation. For fast
string matching/searching, as long as the subject
string and the pattern use the same encoding, you can
treat multi-code-unit characters equivalent to a sequence
of code units: Searching a sequence of characters is
equivalent to searching for a sequence of code units.
With that set of assumptions (high locality of mutations and
a 25% waste of space) you've leant support to your formal
proposal for STRING-APPEND! but not any for markers.
On the contrary, you should be happy with a STRING-REPLACE!
that replaces an arbitrary substring, not necessarily preserving
length. Your implementation is free to use gap buffers
internally and, if your use assumptions hold for a given
application, it will perform swell -- no markers needed.
The problem is with the API for specifying the substring:
Assume the buffer contains UTF-8 or UTF-16 code units.
If the position is specified as a character (scalar value)
index then we need to scan (or use some kind of index) to
map that index into a buffer offset. If the position is
specified as code unit offset, or a unspecified "magic
cookie" then we can index directly into the buffer.
An advantage of using opaque "marker" objects rather than
indexes is that it's a way to leave the representation
up to the implementation, so it can use whatever is most
efficient.
--
--Per Bothner
[EMAIL PROTECTED] http://per.bothner.com/
_______________________________________________
r6rs-discuss mailing list
[email protected]
http://lists.r6rs.org/cgi-bin/mailman/listinfo/r6rs-discuss
