| 784 | |
| 785 | |
| 786 | class RadixTrie: |
| 787 | __slots__ = ("root", "sequences", "sequence_lengths") |
| 788 | |
| 789 | @dataclass |
| 790 | class Node: |
| 791 | label: Tuple[int, ...] = () |
| 792 | parent: Optional["RadixTrie.Node"] = None |
| 793 | children: Dict[int, "RadixTrie.Node"] = field(default_factory=dict) |
| 794 | sequences: set[int] = field(default_factory=set) |
| 795 | tails: set[int] = field(default_factory=set) |
| 796 | |
| 797 | def __init__(self) -> None: |
| 798 | self.root = RadixTrie.Node() |
| 799 | self.sequences: Dict[int, RadixTrie.Node] = {} |
| 800 | self.sequence_lengths: Dict[int, int] = {} |
| 801 | |
| 802 | @staticmethod |
| 803 | def _pick_sequence(candidates: set[int], preferred_sequences: Optional[Any]) -> int: |
| 804 | if preferred_sequences is None: |
| 805 | return next(iter(candidates)) |
| 806 | if isinstance(preferred_sequences, OrderedDict): |
| 807 | for sequence_id in reversed(preferred_sequences): |
| 808 | if sequence_id in candidates: |
| 809 | return sequence_id |
| 810 | return next(iter(candidates)) |
| 811 | if isinstance(preferred_sequences, (list, tuple)): |
| 812 | for sequence_id in reversed(preferred_sequences): |
| 813 | if sequence_id in candidates: |
| 814 | return sequence_id |
| 815 | return next(iter(candidates)) |
| 816 | preferred = candidates & preferred_sequences |
| 817 | if preferred: |
| 818 | return next(iter(preferred)) |
| 819 | return next(iter(candidates)) |
| 820 | |
| 821 | @staticmethod |
| 822 | def _common_prefix_len( |
| 823 | label: Sequence[int], |
| 824 | tokens: Sequence[int], |
| 825 | offset: int, |
| 826 | ) -> int: |
| 827 | limit = min(len(label), len(tokens) - offset) |
| 828 | match_len = 0 |
| 829 | while match_len < limit and label[match_len] == tokens[offset + match_len]: |
| 830 | match_len += 1 |
| 831 | return match_len |
| 832 | |
| 833 | def _split_child( |
| 834 | self, |
| 835 | parent: "RadixTrie.Node", |
| 836 | child: "RadixTrie.Node", |
| 837 | prefix_len: int, |
| 838 | ) -> "RadixTrie.Node": |
| 839 | assert 0 < prefix_len < len(child.label) |
| 840 | prefix = child.label[:prefix_len] |
| 841 | suffix = child.label[prefix_len:] |
| 842 | middle = RadixTrie.Node( |
| 843 | label=prefix, |
no outgoing calls
no test coverage detected
searching dependent graphs…