On 9/6/07, Ruby Quiz <james / grayproductions.net> wrote:
> The discussion for this quiz was very interesting.  It's probably worth your
> time to go back and read those messages, if you haven't already.  Some points I
> got out of the discussion were:
>
>         * It's tricky to get ropes right.  Clever implementations may loose key
>           rope qualities, like the O(1) concatenation time.
>         * The functional approach, building immutable ropes, is probably
>           superior considering how ropes are intended to be used.
>         * Autorebalancing didn't hurt much, at least in the quiz test case.
>         * Copy-On-Write is helpful, when it works.
>
> Many of these points came out due to Eric Mahurin's work in benchmarking the
> submitted solutions.  Eric also submitted several variations of rope classes, a
> few of which I want to take a look at below.

I'm glad to see that you didn't let requests of the quiz get in the
way.  There were a bunch of things that I didn't do that the quiz
asked for (in the classes you presented):

* be able to append/prepend/shift mutable ropes (made immutable ropes instead)
* allow ropes to operate directly with strings (required a separate
StringRope proxy class instead)
* provide a normalize method (used auto-balancing concatenation instead)
* O(1) concatenation - the max and average number of rotations for my
auto-balancing concatenation is O(log(n)).  Slicing is also O(log(n)),
so it isn't a big problem.

Eric