------art_13195_20751602.1194077764280
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Hi Eric,

you're right, I missed this point with my first solution. One simple way to
improve this -- as you mentioned in your hint -- use a fraction A of the
complete gap length. This way we will have O(n).

Nevertheless, I wanted to send in a second solution, which will take care of
all the other cases (better multi-lines, ...) this time with two strings as
data buffer. This solution is still quite handy, but unfortunately not yet
finished. I think, with two buffers (first before the gap, second after) the
O(n) is always valid.

Unfortunately, I think I don't have enough time to complete the full
solution, maybe the first part with two strings.

Holger



2007/11/2, Eric Mahurin <eric.mahurin / gmail.com>:
>
> On 10/30/07, Holger <hmack.gm / googlemail.com> wrote:
> > First attempt
> > - plain gap buffer implementation without much optimization
> > - only basic operations
> > - O(n)
> >
> > Regards
> > Holger
> >
> >
> >
> >
> > # Solution to ruby quiz #145
> > # http://www.rubyquiz.com/quiz145.html
> > # by Holger
> > #
> > # GapBuffer works similar to StringCaret
> > #
> > # Some remarks:
> > # - if gap size is zero before insert it will be set to 64
> > # - data buffer will never shrink -> gap might be very large
> > # - lazy up and down methods, but cursor remains in same column (if fits
> in
> > line)
>
>
> Hi Holger,
>
> Thanks for the solution.  One comment though.  This solution is not
> O(n).  Keep in mind that every time you increase the gap (insert in
> the middle of a string), it is an O(n) operation (written in C
> though).  For each 64 characters that you insert, you'll hit this
> case.  For insert, you have one component that is O(n) and another
> that is O(n*n/64)~O(n**2).  For large n, the n**2 component will
> dominate, so it is O(n**2).  For the sizes you are looking at, the
> n**2 component isn't dominating because its coefficient is small (1/64
> * insert written in C).
>
> With a small change, you can make this order n.  Hint: don't increase
> the gap by a constant amount.
>
> Eric
>
>

------art_13195_20751602.1194077764280--