Database-Indexing/Btree.py at master · nsk06/Database-Indexing · 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
149
import sys,os
from bisect import *
from Node import Node
class Btree:
    '''Btree main class'''
    def __init__(self):
        self.nodecapacity = 3
        self.treeroot = Node(self.nodecapacity)
    def keyinsertstart(self,query):
        cur_root = self.treeroot
        mynewnode,splitroot = self.keyinsert(query,self.treeroot)
        if splitroot:
            tempnode = Node(self.nodecapacity)
            tempnode.keys.append(splitroot)
            tempnode.pointers.append(self.treeroot)
            tempnode.pointers.append(mynewnode)
            tempnode.leafcheck = False
            self.treeroot = tempnode

    def keyinsert(self,query,insertnode):
        splitcheck = None
        if insertnode.leafcheck == True:
            pos = bisect_right(insertnode.keys,query)
            if(pos > len(insertnode.keys)-1):
                insertnode.keys.append(query)
            else:
                insertnode.keys.insert(pos,query)
            if len(insertnode.keys) > insertnode.capacity:
                midpoint,mynewnode = insertnode.nodesplit()
                return mynewnode,midpoint
            else:
                return None,None

        else:

            if query < insertnode.keys[0]:
                mynewnode,splitcheck = self.keyinsert(query,insertnode.pointers[0])
            if (query >= insertnode.keys[len(insertnode.keys)-1]):
                mynewnode,splitcheck  = self.keyinsert(query,insertnode.pointers[len(insertnode.pointers)-1])

            for i in range(len(insertnode.keys)-1):
                if (query < insertnode.keys[i+1] and  query >= insertnode.keys[i]  ):
                    mynewnode,splitcheck = self.keyinsert(query,insertnode.pointers[i+1])

        if splitcheck:
            pos = bisect_right(insertnode.keys,splitcheck)
            if(pos > len(insertnode.keys)-1):
                insertnode.keys.append(splitcheck)
                insertnode.pointers.insert(pos+1,mynewnode)
            else:
                insertnode.keys.insert(pos,splitcheck)
                insertnode.pointers.insert(pos+1,mynewnode)
            if(len(insertnode.keys) > insertnode.capacity):
                midpoint,mynewnode = insertnode.nodesplit()
                return mynewnode,midpoint
            else:
                return None,None
        else:
            return None,None

    def findnode(self,query,curnode):
        if curnode.leafcheck == True:
            return curnode
        if query <= curnode.keys[0]:
            check_node = self.findnode(query,curnode.pointers[0])
            return check_node
        if query > curnode.keys[len(curnode.keys)-1]:
            return self.findnode(query,curnode.pointers[len(curnode.pointers)-1])
        for i in range(len(curnode.keys)-1):
            if (query <= curnode.keys[i+1] and query > curnode.keys[i]):
                check_node = self.findnode(query,curnode.pointers[i+1])
                return check_node
    def rangecount(self,startmin,endmax,startnode):
        ret = 0
        right_node = None
        if(len(startnode.keys)==0):
            return 0,None

        for keys in startnode.keys:
            if (keys <= endmax and keys>=startmin):
                # print("here",keys)
                ret+=1
        if(startnode.keys[len(startnode.keys)-1]>endmax):
            right_node = None
        else:
            if not startnode.right_node :
                right_node = None

            else:
                right_node = startnode.right_node


        return ret,right_node
    def rangeinitialise(self,mymin,mymax):
        start_node = self.findnode(mymin,self.treeroot)
        res = 0
        count,right_node = self.rangecount(mymin,mymax,start_node)
        res += count
        while right_node != None:
            count,right_node = self.rangecount(mymin,mymax,right_node)
            res += count
        return res


def runtests(command):
    global Tree
    if(command[0]=="INSERT"):
        Tree.keyinsertstart(int(command[1]))
        return -1
    elif(command[0]=="FIND"):
        ans = Tree.rangeinitialise(int(command[1]),int(command[1]))
        if ans ==0:
            return "NO"
        else:
            return "YES"
    elif(command[0]=="COUNT"):
        ans = Tree.rangeinitialise(int(command[1]),int(command[1]))
        return ans
    elif(command[0]=="RANGE"):
        ans = Tree.rangeinitialise(int(command[1]),int(command[2]))
        return ans
    else:
        print("Query Not Supported")
        sys.exit(-1)

def main():
    if(len(sys.argv)!=2):
        print("Please only input test_file as command line")
        sys.exit(-1)
    filename = sys.argv[1]
    with open(filename) as f:
        lines = f.readlines()
        lines = [i.strip() for i in lines]
        commands = []
        for i in lines:
            commands.append(i.split())
    out = []
    for c in commands:
        ret = runtests(c)
        if(ret!=-1):
            out.append(ret)
    for o in out:
        print(o)

if __name__ == "__main__":
    Tree = Btree()
    main()