Skip to content

Instantly share code, notes, and snippets.

@yhara
Created August 7, 2008 07:41
Show Gist options
  • Save yhara/4357 to your computer and use it in GitHub Desktop.
Save yhara/4357 to your computer and use it in GitHub Desktop.
Ruby implementation of Zipper (and its spec)
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 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment