NAPPTextureUtility/RadixTree.py at main · JsMarq96/NAPPTextureUtility · 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
#!/usr/bin/env python3

'''
    Radix tree utility for speeding up the directory comparison
    by Juan S. Marquerie
'''


def str_compare(str1, str2):
    '''Returns the char similarity count between 2 strigs'''
    i = 0
    for i in range(min(len(str1), len(str2))):
        if str1[i] != str2[i]:
            return i + 1
    return i + 1

class RT_Node:
    '''Node of a radix tree'''
    def __init__(self):
        self.base_str = None
        self.result = None
        self.nodes = [None] * 128

class RadixTree:
    '''Custom radix tree implementation'''
    def __init__(self, default_value=None):
        self.base_node = RT_Node()
        self.default_result = default_value

    def get(self, search_str):
        '''Fethc an element from the radix tree'''
        iter_node = self.base_node.nodes[ord(search_str[0])]
        while not iter_node is None:
            similarity = str_compare(search_str, iter_node.base_str)

            #print(':+SEARCH ', similarity, search_str, iter_node.base_str)
            if similarity == len(search_str) and similarity == len(iter_node.base_str):
                return iter_node.result
            elif similarity == 0 or similarity < len(iter_node.base_str):
                return self.default_result
            else:
                # Split the similar part of the serach and continues search on another node
                search_str = search_str[similarity:]
                iter_node = iter_node.nodes[ord(search_str[0])]

        return self.default_result

    def get_with_wildcard(self, search_str):
        '''Flexibilices the get procedure with the addiciont of * wildcards'''
        if 'magma' in search_str:
            print(search_str, '--------<<<<<<<')
        iter_node = self.base_node.nodes[ord(search_str[0])]
        while not iter_node is None:
            similarity = str_compare(search_str, iter_node.base_str)

             # Addition of the wildcard
            if iter_node.base_str[similarity - 1] == '*':
                return iter_node.result
            if similarity == len(search_str) and similarity == len(iter_node.base_str):
                return iter_node.result
            elif similarity == 0 or similarity < len(iter_node.base_str):
                return self.default_result
            else:
                # Split the similar part of the serach and continues search on another node
                search_str = search_str[similarity:]
                iter_node = iter_node.nodes[ord(search_str[0])]

        return self.default_result

    def add(self, search_str, result):
        '''Append an element to the radix tree'''
        # Base node insert
        if self.base_node.nodes[ord(search_str[0])] is None:
            tmp = RT_Node()
            tmp.base_str = search_str
            tmp.result = result
            self.base_node.nodes[ord(search_str[0])] = tmp

            return

        iter_node = self.base_node.nodes[ord(search_str[0])]

        while True:
            base_similarity = str_compare(search_str, iter_node.base_str)
            crop_search_str = search_str[base_similarity:]
            print('~~~crop search str', crop_search_str, 'search_str', search_str)
            search_index = ord(crop_search_str[0])

            if base_similarity < len(iter_node.base_str):
                old_root_node = RT_Node()
                old_root_node.nodes = iter_node.nodes
                old_root_node.base_str = iter_node.base_str[base_similarity-1:]
                old_root_node.result = iter_node.result

                iter_node.base_str = search_str[:base_similarity-1]
                iter_node.nodes = [None] * 128

                iter_node.nodes[ord(old_root_node.base_str[0])] = old_root_node

                new_node = RT_Node()
                new_node.base_str = search_str[base_similarity-1:]
                new_node.result = result

                iter_node.nodes[ord(new_node.base_str[0])] = new_node

                return
            elif base_similarity > len(iter_node.base_str):
                if iter_node.nodes[search_index] is None:
                    new_node = RT_Node()
                    new_node.base_str = crop_search_str
                    new_node.result = result

                    iter_node.nodes[search_index] = new_node
                    return

                iter_node = iter_node.nodes[search_index]
                search_str = crop_search_str
            else:
                if iter_node.nodes[search_index] is None:
                    new_node = RT_Node()
                    new_node.base_str = crop_search_str
                    new_node.result = result

                    iter_node.nodes[search_index] = new_node
                    return
                search_str = crop_search_str
                iter_node = iter_node.nodes[search_index]

if __name__ == '__main__':
    rt = RadixTree(True)

    test_arr = ['assets/minecraft/textures/gui/title/background/panorama_0.png',
                'assets/minecraft/textures/gui/title/background/panorama_4.png',
                'assets/minecraft/textures/gui/title/background/panorama_3.png',
                'assets/minecraft/textures/gui/title/background/panorama_5.png',
                'assets/minecraft/textures/gui/title/background/panorama_2.png',
                'assets/minecraft/textures/gui/title/background/panorama_1.png']

    for t in test_arr:
        print('Inserting ', t)
        rt.add(t, False)
        for v in test_arr:
            print(v, rt.get(v))
        print('==========')