I've done parts one and two so far.  I'll try to add more in the next
few days.

For simplicity and speed, append and prepend don't modify the
receiver.

If anyone has any questions about my code, I'll be happy to answer.

Carl

require "rubygems"
require "facets"
require "kernel/with"
require "symbol/to_proc"

class String
  def shift
    return nil if empty?
    returning self[0].chr do
      self[0] = ""
    end
  end
end

class Rope
  attr_reader :left, :right, :length

  def Rope.new(*args)
    if args.size <= 2
      super
    else # build balanced tree
      mid = args.size / 2
      args[mid,2] = Rope.new(*args[mid,2])
      Rope.new(*args)
    end
  end

  def initialize(left="",right="")
    @left, @right = left, right
    @length = @left.length + @right.length
  end

  def replace(rope)
    initialize(rope.left,rope.right)
    self
  end

  # clean out empty strings and rebuild tree
  def normalize
    Rope.new(*flat_strings.reject(&:empty?))
  end

  def to_s
    flat_strings.join('')
  end

  def append(str)
    Rope.new(self,str)
  end
  alias_method :<<, :append

  def prepend(str)
    Rope.new(str,self)
  end

  def slice(start,length=@length-start)
    if start > left.length # right
      right.slice(start-left.length,length-left.length)
    elsif left.length < length # left and right
      left.slice(start,left.length) +
      right.slice(start-left.length,length-left.length)
    else # left
      left.slice(start,length)
    end
  end

  def shift
    if letter = left.shift || right.shift
      @length -= 1
      letter
    else
      nil
    end
  end

  def index(letter,start=0)
    if start > left.length # right
      left.length + right.index(letter,start - left.length)
    else # left
      left.index(letter,start) || left.length + right.index(letter)
    end
  rescue
    nil
  end

  # TODO implement rest of methods
  def method_missing(method, *args, &block)
    result = to_s.send(method, *args, &block)
    if result.is_a?(String)
      if method.to_s =~ /!$/
        replace(Rope.new(result))
      else
        Rope.new(result)
      end
    else
      result
    end
  end

protected

  # traverse the tree
  def traverse(&block)
    @left.is_a?(Rope) ? @left.traverse(&block) : block.call(@left)
    @right.is_a?(Rope) ? @right.traverse(&block) : block.call(@right)
  end

  # collect all the flat strings
  def flat_strings
    returning [] do |ary|
      traverse { |str| ary << str }
    end
  end

end


On Aug 31, 6:19 am, Ruby Quiz <ja... / grayproductions.net> wrote:
> The three rules of Ruby Quiz:
>
> 1.  Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.
>
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
>
> http://www.rubyquiz.com/
>
> 3.  Enjoy!
>
> Suggestion:  A [QUIZ] in the subject of emails about the problem helps everyone
> on Ruby Talk follow the discussion.  Please reply to the original quiz message,
> if you can.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- =-=-=
>
> by John Miller
>
> This week's task is to implement the Rope data structure as a Ruby class.  This
> topic comes out of the ICFP programming competition
> (http://www.icfpcontest.com/) which had competitors manipulating a 7.5 million
> character string this year.
>
>         What is a Rope:
>
> You may not realize it, but for many changes the content to a String, Ruby
> creates a new copy of the original with the modifications applied.  For small
> strings that are created once and read often this is actually a very efficient
> way to do thing, but what happens when the string starts to get long, and is
> undergoing a lot of changes?  First, the program will spend more and more of its
> processing cycles just copying bits around.  Second, the garbage collector will
> be called more and more often to pick up the little stringy scraps you've left
> all over the memory.
>
> Ropes (the name is a pun for a heavy duty string) are tree structures where a
> node represents the concatenation of its left branch with its right, and leaves
> are flat strings. (This is a little sloppy. A rope may contain shared subtrees,
> and is thus really a directed acyclic graph, where the out-edges of each vertex
> are ordered. We will continue to be sloppy.)  E.g. To prepend Text A to Text B,
> one creates a Node (call it N1) with A as its left branch and B as its right.  
> To further append Text C create a new Node N2 with its left branch pointing to
> N1 and its right to C.  Easy, right?  To find out more see Boehm, Atkinson and
> Plass "Ropes: an Alternative to Strings" at:
>
>        http://rubyurl.com/2FRbO
>
> The task comes in three parts, each increasing in difficulty:
>
> Part one:
>
> Create a Rope class that can do the following:
>
>         a. 'append' or 'prepend' a String or another Rope
>            (alias the << operator to the append function)    
>         b. Return the fully concatenated text with 'to_s'
>         c. define 'slice' to call to_s.slice  
>         d. provide a 'length' method
>
> Part two:
>
> Add the following:
>
>         a. Add the ability to 'index' a single character given a 0-based offset
>            from the beginning of the string.
>         b. Add the ability to 'shift' a single character from the front of a Rope.
>            (Remove and return the character)
>         c. Add your own 'slice' method that returns a String. Implement as many of
>            the String method's forms as possible.  To run the example code this
>            function will only need to understand the slice(offset,length) form.
>            Major Bonus for Regex and Substring forms.
>         d. "Balance" the tree with a 'normalize' method.
>            (see Boehm, Atkinson and Plass 1319 Rebalancing)
>
> Part three: (bonus)
>
> Add the following:
>
>         a. Change the 'slice' method to return a Rope. Ideally this method should
>            do as little string copying as possible. (Doing this will well
>            dramatically increase the speed of the example code)
>         b. Allow 'shift' to optionally accept an integer number of characters to
>            remove and return.
>         c. modify the '<<' operator so that can efficiently append a few
>            characters at a time. (see Boehm, Atkinson and Plass 1318 para. 4)
>         d. *Major Bonus* Add the ability to append and prepend IO classes in a
>            lazy fashion. (see Boehm, Atkinson and Plass 1318 para. 2)
>
> The following code may help you explore how efficient your code is and show
> where Ropes are useful.  `ruby -r /path/to/your/rope/class this_script.rb Rope`
> will run the test with your code.  Run the script without arguments to see how
> well String does.  Also play around with the SIZE and CHUNKS constants to get a
> feel for how they affect performance.
>
>         require 'benchmark'
>
>         #This code make a String/Rope of  CHUNCKS chunks of text
>         #each chunck is SIZE bytes long.  Each chunck starts with
>         #an 8 byte number.  Initially the chuncks are shuffled the
>         #qsort method sorts them into ascending order.
>         #
>         #pass the name of the class to use as a parameter
>         #ruby -r rope.rb this_file Rope
>
>         puts 'preparing data...'
>         TextClass = Object.const_get(ARGV.shift || :String)
>
>         def qsort(text)
>           return TextClass.new if text.length == 0
>           pivot = text.slice(0,8).to_s.to_i
>           less = TextClass.new
>           more = TextClass.new
>           offset = 8+SIZE
>           while (offset < text.length)
>             i = text.slice(offset,8).to_s.to_i
>             (i < pivot ? less : more) << text.slice(offset,8+SIZE)
>             offset = offset + 8+SIZE
>           end
>           print "*"
>           return qsort(less) << text.slice(0,8+SIZE) << qsort(more)
>         end
>
>         SIZE  = 512 * 1024
>         CHUNCKS = 128
>         CHARS = %w[R O P E]
>         data = TextClass.new
>         bulk_string =
>           TextClass.new(Array.new(SIZE) { CHARS[rand(4)] }.join)
>         puts 'Building Text...'
>         build = Benchmark.measure do
>           (0..CHUNCKS).sort_by { rand }.each do |n|
>             data<< sprintf("%08i",n) << bulk_string
>           end
>           data.normalize  if data.respond_to? :normalize
>         end
>         GC.start
>         sort = Benchmark.measure do
>           puts "Sorting Text..."
>           qsort(data)
>           puts"\nEND"
>         end
>
>         puts "Build: #{build}Sort: #{sort}"