[r6rs-discuss] Strings

From: Thomas Lord <lord>
Date: Sat Mar 24 16:05:59 2007

Per Bothner wrote:
> I've expressed my preference: introduce a "marker" type,
> where a marker is a position in a string or a "buffer".
> Simple operations (e.g. get next characater, set next character,
> or move position) are O(1) regardless of the reresentation used.


I'm not so sure about the O(1) claim.

It should be easy to see that O(1) is unlikely in the
case where mutations are permitted to change the
STRING-LENGTH of the string both because
of the need to copy string data and the need to
update other markers.

Even if STRING-LENGTH doesn't change, as you
point out in your formal comment, unless the implementation
is using UTF-32 or similar, setting a character
will have similar impacts.

Also, would you have your markers include an
operation like (MOVE-MARKER! M N) that changes
the position of a marker by some arbitrary integer
N? If not, the core string API would penalize operations
that /do/ have efficient random access to strings.
If so, then you have a simple operation which is
O(N) in many popular representations.

I basically agree with you that a rich, buffer-like data
structure is a very good idea for both strings in general
and Unicode texts specifically but there are so many
ways to do that that the core should have something like
the R5 strings ops, perhaps augmented with your proposed
length-changing operations. Those primitives need have
only modest performance to support very efficient buffers.

-t
Received on Sat Mar 24 2007 - 16:16:02 UTC