class Rope

  # Cat two ropes by building a new binary node.
  # The parent count is the left child's length.
  def cat(s)
    if self.len == 0
      s
    elsif s.len == 0
      self
    else
      Node.new(self, s, len)
    end
  end

  # Insert a new string into a rope by splitting it
  # and concatenating twice with a new leaf in the middle.
  def insert(s, p)
    a, b = split_at(p)
    a.cat(Leaf.new(s)).cat(b)
  end

end

class Leaf < Rope
  # A leaf holds characters as a string.
  attr_accessor :chars

  # Construct a new leaf with given characters.
  def initialize(chars)
    @chars = chars
  end

  # The count in this rope is just the number of characters.
  def count
    chars.length
  end

  # The length is kind of obvious.
  def len
    chars.length
  end

  # Convert to a string by just returning the characters.
  def to_s
    chars
  end

  # Split by dividing the string.
  def split_at(p)
    [ Leaf.new(chars[0...p]), Leaf.new(chars[p..-1]) ]
  end
end

class Node < Rope
  # Fields of the binary node.
  attr_accessor :left, :right, :count

  # Construct a new binary node.
  def initialize(left, right, count)
    @left = left
    @right = right
    @count = count
  end

  # Length is our count plus right subtree length. Memoize for efficiency.
  def len
    @len ||= count + right.len
  end

  # The string rep is just concatenating the children's string reps.
  def to_s
    left.to_s + right.to_s
  end

  # Split recursively by splitting the left or right
  # subtree and recombining the results.
  def split_at(p)
    if p < count
      a, b = left.split_at(p)
      [ a, b.cat(right) ]
    elsif p > count
      a, b = right.split_at(p - count)
      [ left.cat(a), b ]
    else
      [ left, right ]
    end
  end
end