On 01/25/2012 04:57 AM, Alex Shinn wrote:
> Oh, by all means use a gap buffer (or whatever you want)
> for the reference implementation!  But I still fail to see why
> that has to be exposed in the API... or even _can_ be in
> most cases.

I don't I've suggested "exposing" the implementation in the API.

> Perhaps you're just referring to the fact that there will
> be an implicit cursor,

No, that's not a factor.

My point is simple:
(1) Scheme has mutable fixed-length strings.  The "implied"
implementation is a simple array,though that doesn't mean
the implementation is "exposed".
(2) Mutable fixed-length strings don't really make sense
in the Unicode world.
(3) A conservative extension to the Scheme string API
would be to support variable-length strings, with
append/insert/delete/replace operations.
(4) Buffer-gap is a reasonable implementation of (3);
if works well as a conservative extension of the
traditional simple array in (1).
(5) Buffer-gap obviously has some performance problems:
Substring operations and copying come to mind.  But it shares
those with the simple array-based implementation implied by (1).
(6) Neither the traditional Scheme string API or one enhanced
to variable-length strings *preclude* a more sophisticated
string implementation, but such an implementation may be
overkill for the default string implementation
of a general-purpose Scheme implementation.

>but there are a number of data
> structures that make the same assumption.  A good
> survey is here:
>
> http://www.cs.unm.edu/~crowley/papers/sds/sds.html

Thanks - I'll read it.

Do you have a reference that actually includes the figures?
--
	--Per Bothner
per@bothner.com   http://per.bothner.com/

_______________________________________________
Scheme-reports mailing list
Scheme-reports@scheme-reports.org
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports