破壊操作型赤黒木 その2.1 データ駆動テスト

前回で rspec へ直訳した Gauche 添付のテストを、データ駆動テストへ書き改めます。Gauche 添付のテストは、テスト対象の木の副作用を追いながら状況をテストしていく書き方になっています。この書き方ですと、どの状況を対象とする操作にバグがあるのか切り分けるのが面倒だからです。そこで、各状況のテストの入力の木をその都度組み立てるやりかたに変えます。こうすることで、各々の状況を個別にテストできるようになります。その上、データ駆動では各状況をばらばらに分離可能なので、挿入操作用と削除操作用に別の rspec ファイルに切り分けることもできます。

挿入のテストを spec/insert.rb に定義します。木の手動組み立てを簡潔に記述するため、黒ノードを作る B 関数、赤ノードを作る r 関数、NULL を表す N 定数を定義しています。

#!/usr/bin/env rspec -I.
require 'rspec'
require 'redblacktree.rb'

# from https://github.com/shirok/Gauche/blob/master/test/treemap.scm by Shiro Kawai

if not Object.const_defined?(:B)
  Object.const_set(:B, lambda{|*a| RedBlacktree::Node.black(*a) })
  Object.const_set(:N, RedBlacktree::NULL)
end
def r(*a) RedBlacktree::Node.red(*a) end

describe RedBlacktree do
  before do
    @tree = RedBlacktree.new
  end

  it 'insertion case 0. adding to an empty tree' do
    @tree.insert(0)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([0])
  end

  it 'insertion case 2. adding to a black parent' do
    @tree.root = B[N, 0, N]
    @tree.insert(1)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([0, 1])
  end

  it 'insertion case 3&1. adding to a red parent, while uncle is also red.' do
    @tree.root = B[N, 0, r(N, 1, N)]
    [-1, -2, 2].each{|i| @tree.insert(i) }
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-2, -1, 0, 1, 2])
  end

  it 'insertion case 5b. adding to a red parent, while uncle is black.' do
    @tree.root = B[B[r(N, -2, N), -1, N], 0, B[N, 1, r(N, 2, N)]]
    @tree.insert(1.5)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-2, -1, 0, 1, 1.5, 2])
  end

  it 'insertion case 5a. same as 3a except left and right is swapped.' do
    @tree.root = B[B[r(N, -2, N), -1, N], 0, B[r(N, 1, N), 1.5, r(N, 2, N)]]
    @tree.insert(-1.5)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-2, -1.5, -1, 0, 1, 1.5, 2])
  end

  it 'insertion case 4a.' do
    @tree.root = B[r(B[r(N, -4, N), -3, r(N, -2, N)], -1, B[r(N, -0.7, N), -0.5, N]), 0, B[N, 2.5, r(N, 4, N)]]
    @tree.insert(-0.6)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-4, -3, -2, -1, -0.7, -0.6, -0.5, 0, 2.5, 4])
  end

  it 'insertion case4b' do
    @tree.root = B[B[r(N, -2, N), -1, N], -0.6, r(B[N, -0.5, r(N, -0.3, N)], 0, B[r(N, 1, N), 2, r(N, 3, N)])]
    @tree.insert(-0.4)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-2, -1, -0.6, -0.5, -0.4, -0.3, 0, 1, 2, 3])
  end
end

削除のテストも spec/delete.rb に同様に定義します。

#!/usr/bin/env rspec -I.
require 'rspec'
require 'redblacktree.rb'

# from https://github.com/shirok/Gauche/blob/master/test/treemap.scm by Shiro Kawai

if not Object.const_defined?(:B)
  Object.const_set(:B, lambda{|*a| RedBlacktree::Node.black(*a) })
  Object.const_set(:N, RedBlacktree::NULL)
end
def r(*a) RedBlacktree::Node.red(*a) end

describe RedBlacktree do
  before do
    @tree = RedBlacktree.new
  end

  it 'deletion case 1. deleting the leaf red node.' do
    @tree.root = B[B[r(N, -2, N), -1.5, r(N, -1, N)], 0, B[r(N, 1, N), 1.5, r(N, 2, N)]]
    @tree.delete(2)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-2, -1.5, -1, 0, 1, 1.5])
  end

  it 'deletion case 8a. deleting the leaf black node.' do
    @tree.root = B[r(B[r(N, -3, N), -2, N], -1.5, B[N, -1, N]), 0, r(B[N, 1, N], 1.5, B[N, 2, r(N, 3, N)])]
    @tree.delete(1)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-3, -2, -1.5, -1, 0, 1.5, 2, 3])
  end

  it 'deletion case 8b. same, except left/right swapped' do
    @tree.root = B[r(B[r(N, -3, N), -2, N], -1.5, B[N, -1, N]), 0, r(B[N, 1.5, N], 2, B[N, 3, N])]
    @tree.delete(-1)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-3, -2, -1.5, 0, 1.5, 2, 3])
  end

  it 'deletion case 6. deleting red node w/ both children' do
    @tree.root = B[r(B[N, -3, N], -2, B[N, -1.5, N]), 0, r(B[N, 1.5, N], 2, B[N, 3, N])]
    @tree.delete(2)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-3, -2, -1.5, 0, 1.5, 3])
  end

  it 'deletion case 2. deleting black node, whose parent is black and sibing is red.' do
    @tree.root = B[r(B[N, -3, N], -2, B[N, -1.5, N]), 0, B[N, 1.5, r(N, 3, N)]]
    @tree.delete(1.5)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-3, -2, -1.5, 0, 3])
  end

  it 'deletion case 5. deleting black node, whose parent and sibling is black' do
    @tree.root = B[B[B[N, -3, N], -2, B[N, -1.5, N]], 0, B[B[r(N, 0.5, N), 1, N], 2, r(B[N, 2.5, N], 3, B[N, 3.5, r(N, 4, N)])]]
    @tree.delete(-3)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-2, -1.5, 0, 0.5, 1, 2, 2.5, 3, 3.5, 4])
  end

  it 'deletion case 7a deleting black node, which is a left child of its parent,' do
    @tree.root = B[B[r(B[N, -2, N], -1.5, B[r(N, -1, N), -0.5, N]), 0, B[r(N, 0.5, N), 1, N]], 2, B[B[N, 2.5, N], 3, B[N, 3.5, r(N, 4, N)]]]
    @tree.delete(-2)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-1.5, -1, -0.5, 0, 0.5, 1, 2, 2.5, 3, 3.5, 4])
  end

  it 'deletion case 4b. deleting black node, whose sibling is red.' do
    @tree.root = B[B[r(B[N, -1.5, N], -1, B[N, -0.5, N]), 0, B[N, 1, N]], 2, B[B[N, 2.5, N], 3, B[N, 3.5, r(N, 4, N)]]]
    @tree.delete(1)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-1.5, -1, -0.5, 0, 2, 2.5, 3, 3.5, 4])
  end

  it 'deletion case 3. this goes through parent==NULL stop condition in the' do
    @tree.root = B[B[B[N, -1.5, N], -1, B[r(N, -0.5, N), 0, N]], 2, B[B[N, 2.5, N], 3, B[N, 3.5, r(N, 4, N)]]]
    @tree.delete(2)
    @tree.delete(-1)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-1.5, -0.5, 0, 2.5, 3, 3.5, 4])
  end

  it 'deletion case4a. the reverse case of 4b' do
    @tree.root = B[B[N, -2, N], -1, r(B[N, -0.7, N], -0.6, B[r(N, -0.5, N), 0, N])]
    @tree.delete(-2)
    expect(@tree).to be_consistent
    expect(@tree.to_a).to eq([-1, -0.7, -0.6, -0.5, 0])
  end
end

これで、挿入と削除のルーチンを書く準備が整いました。