A very basic version of persistent vector data structure

persistent_vector.rb

class Node
  attr_accessor :edit, :array
  def initialize(edit, list)
    @edit = edit
    @array = list
    @count = 0
    @shift = 0
  end
end

class PersistentVector
  attr_reader :count, :root, :tail, :shift

  def initialize(count, shift, root, tail)
    @count = count
    @root = root
    @shift = shift
    @tail = tail
  end

  EMPTY_NODE = Node.new(Thread.current, Array.new(32))
  EMPTY = PersistentVector.new(0, 5, EMPTY_NODE, Array.new(32))

  def self.create(vals)
   ret = EMPTY.to_transient 
   vals.each { |i| ret = ret.conj(i)}
   ret.persistent
  end

  def to_transient
    TransientVector.new(count, shift, root, tail)
  end

  def size
    count
  end

  def [](i)
    node = array_for(i)
    node[i & 0x01f]
  end

  def set(i, val)
    raise unless i >= 0 && i < count
    if i >= tailoff
      new_tail = tail.dup
      new_tail[i & 0x01f] = val
      PersistentVector.new(count, shift, root, new_tail)
    else
      PersistentVector.new(count, shift, set_assoc(shift, root, i, val), tail)
    end
  end


  def set_assoc(level, node, i, val)
    ret = Node.new(node.edit, node.array.clone)
    if level == 0
      ret.array[i & 0x01f] = val
    else
      subdix = (i >> level) & 0x01f
      ret.array[subdix] = set_assoc(level-5, node.array[subdix], i, val)
    end
    ret
  end

  def <<(val)
    if (count - tailoff) < 32
      new_tail = tail + [val] 
      return PersistentVector.new(count+1, shift, root, new_tail)
    end

    newroot = nil
    tail_node = Node.new(root.edit, tail)
    newshift = shift

    if (count >> 5) > (1 << shift)
      newroot = Node.new(root.edit, Array.new(32))
      newroot.array[0] = root
      newroot.array[1] = new_path(root.edit, shift, tail_node)
      newshift += 5
    else
      newroot = push_tail(shift, @root, tail_node)
    end

    PersistentVector.new(count+1, newshift, newroot, [val])
  end


  def push_tail(level, parent, tailnode)
    subdix = ((count-1) >> level) & 0x01f
    ret = Node.new(parent.edit, parent.array.clone)
    node_to_insert = nil
    if level == 5
      node_to_insert = tailnode
    else
      child = parent.array[subdix]
      node_to_insert = child.nil? ? new_path(root.edit, level-5, tailnode) : push_tail(level-5, child, tailnode)
    end
    ret.array[subdix] = node_to_insert
    ret
  end

  private

  def tailoff
    return 0 if count < 32
    ((count-1) >> 5) << 5
  end

  def array_for(i)
    raise unless i >= 0 && i < count
    return tail if i >= tailoff
    node = root
    level = shift
    until level <= 0
      node = node.array[(i >> level) & 0x01f]
      level -= 5
    end
    node.array
  end

  def new_path(edit, level, node)
    return node if level == 0
    ret = Node.new(edit, Array.new(32))
    ret.array[0] = new_path(edit, level-5, node)
    ret
  end

end

class TransientVector
  attr_reader :count, :shift, :root, :tail

  def initialize(count, shift, root, tail)
    @count = count
    @shift = shift
    @root = root
    @tail = tail
  end

  def persistent
    root.edit = nil
    trimmed_tail = tail[0...(count-tailoff)]
    PersistentVector.new(count, shift, root, trimmed_tail)
  end


  def conj(val)
    i = count

    if (i - tailoff) < 32
      @tail[i & 0x01f] = val
      @count += 1
      return self
    end

    tailnode = Node.new(root.edit, tail.dup)
    @tail = []
    @tail[0] = val

    newshift = shift

    if (count >> 5) > (1 << shift)
      newroot = Node.new(root.edit, Array.new(32))
      newroot.array[0] = root
      newroot.array[1] = new_path(root.edit, shift, tailnode)
      newshift += 5
    else
      newroot = push_tail(shift, @root, tailnode)
    end

    @root = newroot
    @shift = newshift
    @count += 1
    self
  end


  def push_tail(level, parent, tailnode)
    subdix = ((count-1) >> level) & 0x01f
    ret = parent
    node_to_insert = nil
    if level == 5
      node_to_insert = tailnode
    else
      child = parent.array[subdix]
      node_to_insert = child.nil? ? new_path(root.edit, level-5, tailnode) : push_tail(level-5, child, tailnode)
    end
    ret.array[subdix] = node_to_insert
    ret
  end

  private

  def ensure_editable
    raise "Error" unless root.edit == Thread.current
  end

  def tailoff
    return 0 if count < 32
    ((count-1) >> 5) << 5
  end

  def new_path(edit, level, node)
    return node if level == 0
    ret = Node.new(edit, Array.new(32))
    ret.array[0] = new_path(edit, level-5, node)
    ret
  end
end


acc = (1..120).inject([]) { |arry, i| arry << i }
p t = PersistentVector.create(acc)
p t[23]
p t[115]
p t[65]
p t.set(115, "boo")
p t.set(65, "boo")

require 'benchmark'

a = []
p d = PersistentVector.create([1, 2, 3])
p Benchmark.measure { 1000.times { |i| d = (d << i) } }
p Benchmark.measure { 1000.times { |i| a << i } }