ALDS1_8_C: Binary Search Tree III (続き4)

いろんなケースでちゃんと動くことを確認しようと思ったら
どれだけ書けばいいか見当がつかない

こういう場合コンピュータの中の人に力づくでテストしてもらうっていうのは
どうだろう

ランダムにノードを挿入してランダムに削除する
毎回要素のありなしと、中間順巡回がソートされた結果になっていることを
確認する
たくさん繰り返す
くらいでどうか
中間順巡回だけでも十分なくらいかも？

要素数が少なければ総当たりもできるかな？
6つくらい要素があればかなりのパターンを試せそうな気も

などと考えつつこんなテストを書いてみた

from random import randrange

class Tree():

    def fold_inorder(self, f, init):
        def rec(node, b):
            nonlocal f, init

            if not node:
                return b
            else:
                return rec(node.right,
                           f(node.key,
                             rec(node.left, b)))

        return rec(self.root, init)

    def flatten_inorder(self):
        return self.fold_inorder(
            lambda a, b: b + [a],
            [])

def random_test_repr(n, p, q, T):
    return "n:{}\np:{}\nq:{}\nT:{}".format(
        n, p, q, str(T))

def test_a_random_case(p, q):
    T = Tree()
    inserted = []

    for n in p:
        assert not T.find(n), \
            "Before Insert:\n" + \
            random_test_repr(n, p, q, str(T))
        T.insert(Node(n))
        assert T.find(n), \
            "After Insert:\n" + \
            random_test_repr(n, p, q, str(T))

        inserted.append(n)
        assert T.flatten_inorder() == sorted(inserted), \
            "Inorder(Inserting):\n" + \
            random_test_repr(n, p, q, str(T))

    for n in q:
        T.delete(n)
        assert not T.find(n), \
            "After Delete:\n" + \
            random_test_repr(n, p, q, str(T))

        inserted.remove(n)
        assert T.flatten_inorder() == sorted(inserted), \
            "Inorder(Deleting):\n" + \
            random_test_repr(n, p, q, str(T))

def random_array(l):
    arr = list(range(l))
    for i in range(l):
        j = randrange(l)
        tmp = arr[i]
        arr[i] = arr[j]
        arr[j] = tmp
    return arr

def random_test():
    N = 10000
    L = 7

    for i in range(N):
        test_a_random_case(
            random_array(L), random_array(L))

random_test()

要素数7とか試行回数10000は適当

ほしくなったのでTreeクラスにfoldを書いてみた
木でやるときもfoldって言うのかなあ
ただしinorderだけ
preorderとかpostorderと共通化する方法はまだ思いつかない

直したソースはこちら
本に載ってるコードに合わせればいいんだろうけどまずは自分のコード直した
親がいない場合を追加しただけ
ただし3箇所
ここまで来るとさすがになんとかアンチDRYを発動させないとという気分

    def delete_node(self, x):
        if x.left is None and x.right is None:
            if x.parent is None:
                self.root = None
            elif x.parent.left == x:
                x.parent.left = None
            else:
                x.parent.right = None
        elif x.left is None:
            if x.parent is None:
                self.root = x.right
            elif x.parent.left == x:
                x.parent.left = x.right
            else:
                x.parent.right = x.right
            x.right.parent = x.parent
        elif x.right is None:
            if x.parent is None:
                self.root = x.left
            elif x.parent.left == x:
                x.parent.left = x.left
            else:
                x.parent.right = x.left
            x.left.parent = x.parent

これでジャッジ通らなくなってたりしたら笑うけど無事AC

PAIZA解くのにテスト書いてこんなに時間かかってたら時間切れになりますね
っていうのは納期があるからテストは省略とかいうブラックな職場と同じになってしまうのだろうかと思ったり
おまえそれt_wadaの前でも言える？とかいうフレーズが思い浮かんだり