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