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

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

2"""Main GeneralizedTrie implementation.""" 

3 

4from .access import TrieAccessMixin 

5from .base import TrieBase 

6from .collection import TrieCollectionMixin 

7from .mutation import TrieMutationMixin 

8from .removal import TrieRemovalMixin 

9from .storage import TrieStorageMixin 

10from .traversal import TrieTraversalMixin 

11 

12 

13class GeneralizedTrie( 

14 TrieBase, 

15 TrieStorageMixin, 

16 TrieAccessMixin, 

17 TrieRemovalMixin, 

18 TrieTraversalMixin, 

19 TrieMutationMixin, 

20 TrieCollectionMixin 

21): 

22 """A general purpose trie. 

23 

24 Unlike many trie implementations which only support strings as keys 

25 and token match only at the character level, it is agnostic as to the 

26 types of tokens used to key it and thus far more general purpose. 

27 

28 It requires only that the indexed tokens be hashable. This is verified 

29 at runtime using the :class:`gentrie.TrieKeyToken` protocol. 

30 

31 Tokens in a key do NOT have to all be the same type as long as they 

32 can be compared for equality. 

33 

34 It can handle a :class:`Sequence` of :class:`TrieKeyToken` conforming objects as keys 

35 for the trie out of the box. 

36 

37 You can 'mix and match' types of objects used as token in a key as 

38 long as they all conform to the :class:`TrieKeyToken` protocol. 

39 

40 The code emphasizes robustness and correctness. 

41 

42 .. warning:: **GOTCHA: Using User Defined Classes As Tokens In Keys** 

43 

44 Objects of user-defined classes are conformant with the :class:`TrieKeyToken` protocol 

45 by default, but **this will not work as naively expected.** The hash value of an object 

46 is based on its memory address by default. This results in the hash value of an object changing 

47 every time the object is created and means that the object will not be found in 

48 the trie unless you have a reference to the original object. 

49 

50 If you want to use a user-defined class as a token in a key to look up by value 

51 instead of the instance, you must implement the ``__eq__()`` and ``__hash__()`` 

52 dunder methods in a content aware way (the hash and eq values must depend on the 

53 content of the object). 

54 

55 .. tip:: **Using `dataclasses.dataclass` For Content-Aware User Defined Classes** 

56 

57 A simple way to implement a user-defined class that is content aware hashable 

58 is to use the :class:`dataclasses.dataclass` decorator using the ``frozen=True`` and 

59 ``eq=True`` options . This will automatically implement appropriate ``__eq__()`` 

60 and ``__hash__()`` methods for you. 

61 

62 .. code-block:: python 

63 :linenos: 

64 :caption: Example of a content-aware user-defined class 

65 

66 from dataclasses import dataclass 

67 

68 from gentrie import TrieKeyToken 

69 

70 @dataclass(frozen=True, eq=True) 

71 class MyTokenClass: 

72 name: str 

73 value: int 

74 

75 # Create an instance of the token class 

76 token = MyTokenClass(name="example", value=42) 

77 

78 # Check if the token is hashable 

79 if isinstance(token, TrieKeyToken): 

80 print("token is usable as a TrieKeyToken") 

81 else: 

82 print("token is not usable as a TrieKeyToken") 

83 

84 """ 

85 

86 # All functionality is provided by the mixins