## 2019年4月16日火曜日

### Algorithm - Python - 質問するにもお金がかかる - オブジェクト指向プログラミング、二分探索木 - キー、昇順、リスト

コード

Python 3

```#!/usr/bin/env python3
from unittest import TestCase, main

class BSTreeTest(TestCase):
def setUp(self):
self.t0 = BSTree()
self.t1 = BSTree(BSTVertex(22))
self.t2 = BSTree(BSTVertex(22,
BSTVertex(21)))
self.t3 = BSTree(BSTVertex(22,
BSTVertex(21),
BSTVertex(23, None, BSTVertex(24))))

def tearDown(self):
pass

def test_len_zero(self):
self.assertEqual(0, len(self.t0))

def test_len_one(self):
self.assertEqual(1, len(self.t1))

def test_len_two(self):
self.assertEqual(2, len(self.t2))

def test_len_four(self):
self.assertEqual(4, len(self.t3))

def test_range_keys(self):
bst = BSTree(BSTVertex(22,
BSTVertex(14,
BSTVertex(2, None, None),
BSTVertex(17, None, None)),
BSTVertex(33,
BSTVertex(27, None, None),
None)))
self.assertEqual([14, 17, 22], bst.range_keys(10, 22))

class BSTVertex:
def __init__(self, val, left_child=None, right_child=None):
self.val = val
self.left_child = left_child
self.right_child = right_child

def __len__(self):
count = 1
if self.left_child is not None:
count += len(self.left_child)
if self.right_child is not None:
count += len(self.right_child)
return count

def range_keys(self, k1, k2):
keys = []
if k1 <= self.val <= k2:
keys.append(self.val)
if self.left_child is not None:
keys += self.left_child.range_keys(k1, k2)
if self.right_child is not None:
keys += self.right_child.range_keys(k1, k2)
return sorted(keys)

class BSTree:
def __init__(self, root=None):
self.root = root

def lookup(self, val) -> bool:
def helper(val, vertex):
if vertex == None:
return False
if val == vertex.val:
return True
if val < vertex.val:
return helper(val, vertex.left_child)
return lookup(val, vertex.right_child)
return helper(val, self.root)

def __len__(self) -> int:
if self.root is None:
return 0
return len(self.root)

def range_keys(self, k1, k2):
if self.root is None:
return []
return self.root.range_keys(k1, k2)

if __name__ == '__main__':
main()
```

```C:\Usrs\...>py sample4.py
EEEE
======================================================================
ERROR: test_len_four (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "sample4.py", line 28, in test_len_four
self.assertEqual(4, len(self.t3))
TypeError: 'NoneType' object cannot be interpreted as an integer

======================================================================
ERROR: test_len_one (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "sample4.py", line 22, in test_len_one
self.assertEqual(1, len(self.t1))
TypeError: 'NoneType' object cannot be interpreted as an integer

======================================================================
ERROR: test_len_two (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "sample4.py", line 25, in test_len_two
self.assertEqual(2, len(self.t2))
TypeError: 'NoneType' object cannot be interpreted as an integer

======================================================================
ERROR: test_len_zero (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "sample4.py", line 19, in test_len_zero
self.assertEqual(0, len(self.t0))
TypeError: 'NoneType' object cannot be interpreted as an integer

----------------------------------------------------------------------
Ran 4 tests in 0.001s

FAILED (errors=4)

C:\Usrs\...>py sample4.py
EEE.
======================================================================
ERROR: test_len_four (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "sample4.py", line 28, in test_len_four
self.assertEqual(4, len(self.t3))
File "sample4.py", line 64, in __len__
return len(self.root)
TypeError: object of type 'BSTVertex' has no len()

======================================================================
ERROR: test_len_one (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "sample4.py", line 22, in test_len_one
self.assertEqual(1, len(self.t1))
File "sample4.py", line 64, in __len__
return len(self.root)
TypeError: object of type 'BSTVertex' has no len()

======================================================================
ERROR: test_len_two (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "sample4.py", line 25, in test_len_two
self.assertEqual(2, len(self.t2))
File "sample4.py", line 64, in __len__
return len(self.root)
TypeError: object of type 'BSTVertex' has no len()

----------------------------------------------------------------------
Ran 4 tests in 0.001s

FAILED (errors=3)

C:\Usrs\...>py sample4.py
F...
======================================================================
FAIL: test_len_four (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "sample4.py", line 28, in test_len_four
self.assertEqual(4, len(self.t3))
AssertionError: 4 != 2

----------------------------------------------------------------------
Ran 4 tests in 0.001s

FAILED (failures=1)

C:\Usrs\...>py sample4.py
....
----------------------------------------------------------------------
Ran 4 tests in 0.000s

OK

C:\Usrs\...>py sample4.py
....E
======================================================================
ERROR: test_range_keys (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "sample4.py", line 38, in test_range_keys
self.assertEqual([14, 17, 22], bst.range_keys(10, 22))
AttributeError: 'BSTree' object has no attribute 'range_keys'

----------------------------------------------------------------------
Ran 5 tests in 0.001s

FAILED (errors=1)

C:\Usrs\...>py sample4.py
....E
======================================================================
ERROR: test_range_keys (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "sample4.py", line 38, in test_range_keys
self.assertEqual([14, 17, 22], bst.range_keys(10, 22))
File "sample4.py", line 89, in range_keys
return self.root.range_keys(k1, k2)
AttributeError: 'BSTVertex' object has no attribute 'range_keys'

----------------------------------------------------------------------
Ran 5 tests in 0.001s

FAILED (errors=1)

C:\Usrs\...>py sample4.py
....E
======================================================================
ERROR: test_range_keys (__main__.BSTreeTest)
----------------------------------------------------------------------
Traceback (most recent call last):
File "sample4.py", line 38, in test_range_keys
self.assertEqual([14, 17, 22], bst.range_keys(10, 22))
File "sample4.py", line 89, in range_keys
return self.root.range_keys(k1, k2)
File "sample4.py", line 62, in range_keys
keys += self.right_child.range_keys(k1, k2)
File "sample4.py", line 62, in range_keys
keys += self.right_child.range_keys(k1, k2)
AttributeError: 'NoneType' object has no attribute 'range_keys'

----------------------------------------------------------------------
Ran 5 tests in 0.001s

FAILED (errors=1)

C:\Usrs\...>py sample4.py
.....
----------------------------------------------------------------------
Ran 5 tests in 0.000s

OK

C:\Usrs\...>py sample4.py  -v
test_len_four (__main__.BSTreeTest) ... ok
test_len_one (__main__.BSTreeTest) ... ok
test_len_two (__main__.BSTreeTest) ... ok
test_len_zero (__main__.BSTreeTest) ... ok
test_range_keys (__main__.BSTreeTest) ... ok

----------------------------------------------------------------------
Ran 5 tests in 0.000s

OK

C:\Users\...>
```

ついでに問題2のsize関数を、ビルトイン関数のlen関数を使えるように、特殊メソッド__len__に変更してみた。