bench_zipper.rb

require 'zipper'
require 'benchmark'

MAX = 5000
Benchmark.bm do |x|
  x.report "zipper" do
    original = Zipper.make(*(0..MAX).to_a)
    zippers = (0..MAX).map{|i|
      original.next.set(i)
    }
    zippers
  end
  x.report "array" do
    ary = (0..MAX).to_a
    arys = (0..MAX).map {|i|
      item = ary.dup
      item[0] = i
      item
    }
  end
end

spec_zipper.rb

require 'zipper.rb'

describe "Zipper.ary_to_listは" do
  it "配列をリストに変換する" do
    Zipper.ary_to_list([1,2,3]).should == [1, [2, [3, []]]]
  end
end

describe "Zipper.list_to_aryは" do
  it "リストを配列に変換する" do
    Zipper.list_to_ary([1, [2, [3, []]]]).should == [1,2,3]
  end
end

describe "Zipperは" do
  context "単純なリストを与えられたとき" do
    before :all do
      @zipper = Zipper.make(1,2,3)
    end

    it "作ったばかりのときは先頭にいる" do
      @zipper.begin?.should be_true
      @zipper.end?.should be_false
    end

    it "作ったばかりのときは最初の要素を取れる" do
      @zipper.get.should == 1
    end

    it "1つ進むと2番目の要素を取れる" do
      @zipper.next.get.should == 2
    end

    it "1つ進んで戻ると1番目の要素を取れる" do
      @zipper.next.prev.get.should == 1
    end

    it "3つ進むと末尾に来る" do
      @zipper.next.next.next.end?.should be_true
    end
  end

  context "書き変えを行ったとき" do
    before :all do
      @zipper = Zipper.make(1,2,3).next.set(4)
    end

    it "getすると値が書き換わっている" do
      @zipper.get.should == 4
    end

    it "カーソルを移動してもちゃんと書き換わっている" do
      @zipper.next.prev.get.should == 4
    end
  end

  context "Enumerableをincludeしているので" do
    before :all do
      @zipper = Zipper.make(1,2,3)
    end

    it "to_aで配列に変換できる" do
      @zipper.to_a.should == [1,2,3]
    end

    it "書き換えてもちゃんと変換できる" do
      @zipper.next.set(4).to_a.should == [1,4,3]
    end
  end

  it "insertで長さを伸ばせる" do
    Zipper.make(1,2,3).insert(0).to_a.should == [0,1,2,3]
  end
  
  it "removeで長さを減らせる" do
    Zipper.make(1,2,3).remove.to_a.should == [2,3]
  end

  it "大量にコピーしてそれぞれ書き換えたりしてもへっちゃら！" do
    original = Zipper.make(*(0..10000).to_a)
    zippers = (0..10000).map{|i|
      original.next.set(i)
    }
    zippers[99].get.should == 99
    zippers[1234].get.should == 1234
  end

end

zipper.rb

#
# Zipper has @left and @right.
# When a zipper represents [1, 2, 3, <cursor>, 4, 5],
#  @left == [3, [2, [1, []]]],  @right == [4, [5, []]]
# Note that @left is in reverse order.
#
class Zipper
  include Enumerable

  def self.make(*vals)
    new([], ary_to_list(vals))
  end

  def initialize(left = [], right = [])
    @left = left
    @right = right
  end

  def each
    Zipper.list_to_ary(@left).reverse_each do |x|
      yield x
    end
    Zipper.list_to_ary(@right).each do |x|
      yield x
    end
  end

  def begin?
    @left.empty?
  end

  def end?
    @right.empty?
  end

  def next
    Zipper.new( [car(@right), @left], cdr(@right) )
  end

  def prev
    Zipper.new( cdr(@left), [car(@left), @right] )
  end

  def get
    car(@right)
  end

  def set(val)
    Zipper.new( @left, [val, cdr(@right)] )
  end

  def insert(val)
    Zipper.new( @left, [val, @right])
  end

  def remove
    Zipper.new( @left, cdr(@right) )
  end

  private
  def car(pair)
    pair[0]
  end

  def cdr(pair)
    pair[1]
  end

  def self.ary_to_list(ary)
    ary.reverse.inject([]){|list, item|
      [item, list]
    }
  end

  def self.list_to_ary(list)
    ary = []
    until list.empty?
      ary.push list[0]
      list = list[1]
    end
    ary
  end

end