Coverage for src/gentrie/trie/collection.py: 100%

1# -*- coding: utf-8 -*- 

2"""Collection operations for GeneralizedTrie.""" 

3 

4from typing import Generator 

5 

6from ..types import TrieEntry, TrieId 

7 

8from .trie_mixins import TrieMixinsInterface 

9 

10 

11class TrieCollectionMixin: 

12 """Mixin providing collection operations (__len__, __iter__, keys, values, items).""" 

13 

14 def __len__(self: TrieMixinsInterface) -> int: 

15 """Returns the number of keys in the trie. 

16 

17 Returns: 

18 :class:`int`: Number of keys in the trie. 

19 

20 Usage:: 

21 

22 n_keys: int = len(trie) 

23 

24 """ 

25 return len(self._trie_index) # pyright: ignore[reportPrivateUsage] 

26 

27 def __iter__(self: TrieMixinsInterface) -> Generator[TrieId, None, None]: 

28 """Returns an iterator for the trie. 

29 

30 The generator yields the :class:`TrieId`for each key in the trie. 

31 

32 Returns: 

33 :class:`Generator[TrieId, None, None]`: Generator for the trie. 

34 """ 

35 # pylint: disable=consider-iterating-dictionary 

36 return ( 

37 entry for entry in self._trie_entries.keys() # pyright: ignore[reportPrivateUsage] 

38 ) 

39 

40 def keys(self: TrieMixinsInterface) -> Generator[TrieId, None, None]: 

41 """Returns an iterator for all the TrieIds in the trie. 

42 

43 The generator yields the :class:`TrieId` for each key in the trie. 

44 

45 It returns TrieIds instead of GeneralizedKeys because TrieIds are 

46 

47 1. Faster: Lookups using TrieIds are *O(1)* for time regardless 

48 of the length of the GeneralizedKey they are associated with vs *O(n)* 

49 to the length of keys for operations using GeneralizedKeys to look 

50 up entries. 

51 

52 2. More efficient memory usage: TrieIds are typically smaller in size 

53 compared to GeneralizedKeys, leading to reduced memory overhead 

54 when storing and processing keys in the trie. 

55 

56 3. Guaranteed stable even with key modifications: TrieIds remain 

57 consistent even if the underlying GeneralizedKey changes, making 

58 them more reliable for long-term storage and retrieval. 

59 

60 Returns: 

61 :class:`Generator[TrieId, None, None]`: Generator for the trie. 

62 """ 

63 # pylint: disable=consider-iterating-dictionary 

64 return (entry for entry in self._trie_entries.keys()) # pyright: ignore[reportPrivateUsage] 

65 

66 def values(self: TrieMixinsInterface) -> Generator[TrieEntry, None, None]: 

67 """Returns an iterator for all the TrieEntry entries in the trie. 

68 

69 The generator yields the :class:`TrieEntry` for each key in the trie. 

70 

71 Returns: 

72 :class:`Generator[TrieEntry, None, None]`: Generator for the trie. 

73 """ 

74 return (entry for entry in self._trie_entries.values()) # pyright: ignore[reportPrivateUsage] 

75 

76 def items(self: TrieMixinsInterface) -> Generator[tuple[TrieId, TrieEntry], None, None]: 

77 """Returns an iterator for the trie. 

78 

79 The keys are the TrieIds and the values are the TrieEntry instances. 

80 

81 The generator yields the :class:`TrieId` and :class:`TrieEntry` for each key in the trie. 

82 

83 Returns: 

84 :class:`Generator[tuple[TrieId, TrieEntry], None, None]`: Generator for the trie. 

85 """ 

86 return ((key, value) for key, value in self._trie_entries.items()) # pyright: ignore[reportPrivateUsage]