BPlusTree/tests.py at main · nspyrop03/BPlusTree · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
from bplustree import BPlusTree, Node

def print_keys(node):
    print(node.keys)
    if not(node.is_leaf):
        for n in node.pointers:
            print(n.keys,end=' ')
        print()

def create_tree(file_name):
    f = open(file_name, "r")
    order = int(f.readline())
    height = int(f.readline())
    tree = BPlusTree(order)
    rows = []
    for i in range(height):
        nodes = f.readline().split(",")
        row = []
        for n in nodes:
            keys = list(map(int, n.split("|")))
            node = Node(is_leaf=(i==0))
            node.keys = keys
            row.append(node)
        rows.append(row)

    for i in range(height):
        row = rows[i]
        if i == 0:
            for j in range(len(row)):
                node = row[j]
                for key in node.keys:
                    node.pointers.append(f"{key}")
                if j < len(row)-1:
                    node.pointers.append(row[j+1])
        else:
            offset = 0
            for j in range(len(row)):
                node = row[j]
                for k in range(len(node.keys)+1):
                    node.pointers.append(rows[i-1][offset+k])
                offset += len(node.keys)+1

    tree.root = rows[-1][0]
    f.close()
    return tree

def run_test(id, in_file, out_file, tests):
    in_tree = create_tree(in_file)
    for test in tests:
        parts = test.split(" ")
        key = int(parts[1])
        pointer = f"{key}"
        if parts[0] == "i":
            in_tree.insert(key, pointer)
        elif parts[0] == "d":
            in_tree.delete(key, pointer)
    out_tree = create_tree(out_file)
    eq = str(in_tree) == str(out_tree)
    msg = "OK" if eq else "NOT OK"
    print(f"[TESTING] Test {id}: {msg}!")
    if not(eq):
        print("in_tree is:")
        in_tree.print_tree()
        print("out_tree is:")
        out_tree.print_tree()

def run_test2():
    test2 = BPlusTree(5)
    test2.insert(2, '2')
    test2.insert(3, '3')
    test2.insert(4, '4')
    test2.print_tree()
    print(test2.root)
    test2.delete(2, '2')
    test2.delete(3, '3')
    print(test2.root)
    test2.print_tree()
    test2.delete(4, '4')
    print(test2.root)
    test2.print_tree()

def run_int_test():
    print("==========[ INT TEST ]==========")
    test3 = BPlusTree(3)
    test3.insert(1, '1')
    test3.insert(2, '2')
    test3.insert(3, '3')
    test3.print_tree(showPointers=True)
    test3.insert(4, '4')
    test3.print_tree(showPointers=True)
    print(test3.test_find(3))
    test3.delete(4, '4')
    print(str(test3))
    print(test3.test_find(3))
    test3.print_tree(showPointers=True)
    test3.delete(3, '3')
    test3.print_tree(showPointers=True)
    test3.delete(2, '2')
    test3.print_tree(showPointers=True)
    test3.delete(1, '1')
    test3.insert(1, '1')
    test3.print_tree(showPointers=True)

def run_string_test():
    test3 = BPlusTree(3)
    test3.insert('2', '2')
    test3.insert('21', '21')
    test3.insert('3', '3')
    test3.insert('a', 'a')
    test3.print_tree(showPointers=True)
    print(test3.test_find('3'))
    test3.delete('a', 'a')
    print(str(test3))
    print(test3.test_find('3'))
    test3.print_tree(showPointers=True)
    test3.delete('3', '3')
    print(str(test3))

def run_weird_test():
    print("==========[ WEIRD TEST ]==========")
    test = BPlusTree(3)
    test.insert(1, '1')
    test.insert(2, '2')
    test.insert(21, '21')
    test.print_tree(showPointers=True)
    print(test.test_find(3))
    test.insert(3, '3')
    test.print_tree(showPointers=True)

if __name__ == "__main__":
    tree = "trees/tree.txt"
    run_test(1, tree, "trees/tree1.txt", ["i 9"])
    run_test(2, tree, "trees/tree2.txt", ["i 3"])
    run_test(3, tree, "trees/tree3.txt", ["d 8"])
    run_test(5, tree, "trees/tree5.txt", ["i 46", "d 52"])
    run_test(6, tree, "trees/tree6.txt", ["d 91"])
    run_test(7, tree, "trees/tree7.txt", ["i 59", "d 91"])
    run_test(8, tree, "trees/tree8.txt", ["d 32","d 39","d 41","d 45","d 73"])

    test_tree = create_tree("trees/tree.txt")
    print(test_tree.getDictTree())
    test_tree.print_tree()
    print(test_tree.getLevelSizes())

    #run_test2()
    #run_int_test()
    #run_string_test()
    run_weird_test()