Coverage for tests/gentrie/test_gentri.py: 99%
409 statements
« prev ^ index » next coverage.py v7.6.10, created at 2025-08-17 12:33 -0700
1"""Tests for the gentrie module."""
2# pylint: disable=too-many-lines
3# pylint: disable=too-many-public-methods
4# pylint: disable=invalid-name
6import unittest
7from collections.abc import Iterable
8from textwrap import dedent
9from typing import Any
11import pytest
14from src.gentrie import (DuplicateKeyError, ErrorTag, GeneralizedTrie,
15 InvalidGeneralizedKeyError, TrieEntry, TrieId,
16 TrieKeyError, TrieKeyToken, TrieTypeError,
17 TrieValueError, is_generalizedkey)
19from ..testspec import TestSpec, run_tests_list
22class MockDefaultTrieKeyToken:
23 """A mock class that implements the TrieKeyToken interface.
25 This class is used to test the behavior of the GeneralizedTrie with user-defined classes
26 and ensures that it can handle instances of classes that do not implement content-aware
27 equality.
28 """
29 def __init__(self, a: tuple[int, int, int], b: str) -> None:
30 self.a = a
31 self.b = b
34class MockContentAwareTrieKeyToken:
35 """A mock class that implements the TrieKeyToken interface and uses content for equality."""
36 def __init__(self, a: tuple[int, int, int], b: str) -> None:
37 self.a = a
38 self.b = b
40 def __eq__(self, other: Any) -> bool:
41 return hash(self) == hash(other)
43 def __hash__(self) -> int:
44 return hash((self.a, self.b))
47class TestGeneralizedTrie(unittest.TestCase):
48 """Test the GeneralizedTrie class and its methods."""
50 @pytest.mark.order(1)
51 @pytest.mark.dependency(name='test_trieid_class')
52 def test_trieid_class(self) -> None:
53 """Test the creation of TrieId instances."""
54 tests: list[TestSpec] = [
55 TestSpec(
56 name="[TTI001] Creating TrieId(1) results in a TrieId instance",
57 action=lambda: isinstance(TrieId(1), TrieId), # type: ignore[reportUnknownMemberType]
58 expected=True,
59 ),
60 TestSpec(
61 name="[TTI002] int(1) is not a TrieId",
62 action=lambda: isinstance(int(1), TrieId),
63 expected=False,
64 ),
65 TestSpec(
66 name="[TTI003] TrieId(2) is not equal to TrieId(1)",
67 action=lambda: TrieId(2) == TrieId(1),
68 expected=False,
69 ),
70 TestSpec(
71 name="[TTI004] TrieId(1) is equal to itself",
72 action=lambda: TrieId(1) == TrieId(1),
73 expected=True,
74 ),
75 ]
77 run_tests_list(self, tests)
79 @pytest.mark.order(after='test_trieid_class')
80 @pytest.mark.dependency(
81 name='test_triekeytoken_supported_and_unsupported_builtin_types')
82 def test_triekeytoken_supported_and_unsupported_builtin_types(self) -> None:
83 """Tests that built in types are correctly classified as supported or unsupported."""
84 TEST_ID: int = 0
85 TEST_VALUE: int = 1
86 good_types: list[tuple[str, Any]] = [
87 ('TTKT_TSBT001', 'a'),
88 ('TTKT_TSBT002', str('ab')),
89 ('TTKT_TSBT003', frozenset('abc')),
90 ('TTKT_TSBT004', tuple(['a', 'b', 'c', 'd'])),
91 ('TTKT_TSBT005', int(1)),
92 ('TTKT_TSBT006', float(2.0)),
93 ('TTKT_TSBT007', complex(3.0, 4.0)),
94 ('TTKT_TSBT008', bytes(456)),
95 ]
97 tests: list[TestSpec] = [
98 TestSpec(
99 name=f"[{testcase[TEST_ID]}] isinstance({repr(testcase[TEST_VALUE])}, TrieKeyToken) (True)",
100 action=isinstance,
101 args=[testcase[TEST_VALUE], TrieKeyToken],
102 expected=True,
103 )
104 for testcase in good_types
105 ]
106 run_tests_list(self, tests)
108 bad_types: list[tuple[str, Any]] = [
109 ('TTKT_TUBT001', set('a')),
110 ('TTKT_TUBT002', list(['a', 'b'])),
111 ('TTKT_TUBT003', dict({'a': 1, 'b': 2, 'c': 3})),
112 ('TTKT_TUBT004', set('abc')),
113 ]
115 tests = [
116 TestSpec(
117 name=f"[{testcase[TEST_ID]}] isinstance({repr(testcase[TEST_VALUE])}, TrieKeyToken) (False)",
118 action=isinstance,
119 args=[testcase[TEST_VALUE], TrieKeyToken],
120 expected=False,
121 )
122 for testcase in bad_types
123 ]
124 run_tests_list(self, tests)
126 @pytest.mark.order(after=['test_triekeytoken_supported_and_unsupported_builtin_types'])
127 @pytest.mark.dependency(
128 name='test_generalizedkey_supported_and_unsupported_builtin_types',
129 depends=['test_triekeytoken_supported_and_unsupported_builtin_types'])
130 def test_generalizedkey_supported_and_unsupported_builtin_types(self) -> None:
131 """Tests supported and unsupported types for generalized keys.
133 This test checks that types like strings, lists, and tuples
134 of immutable types are recognized as valid generalized keys
135 while non-sequence or mutable types like dict, set, and complex
136 numbers are not considered valid generalized keys."""
137 TEST_ID: int = 0
138 TEST_VALUE: int = 1
139 good_keys: list[tuple[str, Any]] = [
140 ('TGK_SBT001', 'a'),
141 ('TGK_SBT002', str('ab')),
142 ('TGK_SBT003', ['a', 'b']),
143 ('TGK_SBT004', tuple(['a', 'b', 'c', 'd'])),
144 ('TGK_SBT005', [int(1)]),
145 ('TGK_SBT006', [float(2.0)]),
146 ('TGK_SBT007', [complex(3.0, 4.0)]),
147 ('TGK_SBT007', [b'abc']),
148 ('TGK_SBT008', b'abc')
149 ]
150 tests: list[TestSpec] = [
151 TestSpec(
152 name=f"[{testcase[TEST_ID]}] is_generalizedkey({repr(testcase[TEST_VALUE])}) (True)",
153 action=is_generalizedkey,
154 args=[testcase[TEST_VALUE]],
155 expected=True,
156 )
157 for testcase in good_keys
158 ]
159 run_tests_list(self, tests)
161 # Test cases for unsupported types
162 bad_keys: list[tuple[str, Any]] = [
163 ('TGK_TUBT001', ''), # empty string is invalid as a GeneralizedKey
164 ('TGK_TUBT002', dict({'a': 1, 'b': 2, 'c': 3})),
165 ('TGK_TUBT003', set('abc')),
166 ('TGK_TUBT004', frozenset('abc')),
167 ('TGK_TUBT005', complex(3.0, 4.0)),
168 ]
170 tests = [
171 TestSpec(
172 name=f"[{testcase[TEST_ID]}] is_generalizedkey({repr(testcase[TEST_VALUE])}) (False)",
173 action=is_generalizedkey,
174 args=[testcase[TEST_VALUE]],
175 expected=False,
176 )
177 for testcase in bad_keys
178 ]
179 run_tests_list(self, tests)
181 @pytest.mark.order(after=['test_generalizedkey_supported_and_unsupported_builtin_types'])
182 @pytest.mark.dependency(
183 name='test_is_generalizedkey',
184 depends=['test_generalizedkey_supported_and_unsupported_builtin_types'])
185 def test_is_generalizedkey(self) -> None:
186 """Test the is_generalizedkey function with various inputs.
188 This test checks that the is_generalizedkey function correctly identifies
189 valid and invalid generalized keys."""
190 tests: list[TestSpec] = [
191 TestSpec(
192 name="[TIGK001] is_generalizedkey('a') (True)",
193 action=is_generalizedkey,
194 args=['a'],
195 expected=True
196 ),
197 TestSpec(
198 name="[TIGK002] is_generalizedkey(['a', 'b']) (True)",
199 action=is_generalizedkey,
200 args=[['a', 'b']],
201 expected=True
202 ),
203 TestSpec(
204 name="[TIGK003] is_generalizedkey(b'abc') (True)",
205 action=is_generalizedkey,
206 args=[b'abc'],
207 expected=True
208 ),
209 TestSpec(
210 name="[TIGK004] is_generalizedkey('') (False)",
211 action=is_generalizedkey,
212 args=[''],
213 expected=False
214 ),
215 TestSpec(
216 name="[TIGK005] is_generalizedkey([]) (False)",
217 action=is_generalizedkey,
218 args=[[]],
219 expected=False
220 ),
221 TestSpec(
222 name="[TIGK006] is_generalizedkey(123) (False)",
223 action=is_generalizedkey,
224 args=[123],
225 expected=False
226 ),
227 TestSpec(
228 name="[TIGK007] is_generalizedkey(None) (False)",
229 action=is_generalizedkey,
230 args=[None],
231 expected=False
232 ),
233 TestSpec(
234 name="[TIGK008] is_generalizedkey({'a': 1}) (False)",
235 action=is_generalizedkey,
236 args=[{'a': 1}],
237 expected=False
238 ),
239 TestSpec(
240 name="[TIGK009] is_generalizedkey(['a', {'b': 1}]) (False)",
241 action=is_generalizedkey,
242 args=[['a', {'b': 1}]],
243 expected=False
244 ),
245 TestSpec(
246 name="[TIGK010] is_generalizedkey(['a', ['b', ['c']]]) (False)",
247 action=is_generalizedkey,
248 args=[['a', ['b', ['c']]]],
249 expected=False
250 ),
251 ]
252 run_tests_list(self, tests)
254 @pytest.mark.order(order=6)
255 @pytest.mark.dependency(name='test_create_trie')
256 def test_create_trie(self) -> None:
257 """Test the creation of a GeneralizedTrie instance.
259 This test checks that the GeneralizedTrie can be instantiated without any arguments
260 and that it raises a TypeError when an invalid filter_id is provided."""
261 tests: list[TestSpec] = [
262 TestSpec(
263 name="[TCT001] create GeneralizedTrie()",
264 action=GeneralizedTrie,
265 validate_result=lambda found: isinstance(found, # type: ignore[reportUnknownMemberType]
266 GeneralizedTrie),
267 ),
268 TestSpec(
269 name="[TCT002] create GeneralizedTrie(filter_id=1)",
270 action=GeneralizedTrie,
271 kwargs={"filter_id": 1},
272 exception=TypeError,
273 ),
274 ]
275 run_tests_list(self, tests)
277 @pytest.mark.order(after=['test_contains', 'test_bool'])
278 @pytest.mark.dependency(
279 name='test_clear',
280 depends=['test_create_trie', 'test_add', 'test_contains', 'test_bool', 'test_keys'])
281 def test_clear(self) -> None:
282 """Test the clear method of GeneralizedTrie."""
283 trie = GeneralizedTrie()
284 trie.add("a")
285 trie.add("b")
286 self.assertEqual(len(trie), 2, "[TCL001] Trie should have 2 entries after adding 'a' and 'b'")
287 self.assertTrue("a" in trie, "[TCL002] Trie should contain 'a' after addition")
289 trie.clear()
291 self.assertEqual(len(trie), 0, "[TCL003] Trie should be empty after clear()")
292 self.assertFalse(bool(trie), "[TCL004] Trie should evaluate to False after clear()")
293 self.assertFalse("a" in trie, "[TCL005] Trie should not contain 'a' after clear()")
294 # pylint: disable=protected-access
295 self.assertEqual(trie._ident_counter, 0, # type: ignore[reportUnknownMemberType]
296 "[TCL006] Trie ident counter should be reset after clear()")
297 self.assertEqual(list(trie.keys()), [], "[TCL007] Trie keys should be empty after clear()]")
299 @pytest.mark.order(after="test_create_trie")
300 @pytest.mark.dependency(
301 name='test_add',
302 depends=['test_create_trie', 'test_trieid_class'])
303 def test_add(self) -> None:
304 """Test the add method of GeneralizedTrie.
306 This test covers adding various types of keys to the trie using the add() method, including strings,
307 lists, and frozensets, and checks the expected behavior of the trie after each addition.
308 It also includes tests for error handling when invalid keys are added."""
309 # pylint: disable=protected-access, no-member
310 trie = GeneralizedTrie()
311 tests: list[TestSpec] = [
312 # Initialize from a list of strings and validate we get the expected id
313 TestSpec(
314 name="[TA001] trie.add(['tree', 'value', 'ape'])",
315 action=trie.add,
316 args=[["tree", "value", "ape"]],
317 kwargs={},
318 expected=TrieId(1),
319 ),
320 # Validate the dictionary representation of the trie is correct after initialization
321 TestSpec(
322 name="[TA002] _as_dict()",
323 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
324 expected={
325 'ident': None,
326 'children': {
327 'tree': {
328 'ident': None,
329 'token': 'tree',
330 'value': None,
331 'parent': None,
332 'children': {
333 'value': {
334 'ident': None,
335 'token': 'value',
336 'value': None,
337 'parent': 'tree',
338 'children': {
339 'ape': {
340 'ident': TrieId(1),
341 'token': 'ape',
342 'value': None,
343 'parent': 'value',
344 'children': {}
345 }
346 }
347 }
348 }
349 }
350 },
351 'trie_index': [TrieId(1)],
352 'trie_entries': {TrieId(1): "TrieEntry(ident=TrieId(1), key=['tree', 'value', 'ape'], value=None)"}
353 }
354 ),
356 # Add another entry ['tree', 'value'] and validate we get the expected id for it
357 TestSpec(
358 name="[TA003] trie.add(['tree', 'value']",
359 action=trie.add,
360 args=[["tree", "value"]],
361 expected=TrieId(2),
362 ),
363 # Validate the _as_dict representation of the trie is correct
364 TestSpec(
365 name="[TA004] _as_dict()",
366 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
367 expected={
368 'ident': None,
369 'children': {
370 'tree': {
371 'ident': None,
372 'token': 'tree',
373 'value': None,
374 'parent': None,
375 'children': {
376 'value': {
377 'ident': TrieId(2),
378 'token': 'value',
379 'value': None,
380 'parent': 'tree',
381 'children': {
382 'ape': {
383 'ident': TrieId(1),
384 'token': 'ape',
385 'value': None,
386 'parent': 'value',
387 'children': {}
388 }
389 }
390 }
391 }
392 }
393 },
394 'trie_index': [TrieId(1), TrieId(2)],
395 'trie_entries': {
396 TrieId(1): "TrieEntry(ident=TrieId(1), key=['tree', 'value', 'ape'], value=None)",
397 TrieId(2): "TrieEntry(ident=TrieId(2), key=['tree', 'value'], value=None)"
398 }
399 }
400 ),
401 # Add a string entry 'abcdef' and validate we get the expected id for it
402 TestSpec(
403 name="[TA005] trie.add('abcdef')",
404 action=trie.add,
405 args=["abcdef"],
406 expected=TrieId(3),
407 ),
408 # Add another entry [1, 3, 4, 5] and validate we get the expected id for it
409 TestSpec(
410 name="[TA006] trie.add([1, 3, 4, 5])",
411 action=trie.add,
412 args=[[1, 3, 4, 5]],
413 kwargs={},
414 expected=TrieId(4),
415 ),
416 # Add a frozenset entry and validate we get the expected id for it
417 TestSpec(
418 name="[TA007] trie.add(frozenset([1]), 3, 4, 5])",
419 action=trie.add,
420 args=[[frozenset([1]), 3, 4, 5]],
421 kwargs={},
422 expected=TrieId(5),
423 ),
424 # Add another frozenset entry and validate we get a different id for it
425 # than for the previously added frozenset
426 TestSpec(
427 name="[TA008] trie.add(frozenset([1]), 3, 4, 5])",
428 action=trie.add,
429 args=[[frozenset([1]), 3, 4, 6]],
430 expected=TrieId(6),
431 ),
432 # Attempt to add an integer as a key and validate we get the expected exception
433 TestSpec(
434 name="[TA009] trie.add(1)",
435 action=trie.add,
436 args=[1],
437 exception=InvalidGeneralizedKeyError,
438 exception_tag=ErrorTag.STORE_ENTRY_INVALID_GENERALIZED_KEY,
439 ),
440 # Attempt to add an empty list as a key and validate we get the expected exception
441 TestSpec(
442 name="[TA010] trie.add([])",
443 action=trie.add,
444 args=[[]],
445 exception=InvalidGeneralizedKeyError,
446 exception_tag=ErrorTag.STORE_ENTRY_INVALID_GENERALIZED_KEY,
447 ),
448 # Attempt to add a set as a key element and validate we get the expected exception
449 TestSpec(
450 name="[TA011] trie.add([set([1]), 3, 4, 5])",
451 action=trie.add,
452 args=[[set([1]), 3, 4, 5]],
453 exception=InvalidGeneralizedKeyError,
454 exception_tag=ErrorTag.STORE_ENTRY_INVALID_GENERALIZED_KEY,
455 ),
456 # Add a key that is a list of integers and validate we get the expected id for it
457 TestSpec(
458 name="[TA012] trie.add(key=[1, 3, 4, 7])",
459 action=trie.add,
460 kwargs={"key": [1, 3, 4, 7]},
461 expected=TrieId(7),
462 ),
463 # Attempt to pass add the wrong number of arguments and validate we get the expected exception
464 TestSpec(name="[TA013] trie.add()",
465 action=trie.add,
466 exception=TypeError),
467 TestSpec(
468 name="[TA014] trie.add(['a'], ['b'], ['c'])",
469 action=trie.add,
470 args=[["a"], ["b"], ["c"]],
471 exception=TypeError,
472 ),
473 # Validate the length of the trie after all additions
474 TestSpec(name="[TA015] len(trie)", action=len, args=[trie], expected=7),
475 # Add duplicate entry ['tree', 'value', 'ape'] and validate we get a DuplicateKeyError
476 TestSpec(
477 name="[TA016] trie.add(['tree', 'value', 'ape'])",
478 action=trie.add,
479 args=[["tree", "value", "ape"]],
480 kwargs={},
481 exception=DuplicateKeyError,
482 exception_tag=ErrorTag.STORE_ENTRY_DUPLICATE_KEY,
483 ),
484 # Validate the length of the trie trying to add duplicate ['tree', 'value', 'ape'] is unchanged
485 TestSpec(name="[TA017] len(trie)", action=len, args=[trie], expected=7),
486 # Add a trie entry with a value and validate we get the expected id for it
487 TestSpec(
488 name="[TA018] trie.add(['tree', 'value', 'cheetah'], 'feline')",
489 action=trie.add,
490 args=[["tree", "value", "cheetah"], "feline"],
491 expected=TrieId(8),
492 ),
494 ]
495 run_tests_list(self, tests)
497 # New untouched trie for the next sequence of tests
498 # Not using clear() here to keep the clear() tests cleanly separated
499 # from the add() tests.
500 trie = GeneralizedTrie()
502 # Test cases for setting values on trie entries
503 tests = [
504 # Initialize the trie with a key with a value and validate we get the expected id
505 TestSpec(
506 name="[TA019] trie.add(['tree', 'value', 'cheetah'], 'feline')",
507 action=trie.add,
508 args=[["tree", "value", "cheetah"], "feline"],
509 expected=TrieId(1),
510 ),
511 # validate that entry 1 (with the key ['tree', 'value', 'cheetah']) has the value of 'feline'
512 TestSpec(
513 name="[TA020] trie[1].value == 'feline' (_as_dict() check)",
514 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
515 expected={
516 'ident': None,
517 'children': {
518 'tree': {
519 'ident': None,
520 'token': 'tree',
521 'value': None,
522 'parent': None,
523 'children': {
524 'value': {
525 'ident': None,
526 'token': 'value',
527 'value': None,
528 'parent': 'tree',
529 'children': {
530 'cheetah': {
531 'ident': TrieId(1),
532 'token': 'cheetah',
533 'value': 'feline',
534 'parent': 'value',
535 'children': {}
536 }
537 }
538 }
539 }
540 }
541 },
542 'trie_index': [TrieId(1)],
543 'trie_entries': {
544 TrieId(1): "TrieEntry(ident=TrieId(1), key=['tree', 'value', 'cheetah'], value='feline')"
545 }
546 },
547 ),
548 # Add the same key with the same value and validate we get the same id as before
549 # (this is to test that the trie does not create a new entry for the same key with the same value
550 # and that it does not throw an error)
551 TestSpec(
552 name="[TA021] trie.add(['tree', 'value', 'cheetah'], 'feline')",
553 action=trie.add,
554 args=[["tree", "value", "cheetah"], "feline"],
555 exception=DuplicateKeyError,
556 exception_tag=ErrorTag.STORE_ENTRY_DUPLICATE_KEY,
557 # This is expected to raise a DuplicateKeyError, but we are testing that the trie
558 # does not change its state after adding the same key with the same value.
559 # So we do not expect the trie to change, and we will validate that in the
560 # next test case.
561 ),
562 # validate that the trie is unchanged after exception for trying to add the same key with the same value
563 TestSpec(
564 name="[TA022] trie[1].value == 'feline' (_as_dict() check)",
565 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
566 expected={
567 'ident': None,
568 'children': {
569 'tree': {
570 'ident': None,
571 'token': 'tree',
572 'value': None,
573 'parent': None,
574 'children': {
575 'value': {
576 'ident': None,
577 'token': 'value',
578 'value': None,
579 'parent': 'tree',
580 'children': {
581 'cheetah': {
582 'ident': TrieId(1),
583 'token': 'cheetah',
584 'value': 'feline',
585 'parent': 'value',
586 'children': {}
587 }
588 }
589 }
590 }
591 }
592 },
593 'trie_index': [TrieId(1)],
594 'trie_entries': {
595 TrieId(1): "TrieEntry(ident=TrieId(1), key=['tree', 'value', 'cheetah'], value='feline')"
596 }
597 },
598 ),
599 # Add the same key with a DIFFERENT value (default of None) and validate we get a DuplicateKeyError
600 TestSpec(
601 name="[TA022] trie.add(['tree', 'value', 'cheetah'])",
602 action=trie.add,
603 args=[["tree", "value", "cheetah"]],
604 exception=DuplicateKeyError,
605 exception_tag=ErrorTag.STORE_ENTRY_DUPLICATE_KEY,
606 ),
607 # Validate that the trie is unchanged after attempting to add the same key with a different value of None
608 # (this is to test that the trie has not changed the trie despite throwing an error)
609 # Validate that the trie is unchanged after attempting to add the same key with a different value of None
610 # (this is to test that the trie has not changed the trie despite throwing an error)
611 TestSpec(
612 name="[TA023] trie[1].value == 'feline' (_as_dict() check, no change after DuplicateKeyError)",
613 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
614 expected={
615 'ident': None,
616 'children': {
617 'tree': {
618 'ident': None,
619 'token': 'tree',
620 'value': None,
621 'parent': None,
622 'children': {
623 'value': {
624 'ident': None,
625 'token': 'value',
626 'value': None,
627 'parent': 'tree',
628 'children': {
629 'cheetah': {
630 'ident': TrieId(1),
631 'token': 'cheetah',
632 'value': 'feline',
633 'parent': 'value',
634 'children': {}
635 }
636 }
637 }
638 }
639 }
640 },
641 'trie_index': [TrieId(1)],
642 'trie_entries': {
643 TrieId(1): "TrieEntry(ident=TrieId(1), key=['tree', 'value', 'cheetah'], value='feline')"
644 }
645 },
646 ),
647 # Add the same key with a DIFFERENT value (explictly specified) and validate we get a DuplicateKeyError
648 TestSpec(
649 name="[TA024] trie.add(['tree', 'value', 'cheetah'], 'canide)",
650 action=trie.add,
651 args=[["tree", "value", "cheetah"], "canide"],
652 exception=DuplicateKeyError,
653 exception_tag=ErrorTag.STORE_ENTRY_DUPLICATE_KEY,
654 ),
655 ]
656 run_tests_list(self, tests)
658 @pytest.mark.order(after=['test_create_trie', 'test_trieid_class'])
659 @pytest.mark.dependency(
660 name='test_update',
661 depends=['test_create_trie', 'test_trieid_class'])
662 def test_update(self) -> None:
663 """Test the update method of GeneralizedTrie.
665 This test covers adding various types of keys to the trie via the update() method, including strings,
666 lists, and frozensets, and checks the expected behavior of the trie after each addition.
667 It also includes tests for error handling when invalid keys are added."""
668 # pylint: disable=protected-access, no-member
669 trie = GeneralizedTrie()
670 tests: list[TestSpec] = [
671 # Initialize from a list of strings and validate we get the expected id
672 TestSpec(
673 name="[TU001] trie.update(['tree', 'value', 'ape'])",
674 action=trie.update,
675 args=[["tree", "value", "ape"]],
676 kwargs={},
677 expected=TrieId(1),
678 ),
679 # Validate the dictionary representation of the trie is correct after initialization
680 TestSpec(
681 name="[TU002] _as_dict()",
682 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
683 expected={
684 'ident': None,
685 'children': {
686 'tree': {
687 'ident': None,
688 'token': 'tree',
689 'value': None,
690 'parent': None,
691 'children': {
692 'value': {
693 'ident': None,
694 'token': 'value',
695 'value': None,
696 'parent': 'tree',
697 'children': {
698 'ape': {
699 'ident': TrieId(1),
700 'token': 'ape',
701 'value': None,
702 'parent': 'value',
703 'children': {}
704 }
705 }
706 }
707 }
708 }
709 },
710 'trie_index': [TrieId(1)],
711 'trie_entries': {TrieId(1): "TrieEntry(ident=TrieId(1), key=['tree', 'value', 'ape'], value=None)"}
712 }
713 ),
715 # Add another entry ['tree', 'value'] and validate we get the expected id for it
716 TestSpec(
717 name="[TU003] trie.update(['tree', 'value']",
718 action=trie.update,
719 args=[["tree", "value"]],
720 expected=TrieId(2),
721 ),
722 # Validate the _as_dict representation of the trie is correct
723 TestSpec(
724 name="[TU004] _as_dict()",
725 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
726 expected={
727 'ident': None,
728 'children': {
729 'tree': {
730 'ident': None,
731 'token': 'tree',
732 'value': None,
733 'parent': None,
734 'children': {
735 'value': {
736 'ident': TrieId(2),
737 'token': 'value',
738 'value': None,
739 'parent': 'tree',
740 'children': {
741 'ape': {
742 'ident': TrieId(1),
743 'token': 'ape',
744 'value': None,
745 'parent': 'value',
746 'children': {}
747 }
748 }
749 }
750 }
751 }
752 },
753 'trie_index': [TrieId(1), TrieId(2)],
754 'trie_entries': {
755 TrieId(1): "TrieEntry(ident=TrieId(1), key=['tree', 'value', 'ape'], value=None)",
756 TrieId(2): "TrieEntry(ident=TrieId(2), key=['tree', 'value'], value=None)"
757 }
758 }
759 ),
760 # Add a string entry 'abcdef' and validate we get the expected id for it
761 TestSpec(
762 name="[TU005] trie.update('abcdef')",
763 action=trie.update,
764 args=["abcdef"],
765 expected=TrieId(3),
766 ),
767 # Add another entry [1, 3, 4, 5] and validate we get the expected id for it
768 TestSpec(
769 name="[TU006] trie.update([1, 3, 4, 5])",
770 action=trie.update,
771 args=[[1, 3, 4, 5]],
772 kwargs={},
773 expected=TrieId(4),
774 ),
775 # Add a frozenset entry and validate we get the expected id for it
776 TestSpec(
777 name="[TU007] trie.update(frozenset([1]), 3, 4, 5])",
778 action=trie.update,
779 args=[[frozenset([1]), 3, 4, 5]],
780 kwargs={},
781 expected=TrieId(5),
782 ),
783 # Add another frozenset entry and validate we get a different id for it
784 # than for the previously added frozenset
785 TestSpec(
786 name="[TU008] trie.update(frozenset([1]), 3, 4, 5])",
787 action=trie.update,
788 args=[[frozenset([1]), 3, 4, 6]],
789 expected=TrieId(6),
790 ),
791 # Attempt to add an integer as a key and validate we get the expected exception
792 TestSpec(
793 name="[TU009] trie.update(1)",
794 action=trie.update,
795 args=[1],
796 exception=InvalidGeneralizedKeyError,
797 exception_tag=ErrorTag.STORE_ENTRY_INVALID_GENERALIZED_KEY,
798 ),
799 # Attempt to add an empty list as a key and validate we get the expected exception
800 TestSpec(
801 name="[TU010] trie.update([])",
802 action=trie.update,
803 args=[[]],
804 exception=InvalidGeneralizedKeyError,
805 exception_tag=ErrorTag.STORE_ENTRY_INVALID_GENERALIZED_KEY,
806 ),
807 # Attempt to add a set as a key element and validate we get the expected exception
808 TestSpec(
809 name="[TU011] trie.update([set([1]), 3, 4, 5])",
810 action=trie.update,
811 args=[[set([1]), 3, 4, 5]],
812 exception=InvalidGeneralizedKeyError,
813 exception_tag=ErrorTag.STORE_ENTRY_INVALID_GENERALIZED_KEY,
814 ),
815 # Add a key that is a list of integers and validate we get the expected id for it
816 TestSpec(
817 name="[TU012] trie.update(key=[1, 3, 4, 7])",
818 action=trie.update,
819 kwargs={"key": [1, 3, 4, 7]},
820 expected=TrieId(7),
821 ),
822 # Attempt to pass add the wrong number of arguments and validate we get the expected exception
823 TestSpec(name="[TU013] trie.update()", action=trie.update, exception=TypeError),
824 TestSpec(
825 name="[TU014] trie.update(['a'], ['b'], ['c'])",
826 action=trie.update,
827 args=[["a"], ["b"], ["c"]],
828 exception=TypeError,
829 ),
830 # Validate the length of the trie after all additions
831 TestSpec(name="[TU015] len(trie)", action=len, args=[trie], expected=7),
832 # Add duplicate entry ['tree', 'value', 'ape'] and validate we get the original id for it
833 TestSpec(
834 name="[TU016] trie.update(['tree', 'value', 'ape'])",
835 action=trie.update,
836 args=[["tree", "value", "ape"]],
837 kwargs={},
838 expected=TrieId(1),
839 ),
840 # Validate the length of the trie after adding duplicate ['tree', 'value', 'ape'] is unchanged
841 TestSpec(name="[TU017] len(trie)", action=len, args=[trie], expected=7),
842 # Add a trie entry with a value and validate we get the expected id for it
843 TestSpec(
844 name="[TU018] trie.update(['tree', 'value', 'cheetah'], 'feline')",
845 action=trie.update,
846 args=[["tree", "value", "cheetah"], "feline"],
847 expected=TrieId(8),
848 ),
850 ]
851 run_tests_list(self, tests)
853 # New untouched trie for the next sequence of tests
854 # Not using clear() here to keep the clear() tests cleanly separated
855 # from the update() tests.
856 trie = GeneralizedTrie()
858 # Test cases for setting values on trie entries
859 tests = [
860 # Initialize the trie with a key with a value and validate we get the expected id
861 TestSpec(
862 name="[TU019] trie.update(['tree', 'value', 'cheetah'], 'feline')",
863 action=trie.update,
864 args=[["tree", "value", "cheetah"], "feline"],
865 expected=TrieId(1),
866 ),
867 # validate that entry 1 (with the key ['tree', 'value', 'cheetah']) has the value of 'feline'
868 TestSpec(
869 name="[TU020] trie[1].value == 'feline' (_as_dict() check)",
870 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
871 expected={
872 'ident': None,
873 'children': {
874 'tree': {
875 'ident': None,
876 'token': 'tree',
877 'value': None,
878 'parent': None,
879 'children': {
880 'value': {
881 'ident': None,
882 'token': 'value',
883 'value': None,
884 'parent': 'tree',
885 'children': {
886 'cheetah': {
887 'ident': TrieId(1),
888 'token': 'cheetah',
889 'value': 'feline',
890 'parent': 'value',
891 'children': {}
892 }
893 }
894 }
895 }
896 }
897 },
898 'trie_index': [TrieId(1)],
899 'trie_entries': {
900 TrieId(1): "TrieEntry(ident=TrieId(1), key=['tree', 'value', 'cheetah'], value='feline')"
901 }
902 },
903 ),
904 # Add the same key with the same value and validate we get the same id as before
905 # (this is to test that the trie does not create a new entry for the same key with the same value
906 # and that it does not throw an error)
907 TestSpec(
908 name="[TU021] trie.update(['tree', 'value', 'cheetah'], 'feline')",
909 action=trie.update,
910 args=[["tree", "value", "cheetah"], "feline"],
911 expected=TrieId(1),
912 ),
913 # validate that the trie is unchanged after adding the same key with the same value
914 TestSpec(
915 name="[TU022] trie[1].value == 'feline' (_as_dict() check)",
916 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
917 expected={
918 'ident': None,
919 'children': {
920 'tree': {
921 'ident': None,
922 'token': 'tree',
923 'value': None,
924 'parent': None,
925 'children': {
926 'value': {
927 'ident': None,
928 'token': 'value',
929 'value': None,
930 'parent': 'tree',
931 'children': {
932 'cheetah': {
933 'ident': TrieId(1),
934 'token': 'cheetah',
935 'value': 'feline',
936 'parent': 'value',
937 'children': {}
938 }
939 }
940 }
941 }
942 }
943 },
944 'trie_index': [TrieId(1)],
945 'trie_entries': {
946 TrieId(1): "TrieEntry(ident=TrieId(1), key=['tree', 'value', 'cheetah'], value='feline')"
947 }
948 },
949 ),
950 # Add the same key with a DIFFERENT value (default of None) and validate we get the expected id
951 # (this is to test that the trie updates the value of the existing entry)
952 TestSpec(
953 name="[TU023] trie.update(['tree', 'value', 'cheetah'])",
954 action=trie.update,
955 args=[["tree", "value", "cheetah"]],
956 expected=TrieId(1),
957 ),
958 # Validate that the trie was correctly updated after adding the same key with a different value of None
959 TestSpec(
960 name="[TU024] trie[1].value == None (_as_dict() check)",
961 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
962 expected={
963 'ident': None,
964 'children': {
965 'tree': {
966 'ident': None,
967 'token': 'tree',
968 'value': None,
969 'parent': None,
970 'children': {
971 'value': {
972 'ident': None,
973 'token': 'value',
974 'value': None,
975 'parent': 'tree',
976 'children': {
977 'cheetah': {
978 'ident': TrieId(1),
979 'token': 'cheetah',
980 'value': None,
981 'parent': 'value',
982 'children': {}
983 }
984 }
985 }
986 }
987 }
988 },
989 'trie_index': [TrieId(1)],
990 'trie_entries': {
991 TrieId(1): "TrieEntry(ident=TrieId(1), key=['tree', 'value', 'cheetah'], value=None)"
992 }
993 },
994 ),
995 # Add the same key with a DIFFERENT value (explictly specified) and validate we get the same id as before
996 TestSpec(
997 name="[TU025] trie.update(['tree', 'value', 'cheetah'], 'canide)",
998 action=trie.update,
999 args=[["tree", "value", "cheetah"], "canide"],
1000 expected=TrieId(1),
1001 ),
1002 # Validate that the trie was correctly updated after adding the same key with a different value of 'canide'
1003 TestSpec(
1004 name="[TU026] trie[1].value == 'canide' (_as_dict() check)",
1005 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
1006 expected={
1007 'ident': None,
1008 'children': {
1009 'tree': {
1010 'ident': None,
1011 'token': 'tree',
1012 'value': None,
1013 'parent': None,
1014 'children': {
1015 'value': {
1016 'ident': None,
1017 'token': 'value',
1018 'value': None,
1019 'parent': 'tree',
1020 'children': {
1021 'cheetah': {
1022 'ident': TrieId(1),
1023 'token': 'cheetah',
1024 'value': 'canide',
1025 'parent': 'value',
1026 'children': {}
1027 }
1028 }
1029 }
1030 }
1031 }
1032 },
1033 'trie_index': [TrieId(1)],
1034 'trie_entries': {
1035 TrieId(1): "TrieEntry(ident=TrieId(1), key=['tree', 'value', 'cheetah'], value='canide')"
1036 }
1037 },
1038 ),
1039 ]
1040 run_tests_list(self, tests)
1042 @pytest.mark.order(after=['test_create_trie', 'test_add'])
1043 @pytest.mark.dependency(
1044 name='test_add_user_defined_classes',
1045 depends=['test_create_trie', 'test_add'])
1046 def test_add_user_defined_classes(self) -> None:
1047 """Test adding user-defined classes to GeneralizedTrie.
1049 This test checks that the trie can handle user-defined classes that implement
1050 the TrieKeyToken interface and that it can distinguish between different instances
1051 of these classes based on their content."""
1052 trie = GeneralizedTrie()
1053 a: list[str | MockDefaultTrieKeyToken] = ['red', MockDefaultTrieKeyToken(a=(1, 2, 3), b='hello')]
1054 b: list[str | MockDefaultTrieKeyToken] = ['red', MockDefaultTrieKeyToken(a=(1, 2, 3), b='hello')]
1055 c: list[str | MockContentAwareTrieKeyToken] = ['red', MockContentAwareTrieKeyToken(a=(1, 2, 3), b='hello')]
1056 d: list[str | MockContentAwareTrieKeyToken] = ['red', MockContentAwareTrieKeyToken(a=(1, 2, 3), b='hello')]
1058 with self.subTest(msg='[TAUDC001] a <=> b'):
1059 self.assertNotEqual(a, b)
1060 with self.subTest(msg='[TAUDC002] a <=> a'):
1061 self.assertEqual(a, a)
1062 with self.subTest(msg='[TAUDC003] c <=> d'):
1063 self.assertEqual(c, d)
1064 with self.subTest(msg='[TAUDC004] c <=> c'):
1065 self.assertEqual(c, c, msg='c <=> c')
1067 tests: list[TestSpec] = [
1068 TestSpec(
1069 name="[TAUDC005] trie.add(['red', MockDefaultTrieKeyToken(a=(1, 2, 3), b='hello')])",
1070 action=trie.add,
1071 args=[a],
1072 expected=TrieId(1),
1073 ),
1074 TestSpec(
1075 name="[TAUDC006] trie.add(['red', MockDefaultTrieKeyToken(a=[1, 2, 3], b='hello')])",
1076 action=trie.add,
1077 args=[b],
1078 expected=TrieId(2),
1079 ),
1080 TestSpec(
1081 name="[TAUDC007] trie.add(['red', MockContentAwareTrieKeyToken(a=(1, 2, 3), b='hello')])",
1082 action=trie.add,
1083 args=[c],
1084 expected=TrieId(3),
1085 ),
1086 TestSpec(
1087 name="[TAUDC008] trie.add(['red', MockContentAwareTrieKeyToken(a=(1, 2, 3), b='hello')])",
1088 action=trie.add,
1089 args=[d],
1090 exception=DuplicateKeyError,
1091 exception_tag=ErrorTag.STORE_ENTRY_DUPLICATE_KEY,
1092 ),
1093 ]
1094 run_tests_list(self, tests)
1096 @pytest.mark.order(after=['test_create_trie', 'test_add', 'test_trieid_class'])
1097 @pytest.mark.dependency(
1098 name='test_prefixes',
1099 depends=['test_create_trie', 'test_add', 'test_trieid_class'])
1100 def test_prefixes(self) -> None:
1101 """Test the prefixes method of GeneralizedTrie.
1103 This test checks that the prefixes method correctly identifies all prefixes
1104 of a given key in the trie, including those that are not complete entries."""
1105 trie: GeneralizedTrie = GeneralizedTrie()
1106 tests: list[TestSpec] = [
1107 TestSpec(
1108 name="[TGT_TP001] trie.prefixes(['tree', 'value', 'ape']) (empty trie)",
1109 action=lambda key: list(trie.prefixes(key)), # type: ignore[reportUnknownMemberType]
1110 args=[['tree', 'value', 'ape']],
1111 expected=[]
1112 ),
1113 TestSpec(
1114 name="[TGT_TP002] trie.add(['tree', 'value', 'ape'])",
1115 action=trie.add,
1116 args=[["tree", "value", "ape"]],
1117 expected=TrieId(1)
1118 ),
1119 TestSpec(
1120 name="[TGT_TP003] trie.prefixes(['tree', 'value', 'ape']) (exact key in trie)",
1121 action=lambda key: list(trie.prefixes(key)), # type: ignore[reportUnknownMemberType]
1122 args=[['tree', 'value', 'ape']],
1123 expected=[TrieEntry(TrieId(1), ['tree', 'value', 'ape'])]
1124 ),
1125 TestSpec(
1126 name=("[TGT_TP004] trie.prefixes(['tree', 'value', 'ape', 'grape']) "
1127 "(NOT exact key in trie, but has other keys that are prefix)"),
1128 action=lambda key: list(trie.prefixes(key)), # type: ignore[reportUnknownMemberType]
1129 args=[['tree', 'value', 'ape', 'grape']],
1130 expected=[TrieEntry(TrieId(1), ['tree', 'value', 'ape'])]
1131 ),
1132 TestSpec(
1133 name=("[TGT_TP005] trie.prefixes(['tree', 'value']) "
1134 "(NOT exact key in trie, does not have other keys that are prefix)"),
1135 action=lambda key: list(trie.prefixes(key)), # type: ignore[reportUnknownMemberType]
1136 args=[['tree', 'value']],
1137 expected=[]
1138 ),
1139 ]
1140 run_tests_list(self, tests)
1142 @pytest.mark.order(after=['test_create_trie', 'test_add', 'test_trieid_class'])
1143 @pytest.mark.dependency(
1144 name='test_prefixed_by',
1145 depends=['test_create_trie', 'test_add', 'test_trieid_class'])
1146 def test_prefixed_by(self) -> None:
1147 """Test the prefixed_by method of GeneralizedTrie.
1149 This test checks that the prefixed_by method correctly identifies all keys
1150 in the trie that are prefixed by the specified key."""
1151 trie: GeneralizedTrie = GeneralizedTrie()
1152 tests: list[TestSpec] = [
1153 TestSpec(
1154 name="[TGT_TPB001] tree.prefixed_by(['tree']) (empty trie, no possible prefixed keys)",
1155 action=lambda key: list(trie.prefixed_by(key)), # type: ignore[reportUnknownMemberType]
1156 args=[['tree']],
1157 expected=[]
1158 ),
1159 TestSpec(
1160 name="[TGT_TPB002] trie.add(['tree', 'value', 'ape']) (one key in trie)",
1161 action=trie.add,
1162 args=[["tree", "value", "ape"]],
1163 expected=TrieId(1)
1164 ),
1165 TestSpec(
1166 name="[TGT_TPB003] trie.prefixed_by(['tree', 'value', 'ape']) (exact key in trie, no others)",
1167 action=lambda key: list(trie.prefixed_by(key)), # type: ignore[reportUnknownMemberType]
1168 args=[['tree', 'value', 'ape']],
1169 expected=[TrieEntry(TrieId(1), ['tree', 'value', 'ape'])]
1170 ),
1171 TestSpec(
1172 name=("[TGT_TPB004] trie.prefixed_by(['tree']) "
1173 "(NOT exact key in trie, but prefixes other keys in the trie)"),
1174 action=lambda key: list(trie.prefixed_by(key)), # type: ignore[reportUnknownMemberType]
1175 args=[['tree']],
1176 expected=[TrieEntry(TrieId(1), ['tree', 'value', 'ape'])]
1177 ),
1178 TestSpec(
1179 name=("[TGT_TPB005] trie.prefixed_by(['tree', 'value', 'ape', 'grape']) "
1180 "(NOT exact key in trie, does not have other keys in trie it is a prefix for)"),
1181 action=lambda key: list(trie.prefixed_by(key)), # type: ignore[reportUnknownMemberType]
1182 args=[['tree', 'value', 'ape', 'grape']],
1183 expected=[]
1184 ),
1185 TestSpec(
1186 name=("[TGT_TPB006] trie.prefixed_by(key=['tree'], depth=0) "
1187 "(NO exact key in trie)"),
1188 action=lambda key, depth: list(trie.prefixed_by( # pyright: ignore[reportUnknownLambdaType]
1189 key=key, depth=depth)), # type: ignore[reportUnknownMemberType]
1190 kwargs={'key': ['tree'], 'depth': 0},
1191 expected=[]
1192 ),
1193 TestSpec(
1194 name=("[TGT_TPB007] trie.prefixed_by(key=['tree'], depth=1) "
1195 "(NOT exact key in trie, does not have other keys in trie it is a prefix for within depth 1)"),
1196 action=lambda key, depth: list(trie.prefixed_by( # pyright: ignore[reportUnknownLambdaType]
1197 key=key, depth=depth)), # type: ignore[reportUnknownMemberType]
1198 kwargs={'key': ['tree'], 'depth': 1},
1199 expected=[]
1200 ),
1201 TestSpec(
1202 name=("[TGT_TPB008] trie.prefixed_by(key=['tree'], depth=2) "
1203 "(NOT exact key in trie, has other keys in trie it is a prefix for within depth 2)"),
1204 action=lambda key, depth: list(trie.prefixed_by( # pyright: ignore[reportUnknownLambdaType]
1205 key=key, depth=depth)), # type: ignore[reportUnknownMemberType]
1206 kwargs={'key': ['tree'], 'depth': 2},
1207 expected=[TrieEntry(TrieId(1), ['tree', 'value', 'ape'])]
1208 ),
1209 TestSpec(
1210 name=("[TGT_TPB009] trie.prefixed_by(key=['tree'], depth=-1) "
1211 "(NOT exact key in trie, has other keys in trie it is a prefix for within any depth)"),
1212 action=lambda key, depth: list(trie.prefixed_by( # pyright: ignore[reportUnknownLambdaType]
1213 key=key, depth=depth)), # type: ignore[reportUnknownMemberType]
1214 kwargs={'key': ['tree'], 'depth': -1},
1215 expected=[TrieEntry(TrieId(1), ['tree', 'value', 'ape'])]
1216 ),
1217 TestSpec(
1218 name=("[TGT_TPB010] trie.prefixed_by(key=['tree'], depth=-2) "
1219 "(TrieValueError, TRIE_PREFIXED_BY_BAD_DEPTH_VALUE)"),
1220 action=lambda key, depth: list(trie.prefixed_by( # pyright: ignore[reportUnknownLambdaType]
1221 key=key, depth=depth)), # type: ignore[reportUnknownMemberType]
1222 kwargs={'key': ['tree'], 'depth': -2},
1223 exception=TrieValueError,
1224 exception_tag=ErrorTag.TRIE_PREFIXED_BY_BAD_DEPTH_VALUE,
1225 ),
1226 TestSpec(
1227 name=("[TGT_TPB011] trie.prefixed_by(key=['tree'], depth=-1.0) "
1228 "(TrieTypeError, TRIE_PREFIXED_BY_BAD_DEPTH_TYPE)"),
1229 action=lambda key, depth: list(trie.prefixed_by( # pyright: ignore[reportUnknownLambdaType]
1230 key=key, depth=depth)), # type: ignore[reportUnknownMemberType]
1231 kwargs={'key': ['tree'], 'depth': -1.0},
1232 exception=TrieTypeError,
1233 exception_tag=ErrorTag.TRIE_PREFIXED_BY_BAD_DEPTH_TYPE,
1234 ),
1235 TestSpec(
1236 name=("[TGT_TPB012] trie.prefixed_by([set([1]), 3, 4, 5]) "
1237 "(InvalidGeneralizedKeyError, TRIE_PREFIXED_BY_INVALID_GENERALIZED_KEY)"),
1238 action=lambda key: list(trie.prefixed_by(key)), # type: ignore[reportUnknownMemberType]
1239 args=[[set([1]), 3, 4, 5]],
1240 exception=InvalidGeneralizedKeyError,
1241 exception_tag=ErrorTag.TRIE_PREFIXED_BY_INVALID_GENERALIZED_KEY,
1242 ),
1243 TestSpec(
1244 name=("[TGT_TPB013] trie.add(['tree', 'value']) (two keys in trie, overlapping)"),
1245 action=trie.add,
1246 args=[["tree", "value"]],
1247 expected=TrieId(2)
1248 ),
1249 ]
1250 run_tests_list(self, tests)
1252 @pytest.mark.order(after=['test_create_trie', 'test_add', 'test_trieid_class', 'test_contains'])
1253 @pytest.mark.dependency(
1254 name='test_deeply_nested_keys',
1255 depends=['test_create_trie', 'test_add', 'test_trieid_class', 'test_contains'])
1256 def test_deeply_nested_keys(self):
1257 """Test that deeply nested keys can be added and queried correctly.
1259 This test checks that the trie can handle keys with a large number of elements
1260 and that it correctly identifies prefixes and suffixes for such keys."""
1261 trie = GeneralizedTrie()
1262 deep_key = ["a"] * 100
1263 id1 = trie.add(deep_key)
1264 self.assertEqual(id1, TrieId(1))
1265 self.assertTrue(deep_key in trie)
1266 self.assertEqual(set(trie.prefixes(deep_key)), set([TrieEntry(TrieId(1), deep_key)]))
1267 self.assertEqual(set(trie.prefixed_by(deep_key)), set([TrieEntry(TrieId(1), deep_key)]))
1269 @pytest.mark.order(after=['test_create_trie', 'test_add', 'test_trieid_class', 'test_contains'])
1270 @pytest.mark.dependency(
1271 name='test_unicode_and_bytes_keys',
1272 depends=['test_create_trie', 'test_add', 'test_trieid_class', 'test_contains'])
1273 def test_unicode_and_bytes_keys(self):
1274 """Test that unicode and bytes keys can coexist in the trie.
1276 This test checks that the trie can handle both unicode strings and byte strings
1277 as keys, and that they are treated as distinct entries."""
1278 trie = GeneralizedTrie()
1279 unicode_key = ["α", "β", "γ"]
1280 bytes_key = [b"\xf0\x9f\x92\xa9"]
1281 id1 = trie.add(unicode_key)
1282 id2 = trie.add(bytes_key)
1283 self.assertEqual(id1, TrieId(1))
1284 self.assertEqual(id2, TrieId(2))
1285 self.assertTrue(unicode_key in trie)
1286 self.assertTrue(bytes_key in trie)
1288 @pytest.mark.order(after=['test_contains'])
1289 @pytest.mark.dependency(
1290 name='test_mutated_key_after_insertion',
1291 depends=['test_trieid_class', 'test_create_trie', 'test_add', 'test_contains'])
1292 def test_mutated_key_after_insertion(self):
1293 """Test that mutating a key after insertion does not affect the trie.
1295 This test checks that the trie maintains the integrity of the original key.
1296 """
1297 trie = GeneralizedTrie()
1298 key = ["a", "b"]
1299 _ = trie.add(key)
1300 key.append("c") # Mutate after insertion
1301 # The mutated key should not be found as the original
1302 self.assertFalse(key in trie)
1303 # The original key (["a", "b"]) should still be present
1304 self.assertTrue(["a", "b"] in trie)
1306 @pytest.mark.order(after=['test_create_trie', 'test_is_generalizedkey'])
1307 @pytest.mark.dependency(
1308 name='test_invalid_argument_types_for_prefixes',
1309 depends=['test_create_trie', 'test_is_generalizedkey'])
1310 def test_invalid_argument_types_for_prefixes(self):
1311 """Test that invalid argument types raise correct exceptions."""
1312 trie = GeneralizedTrie()
1313 with self.assertRaises(
1314 InvalidGeneralizedKeyError,
1315 msg='[TIATFP001] Failed to raise InvalidGeneralizedKeyError for trie.prefixes(12345)'):
1316 # Attempt to get prefixes for an invalid key type. Because a Generator is
1317 # returned, it will not raise the error until the generator is consumed.
1318 _ = set(trie.prefixes(12345)) # type: ignore[reportGeneralTypeIssues] # int is not a valid key
1319 with self.assertRaises(
1320 InvalidGeneralizedKeyError,
1321 msg='[TIATFP002] Failed to raise InvalidGeneralizedKeyError for trie.prefixes(3.14)'):
1322 _ = set(trie.prefixes(3.14)) # type: ignore[reportGeneralTypeIssues] # float is not a valid key
1324 def test_invalid_argument_types_for_prefixed_by(self):
1325 """Test that invalid argument types raise TypeError."""
1326 trie = GeneralizedTrie()
1327 with self.assertRaises(
1328 InvalidGeneralizedKeyError,
1329 msg='[TIATFPB001] Failed to raise InvalidGeneralizedKeyError for trie.prefixed_by(12345)'):
1330 _ = set(trie.prefixed_by(12345)) # type: ignore[reportGeneralTypeIssues] # int is not a valid key
1331 with self.assertRaises(
1332 InvalidGeneralizedKeyError,
1333 msg='[TIATFPB002] Failed to raise InvalidGeneralizedKeyError for trie.prefixed_by(3.14)'):
1334 _ = set(trie.prefixed_by(3.14)) # type: ignore[reportGeneralTypeIssues] # float is not a valid key
1336 def test_large_trie_performance(self):
1337 """Test performance of adding a large number of entries to the trie."""
1338 trie = GeneralizedTrie()
1339 for i in range(1000):
1340 trie.add([i, i+1, i+2])
1341 self.assertEqual(len(trie), 1000)
1342 # Spot check a few
1343 self.assertTrue([10, 11, 12] in trie)
1344 self.assertTrue([999, 1000, 1001] in trie)
1346 @pytest.mark.order(after='test_contains')
1347 @pytest.mark.dependency(name='test_bytes_vs_str',
1348 depends=['test_create_trie', 'test_contains'])
1349 def test_bytes_vs_str(self):
1350 """Test that adding a string and bytes with the same content generates different IDs.
1352 This test checks that the trie treats strings and bytes as distinct types."""
1353 trie = GeneralizedTrie()
1354 id1 = trie.add("abc")
1355 id2 = trie.add(b"abc")
1356 self.assertNotEqual(id1, id2)
1357 self.assertTrue("abc" in trie)
1358 self.assertTrue(b"abc" in trie)
1360 def test_empty_trie_iter(self):
1361 """Test that an empty trie iterates to an empty list."""
1362 trie = GeneralizedTrie()
1363 self.assertEqual(list(trie), [])
1365 def test_remove_nonexistent_id(self):
1366 """Test removing a non-existent ID from the trie.
1368 This test checks that attempting to remove an ID that does not exist
1369 raises a KeyError.
1370 """
1371 trie = GeneralizedTrie()
1372 self.assertEqual(
1373 trie.add("abc"),
1374 TrieId(1),
1375 msg='[TRNEI001] Add an entry to ensure the trie is not empty. Should have TrieId(1)')
1376 with self.assertRaises(KeyError,
1377 msg='[TRNEI002] Removing a non-existent TrieId(999999) should raise KeyError'):
1378 trie.remove(TrieId(999999)) # Non-existent TrieId
1379 with self.assertRaises(
1380 TypeError,
1381 msg=('[TRNEI003] Removing 1 should raise a TypError because it is not a '
1382 'TrieId or a valid GeneralizedKey')):
1383 trie.remove(1) # type: ignore[reportGeneralTypeIssues]
1385 def test_remove_and_readd(self):
1386 """Test removing an entry and then re-adding it to ensure a new ID is generated.
1388 This test checks that after removing an entry, adding the same key again
1389 generates a new ID, confirming that the trie correctly handles the removal
1390 and re-adding of entries."""
1391 trie = GeneralizedTrie()
1392 key = ["x", "y", "z"]
1393 id1 = trie.add(key)
1394 trie.remove(id1)
1395 id2 = trie.add(key)
1396 self.assertNotEqual(id1, id2)
1397 self.assertTrue(key in trie)
1399 @pytest.mark.order(after='test_add')
1400 @pytest.mark.dependency(name='test_remove', depends=[
1401 'test_create_trie', 'test_trieid_class', 'test_add'])
1402 def test_remove(self) -> None:
1403 """Test the remove method of GeneralizedTrie.
1405 This test covers adding, removing, and checking the state of the trie.
1407 It includes various scenarios such as removing existing entries, handling
1408 non-existing entries, and checking the length of the trie after removals.
1410 The test also checks for correct exception handling when trying to remove
1411 non-existing entries or entries with invalid types.
1413 This test is designed to ensure that the remove method behaves correctly
1414 and maintains the integrity of the trie structure."""
1415 trie: GeneralizedTrie = GeneralizedTrie()
1416 tests: list[TestSpec] = [
1417 TestSpec(
1418 name="[TR001] trie.add('a')", action=trie.add, args=["a"], expected=TrieId(1)
1419 ),
1420 TestSpec(
1421 name="[TR002] trie.add('ab')", action=trie.add, args=["ab"], expected=TrieId(2)
1422 ),
1423 TestSpec(
1424 name="[TR003] trie.add('abc')", action=trie.add, args=["abc"], expected=TrieId(3),
1425 ),
1426 TestSpec(
1427 name="[TR004] trie.add('abe')",
1428 action=trie.add,
1429 args=["abe"],
1430 expected=TrieId(4),
1431 ),
1432 TestSpec(
1433 name="[TR005] trie.add('abef')",
1434 action=trie.add,
1435 args=["abef"],
1436 expected=TrieId(5),
1437 ),
1438 TestSpec(
1439 name="[TR006] trie.add('abcd')",
1440 action=trie.add,
1441 args=["abcd"],
1442 expected=TrieId(6),
1443 ),
1444 TestSpec(
1445 name="[TR007] trie.add('abcde')",
1446 action=trie.add,
1447 args=["abcde"],
1448 expected=TrieId(7),
1449 ),
1450 TestSpec(
1451 name="[TR008] trie.add('abcdf')",
1452 action=trie.add,
1453 args=["abcdef"],
1454 expected=TrieId(8),
1455 ),
1456 TestSpec(
1457 name="[TR009] trie.add('abcdefg')",
1458 action=trie.add,
1459 args=["abcdefg"],
1460 expected=TrieId(9),
1461 ),
1462 TestSpec(
1463 name="[TR010] trie.remove(TrieId(9))",
1464 action=trie.remove,
1465 args=[TrieId(9)],
1466 expected=None,
1467 ),
1468 TestSpec(name="[TR011] len(trie)", action=len, args=[trie], expected=8),
1469 TestSpec(
1470 name="[TR012] trie.remove(TrieId(9)) (TrieKeyError, REMOVAL_KEY_NOT_FOUND)",
1471 action=trie.remove,
1472 args=[TrieId(9)],
1473 exception=TrieKeyError,
1474 exception_tag=ErrorTag.REMOVAL_KEY_NOT_FOUND,
1475 ),
1476 TestSpec(name="[TR013] len(trie)", action=len, args=[trie], expected=8),
1477 TestSpec(
1478 name="[TR014] trie.remove(TrieId(1))",
1479 action=trie.remove,
1480 args=[TrieId(1)],
1481 expected=None,
1482 ),
1483 TestSpec(name="[TR015] len(trie)", action=len, args=[trie], expected=7),
1484 TestSpec(
1485 name="[TR016] trie.remove(TrieId(2))",
1486 action=trie.remove,
1487 args=[TrieId(2)],
1488 expected=None,
1489 ),
1490 TestSpec(name="[TR017] len(trie)", action=len, args=[trie], expected=6),
1491 TestSpec(
1492 name="[TR018] trie.remove('defghi') (TrieKeyError, REMOVAL_KEY_NOT_FOUND)",
1493 action=trie.remove,
1494 args=["defghi"],
1495 exception=TrieKeyError,
1496 exception_tag=ErrorTag.REMOVAL_KEY_NOT_FOUND,
1497 ),
1498 TestSpec(
1499 name="[TR019] trie.remove(TrieId(0)) (TrieKeyError, REMOVAL_KEY_NOT_FOUND)",
1500 action=trie.remove,
1501 args=[TrieId(0)],
1502 exception=TrieKeyError,
1503 exception_tag=ErrorTag.REMOVAL_KEY_NOT_FOUND,
1504 ),
1505 TestSpec(
1506 name="[TR020] trie.add('qrstuv')",
1507 action=trie.add,
1508 args=['qrstuv'],
1509 expected=TrieId(10),
1510 ),
1511 TestSpec(
1512 name="[TR021] trie.remove(TrieId(10))",
1513 action=trie.remove,
1514 args=[TrieId(10)],
1515 expected=None,
1516 ),
1517 TestSpec(
1518 name="[TR022] len(trie)",
1519 action=len,
1520 args=[trie],
1521 expected=6,
1522 ),
1523 ]
1524 run_tests_list(self, tests)
1526 def test_str(self) -> None:
1527 """Test the string representation of GeneralizedTrie.
1529 This test checks the output of the __str__ method of GeneralizedTrie
1530 for various string inputs. It verifies that the string representation
1531 correctly reflects the structure of the trie, including the children,
1532 parent nodes, and trie IDs.
1534 The test includes multiple scenarios with different string lengths
1535 and ensures that the output matches the expected format."""
1536 trie = GeneralizedTrie()
1537 test_string = 'a'
1538 self.assertIsInstance(test_string, TrieKeyToken)
1539 self.assertIsInstance(test_string, Iterable)
1541 trie.add(test_string)
1542 found: str = dedent(str(trie))
1543 expected: str = dedent("""\
1544 {
1545 trie number = 1
1546 children = {
1547 'a' = {
1548 parent = root node
1549 node token = 'a'
1550 trie id = TrieId(1)
1551 }
1552 }
1553 trie index = dict_keys([TrieId(1)])
1554 }""")
1555 self.assertEqual(found, expected, msg='[TSTR001] str(trie)')
1557 trie = GeneralizedTrie()
1558 test_string = 'ab'
1559 trie.add(test_string)
1560 found = dedent(str(trie))
1561 expected = dedent("""\
1562 {
1563 trie number = 1
1564 children = {
1565 'a' = {
1566 parent = root node
1567 node token = 'a'
1568 children = {
1569 'b' = {
1570 parent = 'a'
1571 node token = 'b'
1572 trie id = TrieId(1)
1573 }
1574 }
1575 }
1576 }
1577 trie index = dict_keys([TrieId(1)])
1578 }""")
1579 self.assertEqual(found, expected, msg='[TSTR002] str(trie))')
1581 trie = GeneralizedTrie()
1582 test_string = 'abc'
1583 trie.add(test_string)
1584 found = dedent(str(trie))
1585 expected = dedent("""\
1586 {
1587 trie number = 1
1588 children = {
1589 'a' = {
1590 parent = root node
1591 node token = 'a'
1592 children = {
1593 'b' = {
1594 parent = 'a'
1595 node token = 'b'
1596 children = {
1597 'c' = {
1598 parent = 'b'
1599 node token = 'c'
1600 trie id = TrieId(1)
1601 }
1602 }
1603 }
1604 }
1605 }
1606 }
1607 trie index = dict_keys([TrieId(1)])
1608 }""")
1609 self.assertEqual(found, expected, msg='[TSTR003] str(trie))')
1611 def test_getitem(self) -> None:
1612 """Test the __getitem__ dunder method of GeneralizedTrie.
1614 This test checks whether the trie correctly retrieves values for
1615 existing keys and raises the appropriate errors for non-existing
1616 keys or invalid key types."""
1617 trie: GeneralizedTrie = GeneralizedTrie()
1618 tests: list[TestSpec] = [
1619 TestSpec(
1620 name="[TGI001] trie.__getitem__(TrieId(1)) (Empty Trie, TrieKeyError, GETITEM_ID_NOT_FOUND)",
1621 action=trie.__getitem__,
1622 args=[TrieId(1)],
1623 exception=TrieKeyError,
1624 exception_tag=ErrorTag.GETITEM_ID_NOT_FOUND
1625 ),
1626 TestSpec(
1627 name="[TGI002] trie.add(key='a', value='value')",
1628 action=trie.add,
1629 kwargs={"key": "a", "value": "value"},
1630 expected=TrieId(1)
1631 ),
1632 TestSpec(
1633 name="[TGI003] trie.__getitem__('a') ('a' -> 'value' after add)",
1634 action=trie.__getitem__,
1635 args=['a'],
1636 expected=TrieEntry(ident=TrieId(1), key='a', value='value')
1637 ),
1638 TestSpec(
1639 name="[TGI004] trie.__getitem__('abc') (Non-existent key, TrieKeyError, GETITEM_KEY_NOT_FOUND)",
1640 action=trie.__getitem__,
1641 args=['abc'],
1642 exception=TrieKeyError,
1643 exception_tag=ErrorTag.GETITEM_KEY_NOT_FOUND
1644 ),
1645 TestSpec(
1646 name="[TGI005] trie.__getitem__(set('a')) (TrieTypeError, GETITEM_INVALID_KEY_TYPE)",
1647 action=trie.__getitem__,
1648 args=[set('abc')],
1649 exception=TrieTypeError,
1650 exception_tag=ErrorTag.GETITEM_INVALID_KEY_TYPE
1651 ),
1652 TestSpec(
1653 name="[TGI006] trie.add(key='abc', value='another value')",
1654 action=trie.add,
1655 kwargs={"key": "abc", "value": "another value"},
1656 expected=TrieId(2)
1657 ),
1658 TestSpec(
1659 name="[TGI007] trie.__getitem__('ab') (Non-existent key, TrieKeyError, GETITEM_NOT_TERMINAL)",
1660 action=trie.__getitem__,
1661 args=['ab'],
1662 exception=TrieKeyError,
1663 exception_tag=ErrorTag.GETITEM_NOT_TERMINAL
1664 ),
1665 ]
1666 run_tests_list(self, tests)
1668 @pytest.mark.order(after='test_add')
1669 @pytest.mark.dependency(name='test_contains', depends=[
1670 'test_create_trie', 'test_add'])
1671 def test_contains(self) -> None:
1672 """Test the __contains__ dundermethod of GeneralizedTrie.
1674 This test checks whether the trie correctly identifies the presence
1675 or absence of various keys. It includes tests for both existing and
1676 non-existing keys, as well as checks for keys that have been added
1677 and then removed.
1679 The test verifies that the __contains__ dunder method returns the expected
1680 boolean values for each key, ensuring that the trie behaves correctly
1681 when checking for membership."""
1682 trie: GeneralizedTrie = GeneralizedTrie()
1683 tests: list[TestSpec] = [
1684 TestSpec(
1685 name="[TC001] trie.__contains__('a') (false)",
1686 action=trie.__contains__,
1687 args=['a'],
1688 expected=False
1689 ),
1690 TestSpec(
1691 name="[TC002] trie.add('a')", action=trie.add, args=["a"], expected=TrieId(1)
1692 ),
1693 TestSpec(
1694 name="[TC003] trie.__contains__('a') (true)",
1695 action=trie.__contains__,
1696 args=['a'],
1697 expected=True
1698 ),
1699 TestSpec(
1700 name="[TC004] trie.remove(TrieId(1))", action=trie.remove, args=[TrieId(1)], expected=None
1701 ),
1702 TestSpec(
1703 name="[TC005] trie.__contains__('a') (false after removal)",
1704 action=trie.__contains__,
1705 args=['a'],
1706 expected=False
1707 ),
1708 ]
1709 run_tests_list(self, tests)
1711 with self.subTest(msg="[TC006] [1] in trie"):
1712 self.assertFalse([1] in trie)
1714 with self.subTest(msg="[TC007] 'a' in trie"):
1715 trie.add("a")
1716 self.assertTrue("a" in trie)
1718 with self.subTest(msg="[TC008] 'abc' in trie"):
1719 trie.add("abc")
1720 self.assertTrue("abc" in trie)
1722 trie = GeneralizedTrie() # Reset trie for next tests
1723 test_keys: list[str] = [
1724 '0123456789ABCDE', '0123456789ABCDF', '0123456789ABCDG', '0123456789ABCDH', '0123456789ABCDI',
1725 '0123456789ABCDJ', '0123456789ABCDK', '0123456789ABCDL', '0123456789ABCDM', '0123456789ABCDN'
1726 ]
1727 for key in test_keys:
1728 trie[key] = key
1730 with self.subTest(msg="[TC010] '0123456789ABCDE' in trie"):
1731 self.assertTrue('0123456789ABCDE' in trie)
1733 @pytest.mark.order(after='test_remove')
1734 @pytest.mark.dependency(name='test_keys', depends=[
1735 'test_create_trie', 'test_add', 'test_contains', 'test_remove'])
1736 def test_keys(self) -> None:
1737 """Test the keys method of GeneralizedTrie.
1739 This test checks the functionality of the keys method, which should
1740 return an iterable of TrieId objects representing the keys in the trie.
1742 The test includes scenarios for an empty trie, adding keys, and
1743 removing keys. It verifies that the keys method returns the expected
1744 TrieId objects in the correct order."""
1745 trie: GeneralizedTrie = GeneralizedTrie()
1747 with self.subTest(msg="[TK001] trie.keys()"):
1748 expect_id_list: list[TrieId] = []
1749 found_id_list: list[TrieId] = list(trie.keys())
1750 self.assertEqual(found_id_list, expect_id_list)
1752 with self.subTest(msg="[TK002] trie.add('abcdef')"):
1753 expect_id: TrieId = TrieId(1)
1754 found_id: TrieId = trie.add("abcdef")
1755 self.assertEqual(found_id, expect_id)
1757 with self.subTest(msg="[TK003] trie.keys()"):
1758 expect_id_list: list[TrieId] = [TrieId(1)]
1759 found_id_list: list[TrieId] = list(trie.keys())
1760 self.assertEqual(found_id_list, expect_id_list)
1762 with self.subTest(msg="[TK004] trie.add('abc')"):
1763 expect_id = TrieId(2)
1764 found_id = trie.add("abc")
1765 self.assertEqual(found_id, expect_id)
1767 with self.subTest(msg="[TK005] trie.keys()"):
1768 expect_id_list = [TrieId(1), TrieId(2)]
1769 found_id_list = list(sorted(trie.keys()))
1770 self.assertEqual(found_id_list, expect_id_list)
1772 with self.assertRaises(TypeError, msg="[TK006] trie.remove('abc')"):
1773 trie.remove(set('abc')) # type: ignore[reportGeneralTypeIssues]
1775 with self.subTest(msg="[TK007] trie.remove(TrieId(1))"):
1776 trie.remove(TrieId(1))
1777 expect_id_list = [TrieId(2)]
1778 found_id_list = list(trie.keys())
1779 self.assertEqual(found_id_list, expect_id_list)
1781 with self.subTest(msg="[TK008] trie.remove(TrieId(2))"):
1782 trie.remove(TrieId(2))
1783 expect_id_list = []
1784 found_id_list = list(trie.keys())
1785 self.assertEqual(found_id_list, expect_id_list)
1787 @pytest.mark.order(after='test_add')
1788 @pytest.mark.dependency(name='test_values', depends=['test_create_trie', 'test_trieid_class', 'test_add'])
1789 def test_values(self) -> None:
1790 """Test the values method of GeneralizedTrie.
1792 This test checks the functionality of the values method, which should
1793 return an iterable of TrieEntry objects representing the values in the trie.
1794 The test includes scenarios for an empty trie, adding entries, and
1795 removing entries. It verifies that the values method returns the expected
1796 TrieEntry objects in the correct order.
1797 It also checks that the values method behaves correctly when entries are
1798 added and removed, ensuring that the trie maintains its integrity."""
1799 trie: GeneralizedTrie = GeneralizedTrie()
1801 with self.subTest(msg="[TV001] trie.values()"):
1802 expect_entries_list: list[TrieEntry] = []
1803 found_entries_list: list[TrieEntry] = list(trie.values())
1804 self.assertEqual(found_entries_list, expect_entries_list)
1806 with self.subTest(msg="[TV002] trie.add('abcdef')"):
1807 expect_id: TrieId = TrieId(1)
1808 found_id: TrieId = trie.add("abcdef")
1809 self.assertEqual(found_id, expect_id)
1811 with self.subTest(msg="[TV003] trie.values()"):
1812 expect_entries_list = [TrieEntry(TrieId(1), 'abcdef')]
1813 found_entries_list = list(trie.values())
1814 self.assertEqual(found_entries_list, expect_entries_list)
1816 with self.subTest(msg="[TV004] trie.add('abc')"):
1817 expect_id = TrieId(2)
1818 found_id = trie.add("abc")
1819 self.assertEqual(found_id, expect_id)
1821 with self.subTest(msg="[TV005] trie.values()"):
1822 expect_entries_list = [TrieEntry(TrieId(1), 'abcdef'), TrieEntry(TrieId(2), 'abc')]
1823 found_entries_list = list(sorted(trie.values()))
1824 self.assertEqual(found_entries_list, expect_entries_list)
1826 with self.subTest(msg="[TV006] trie.remove(TrieId(1))"):
1827 trie.remove(TrieId(1))
1828 expect_entries_list = [TrieEntry(TrieId(2), 'abc')]
1829 found_entries_list = list(trie.values())
1830 self.assertEqual(found_entries_list, expect_entries_list)
1832 with self.subTest(msg="[TV007] trie.remove(TrieId(2))"):
1833 trie.remove(TrieId(2))
1834 expect_entries_list = []
1835 found_entries_list = list(trie.values())
1836 self.assertEqual(found_entries_list, expect_entries_list)
1838 def test_items(self) -> None:
1839 """Test the items method of GeneralizedTrie.
1841 This test checks the functionality of the items method, which should
1842 return an iterable of tuples containing TrieId and TrieEntry objects.
1843 The test includes scenarios for an empty trie, adding entries, and
1844 removing entries. It verifies that the items method returns the expected
1845 tuples in the correct order.
1846 It also checks that the items method behaves correctly when entries are
1847 added and removed, ensuring that the trie maintains its integrity."""
1848 trie: GeneralizedTrie = GeneralizedTrie()
1850 with self.subTest(msg="[TI001] trie.items()"):
1851 expect_items_list: list[tuple[TrieId, TrieEntry]] = []
1852 found_items_list: list[tuple[TrieId, TrieEntry]] = list(trie.items())
1853 self.assertEqual(found_items_list, expect_items_list)
1855 with self.subTest(msg="[TI002] trie.add('abcdef')"):
1856 expect_id: TrieId = TrieId(1)
1857 found_id: TrieId = trie.add("abcdef")
1858 self.assertEqual(found_id, expect_id)
1860 with self.subTest(msg="[TI003] trie.items()"):
1861 expect_items_list = [(TrieId(1), TrieEntry(TrieId(1), 'abcdef'))]
1862 found_items_list = list(sorted(trie.items()))
1863 self.assertEqual(found_items_list, expect_items_list)
1865 with self.subTest(msg="[TI004] trie.add('abc')"):
1866 expect_id = TrieId(2)
1867 found_id = trie.add("abc")
1868 self.assertEqual(found_id, expect_id)
1870 with self.subTest(msg="[TI005] trie.items()"):
1871 expect_items_list = [
1872 (TrieId(1), TrieEntry(TrieId(1), 'abcdef')),
1873 (TrieId(2), TrieEntry(TrieId(2), 'abc'))]
1874 found_items_list = list(sorted(trie.items()))
1875 self.assertEqual(found_items_list, expect_items_list)
1877 with self.subTest(msg="[TI006] trie.remove(TrieId(1))"):
1878 trie.remove(TrieId(1))
1879 expect_items_list = [(TrieId(2), TrieEntry(TrieId(2), 'abc'))]
1880 found_items_list = list(sorted(trie.items()))
1881 self.assertEqual(found_items_list, expect_items_list)
1883 with self.subTest(msg="[TI007] trie.remove(TrieId(2))"):
1884 trie.remove(TrieId(2))
1885 expect_items_list = []
1886 found_items_list = list(sorted(trie.items()))
1887 self.assertEqual(found_items_list, expect_items_list)
1889 @pytest.mark.order(after='test_remove')
1890 @pytest.mark.dependency(name="test_getitem_dunder", depends=[
1891 'test_create_trie', 'test_add',
1892 'test_remove', 'test_trieid_class'])
1893 def test_getitem_dunder(self) -> None:
1894 """Test the __getitem__ method of GeneralizedTrie.
1896 This test checks the functionality of the __getitem__ method, which should
1897 allow access to TrieEntry objects by their TrieId. The test includes scenarios
1898 for an empty trie, adding entries, and accessing entries by their IDs.
1899 It verifies that the __getitem__ method returns the expected TrieEntry objects
1900 and raises KeyError when trying to access non-existing IDs.
1901 It also checks that the method behaves correctly when entries are added and
1902 accessed, ensuring that the trie maintains its integrity."""
1903 trie: GeneralizedTrie = GeneralizedTrie()
1905 with self.assertRaises(KeyError, msg="[TGID001] trie[TrieId(1)]"):
1906 _ = trie[TrieId(1)]
1908 with self.subTest(msg="[TGID002] trie.add('abcdef')"):
1909 expect_id: TrieId = TrieId(1)
1910 found_id: TrieId = trie.add("abcdef")
1911 self.assertEqual(found_id, expect_id)
1913 with self.subTest(msg="[TGID003] trie[TrieId(1)]"):
1914 expect_entry: TrieEntry = TrieEntry(TrieId(1), 'abcdef')
1915 found_entry: TrieEntry = trie[TrieId(1)]
1916 self.assertEqual(found_entry, expect_entry)
1918 with self.subTest(msg="[TGID004] trie.add('abc')"):
1919 expect_id = TrieId(2)
1920 found_id = trie.add("abc")
1921 self.assertEqual(found_id, expect_id)
1923 with self.subTest(msg="[TGID005] trie[TrieId(2)]"):
1924 expect_entry = TrieEntry(TrieId(2), 'abc')
1925 found_entry = trie[TrieId(2)]
1926 self.assertEqual(found_entry, expect_entry)
1928 with self.assertRaises(KeyError, msg="[TGID006] trie[TrieId(3)]"):
1929 _ = trie[TrieId(3)]
1931 def test_iter(self) -> None:
1932 """Test the iteration over GeneralizedTrie."""
1933 trie: GeneralizedTrie = GeneralizedTrie()
1935 with self.subTest(msg="[TITER001] for entry in trie:"):
1936 expect_ids_list: list[TrieId] = []
1937 found_ids_list: list[TrieId] = []
1938 for entry in trie: 1938 ↛ 1939line 1938 didn't jump to line 1939 because the loop on line 1938 never started
1939 found_ids_list.append(entry)
1940 self.assertEqual(found_ids_list, expect_ids_list)
1942 with self.subTest(msg="[TITER002] trie.add('abcdef')"):
1943 expect_id: TrieId = TrieId(1)
1944 found_id: TrieId = trie.add("abcdef")
1945 self.assertEqual(found_id, expect_id)
1947 with self.subTest(msg="[TITER003] for ident in trie:"):
1948 expect_ids_list = [TrieId(1)]
1949 found_ids_list = []
1950 for ident in trie:
1951 found_ids_list.append(ident)
1952 self.assertEqual(sorted(found_ids_list), expect_ids_list)
1954 with self.subTest(msg="[TITER004] trie.add('abc')"):
1955 expect_id = TrieId(2)
1956 found_id = trie.add("abc")
1957 self.assertEqual(found_id, expect_id)
1959 with self.subTest(msg="[TITER005] for entry in trie:"):
1960 expect_ids_list: list[TrieId] = [TrieId(1), TrieId(2)]
1961 found_ids_list: list[TrieId] = []
1962 for entry in trie:
1963 found_ids_list.append(entry)
1964 self.assertEqual(sorted(found_ids_list), expect_ids_list)
1966 @pytest.mark.order(after='test_remove')
1967 @pytest.mark.dependency(name='test_bool', depends=[
1968 'test_create_trie', 'test_add',
1969 'test_remove'])
1970 def test_bool(self) -> None:
1971 """Test the __bool__ method of GeneralizedTrie.
1973 This test checks the functionality of the __bool__ method, which should
1974 return True if the trie contains any entries, and False if it is empty.
1975 The test includes scenarios for an empty trie, adding entries, and removing
1976 entries. It verifies that the __bool__ method returns the expected boolean
1977 values for each scenario, ensuring that the trie behaves correctly when
1978 checking its truthiness."""
1979 trie = GeneralizedTrie()
1980 tests: list[TestSpec] = [
1981 TestSpec(
1982 name="[TB001] bool(trie)", action=bool, args=[trie], expected=False
1983 ),
1984 TestSpec(
1985 name="[TB002] trie.add('a')", action=trie.add, args=["a"], expected=TrieId(1)
1986 ),
1987 TestSpec(
1988 name="[TB003] bool(trie)", action=bool, args=[trie], expected=True
1989 ),
1990 TestSpec(
1991 name="[TB004] trie.remove(TrieId(1))", action=trie.remove, args=[TrieId(1)], expected=None
1992 ),
1993 TestSpec(
1994 name="[TB005] bool(trie)", action=bool, args=[trie], expected=False
1995 ),
1996 ]
1997 run_tests_list(self, tests)
2000if __name__ == "__main__":
2001 unittest.main()