data_structures/trie/radix_tree.py wont really end up in 'case 1' for insert

[SimonUnge]

Repository commit

2e405f3

Python version (python --version)

Python 3.11.6

Dependencies version (pip freeze)

n/a

Expected behavior

root_node = RadixNode()
root_node.insert('fooaaa')
root_node.insert('foobbb')
root_node.insert('foo')

Should work., i.e should have a structure like this

root_node.print_tree()
- foo (leaf)
-- aaa   (leaf)
-- bbb   (leaf)

Actual behavior

root_node.insert("foo")
---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
Cell In[5], line 1
----> 1 root_node.insert("foo")

File ~/git/python/radix/radix.py:85, in RadixNode.insert(self, word)
     82 # Case 3: The node prefix is equal to the matching
     83 # Solution: We insert remaining word on the next node
     84 if remaining_prefix == "":
---> 85     self.nodes[matching_string[0]].insert(remaining_word)
     86 # Case 5: The word is greater equal to the matching
     87 # Solution: Create a node in between both nodes, change
     88 # prefixes and add the new node for the remaining word
     89 else:
     90     incoming_node.prefix = remaining_prefix

File ~/git/python/radix/radix.py:73, in RadixNode.insert(self, word)
     68     self.is_leaf = True
     70 # Case 2: The node has no edges that have a prefix to the word
     71 # Solution: We create an edge from the current node to a new one
     72 # containing the word
---> 73 elif word[0] not in self.nodes:
     74     self.nodes[word[0]] = RadixNode(prefix=word, is_leaf=True)
     76 else:

IndexError: string index out of range

[SimonUnge]

something like this might fix it?

...
        else:
            incoming_node = self.nodes[word[0]]
            matching_string, remaining_prefix, remaining_word = incoming_node.match(
                word
            )
                                      
            if remaining_prefix == "" and not remaining_word == "": # <---- better check
                self.nodes[matching_string[0]].insert(remaining_word)
                                                                        
            elif remaining_prefix == "":  # <--- make sure we end in case 1 next lap 
                self.nodes[matching_string[0]].insert(matching_string)

[swarna-lohitt]

class RadixNode:
def init(self, prefix="", is_leaf=False):
self.prefix = prefix
self.is_leaf = is_leaf
self.nodes = {}

def insert(self, word):
    if not word:
        return

    matching_prefix = self._find_matching_string(word)
    remaining_word = word[len(matching_prefix):]
    remaining_prefix = self.prefix[len(matching_prefix):]

    if remaining_prefix == "":
        # Case: Insert remaining word into the next node
        if matching_prefix and matching_prefix[0] in self.nodes:
            self.nodes[matching_prefix[0]].insert(remaining_word)
        else:
            self.nodes[word[0]] = RadixNode(prefix=remaining_word, is_leaf=True)
    else:
        # Case: Split the current node and insert the word
        new_node = RadixNode(prefix=remaining_prefix, is_leaf=self.is_leaf)
        new_node.nodes = self.nodes
        self.nodes = {remaining_prefix[0]: new_node}
        self.prefix = matching_prefix
        self.is_leaf = False

        if remaining_word:
            self.nodes[remaining_prefix[0]].insert(remaining_word)
        else:
            self.nodes[remaining_prefix[0]].is_leaf = True

def _find_matching_string(self, word):
    match_len = 0
    while match_len < len(self.prefix) and match_len < len(word) and self.prefix[match_len] == word[match_len]:
        match_len += 1
    return self.prefix[:match_len]

Usage example:

root_node = RadixNode()
root_node.insert('fooaaa')
root_node.insert('foobbb')
root_node.insert('foo')