
"""simple docstring"""



class 		a_    :







    def __init__(      self      :							List[str]  ,       __UpperCamelCase      :							str = ""  ,       __UpperCamelCase      :							bool = False  )		->None:






        '''simple docstring'''






        _UpperCAmelCase        = {}

        # A node will be a leaf if the tree contains its word
        _UpperCAmelCase        = is_leaf

        _UpperCAmelCase        = prefix







    def   _snake_case       (      self      :							Tuple  ,       __UpperCamelCase      :							str  )		->tuple[str, str, str]:






        '''simple docstring'''






        _UpperCAmelCase        = 0
        for q, w in zip(self.prefix  ,       __UpperCamelCase  ):
            if q != w:
                break

            x += 1

        return self.prefix[:x], self.prefix[x:], word[x:]







    def   _snake_case       (      self      :							Dict  ,       __UpperCamelCase      :							list[str]  )		->None:






        '''simple docstring'''






        for word in words:
            self.insert(__UpperCamelCase  )







    def   _snake_case       (      self      :							Tuple  ,       __UpperCamelCase      :							str  )		->None:






        '''simple docstring'''






        if self.prefix == word:
            _UpperCAmelCase        = True

        # Case 2: The node has no edges that have a prefix to the word
        # Solution: We create an edge from the current node to a new one
        # containing the word
        elif word[0] not in self.nodes:
            _UpperCAmelCase        = RadixNode(prefix=__UpperCamelCase  ,       is_leaf=__UpperCamelCase  )

        else:
            _UpperCAmelCase        = self.nodes[word[0]]
            _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = incoming_node.match(
                __UpperCamelCase  )

            # Case 3: The node prefix is equal to the matching
            # Solution: We insert remaining word on the next node
            if remaining_prefix == "":
                self.nodes[matching_string[0]].insert(__UpperCamelCase  )

            # Case 4: The word is greater equal to the matching
            # Solution: Create a node in between both nodes, change
            # prefixes and add the new node for the remaining word
            else:
                _UpperCAmelCase        = remaining_prefix

                _UpperCAmelCase        = self.nodes[matching_string[0]]
                _UpperCAmelCase        = RadixNode(__UpperCamelCase  ,       __UpperCamelCase  )
                _UpperCAmelCase        = aux_node

                if remaining_word == "":
                    _UpperCAmelCase        = True
                else:
                    self.nodes[matching_string[0]].insert(__UpperCamelCase  )







    def   _snake_case       (      self      :							List[str]  ,       __UpperCamelCase      :							str  )		->bool:






        '''simple docstring'''






        _UpperCAmelCase        = self.nodes.get(word[0]  ,       __UpperCamelCase  )
        if not incoming_node:
            return False
        else:
            _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = incoming_node.match(
                __UpperCamelCase  )
            # If there is remaining prefix, the word can't be on the tree
            if remaining_prefix != "":
                return False
            # This applies when the word and the prefix are equal
            elif remaining_word == "":
                return incoming_node.is_leaf
            # We have word remaining so we check the next node
            else:
                return incoming_node.find(__UpperCamelCase  )







    def   _snake_case       (      self      :							Dict  ,       __UpperCamelCase      :							str  )		->bool:






        '''simple docstring'''






        _UpperCAmelCase        = self.nodes.get(word[0]  ,       __UpperCamelCase  )
        if not incoming_node:
            return False
        else:
            _UpperCAmelCase     ,_UpperCAmelCase     ,_UpperCAmelCase        = incoming_node.match(
                __UpperCamelCase  )
            # If there is remaining prefix, the word can't be on the tree
            if remaining_prefix != "":
                return False
            # We have word remaining so we check the next node
            elif remaining_word != "":
                return incoming_node.delete(__UpperCamelCase  )
            else:
                # If it is not a leaf, we don't have to delete
                if not incoming_node.is_leaf:
                    return False
                else:
                    # We delete the nodes if no edges go from it
                    if len(incoming_node.nodes  ) == 0:
                        del self.nodes[word[0]]
                        # We merge the current node with its only child
                        if len(self.nodes  ) == 1 and not self.is_leaf:
                            _UpperCAmelCase        = list(self.nodes.values()  )[0]
                            _UpperCAmelCase        = merging_node.is_leaf
                            self.prefix += merging_node.prefix
                            _UpperCAmelCase        = merging_node.nodes
                    # If there is more than 1 edge, we just mark it as non-leaf
                    elif len(incoming_node.nodes  ) > 1:
                        _UpperCAmelCase        = False
                    # If there is 1 edge, we merge it with its child
                    else:
                        _UpperCAmelCase        = list(incoming_node.nodes.values()  )[0]
                        _UpperCAmelCase        = merging_node.is_leaf
                        incoming_node.prefix += merging_node.prefix
                        _UpperCAmelCase        = merging_node.nodes

                    return True







    def   _snake_case       (      self      :							Union[str, Any]  ,       __UpperCamelCase      :							int = 0  )		->None:






        '''simple docstring'''






        if self.prefix != "":
            print("""-""" * height  ,       self.prefix  ,       """  (leaf)""" if self.is_leaf else """"""  )

        for value in self.nodes.values():
            value.print_tree(height + 1  )







def 			_UpperCamelCase						(    )     ->	bool:





    """simple docstring"""

    _UpperCAmelCase        = """banana bananas bandana band apple all beast""".split()
    _UpperCAmelCase        = RadixNode()
    root.insert_many(_A   )

    assert all(root.find(_A   ) for word in words   )
    assert not root.find("""bandanas"""   )
    assert not root.find("""apps"""   )
    root.delete("""all"""   )
    assert not root.find("""all"""   )
    root.delete("""banana"""   )
    assert not root.find("""banana"""   )
    assert root.find("""bananas"""   )

    return True


def 			_UpperCamelCase						(    )     ->	None:





    """simple docstring"""

    assert test_trie()


def 			_UpperCamelCase						(    )     ->	None:





    """simple docstring"""

    _UpperCAmelCase        = RadixNode()
    _UpperCAmelCase        = """banana bananas bandanas bandana band apple all beast""".split()
    root.insert_many(_A   )

    print("""Words:"""       ,   _A   )
    print("""Tree:"""   )
    root.print_tree()


if __name__ == "__main__":
 main()

"""simple docstring"""



import math
import unittest


def 			_UpperCamelCase						(    _A   )     ->	bool:





    """simple docstring"""

    assert isinstance(_A       ,   _A   ) and (
        number >= 0
    ), "'number' must been an int and positive"

    if 1 < number < 4:
        # 2 and 3 are primes
        return True
    elif number < 2 or number % 2 == 0 or number % 3 == 0:
        # Negatives, 0, 1, all even numbers, all multiples of 3 are not primes
        return False

    # All primes number are in format of 6k +/- 1
    for i in range(5       ,   int(math.sqrt(_A   ) + 1   )       ,   6   ):
        if number % i == 0 or number % (i + 2) == 0:
            return False
    return True




class 		a_    (			unittest.TestCase						):







    def   _snake_case       (      self      :							int  )		->Optional[int]:






        '''simple docstring'''






        self.assertTrue(is_prime(2  )  )
        self.assertTrue(is_prime(3  )  )
        self.assertTrue(is_prime(5  )  )
        self.assertTrue(is_prime(7  )  )
        self.assertTrue(is_prime(11  )  )
        self.assertTrue(is_prime(13  )  )
        self.assertTrue(is_prime(17  )  )
        self.assertTrue(is_prime(19  )  )
        self.assertTrue(is_prime(23  )  )
        self.assertTrue(is_prime(29  )  )







    def   _snake_case       (      self      :							Union[str, Any]  )		->Optional[Any]:






        '''simple docstring'''






        with self.assertRaises(__UpperCamelCase  ):
            is_prime(-19  )
        self.assertFalse(
            is_prime(0  )  ,       """Zero doesn't have any positive factors, primes must have exactly two."""  ,       )
        self.assertFalse(
            is_prime(1  )  ,       """One only has 1 positive factor, primes must have exactly two."""  ,       )
        self.assertFalse(is_prime(2 * 2  )  )
        self.assertFalse(is_prime(2 * 3  )  )
        self.assertFalse(is_prime(3 * 3  )  )
        self.assertFalse(is_prime(3 * 5  )  )
        self.assertFalse(is_prime(3 * 5 * 7  )  )


if __name__ == "__main__":
 unittest.main()