Coverage for tests/gentrie/test_gentri.py: 99%
454 statements
« prev ^ index » next coverage.py v7.6.10, created at 2025-08-20 07:41 -0700
1"""Tests for the gentrie module."""
2# pylint: disable=too-many-lines
3# pylint: disable=too-many-public-methods
4# pylint: disable=too-few-public-methods
5# pylint: disable=invalid-name
7import unittest
8from collections.abc import Iterable
9from textwrap import dedent
10from typing import Any
12import pytest
15from src.gentrie import (DuplicateKeyError, ErrorTag, GeneralizedTrie,
16 InvalidGeneralizedKeyError, TrieEntry, TrieId,
17 TrieKeyError, TrieKeyToken, TrieTypeError,
18 TrieValueError, is_generalizedkey, is_triekeytoken,
19 is_hashable)
21from ..testspec import TestSpec, run_tests_list
24class MockDefaultTrieKeyToken:
25 """A mock class that implements the TrieKeyToken interface.
27 This class is used to test the behavior of the GeneralizedTrie with user-defined classes
28 and ensures that it can handle instances of classes that do not implement content-aware
29 equality.
30 """
31 def __init__(self, a: tuple[int, int, int], b: str) -> None:
32 self.a = a
33 self.b = b
36class MockContentAwareTrieKeyToken:
37 """A mock class that implements the TrieKeyToken interface and uses content for equality."""
38 def __init__(self, a: tuple[int, int, int], b: str) -> None:
39 self.a = a
40 self.b = b
42 def __eq__(self, other: Any) -> bool:
43 return hash(self) == hash(other)
45 def __hash__(self) -> int:
46 return hash((self.a, self.b))
49class TestGeneralizedTrie(unittest.TestCase):
50 """Test the GeneralizedTrie class and its methods."""
52 @pytest.mark.order(1)
53 @pytest.mark.dependency(name='test_trieid_class')
54 def test_trieid_class(self) -> None:
55 """Test the creation of TrieId instances."""
56 tests: list[TestSpec] = [
57 TestSpec(
58 name="[TTI001] Creating TrieId(1) results in a TrieId instance",
59 action=lambda: isinstance(TrieId(1), TrieId), # type: ignore[reportUnknownMemberType]
60 expected=True,
61 ),
62 TestSpec(
63 name="[TTI002] int(1) is not a TrieId",
64 action=lambda: isinstance(int(1), TrieId),
65 expected=False,
66 ),
67 TestSpec(
68 name="[TTI003] TrieId(2) is not equal to TrieId(1)",
69 action=lambda: TrieId(2) == TrieId(1),
70 expected=False,
71 ),
72 TestSpec(
73 name="[TTI004] TrieId(1) is equal to itself",
74 action=lambda: TrieId(1) == TrieId(1),
75 expected=True,
76 ),
77 ]
79 run_tests_list(self, tests)
81 @pytest.mark.order(after='test_trieid_class')
82 @pytest.mark.dependency(
83 name='test_triekeytoken_supported_and_unsupported_builtin_types')
84 def test_triekeytoken_supported_and_unsupported_builtin_types(self) -> None:
85 """Tests that built in types are correctly classified as supported or unsupported."""
86 TEST_ID: int = 0
87 TEST_VALUE: int = 1
88 good_types: list[tuple[str, Any]] = [
89 ('TTKT_TSBT001', 'a'),
90 ('TTKT_TSBT002', str('ab')),
91 ('TTKT_TSBT003', frozenset('abc')),
92 ('TTKT_TSBT004', tuple(['a', 'b', 'c', 'd'])),
93 ('TTKT_TSBT005', int(1)),
94 ('TTKT_TSBT006', float(2.0)),
95 ('TTKT_TSBT007', complex(3.0, 4.0)),
96 ('TTKT_TSBT008', bytes(456)),
97 ]
99 tests: list[TestSpec] = [
100 TestSpec(
101 name=f"[{testcase[TEST_ID]}] isinstance({repr(testcase[TEST_VALUE])}, TrieKeyToken) (True)",
102 action=isinstance,
103 args=[testcase[TEST_VALUE], TrieKeyToken],
104 expected=True,
105 )
106 for testcase in good_types
107 ]
108 run_tests_list(self, tests)
110 bad_types: list[tuple[str, Any]] = [
111 ('TTKT_TUBT001', set('a')),
112 ('TTKT_TUBT002', list(['a', 'b'])),
113 ('TTKT_TUBT003', dict({'a': 1, 'b': 2, 'c': 3})),
114 ('TTKT_TUBT004', set('abc')),
115 ]
117 tests = [
118 TestSpec(
119 name=f"[{testcase[TEST_ID]}] isinstance({repr(testcase[TEST_VALUE])}, TrieKeyToken) (False)",
120 action=isinstance,
121 args=[testcase[TEST_VALUE], TrieKeyToken],
122 expected=False,
123 )
124 for testcase in bad_types
125 ]
126 run_tests_list(self, tests)
128 @pytest.mark.order(after=['test_triekeytoken_supported_and_unsupported_builtin_types'])
129 @pytest.mark.dependency(
130 name='test_is_triekeytoken',
131 depends=['test_triekeytoken_supported_and_unsupported_builtin_types']
132 )
133 def test_is_triekeytoken(self) -> None:
134 """Test the is_triekeytoken function with various inputs.
136 This test checks that the is_triekeytoken function correctly identifies
137 valid and invalid trie key tokens."""
138 TEST_ID: int = 0
139 TEST_VALUE: int = 1
140 good_tokens: list[tuple[str, Any]] = [
141 ('TGT_TITKT001', 'a'),
142 ('TGT_TITKT002', str('ab')),
143 ('TGT_TITKT003', frozenset('abc')),
144 ('TGT_TITKT004', tuple(['a', 'b', 'c', 'd'])),
145 ('TGT_TITKT005', int(1)),
146 ('TGT_TITKT006', float(2.0)),
147 ('TGT_TITKT007', complex(3.0, 4.0)),
148 ('TGT_TITKT008', bytes(456)),
149 ]
151 tests: list[TestSpec] = [
152 TestSpec(
153 name=f"[{testcase[TEST_ID]}] is_triekeytoken({repr(testcase[TEST_VALUE])}) (True)",
154 action=is_triekeytoken,
155 args=[testcase[TEST_VALUE]],
156 expected=True,
157 )
158 for testcase in good_tokens
159 ]
160 run_tests_list(self, tests)
162 bad_tokens: list[tuple[str, Any]] = [
163 ('TGT_TITKT001', set('a')),
164 ('TGT_TITKT002', list(['a', 'b'])),
165 ('TGT_TITKT003', dict({'a': 1, 'b': 2, 'c': 3})),
166 ('TGT_TITKT004', set('abc')),
167 ]
169 tests = [
170 TestSpec(
171 name=f"[{testcase[TEST_ID]}] is_triekeytoken({repr(testcase[TEST_VALUE])}) (False)",
172 action=is_triekeytoken,
173 args=[testcase[TEST_VALUE]],
174 expected=False,
175 )
176 for testcase in bad_tokens
177 ]
178 run_tests_list(self, tests)
180 @pytest.mark.order(after=['test_triekeytoken_supported_and_unsupported_builtin_types'])
181 @pytest.mark.dependency(
182 name='test_is_hashable',
183 depends=['test_triekeytoken_supported_and_unsupported_builtin_types']
184 )
185 def test_is_hashable(self) -> None:
186 """Test the deprecated is_hashable function with various inputs.
188 This test checks that the is_hashable function correctly identifies
189 valid and invalid trie key tokens."""
190 TEST_ID: int = 0
191 TEST_VALUE: int = 1
192 good_tokens: list[tuple[str, Any]] = [
193 ('TGT_TIH001', 'a'),
194 ('TGT_TIH002', str('ab')),
195 ('TGT_TIHT003', frozenset('abc')),
196 ('TGT_TIHT004', tuple(['a', 'b', 'c', 'd'])),
197 ('TGT_TIHT005', int(1)),
198 ('TGT_TIHT006', float(2.0)),
199 ('TGT_TIHT007', complex(3.0, 4.0)),
200 ('TGT_TIHT008', bytes(456)),
201 ]
203 tests: list[TestSpec] = [
204 TestSpec(
205 name=f"[{testcase[TEST_ID]}] is_hashable({repr(testcase[TEST_VALUE])}) (True)",
206 action=is_hashable,
207 args=[testcase[TEST_VALUE]],
208 expected=True,
209 )
210 for testcase in good_tokens
211 ]
212 run_tests_list(self, tests)
214 bad_tokens: list[tuple[str, Any]] = [
215 ('TGT_TIHT001', set('a')),
216 ('TGT_TIHT002', list(['a', 'b'])),
217 ('TGT_TIHT003', dict({'a': 1, 'b': 2, 'c': 3})),
218 ('TGT_TIHT004', set('abc')),
219 ]
221 tests = [
222 TestSpec(
223 name=f"[{testcase[TEST_ID]}] is_hashable({repr(testcase[TEST_VALUE])}) (False)",
224 action=is_hashable,
225 args=[testcase[TEST_VALUE]],
226 expected=False,
227 )
228 for testcase in bad_tokens
229 ]
230 run_tests_list(self, tests)
232 @pytest.mark.order(after=['test_triekeytoken_supported_and_unsupported_builtin_types'])
233 @pytest.mark.dependency(
234 name='test_generalizedkey_supported_and_unsupported_builtin_types',
235 depends=['test_triekeytoken_supported_and_unsupported_builtin_types'])
236 def test_generalizedkey_supported_and_unsupported_builtin_types(self) -> None:
237 """Tests supported and unsupported types for generalized keys.
239 This test checks that types like strings, lists, and tuples
240 of immutable types are recognized as valid generalized keys
241 while non-sequence or mutable types like dict, set, and complex
242 numbers are not considered valid generalized keys."""
243 TEST_ID: int = 0
244 TEST_VALUE: int = 1
245 good_keys: list[tuple[str, Any]] = [
246 ('TGK_SBT001', 'a'),
247 ('TGK_SBT002', str('ab')),
248 ('TGK_SBT003', ['a', 'b']),
249 ('TGK_SBT004', tuple(['a', 'b', 'c', 'd'])),
250 ('TGK_SBT005', [int(1)]),
251 ('TGK_SBT006', [float(2.0)]),
252 ('TGK_SBT007', [complex(3.0, 4.0)]),
253 ('TGK_SBT007', [b'abc']),
254 ('TGK_SBT008', b'abc')
255 ]
256 tests: list[TestSpec] = [
257 TestSpec(
258 name=f"[{testcase[TEST_ID]}] is_generalizedkey({repr(testcase[TEST_VALUE])}) (True)",
259 action=is_generalizedkey,
260 args=[testcase[TEST_VALUE]],
261 expected=True,
262 )
263 for testcase in good_keys
264 ]
265 run_tests_list(self, tests)
267 # Test cases for unsupported types
268 bad_keys: list[tuple[str, Any]] = [
269 ('TGK_TUBT001', ''), # empty string is invalid as a GeneralizedKey
270 ('TGK_TUBT002', dict({'a': 1, 'b': 2, 'c': 3})),
271 ('TGK_TUBT003', set('abc')),
272 ('TGK_TUBT004', frozenset('abc')),
273 ('TGK_TUBT005', complex(3.0, 4.0)),
274 ]
276 tests = [
277 TestSpec(
278 name=f"[{testcase[TEST_ID]}] is_generalizedkey({repr(testcase[TEST_VALUE])}) (False)",
279 action=is_generalizedkey,
280 args=[testcase[TEST_VALUE]],
281 expected=False,
282 )
283 for testcase in bad_keys
284 ]
285 run_tests_list(self, tests)
287 @pytest.mark.order(after=['test_generalizedkey_supported_and_unsupported_builtin_types'])
288 @pytest.mark.dependency(
289 name='test_is_generalizedkey',
290 depends=['test_generalizedkey_supported_and_unsupported_builtin_types'])
291 def test_is_generalizedkey(self) -> None:
292 """Test the is_generalizedkey function with various inputs.
294 This test checks that the is_generalizedkey function correctly identifies
295 valid and invalid generalized keys."""
296 tests: list[TestSpec] = [
297 TestSpec(
298 name="[TIGK001] is_generalizedkey('a') (True)",
299 action=is_generalizedkey,
300 args=['a'],
301 expected=True
302 ),
303 TestSpec(
304 name="[TIGK002] is_generalizedkey(['a', 'b']) (True)",
305 action=is_generalizedkey,
306 args=[['a', 'b']],
307 expected=True
308 ),
309 TestSpec(
310 name="[TIGK003] is_generalizedkey(b'abc') (True)",
311 action=is_generalizedkey,
312 args=[b'abc'],
313 expected=True
314 ),
315 TestSpec(
316 name="[TIGK004] is_generalizedkey('') (False)",
317 action=is_generalizedkey,
318 args=[''],
319 expected=False
320 ),
321 TestSpec(
322 name="[TIGK005] is_generalizedkey([]) (False)",
323 action=is_generalizedkey,
324 args=[[]],
325 expected=False
326 ),
327 TestSpec(
328 name="[TIGK006] is_generalizedkey(123) (False)",
329 action=is_generalizedkey,
330 args=[123],
331 expected=False
332 ),
333 TestSpec(
334 name="[TIGK007] is_generalizedkey(None) (False)",
335 action=is_generalizedkey,
336 args=[None],
337 expected=False
338 ),
339 TestSpec(
340 name="[TIGK008] is_generalizedkey({'a': 1}) (False)",
341 action=is_generalizedkey,
342 args=[{'a': 1}],
343 expected=False
344 ),
345 TestSpec(
346 name="[TIGK009] is_generalizedkey(['a', {'b': 1}]) (False)",
347 action=is_generalizedkey,
348 args=[['a', {'b': 1}]],
349 expected=False
350 ),
351 TestSpec(
352 name="[TIGK010] is_generalizedkey(['a', ['b', ['c']]]) (False)",
353 action=is_generalizedkey,
354 args=[['a', ['b', ['c']]]],
355 expected=False
356 ),
357 ]
358 run_tests_list(self, tests)
360 @pytest.mark.order(order=6)
361 @pytest.mark.dependency(name='test_create_trie')
362 def test_create_trie(self) -> None:
363 """Test the creation of a GeneralizedTrie instance.
365 This test checks that the GeneralizedTrie can be instantiated without any arguments
366 and that it raises a TypeError when an invalid filter_id is provided."""
367 tests: list[TestSpec] = [
368 TestSpec(
369 name="[TCT001] create GeneralizedTrie()",
370 action=GeneralizedTrie,
371 validate_result=lambda found: isinstance(found, # type: ignore[reportUnknownMemberType]
372 GeneralizedTrie),
373 ),
374 TestSpec(
375 name="[TCT002] create GeneralizedTrie(filter_id=1)",
376 action=GeneralizedTrie,
377 kwargs={"filter_id": 1},
378 exception=TypeError,
379 ),
380 ]
381 run_tests_list(self, tests)
383 @pytest.mark.order(after=['test_trieid_class'])
384 @pytest.mark.dependency(name='test_trieid', depends=['test_trieid_class'])
385 def test_trieentry(self) -> None:
386 """Test the TrieEntry class.
387 """
388 id_1: TrieId = TrieId(1)
389 id_2: TrieId = TrieId(2)
391 tests: list[TestSpec] = [
392 TestSpec(
393 name='[TGT_TTE001] Test TrieEntry initialization',
394 action=TrieEntry,
395 kwargs={'ident': id_1, 'key': 'test', 'value': 1},
396 validate_result=lambda found: ( # pyright: ignore[reportUnknownLambdaType]
397 isinstance(found, TrieEntry) and found.ident == id_1 and found.key == 'test' and found.value == 1),
398 ),
399 TestSpec(
400 name='[TGT_TTE002] Test TrieEntry equality vs non-TrieEntry (False)',
401 action=TrieEntry,
402 kwargs={'ident': id_1, 'key': 'test', 'value': 1},
403 validate_result=lambda found: not (found == 1) # pyright: ignore[reportUnknownLambdaType]
404 ),
405 TestSpec(
406 name='[TGT_TTE003] Test non-TrieEntry equality vs TrieEntry (False)',
407 action=TrieEntry,
408 kwargs={'ident': id_1, 'key': 'test', 'value': 1},
409 validate_result=lambda found: not (1 == found) # pyright: ignore[reportUnknownLambdaType]
410 ),
411 TestSpec(
412 name='[TGT_TTE004] trie_entry.__eq__(<other>) (False)',
413 action=TrieEntry,
414 kwargs={'ident': id_1, 'key': 'test', 'value': 1},
415 validate_result=lambda found: not found.__eq__(1) # noqa: E501 # pyright: ignore[reportUnknownLambdaType, reportUnknownMemberType]
416 ),
417 TestSpec(
418 name='[TGT_TTE005] Test TrieEntry equality',
419 action=lambda: TrieEntry(id_1, "test", 1) == TrieEntry(id_1, "test", 1),
420 expected=True,
421 ),
422 TestSpec(
423 name='[TGT_TTE006] Test TrieEntry inequality (ident)',
424 action=lambda: TrieEntry(id_1, "test", 1) == TrieEntry(id_2, "test", 1),
425 expected=False,
426 ),
427 TestSpec(
428 name='[TGT_TTE007] Test TrieEntry inequality (key)',
429 action=lambda: TrieEntry(id_1, "test", 1) == TrieEntry(id_1, "other", 1),
430 expected=False,
431 ),
432 TestSpec(
433 name='[TGT_TTE008] Test TrieEntry inequality (value)',
434 action=lambda: TrieEntry(id_1, "test", 1) == TrieEntry(id_1, "test", 2),
435 expected=False,
436 ),
437 ]
438 run_tests_list(self, tests)
440 @pytest.mark.order(after=['test_contains_dunder', 'test_bool'])
441 @pytest.mark.dependency(
442 name='test_clear',
443 depends=['test_create_trie', 'test_add', 'test_contains_dunder', 'test_bool', 'test_keys'])
444 def test_clear(self) -> None:
445 """Test the clear method of GeneralizedTrie."""
446 trie = GeneralizedTrie()
447 trie.add("a")
448 trie.add("b")
449 self.assertEqual(len(trie), 2, "[TCL001] Trie should have 2 entries after adding 'a' and 'b'")
450 self.assertTrue("a" in trie, "[TCL002] Trie should contain 'a' after addition")
452 trie.clear()
454 self.assertEqual(len(trie), 0, "[TCL003] Trie should be empty after clear()")
455 self.assertFalse(bool(trie), "[TCL004] Trie should evaluate to False after clear()")
456 self.assertFalse("a" in trie, "[TCL005] Trie should not contain 'a' after clear()")
457 # pylint: disable=protected-access
458 self.assertEqual(trie._ident_counter, 0, # type: ignore[reportUnknownMemberType]
459 "[TCL006] Trie ident counter should be reset after clear()")
460 self.assertEqual(list(trie.keys()), [], "[TCL007] Trie keys should be empty after clear()]")
462 @pytest.mark.order(after="test_create_trie")
463 @pytest.mark.dependency(
464 name='test_add',
465 depends=['test_create_trie', 'test_trieid_class'])
466 def test_add(self) -> None:
467 """Test the add method of GeneralizedTrie.
469 This test covers adding various types of keys to the trie using the add() method, including strings,
470 lists, and frozensets, and checks the expected behavior of the trie after each addition.
471 It also includes tests for error handling when invalid keys are added."""
472 # pylint: disable=protected-access, no-member
473 trie = GeneralizedTrie()
474 tests: list[TestSpec] = [
475 # Initialize from a list of strings and validate we get the expected id
476 TestSpec(
477 name="[TA001] trie.add(['tree', 'value', 'ape'])",
478 action=trie.add,
479 args=[["tree", "value", "ape"]],
480 kwargs={},
481 expected=TrieId(1),
482 ),
483 # Validate the dictionary representation of the trie is correct after initialization
484 TestSpec(
485 name="[TA002] _as_dict()",
486 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
487 expected={
488 'ident': None,
489 'children': {
490 'tree': {
491 'ident': None,
492 'token': 'tree',
493 'value': None,
494 'parent': None,
495 'children': {
496 'value': {
497 'ident': None,
498 'token': 'value',
499 'value': None,
500 'parent': 'tree',
501 'children': {
502 'ape': {
503 'ident': TrieId(1),
504 'token': 'ape',
505 'value': None,
506 'parent': 'value',
507 'children': {}
508 }
509 }
510 }
511 }
512 }
513 },
514 'trie_index': [TrieId(1)],
515 'trie_entries': {TrieId(1): "TrieEntry(ident=TrieId(1), key=('tree', 'value', 'ape'), value=None)"}
516 }
517 ),
519 # Add another entry ['tree', 'value'] and validate we get the expected id for it
520 TestSpec(
521 name="[TA003] trie.add(['tree', 'value']",
522 action=trie.add,
523 args=[["tree", "value"]],
524 expected=TrieId(2),
525 ),
526 # Validate the _as_dict representation of the trie is correct
527 TestSpec(
528 name="[TA004] _as_dict()",
529 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
530 expected={
531 'ident': None,
532 'children': {
533 'tree': {
534 'ident': None,
535 'token': 'tree',
536 'value': None,
537 'parent': None,
538 'children': {
539 'value': {
540 'ident': TrieId(2),
541 'token': 'value',
542 'value': None,
543 'parent': 'tree',
544 'children': {
545 'ape': {
546 'ident': TrieId(1),
547 'token': 'ape',
548 'value': None,
549 'parent': 'value',
550 'children': {}
551 }
552 }
553 }
554 }
555 }
556 },
557 'trie_index': [TrieId(1), TrieId(2)],
558 'trie_entries': {
559 TrieId(1): "TrieEntry(ident=TrieId(1), key=('tree', 'value', 'ape'), value=None)",
560 TrieId(2): "TrieEntry(ident=TrieId(2), key=('tree', 'value'), value=None)"
561 }
562 }
563 ),
564 # Add a string entry 'abcdef' and validate we get the expected id for it
565 TestSpec(
566 name="[TA005] trie.add('abcdef')",
567 action=trie.add,
568 args=["abcdef"],
569 expected=TrieId(3),
570 ),
571 # Add another entry [1, 3, 4, 5] and validate we get the expected id for it
572 TestSpec(
573 name="[TA006] trie.add([1, 3, 4, 5])",
574 action=trie.add,
575 args=[[1, 3, 4, 5]],
576 kwargs={},
577 expected=TrieId(4),
578 ),
579 # Add a frozenset entry and validate we get the expected id for it
580 TestSpec(
581 name="[TA007] trie.add(frozenset([1]), 3, 4, 5])",
582 action=trie.add,
583 args=[[frozenset([1]), 3, 4, 5]],
584 kwargs={},
585 expected=TrieId(5),
586 ),
587 # Add another frozenset entry and validate we get a different id for it
588 # than for the previously added frozenset
589 TestSpec(
590 name="[TA008] trie.add(frozenset([1]), 3, 4, 5])",
591 action=trie.add,
592 args=[[frozenset([1]), 3, 4, 6]],
593 expected=TrieId(6),
594 ),
595 # Attempt to add an integer as a key and validate we get the expected exception
596 TestSpec(
597 name="[TA009] trie.add(1)",
598 action=trie.add,
599 args=[1],
600 exception=InvalidGeneralizedKeyError,
601 exception_tag=ErrorTag.STORE_ENTRY_INVALID_GENERALIZED_KEY,
602 ),
603 # Attempt to add an empty list as a key and validate we get the expected exception
604 TestSpec(
605 name="[TA010] trie.add([])",
606 action=trie.add,
607 args=[[]],
608 exception=InvalidGeneralizedKeyError,
609 exception_tag=ErrorTag.STORE_ENTRY_INVALID_GENERALIZED_KEY,
610 ),
611 # Attempt to add a set as a key element and validate we get the expected exception
612 TestSpec(
613 name="[TA011] trie.add([set([1]), 3, 4, 5])",
614 action=trie.add,
615 args=[[set([1]), 3, 4, 5]],
616 exception=InvalidGeneralizedKeyError,
617 exception_tag=ErrorTag.STORE_ENTRY_INVALID_GENERALIZED_KEY,
618 ),
619 # Add a key that is a list of integers and validate we get the expected id for it
620 TestSpec(
621 name="[TA012] trie.add(key=[1, 3, 4, 7])",
622 action=trie.add,
623 kwargs={"key": [1, 3, 4, 7]},
624 expected=TrieId(7),
625 ),
626 # Attempt to pass add the wrong number of arguments and validate we get the expected exception
627 TestSpec(name="[TA013] trie.add()",
628 action=trie.add,
629 exception=TypeError),
630 TestSpec(
631 name="[TA014] trie.add(['a'], ['b'], ['c'])",
632 action=trie.add,
633 args=[["a"], ["b"], ["c"]],
634 exception=TypeError,
635 ),
636 # Validate the length of the trie after all additions
637 TestSpec(name="[TA015] len(trie)", action=len, args=[trie], expected=7),
638 # Add duplicate entry ['tree', 'value', 'ape'] and validate we get a DuplicateKeyError
639 TestSpec(
640 name="[TA016] trie.add(['tree', 'value', 'ape'])",
641 action=trie.add,
642 args=[["tree", "value", "ape"]],
643 kwargs={},
644 exception=DuplicateKeyError,
645 exception_tag=ErrorTag.STORE_ENTRY_DUPLICATE_KEY,
646 ),
647 # Validate the length of the trie trying to add duplicate ['tree', 'value', 'ape'] is unchanged
648 TestSpec(name="[TA017] len(trie)", action=len, args=[trie], expected=7),
649 # Add a trie entry with a value and validate we get the expected id for it
650 TestSpec(
651 name="[TA018] trie.add(['tree', 'value', 'cheetah'], 'feline')",
652 action=trie.add,
653 args=[["tree", "value", "cheetah"], "feline"],
654 expected=TrieId(8),
655 ),
657 ]
658 run_tests_list(self, tests)
660 # New untouched trie for the next sequence of tests
661 # Not using clear() here to keep the clear() tests cleanly separated
662 # from the add() tests.
663 trie = GeneralizedTrie()
665 # Test cases for setting values on trie entries
666 tests = [
667 # Initialize the trie with a key with a value and validate we get the expected id
668 TestSpec(
669 name="[TA019] trie.add(['tree', 'value', 'cheetah'], 'feline')",
670 action=trie.add,
671 args=[["tree", "value", "cheetah"], "feline"],
672 expected=TrieId(1),
673 ),
674 # validate that entry 1 (with the key ['tree', 'value', 'cheetah']) has the value of 'feline'
675 TestSpec(
676 name="[TA020] trie[1].value == 'feline' (_as_dict() check)",
677 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
678 expected={
679 'ident': None,
680 'children': {
681 'tree': {
682 'ident': None,
683 'token': 'tree',
684 'value': None,
685 'parent': None,
686 'children': {
687 'value': {
688 'ident': None,
689 'token': 'value',
690 'value': None,
691 'parent': 'tree',
692 'children': {
693 'cheetah': {
694 'ident': TrieId(1),
695 'token': 'cheetah',
696 'value': 'feline',
697 'parent': 'value',
698 'children': {}
699 }
700 }
701 }
702 }
703 }
704 },
705 'trie_index': [TrieId(1)],
706 'trie_entries': {
707 TrieId(1): "TrieEntry(ident=TrieId(1), key=('tree', 'value', 'cheetah'), value='feline')"
708 }
709 },
710 ),
711 # Add the same key with the same value and validate we get the same id as before
712 # (this is to test that the trie does not create a new entry for the same key with the same value
713 # and that it does not throw an error)
714 TestSpec(
715 name="[TA021] trie.add(['tree', 'value', 'cheetah'], 'feline')",
716 action=trie.add,
717 args=[["tree", "value", "cheetah"], "feline"],
718 exception=DuplicateKeyError,
719 exception_tag=ErrorTag.STORE_ENTRY_DUPLICATE_KEY,
720 # This is expected to raise a DuplicateKeyError, but we are testing that the trie
721 # does not change its state after adding the same key with the same value.
722 # So we do not expect the trie to change, and we will validate that in the
723 # next test case.
724 ),
725 # validate that the trie is unchanged after exception for trying to add the same key with the same value
726 TestSpec(
727 name="[TA022] trie[1].value == 'feline' (_as_dict() check)",
728 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
729 expected={
730 'ident': None,
731 'children': {
732 'tree': {
733 'ident': None,
734 'token': 'tree',
735 'value': None,
736 'parent': None,
737 'children': {
738 'value': {
739 'ident': None,
740 'token': 'value',
741 'value': None,
742 'parent': 'tree',
743 'children': {
744 'cheetah': {
745 'ident': TrieId(1),
746 'token': 'cheetah',
747 'value': 'feline',
748 'parent': 'value',
749 'children': {}
750 }
751 }
752 }
753 }
754 }
755 },
756 'trie_index': [TrieId(1)],
757 'trie_entries': {
758 TrieId(1): "TrieEntry(ident=TrieId(1), key=('tree', 'value', 'cheetah'), value='feline')"
759 }
760 },
761 ),
762 # Add the same key with a DIFFERENT value (default of None) and validate we get a DuplicateKeyError
763 TestSpec(
764 name="[TA023] trie.add(['tree', 'value', 'cheetah'])",
765 action=trie.add,
766 args=[["tree", "value", "cheetah"]],
767 exception=DuplicateKeyError,
768 exception_tag=ErrorTag.STORE_ENTRY_DUPLICATE_KEY,
769 ),
770 # Validate that the trie is unchanged after attempting to add the same key with a different value of None
771 # (this is to test that the trie has not changed the trie despite throwing an error)
772 # Validate that the trie is unchanged after attempting to add the same key with a different value of None
773 # (this is to test that the trie has not changed the trie despite throwing an error)
774 TestSpec(
775 name="[TA024] trie[1].value == 'feline' (_as_dict() check, no change after DuplicateKeyError)",
776 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
777 expected={
778 'ident': None,
779 'children': {
780 'tree': {
781 'ident': None,
782 'token': 'tree',
783 'value': None,
784 'parent': None,
785 'children': {
786 'value': {
787 'ident': None,
788 'token': 'value',
789 'value': None,
790 'parent': 'tree',
791 'children': {
792 'cheetah': {
793 'ident': TrieId(1),
794 'token': 'cheetah',
795 'value': 'feline',
796 'parent': 'value',
797 'children': {}
798 }
799 }
800 }
801 }
802 }
803 },
804 'trie_index': [TrieId(1)],
805 'trie_entries': {
806 TrieId(1): "TrieEntry(ident=TrieId(1), key=('tree', 'value', 'cheetah'), value='feline')"
807 }
808 },
809 ),
810 # Add the same key with a DIFFERENT value (explictly specified) and validate we get a DuplicateKeyError
811 TestSpec(
812 name="[TA025] trie.add(['tree', 'value', 'cheetah'], 'canide)",
813 action=trie.add,
814 args=[["tree", "value", "cheetah"], "canide"],
815 exception=DuplicateKeyError,
816 exception_tag=ErrorTag.STORE_ENTRY_DUPLICATE_KEY,
817 ),
818 ]
819 run_tests_list(self, tests)
821 @pytest.mark.order(after=['test_create_trie', 'test_trieid_class'])
822 @pytest.mark.dependency(
823 name='test_update',
824 depends=['test_create_trie', 'test_trieid_class'])
825 def test_update(self) -> None:
826 """Test the update method of GeneralizedTrie.
828 This test covers adding various types of keys to the trie via the update() method, including strings,
829 lists, and frozensets, and checks the expected behavior of the trie after each addition.
830 It also includes tests for error handling when invalid keys are added."""
831 # pylint: disable=protected-access, no-member
832 trie = GeneralizedTrie()
833 tests: list[TestSpec] = [
834 # Initialize from a list of strings and validate we get the expected id
835 TestSpec(
836 name="[TU001] trie.update(['tree', 'value', 'ape'])",
837 action=trie.update,
838 args=[["tree", "value", "ape"]],
839 kwargs={},
840 expected=TrieId(1),
841 ),
842 # Validate the dictionary representation of the trie is correct after initialization
843 TestSpec(
844 name="[TU002] _as_dict()",
845 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
846 expected={
847 'ident': None,
848 'children': {
849 'tree': {
850 'ident': None,
851 'token': 'tree',
852 'value': None,
853 'parent': None,
854 'children': {
855 'value': {
856 'ident': None,
857 'token': 'value',
858 'value': None,
859 'parent': 'tree',
860 'children': {
861 'ape': {
862 'ident': TrieId(1),
863 'token': 'ape',
864 'value': None,
865 'parent': 'value',
866 'children': {}
867 }
868 }
869 }
870 }
871 }
872 },
873 'trie_index': [TrieId(1)],
874 'trie_entries': {TrieId(1): "TrieEntry(ident=TrieId(1), key=('tree', 'value', 'ape'), value=None)"}
875 }
876 ),
878 # Add another entry ['tree', 'value'] and validate we get the expected id for it
879 TestSpec(
880 name="[TU003] trie.update(['tree', 'value']",
881 action=trie.update,
882 args=[["tree", "value"]],
883 expected=TrieId(2),
884 ),
885 # Validate the _as_dict representation of the trie is correct
886 TestSpec(
887 name="[TU004] _as_dict()",
888 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
889 expected={
890 'ident': None,
891 'children': {
892 'tree': {
893 'ident': None,
894 'token': 'tree',
895 'value': None,
896 'parent': None,
897 'children': {
898 'value': {
899 'ident': TrieId(2),
900 'token': 'value',
901 'value': None,
902 'parent': 'tree',
903 'children': {
904 'ape': {
905 'ident': TrieId(1),
906 'token': 'ape',
907 'value': None,
908 'parent': 'value',
909 'children': {}
910 }
911 }
912 }
913 }
914 }
915 },
916 'trie_index': [TrieId(1), TrieId(2)],
917 'trie_entries': {
918 TrieId(1): "TrieEntry(ident=TrieId(1), key=('tree', 'value', 'ape'), value=None)",
919 TrieId(2): "TrieEntry(ident=TrieId(2), key=('tree', 'value'), value=None)"
920 }
921 }
922 ),
923 # Add a string entry 'abcdef' and validate we get the expected id for it
924 TestSpec(
925 name="[TU005] trie.update('abcdef')",
926 action=trie.update,
927 args=["abcdef"],
928 expected=TrieId(3),
929 ),
930 # Add another entry [1, 3, 4, 5] and validate we get the expected id for it
931 TestSpec(
932 name="[TU006] trie.update([1, 3, 4, 5])",
933 action=trie.update,
934 args=[[1, 3, 4, 5]],
935 kwargs={},
936 expected=TrieId(4),
937 ),
938 # Add a frozenset entry and validate we get the expected id for it
939 TestSpec(
940 name="[TU007] trie.update(frozenset([1]), 3, 4, 5])",
941 action=trie.update,
942 args=[[frozenset([1]), 3, 4, 5]],
943 kwargs={},
944 expected=TrieId(5),
945 ),
946 # Add another frozenset entry and validate we get a different id for it
947 # than for the previously added frozenset
948 TestSpec(
949 name="[TU008] trie.update(frozenset([1]), 3, 4, 5])",
950 action=trie.update,
951 args=[[frozenset([1]), 3, 4, 6]],
952 expected=TrieId(6),
953 ),
954 # Attempt to add an integer as a key and validate we get the expected exception
955 TestSpec(
956 name="[TU009] trie.update(1)",
957 action=trie.update,
958 args=[1],
959 exception=InvalidGeneralizedKeyError,
960 exception_tag=ErrorTag.STORE_ENTRY_INVALID_GENERALIZED_KEY,
961 ),
962 # Attempt to add an empty list as a key and validate we get the expected exception
963 TestSpec(
964 name="[TU010] trie.update([])",
965 action=trie.update,
966 args=[[]],
967 exception=InvalidGeneralizedKeyError,
968 exception_tag=ErrorTag.STORE_ENTRY_INVALID_GENERALIZED_KEY,
969 ),
970 # Attempt to add a set as a key element and validate we get the expected exception
971 TestSpec(
972 name="[TU011] trie.update([set([1]), 3, 4, 5])",
973 action=trie.update,
974 args=[[set([1]), 3, 4, 5]],
975 exception=InvalidGeneralizedKeyError,
976 exception_tag=ErrorTag.STORE_ENTRY_INVALID_GENERALIZED_KEY,
977 ),
978 # Add a key that is a list of integers and validate we get the expected id for it
979 TestSpec(
980 name="[TU012] trie.update(key=[1, 3, 4, 7])",
981 action=trie.update,
982 kwargs={"key": [1, 3, 4, 7]},
983 expected=TrieId(7),
984 ),
985 # Attempt to pass add the wrong number of arguments and validate we get the expected exception
986 TestSpec(name="[TU013] trie.update()", action=trie.update, exception=TypeError),
987 TestSpec(
988 name="[TU014] trie.update(['a'], ['b'], ['c'])",
989 action=trie.update,
990 args=[["a"], ["b"], ["c"]],
991 exception=TypeError,
992 ),
993 # Validate the length of the trie after all additions
994 TestSpec(name="[TU015] len(trie)", action=len, args=[trie], expected=7),
995 # Add duplicate entry ['tree', 'value', 'ape'] and validate we get the original id for it
996 TestSpec(
997 name="[TU016] trie.update(['tree', 'value', 'ape'])",
998 action=trie.update,
999 args=[["tree", "value", "ape"]],
1000 kwargs={},
1001 expected=TrieId(1),
1002 ),
1003 # Validate the length of the trie after adding duplicate ['tree', 'value', 'ape'] is unchanged
1004 TestSpec(name="[TU017] len(trie)", action=len, args=[trie], expected=7),
1005 # Add a trie entry with a value and validate we get the expected id for it
1006 TestSpec(
1007 name="[TU018] trie.update(['tree', 'value', 'cheetah'], 'feline')",
1008 action=trie.update,
1009 args=[["tree", "value", "cheetah"], "feline"],
1010 expected=TrieId(8),
1011 ),
1013 ]
1014 run_tests_list(self, tests)
1016 # New untouched trie for the next sequence of tests
1017 # Not using clear() here to keep the clear() tests cleanly separated
1018 # from the update() tests.
1019 trie = GeneralizedTrie()
1021 # Test cases for setting values on trie entries
1022 tests = [
1023 # Initialize the trie with a key with a value and validate we get the expected id
1024 TestSpec(
1025 name="[TU019] trie.update(['tree', 'value', 'cheetah'], 'feline')",
1026 action=trie.update,
1027 args=[["tree", "value", "cheetah"], "feline"],
1028 expected=TrieId(1),
1029 ),
1030 # validate that entry 1 (with the key ['tree', 'value', 'cheetah']) has the value of 'feline'
1031 TestSpec(
1032 name="[TU020] trie[1].value == 'feline' (_as_dict() check)",
1033 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
1034 expected={
1035 'ident': None,
1036 'children': {
1037 'tree': {
1038 'ident': None,
1039 'token': 'tree',
1040 'value': None,
1041 'parent': None,
1042 'children': {
1043 'value': {
1044 'ident': None,
1045 'token': 'value',
1046 'value': None,
1047 'parent': 'tree',
1048 'children': {
1049 'cheetah': {
1050 'ident': TrieId(1),
1051 'token': 'cheetah',
1052 'value': 'feline',
1053 'parent': 'value',
1054 'children': {}
1055 }
1056 }
1057 }
1058 }
1059 }
1060 },
1061 'trie_index': [TrieId(1)],
1062 'trie_entries': {
1063 TrieId(1): "TrieEntry(ident=TrieId(1), key=('tree', 'value', 'cheetah'), value='feline')"
1064 }
1065 },
1066 ),
1067 # Add the same key with the same value and validate we get the same id as before
1068 # (this is to test that the trie does not create a new entry for the same key with the same value
1069 # and that it does not throw an error)
1070 TestSpec(
1071 name="[TU021] trie.update(['tree', 'value', 'cheetah'], 'feline')",
1072 action=trie.update,
1073 args=[["tree", "value", "cheetah"], "feline"],
1074 expected=TrieId(1),
1075 ),
1076 # validate that the trie is unchanged after adding the same key with the same value
1077 TestSpec(
1078 name="[TU022] trie[1].value == 'feline' (_as_dict() check)",
1079 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
1080 expected={
1081 'ident': None,
1082 'children': {
1083 'tree': {
1084 'ident': None,
1085 'token': 'tree',
1086 'value': None,
1087 'parent': None,
1088 'children': {
1089 'value': {
1090 'ident': None,
1091 'token': 'value',
1092 'value': None,
1093 'parent': 'tree',
1094 'children': {
1095 'cheetah': {
1096 'ident': TrieId(1),
1097 'token': 'cheetah',
1098 'value': 'feline',
1099 'parent': 'value',
1100 'children': {}
1101 }
1102 }
1103 }
1104 }
1105 }
1106 },
1107 'trie_index': [TrieId(1)],
1108 'trie_entries': {
1109 TrieId(1): "TrieEntry(ident=TrieId(1), key=('tree', 'value', 'cheetah'), value='feline')"
1110 }
1111 },
1112 ),
1113 # Add the same key with a DIFFERENT value (default of None) and validate we get the expected id
1114 # (this is to test that the trie updates the value of the existing entry)
1115 TestSpec(
1116 name="[TU023] trie.update(['tree', 'value', 'cheetah'])",
1117 action=trie.update,
1118 args=[["tree", "value", "cheetah"]],
1119 expected=TrieId(1),
1120 ),
1121 # Validate that the trie was correctly updated after adding the same key with a different value of None
1122 TestSpec(
1123 name="[TU024] trie[1].value == None (_as_dict() check)",
1124 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
1125 expected={
1126 'ident': None,
1127 'children': {
1128 'tree': {
1129 'ident': None,
1130 'token': 'tree',
1131 'value': None,
1132 'parent': None,
1133 'children': {
1134 'value': {
1135 'ident': None,
1136 'token': 'value',
1137 'value': None,
1138 'parent': 'tree',
1139 'children': {
1140 'cheetah': {
1141 'ident': TrieId(1),
1142 'token': 'cheetah',
1143 'value': None,
1144 'parent': 'value',
1145 'children': {}
1146 }
1147 }
1148 }
1149 }
1150 }
1151 },
1152 'trie_index': [TrieId(1)],
1153 'trie_entries': {
1154 TrieId(1): "TrieEntry(ident=TrieId(1), key=('tree', 'value', 'cheetah'), value=None)"
1155 }
1156 },
1157 ),
1158 # Add the same key with a DIFFERENT value (explictly specified) and validate we get the same id as before
1159 TestSpec(
1160 name="[TU025] trie.update(['tree', 'value', 'cheetah'], 'canide)",
1161 action=trie.update,
1162 args=[["tree", "value", "cheetah"], "canide"],
1163 expected=TrieId(1),
1164 ),
1165 # Validate that the trie was correctly updated after adding the same key with a different value of 'canide'
1166 TestSpec(
1167 name="[TU026] trie[1].value == 'canide' (_as_dict() check)",
1168 action=trie._as_dict, # type: ignore[reportUnknownMemberType]
1169 expected={
1170 'ident': None,
1171 'children': {
1172 'tree': {
1173 'ident': None,
1174 'token': 'tree',
1175 'value': None,
1176 'parent': None,
1177 'children': {
1178 'value': {
1179 'ident': None,
1180 'token': 'value',
1181 'value': None,
1182 'parent': 'tree',
1183 'children': {
1184 'cheetah': {
1185 'ident': TrieId(1),
1186 'token': 'cheetah',
1187 'value': 'canide',
1188 'parent': 'value',
1189 'children': {}
1190 }
1191 }
1192 }
1193 }
1194 }
1195 },
1196 'trie_index': [TrieId(1)],
1197 'trie_entries': {
1198 TrieId(1): "TrieEntry(ident=TrieId(1), key=('tree', 'value', 'cheetah'), value='canide')"
1199 }
1200 },
1201 ),
1202 ]
1203 run_tests_list(self, tests)
1205 @pytest.mark.order(after=['test_create_trie', 'test_add'])
1206 @pytest.mark.dependency(
1207 name='test_add_user_defined_classes',
1208 depends=['test_create_trie', 'test_add'])
1209 def test_add_user_defined_classes(self) -> None:
1210 """Test adding user-defined classes to GeneralizedTrie.
1212 This test checks that the trie can handle user-defined classes that implement
1213 the TrieKeyToken interface and that it can distinguish between different instances
1214 of these classes based on their content."""
1215 trie = GeneralizedTrie()
1216 a: list[str | MockDefaultTrieKeyToken] = ['red', MockDefaultTrieKeyToken(a=(1, 2, 3), b='hello')]
1217 b: list[str | MockDefaultTrieKeyToken] = ['red', MockDefaultTrieKeyToken(a=(1, 2, 3), b='hello')]
1218 c: list[str | MockContentAwareTrieKeyToken] = ['red', MockContentAwareTrieKeyToken(a=(1, 2, 3), b='hello')]
1219 d: list[str | MockContentAwareTrieKeyToken] = ['red', MockContentAwareTrieKeyToken(a=(1, 2, 3), b='hello')]
1221 with self.subTest(msg='[TAUDC001] a <=> b'):
1222 self.assertNotEqual(a, b)
1223 with self.subTest(msg='[TAUDC002] a <=> a'):
1224 self.assertEqual(a, a)
1225 with self.subTest(msg='[TAUDC003] c <=> d'):
1226 self.assertEqual(c, d)
1227 with self.subTest(msg='[TAUDC004] c <=> c'):
1228 self.assertEqual(c, c, msg='c <=> c')
1230 tests: list[TestSpec] = [
1231 TestSpec(
1232 name="[TAUDC005] trie.add(['red', MockDefaultTrieKeyToken(a=(1, 2, 3), b='hello')])",
1233 action=trie.add,
1234 args=[a],
1235 expected=TrieId(1),
1236 ),
1237 TestSpec(
1238 name="[TAUDC006] trie.add(['red', MockDefaultTrieKeyToken(a=[1, 2, 3], b='hello')])",
1239 action=trie.add,
1240 args=[b],
1241 expected=TrieId(2),
1242 ),
1243 TestSpec(
1244 name="[TAUDC007] trie.add(['red', MockContentAwareTrieKeyToken(a=(1, 2, 3), b='hello')])",
1245 action=trie.add,
1246 args=[c],
1247 expected=TrieId(3),
1248 ),
1249 TestSpec(
1250 name="[TAUDC008] trie.add(['red', MockContentAwareTrieKeyToken(a=(1, 2, 3), b='hello')])",
1251 action=trie.add,
1252 args=[d],
1253 exception=DuplicateKeyError,
1254 exception_tag=ErrorTag.STORE_ENTRY_DUPLICATE_KEY,
1255 ),
1256 ]
1257 run_tests_list(self, tests)
1259 @pytest.mark.order(after=['test_create_trie', 'test_add', 'test_trieid_class'])
1260 @pytest.mark.dependency(
1261 name='test_prefixes',
1262 depends=['test_create_trie', 'test_add', 'test_trieid_class'])
1263 def test_prefixes(self) -> None:
1264 """Test the prefixes method of GeneralizedTrie.
1266 This test checks that the prefixes method correctly identifies all prefixes
1267 of a given key in the trie, including those that are not complete entries."""
1268 trie: GeneralizedTrie = GeneralizedTrie()
1269 tests: list[TestSpec] = [
1270 TestSpec(
1271 name="[TGT_TP001] trie.prefixes(['tree', 'value', 'ape']) (empty trie)",
1272 action=lambda key: list(trie.prefixes(key)), # type: ignore[reportUnknownMemberType]
1273 args=[['tree', 'value', 'ape']],
1274 expected=[]
1275 ),
1276 TestSpec(
1277 name="[TGT_TP002] trie.add(['tree', 'value', 'ape'])",
1278 action=trie.add,
1279 args=[["tree", "value", "ape"]],
1280 expected=TrieId(1)
1281 ),
1282 TestSpec(
1283 name="[TGT_TP003] trie.prefixes(['tree', 'value', 'ape']) (exact key in trie)",
1284 action=lambda key: list(trie.prefixes(key)), # type: ignore[reportUnknownMemberType]
1285 args=[['tree', 'value', 'ape']],
1286 expected=[TrieEntry(TrieId(1), ('tree', 'value', 'ape'))]
1287 ),
1288 TestSpec(
1289 name=("[TGT_TP004] trie.prefixes(['tree', 'value', 'ape', 'grape']) "
1290 "(NOT exact key in trie, but has other keys that are prefix)"),
1291 action=lambda key: list(trie.prefixes(key)), # type: ignore[reportUnknownMemberType]
1292 args=[['tree', 'value', 'ape', 'grape']],
1293 expected=[TrieEntry(TrieId(1), ('tree', 'value', 'ape'))]
1294 ),
1295 TestSpec(
1296 name=("[TGT_TP005] trie.prefixes(['tree', 'value']) "
1297 "(NOT exact key in trie, does not have other keys that are prefix)"),
1298 action=lambda key: list(trie.prefixes(key)), # type: ignore[reportUnknownMemberType]
1299 args=[['tree', 'value']],
1300 expected=[]
1301 ),
1302 ]
1303 run_tests_list(self, tests)
1305 @pytest.mark.order(after=['test_create_trie', 'test_add', 'test_trieid_class'])
1306 @pytest.mark.dependency(
1307 name='test_prefixed_by',
1308 depends=['test_create_trie', 'test_add', 'test_trieid_class'])
1309 def test_prefixed_by(self) -> None:
1310 """Test the prefixed_by method of GeneralizedTrie.
1312 This test checks that the prefixed_by method correctly identifies all keys
1313 in the trie that are prefixed by the specified key."""
1314 trie: GeneralizedTrie = GeneralizedTrie()
1315 tests: list[TestSpec] = [
1316 TestSpec(
1317 name="[TGT_TPB001] tree.prefixed_by(['tree']) (empty trie, no possible prefixed keys)",
1318 action=lambda key: list(trie.prefixed_by(key)), # type: ignore[reportUnknownMemberType]
1319 args=[['tree']],
1320 expected=[]
1321 ),
1322 TestSpec(
1323 name="[TGT_TPB002] trie.add(['tree', 'value', 'ape']) (one key in trie)",
1324 action=trie.add,
1325 args=[["tree", "value", "ape"]],
1326 expected=TrieId(1)
1327 ),
1328 TestSpec(
1329 name="[TGT_TPB003] trie.prefixed_by(['tree', 'value', 'ape']) (exact key in trie, no others)",
1330 action=lambda key: list(trie.prefixed_by(key)), # type: ignore[reportUnknownMemberType]
1331 args=[['tree', 'value', 'ape']],
1332 expected=[TrieEntry(TrieId(1), ('tree', 'value', 'ape'))]
1333 ),
1334 TestSpec(
1335 name=("[TGT_TPB004] trie.prefixed_by(['tree']) "
1336 "(NOT exact key in trie, but prefixes other keys in the trie)"),
1337 action=lambda key: list(trie.prefixed_by(key)), # type: ignore[reportUnknownMemberType]
1338 args=[['tree']],
1339 expected=[TrieEntry(TrieId(1), ('tree', 'value', 'ape'))]
1340 ),
1341 TestSpec(
1342 name=("[TGT_TPB005] trie.prefixed_by(['tree', 'value', 'ape', 'grape']) "
1343 "(NOT exact key in trie, does not have other keys in trie it is a prefix for)"),
1344 action=lambda key: list(trie.prefixed_by(key)), # type: ignore[reportUnknownMemberType]
1345 args=[['tree', 'value', 'ape', 'grape']],
1346 expected=[]
1347 ),
1348 TestSpec(
1349 name=("[TGT_TPB006] trie.prefixed_by(key=['tree'], depth=0) "
1350 "(NO exact key in trie)"),
1351 action=lambda key, depth: list(trie.prefixed_by( # pyright: ignore[reportUnknownLambdaType]
1352 key=key, depth=depth)), # type: ignore[reportUnknownMemberType]
1353 kwargs={'key': ['tree'], 'depth': 0},
1354 expected=[]
1355 ),
1356 TestSpec(
1357 name=("[TGT_TPB007] trie.prefixed_by(key=['tree'], depth=1) "
1358 "(NOT exact key in trie, does not have other keys in trie it is a prefix for within depth 1)"),
1359 action=lambda key, depth: list(trie.prefixed_by( # pyright: ignore[reportUnknownLambdaType]
1360 key=key, depth=depth)), # type: ignore[reportUnknownMemberType]
1361 kwargs={'key': ['tree'], 'depth': 1},
1362 expected=[]
1363 ),
1364 TestSpec(
1365 name=("[TGT_TPB008] trie.prefixed_by(key=['tree'], depth=2) "
1366 "(NOT exact key in trie, has other keys in trie it is a prefix for within depth 2)"),
1367 action=lambda key, depth: list(trie.prefixed_by( # pyright: ignore[reportUnknownLambdaType]
1368 key=key, depth=depth)), # type: ignore[reportUnknownMemberType]
1369 kwargs={'key': ['tree'], 'depth': 2},
1370 expected=[TrieEntry(TrieId(1), ('tree', 'value', 'ape'))]
1371 ),
1372 TestSpec(
1373 name=("[TGT_TPB009] trie.prefixed_by(key=['tree'], depth=-1) "
1374 "(NOT exact key in trie, has other keys in trie it is a prefix for within any depth)"),
1375 action=lambda key, depth: list(trie.prefixed_by( # pyright: ignore[reportUnknownLambdaType]
1376 key=key, depth=depth)), # type: ignore[reportUnknownMemberType]
1377 kwargs={'key': ['tree'], 'depth': -1},
1378 expected=[TrieEntry(TrieId(1), ('tree', 'value', 'ape'))]
1379 ),
1380 TestSpec(
1381 name=("[TGT_TPB010] trie.prefixed_by(key=['tree'], depth=-2) "
1382 "(TrieValueError, TRIE_PREFIXED_BY_BAD_DEPTH_VALUE)"),
1383 action=lambda key, depth: list(trie.prefixed_by( # pyright: ignore[reportUnknownLambdaType]
1384 key=key, depth=depth)), # type: ignore[reportUnknownMemberType]
1385 kwargs={'key': ['tree'], 'depth': -2},
1386 exception=TrieValueError,
1387 exception_tag=ErrorTag.TRIE_PREFIXED_BY_BAD_DEPTH_VALUE,
1388 ),
1389 TestSpec(
1390 name=("[TGT_TPB011] trie.prefixed_by(key=['tree'], depth=-1.0) "
1391 "(TrieTypeError, TRIE_PREFIXED_BY_BAD_DEPTH_TYPE)"),
1392 action=lambda key, depth: list(trie.prefixed_by( # pyright: ignore[reportUnknownLambdaType]
1393 key=key, depth=depth)), # type: ignore[reportUnknownMemberType]
1394 kwargs={'key': ['tree'], 'depth': -1.0},
1395 exception=TrieTypeError,
1396 exception_tag=ErrorTag.TRIE_PREFIXED_BY_BAD_DEPTH_TYPE,
1397 ),
1398 TestSpec(
1399 name=("[TGT_TPB012] trie.prefixed_by([set([1]), 3, 4, 5]) "
1400 "(InvalidGeneralizedKeyError, TRIE_PREFIXED_BY_INVALID_GENERALIZED_KEY)"),
1401 action=lambda key: list(trie.prefixed_by(key)), # type: ignore[reportUnknownMemberType]
1402 args=[[set([1]), 3, 4, 5]],
1403 exception=InvalidGeneralizedKeyError,
1404 exception_tag=ErrorTag.TRIE_PREFIXED_BY_INVALID_GENERALIZED_KEY,
1405 ),
1406 ]
1407 run_tests_list(self, tests)
1409 @pytest.mark.order(after=['test_create_trie', 'test_add', 'test_trieid_class', 'test_contains_dunder'])
1410 @pytest.mark.dependency(
1411 name='test_deeply_nested_keys',
1412 depends=['test_create_trie', 'test_add', 'test_trieid_class', 'test_contains_dunder'])
1413 def test_deeply_nested_keys(self):
1414 """Test that deeply nested keys can be added and queried correctly.
1416 This test checks that the trie can handle keys with a large number of elements
1417 and that it correctly identifies prefixes and suffixes for such keys."""
1418 trie = GeneralizedTrie()
1419 deep_key = ["a"] * 100
1420 id1 = trie.add(deep_key)
1421 self.assertEqual(id1, TrieId(1))
1422 self.assertTrue(deep_key in trie)
1423 self.assertEqual(set(trie.prefixes(deep_key)), set([TrieEntry(TrieId(1), tuple(deep_key))]))
1424 self.assertEqual(set(trie.prefixed_by(deep_key)), set([TrieEntry(TrieId(1), tuple(deep_key))]))
1426 @pytest.mark.order(after=['test_create_trie', 'test_add', 'test_trieid_class', 'test_contains_dunder'])
1427 @pytest.mark.dependency(
1428 name='test_unicode_and_bytes_keys',
1429 depends=['test_create_trie', 'test_add', 'test_trieid_class', 'test_contains_dunder'])
1430 def test_unicode_and_bytes_keys(self):
1431 """Test that unicode and bytes keys can coexist in the trie.
1433 This test checks that the trie can handle both unicode strings and byte strings
1434 as keys, and that they are treated as distinct entries."""
1435 trie = GeneralizedTrie()
1436 unicode_key = ["α", "β", "γ"]
1437 bytes_key = [b"\xf0\x9f\x92\xa9"]
1438 id1 = trie.add(unicode_key)
1439 id2 = trie.add(bytes_key)
1440 self.assertEqual(id1, TrieId(1))
1441 self.assertEqual(id2, TrieId(2))
1442 self.assertTrue(unicode_key in trie)
1443 self.assertTrue(bytes_key in trie)
1445 @pytest.mark.order(after=['test_contains_dunder', 'test_create_trie', 'test_add', 'test_trieid_class'])
1446 @pytest.mark.dependency(
1447 name='test_mutated_key_after_insertion',
1448 depends=['test_trieid_class', 'test_create_trie', 'test_add', 'test_contains_dunder'])
1449 def test_mutated_key_after_insertion(self):
1450 """Test that mutating a key after insertion does not affect the trie.
1452 This test checks that the trie maintains the integrity of the original key.
1453 """
1454 trie = GeneralizedTrie()
1455 key = ["a", "b"]
1456 _ = trie.add(key)
1457 key.append("c") # Mutate after insertion
1458 # The mutated key should not be found as the original
1459 self.assertFalse(key in trie)
1460 # The original key (["a", "b"]) should still be present
1461 self.assertTrue(["a", "b"] in trie)
1463 @pytest.mark.order(after=['test_create_trie', 'test_is_generalizedkey'])
1464 @pytest.mark.dependency(
1465 name='test_invalid_argument_types_for_prefixes',
1466 depends=['test_create_trie', 'test_is_generalizedkey'])
1467 def test_invalid_argument_types_for_prefixes(self):
1468 """Test that invalid argument types raise correct exceptions."""
1469 trie = GeneralizedTrie()
1470 with self.assertRaises(
1471 InvalidGeneralizedKeyError,
1472 msg='[TIATFP001] Failed to raise InvalidGeneralizedKeyError for trie.prefixes(12345)'):
1473 # Attempt to get prefixes for an invalid key type. Because a Generator is
1474 # returned, it will not raise the error until the generator is consumed.
1475 _ = set(trie.prefixes(12345)) # type: ignore[reportGeneralTypeIssues] # int is not a valid key
1476 with self.assertRaises(
1477 InvalidGeneralizedKeyError,
1478 msg='[TIATFP002] Failed to raise InvalidGeneralizedKeyError for trie.prefixes(3.14)'):
1479 _ = set(trie.prefixes(3.14)) # type: ignore[reportGeneralTypeIssues] # float is not a valid key
1481 def test_invalid_argument_types_for_prefixed_by(self):
1482 """Test that invalid argument types raise TypeError."""
1483 trie = GeneralizedTrie()
1484 with self.assertRaises(
1485 InvalidGeneralizedKeyError,
1486 msg='[TIATFPB001] Failed to raise InvalidGeneralizedKeyError for trie.prefixed_by(12345)'):
1487 _ = set(trie.prefixed_by(12345)) # type: ignore[reportGeneralTypeIssues] # int is not a valid key
1488 with self.assertRaises(
1489 InvalidGeneralizedKeyError,
1490 msg='[TIATFPB002] Failed to raise InvalidGeneralizedKeyError for trie.prefixed_by(3.14)'):
1491 _ = set(trie.prefixed_by(3.14)) # type: ignore[reportGeneralTypeIssues] # float is not a valid key
1493 def test_large_trie_performance(self):
1494 """Test performance of adding a large number of entries to the trie."""
1495 trie = GeneralizedTrie()
1496 for i in range(1000):
1497 trie.add([i, i+1, i+2])
1498 self.assertEqual(len(trie), 1000)
1499 # Spot check a few
1500 self.assertTrue([10, 11, 12] in trie)
1501 self.assertTrue([999, 1000, 1001] in trie)
1503 @pytest.mark.order(after='test_contains_dunder')
1504 @pytest.mark.dependency(name='test_bytes_vs_str',
1505 depends=['test_create_trie', 'test_contains_dunder'])
1506 def test_bytes_vs_str(self):
1507 """Test that adding a string and bytes with the same content generates different IDs.
1509 This test checks that the trie treats strings and bytes as distinct types."""
1510 trie = GeneralizedTrie()
1511 id1 = trie.add("abc")
1512 id2 = trie.add(b"abc")
1513 self.assertNotEqual(id1, id2)
1514 self.assertTrue("abc" in trie)
1515 self.assertTrue(b"abc" in trie)
1517 def test_empty_trie_iter(self):
1518 """Test that an empty trie iterates to an empty list."""
1519 trie = GeneralizedTrie()
1520 self.assertEqual(list(trie), [])
1522 def test_remove_nonexistent_id(self):
1523 """Test removing a non-existent ID from the trie.
1525 This test checks that attempting to remove an ID that does not exist
1526 raises a KeyError.
1527 """
1528 trie = GeneralizedTrie()
1529 self.assertEqual(
1530 trie.add("abc"),
1531 TrieId(1),
1532 msg='[TRNEI001] Add an entry to ensure the trie is not empty. Should have TrieId(1)')
1533 with self.assertRaises(KeyError,
1534 msg='[TRNEI002] Removing a non-existent TrieId(999999) should raise KeyError'):
1535 trie.remove(TrieId(999999)) # Non-existent TrieId
1536 with self.assertRaises(
1537 TypeError,
1538 msg=('[TRNEI003] Removing 1 should raise a TypError because it is not a '
1539 'TrieId or a valid GeneralizedKey')):
1540 trie.remove(1) # type: ignore[reportGeneralTypeIssues]
1542 def test_remove_and_readd(self):
1543 """Test removing an entry and then re-adding it to ensure a new ID is generated.
1545 This test checks that after removing an entry, adding the same key again
1546 generates a new ID, confirming that the trie correctly handles the removal
1547 and re-adding of entries."""
1548 trie = GeneralizedTrie()
1549 key = ["x", "y", "z"]
1550 id1 = trie.add(key)
1551 trie.remove(id1)
1552 id2 = trie.add(key)
1553 self.assertNotEqual(id1, id2)
1554 self.assertTrue(key in trie)
1556 def test_str(self) -> None:
1557 """Test the string representation of GeneralizedTrie.
1559 This test checks the output of the __str__ method of GeneralizedTrie
1560 for various string inputs. It verifies that the string representation
1561 correctly reflects the structure of the trie, including the children,
1562 parent nodes, and trie IDs.
1564 The test includes multiple scenarios with different string lengths
1565 and ensures that the output matches the expected format."""
1566 trie = GeneralizedTrie()
1567 test_string = 'a'
1568 self.assertIsInstance(test_string, TrieKeyToken)
1569 self.assertIsInstance(test_string, Iterable)
1571 trie.add(test_string)
1572 found: str = dedent(str(trie))
1573 expected: str = dedent("""\
1574 {
1575 trie number = 1
1576 children = {
1577 'a' = {
1578 parent = root node
1579 node token = 'a'
1580 trie id = TrieId(1)
1581 }
1582 }
1583 trie index = dict_keys([TrieId(1)])
1584 }""")
1585 self.assertEqual(found, expected, msg='[TSTR001] str(trie)')
1587 trie = GeneralizedTrie()
1588 test_string = 'ab'
1589 trie.add(test_string)
1590 found = dedent(str(trie))
1591 expected = dedent("""\
1592 {
1593 trie number = 1
1594 children = {
1595 'a' = {
1596 parent = root node
1597 node token = 'a'
1598 children = {
1599 'b' = {
1600 parent = 'a'
1601 node token = 'b'
1602 trie id = TrieId(1)
1603 }
1604 }
1605 }
1606 }
1607 trie index = dict_keys([TrieId(1)])
1608 }""")
1609 self.assertEqual(found, expected, msg='[TSTR002] str(trie))')
1611 trie = GeneralizedTrie()
1612 test_string = 'abc'
1613 trie.add(test_string)
1614 found = dedent(str(trie))
1615 expected = dedent("""\
1616 {
1617 trie number = 1
1618 children = {
1619 'a' = {
1620 parent = root node
1621 node token = 'a'
1622 children = {
1623 'b' = {
1624 parent = 'a'
1625 node token = 'b'
1626 children = {
1627 'c' = {
1628 parent = 'b'
1629 node token = 'c'
1630 trie id = TrieId(1)
1631 }
1632 }
1633 }
1634 }
1635 }
1636 }
1637 trie index = dict_keys([TrieId(1)])
1638 }""")
1639 self.assertEqual(found, expected, msg='[TSTR003] str(trie))')
1641 @pytest.mark.order(after=['test_create_trie', 'test_add', 'test_remove'])
1642 @pytest.mark.dependency(name='test_getitem_dunder', depends=['test_create_trie', 'test_add', 'test_remove'])
1643 def test_getitem_dunder(self) -> None:
1644 """Test the __getitem__ dunder method of GeneralizedTrie.
1646 This test checks whether the trie correctly retrieves values for
1647 existing keys and raises the appropriate errors for non-existing
1648 keys or invalid key types."""
1649 trie: GeneralizedTrie = GeneralizedTrie()
1650 id_ab: TrieId = trie.add("ab", "value for ab")
1651 id_abc: TrieId = trie.add("abc", "another value")
1652 tests: list[TestSpec] = [
1653 TestSpec(
1654 name="[TGT_TGID001] trie.__getitem__(id_abc) (value for existing ID)",
1655 action=trie.__getitem__,
1656 args=[id_abc],
1657 expected=TrieEntry(ident=id_abc, key='abc', value='another value')
1658 ),
1659 TestSpec(
1660 name="[TGT_TGID002] trie.__getitem__('abc') (value for key 'abc')",
1661 action=trie.__getitem__,
1662 args=['abc'],
1663 expected=TrieEntry(ident=id_abc, key='abc', value='another value')
1664 ),
1665 TestSpec(
1666 name="[TGT_TGID003] trie.remove('abc') (remove key 'abc' from trie)",
1667 action=trie.remove,
1668 args=['abc'],
1669 expected=None
1670 ),
1671 TestSpec(
1672 name=("[TGT_TGID004] trie.__getitem__('abc') (non-existent key after removal, "
1673 "TrieKeyError, GETITEM_KEY_NOT_FOUND)"),
1674 action=trie.__getitem__,
1675 args=['abc'],
1676 exception=TrieKeyError,
1677 exception_tag=ErrorTag.GETITEM_KEY_NOT_FOUND
1678 ),
1679 TestSpec(
1680 name=("[TGT_TGID005] trie.__getitem__(id_abc) (non-existent TrieId "
1681 "after removal, TrieKeyError, GETITEM_ID_NOT_FOUND)"),
1682 action=trie.__getitem__,
1683 args=[id_abc],
1684 exception=TrieKeyError,
1685 exception_tag=ErrorTag.GETITEM_ID_NOT_FOUND
1686 ),
1687 TestSpec(
1688 name=("[TGT_TGID006] trie.__getitem__('abc') (Non-existent key, "
1689 "TrieKeyError, GETITEM_KEY_NOT_FOUND)"),
1690 action=trie.__getitem__,
1691 args=['abc'],
1692 exception=TrieKeyError,
1693 exception_tag=ErrorTag.GETITEM_KEY_NOT_FOUND
1694 ),
1695 TestSpec(
1696 name="[TGT_TGID007] trie.__getitem__(set('a')) (TrieTypeError, GETITEM_INVALID_KEY_TYPE)",
1697 action=trie.__getitem__,
1698 args=[set('abc')],
1699 exception=TrieTypeError,
1700 exception_tag=ErrorTag.GETITEM_INVALID_KEY_TYPE
1701 ),
1702 TestSpec(
1703 name="[TGT_TGID008] trie.__getitem__('a') (Non-existent key, TrieKeyError, GETITEM_NOT_TERMINAL)",
1704 action=trie.__getitem__,
1705 args=['a'],
1706 exception=TrieKeyError,
1707 exception_tag=ErrorTag.GETITEM_NOT_TERMINAL
1708 ),
1709 TestSpec(
1710 name="[TGT_TGID009] trie['ab'].value == 'value for ab'",
1711 action=lambda trie, key: trie[key].value, # type: ignore[reportUnknownMemberType]
1712 args=[trie, 'ab'],
1713 expected='value for ab'
1714 ),
1715 TestSpec(
1716 name="[TGT_TGID010] trie[id_ab].value == 'value for ab'",
1717 action=lambda trie, key: trie[key].value, # type: ignore[reportUnknownMemberType]
1718 args=[trie, id_ab],
1719 expected='value for ab'
1720 )
1721 ]
1722 run_tests_list(self, tests)
1724 @pytest.mark.order(after=['test_create_trie', 'test_contains_dunder', 'test_getitem_dunder'])
1725 @pytest.mark.dependency(name='test_setitem_dunder',
1726 depends=['test_create_trie', 'test_contains_dunder', 'test_getitem_dunder'])
1727 def test_setitem_dunder(self) -> None:
1728 """Test the __setitem__ dunder method of GeneralizedTrie.
1730 The __setitem__ dunder method allows assigning values to keys in the trie using
1731 the square bracket notation: trie[<key>] = <value>
1732 """
1733 def _helper_assignment(trie: GeneralizedTrie, key: str, value: str) -> None:
1734 """Helper function to assign a value to a key in the trie.
1736 Args:
1737 trie (GeneralizedTrie): The trie to modify.
1738 key (str): The key to assign the value to.
1739 value (str): The value to assign to the key.
1740 """
1741 trie[key] = value
1743 trie: GeneralizedTrie = GeneralizedTrie()
1745 tests: list[TestSpec] = [
1746 TestSpec(
1747 name="[TGT_TSID001] trie.__setitem__('a', 'value')",
1748 action=trie.__setitem__,
1749 args=['a', 'value'],
1750 expected=None
1751 ),
1752 TestSpec(
1753 name="[TGT_TSID002] 'a' in trie (verify successful insertion with __setitem__)",
1754 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1755 args=['a'],
1756 expected=True
1757 ),
1758 TestSpec(
1759 name="[TGT_TSID003] trie.__setitem__('a', 'value2') (Key already exists, update value)",
1760 action=trie.__setitem__,
1761 args=['a', 'value2'],
1762 expected=None
1763 ),
1764 TestSpec(
1765 name="[TGT_TSID004] trie['a'].value == 'value2' (Key already exists, updated value)",
1766 action=lambda trie, key: trie[key].value, # type: ignore[reportUnknownMemberType]
1767 args=[trie, 'a'],
1768 expected='value2'
1769 ),
1770 TestSpec(
1771 name="[TGT_TSID005] trie['ab'] = 'value3' (Key does not exist, insert new value)",
1772 action=_helper_assignment,
1773 args=[trie, 'ab', 'value3'],
1774 expected=None
1775 ),
1776 TestSpec(
1777 name="[TGT_TSID006] 'ab' in trie (verify successful insertion using trie['ab'] = 'value3')",
1778 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1779 args=['ab'],
1780 expected=True
1781 ),
1782 TestSpec(
1783 name="[TGT_TSID007] trie['ab'] = 'value4' (Key already exists, update value)",
1784 action=_helper_assignment,
1785 args=[trie, 'ab', 'value4'],
1786 expected=None
1787 ),
1788 TestSpec(
1789 name="[TGT_TSID008] trie['ab'].value == 'value4' (Key already exists, updated value)",
1790 action=lambda trie, key: trie[key].value, # type: ignore[reportUnknownMemberType]
1791 args=[trie, 'ab'],
1792 expected='value4'
1793 ),
1794 ]
1795 run_tests_list(self, tests)
1797 @pytest.mark.order(after=['test_create_trie', 'test_add'])
1798 @pytest.mark.dependency(name='test_contains_dunder', depends=['test_create_trie', 'test_add'])
1799 def test_contains_dunder(self) -> None:
1800 """Test the __contains__ dundermethod of GeneralizedTrie.
1802 This test checks whether the trie correctly identifies the presence
1803 or absence of various keys.
1805 The test verifies that the __contains__ dunder method returns the expected
1806 boolean values for each key, ensuring that the trie behaves correctly
1807 when checking for membership."""
1808 trie: GeneralizedTrie = GeneralizedTrie()
1810 tests: list[TestSpec] = [
1811 TestSpec(
1812 name="[TGT_TC001] trie.__contains__() - wrong number of arguments (TypeError)",
1813 action=trie.__contains__,
1814 args=[],
1815 exception=TypeError,
1816 ),
1817 TestSpec(
1818 name="[TGT_TC002] trie.__contains__('a') (false)",
1819 action=trie.__contains__,
1820 args=['a'],
1821 expected=False
1822 ),
1823 TestSpec(
1824 name="[TGT_TC003] 'a' in trie (false)",
1825 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1826 args=['a'],
1827 expected=False
1828 ),
1829 TestSpec(
1830 name="[TGT_TC004] ['a'] in trie (false)",
1831 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1832 args=[['a']],
1833 expected=False
1834 )
1835 ]
1836 run_tests_list(self, tests)
1838 id_a: TrieId = trie.add('a')
1839 tests = [
1840 TestSpec(
1841 name="[TGT_TC005] trie.__contains__('a') (true)",
1842 action=trie.__contains__,
1843 args=['a'],
1844 expected=True
1845 ),
1846 TestSpec(
1847 name="[TGT_TC006] 'a' in trie (true)",
1848 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1849 args=['a'],
1850 expected=True
1851 ),
1852 TestSpec(
1853 name="[TGT_TC007] ['a'] in trie (true)",
1854 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1855 args=[['a']],
1856 expected=True
1857 ),
1858 TestSpec(
1859 name="[TGT_TC008] trie.__contains__(id_a) (true)",
1860 action=trie.__contains__,
1861 args=[id_a],
1862 expected=True
1863 ),
1864 TestSpec(
1865 name="[TGT_TC009] id_a in trie (true)",
1866 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1867 args=[id_a],
1868 expected=True
1869 ),
1870 TestSpec(
1871 name="[TGT_TC010] trie.__contains__('b') (false)",
1872 action=trie.__contains__,
1873 args=['b'],
1874 expected=False
1875 ),
1876 TestSpec(
1877 name="[TGT_TC011] trie.__contains__(['b']) (false)",
1878 action=trie.__contains__,
1879 args=[['b']],
1880 expected=False
1881 ),
1882 TestSpec(
1883 name="[TGT_TC012] 'b' in trie (false)",
1884 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1885 args=['b'],
1886 expected=False
1887 ),
1888 ]
1889 run_tests_list(self, tests)
1891 # Test with different types of keys and a new trie
1892 trie = GeneralizedTrie()
1893 id_list_1: TrieId = trie.add([1])
1894 id_list_none: TrieId = trie.add([None])
1895 tests = [
1896 TestSpec(
1897 name="[TGT_TC013] trie.__contains__(1) (false, int(1) not a valid key type)",
1898 action=trie.__contains__,
1899 args=[1],
1900 expected=False
1901 ),
1902 TestSpec(
1903 name="[TGT_TC014] 1 in trie (false, int(1) not a valid key type)",
1904 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1905 args=[1],
1906 expected=False
1907 ),
1908 TestSpec(
1909 name="[TGT_TC015] trie.__contains__([1]) (true)",
1910 action=trie.__contains__,
1911 args=[[1]],
1912 expected=True
1913 ),
1914 TestSpec(
1915 name="[TGT_TC016] [1] in trie (true)",
1916 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1917 args=[[1]],
1918 expected=True
1919 ),
1920 TestSpec(
1921 name="[TGT_TC0017] trie.__contains__(id_list_1) (true)",
1922 action=trie.__contains__,
1923 args=[id_list_1],
1924 expected=True
1925 ),
1926 TestSpec(
1927 name="[TGT_TC0018] id_list_1 in trie (true)",
1928 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1929 args=[id_list_1],
1930 expected=True
1931 ),
1932 TestSpec(
1933 name="[TGT_TC019] trie.__contains__(None) (false, None is not a valid key type)",
1934 action=trie.__contains__,
1935 args=[None],
1936 expected=False
1937 ),
1938 TestSpec(
1939 name="[TGT_TC020] None in trie (false, None is not a valid key type)",
1940 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1941 args=[None],
1942 expected=False
1943 ),
1944 TestSpec(
1945 name="[TGT_TC021] trie.__contains__([None]) (true)",
1946 action=trie.__contains__,
1947 args=[[None]],
1948 expected=True
1949 ),
1950 TestSpec(
1951 name="[TGT_TC022] [None] in trie (true)",
1952 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1953 args=[[None]],
1954 expected=True
1955 ),
1956 TestSpec(
1957 name="[TGT_TC023] trie.__contains__(id_list_none) (true)",
1958 action=trie.__contains__,
1959 args=[id_list_none],
1960 expected=True
1961 ),
1962 TestSpec(
1963 name="[TGT_TC024] id_list_none in trie (true)",
1964 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1965 args=[id_list_none],
1966 expected=True
1967 ),
1968 ]
1969 run_tests_list(self, tests)
1971 # String key tests
1972 trie = GeneralizedTrie()
1973 id_str_abc: TrieId = trie.add('abc')
1974 tests = [
1975 TestSpec(
1976 name="[TGT_TC027] trie.__contains__('abcd') (false, 'abcd' not in trie)",
1977 action=trie.__contains__,
1978 args=['abcd'],
1979 expected=False
1980 ),
1981 TestSpec(
1982 name="[TGT_TC028] trie.__contains__('abc') (true, 'abc' in trie)",
1983 action=trie.__contains__,
1984 args=['abc'],
1985 expected=True
1986 ),
1987 TestSpec(
1988 name="[TGT_TC029] trie.__contains__(id_str_abc) (true, TrieId id_str_abc in trie)",
1989 action=trie.__contains__,
1990 args=[id_str_abc],
1991 expected=True
1992 ),
1993 TestSpec(
1994 name="[TGT_TC030] trie.__contains__('ab') (false, prefix 'ab' not a key in trie)",
1995 action=trie.__contains__,
1996 args=['ab'],
1997 expected=False
1998 ),
1999 TestSpec(
2000 name="[TGT_TC031] trie.__contains__('a') (false, prefix 'a' not a key in trie)",
2001 action=trie.__contains__,
2002 args=['a'],
2003 expected=False
2004 ),
2005 TestSpec(
2006 name="[TGT_TC032] trie.__contains__('') (false, empty string not a key in trie)",
2007 action=trie.__contains__,
2008 args=[''],
2009 expected=False
2010 ),
2012 ]
2013 run_tests_list(self, tests)
2015 @pytest.mark.order(after=['test_create_trie', 'test_add', 'test_remove'])
2016 @pytest.mark.dependency(name='test_get', depends=['test_create_trie', 'test_add', 'test_remove'])
2017 def test_get(self) -> None:
2018 """Test the get method of GeneralizedTrie.
2020 This test checks whether the trie correctly retrieves values for
2021 existing keys, applies default values or raises the appropriate errors for non-existing
2022 keys or invalid key types."""
2023 trie: GeneralizedTrie = GeneralizedTrie()
2024 id_ab: TrieId = trie.add("ab", "value for ab")
2025 id_abc: TrieId = trie.add("abc", "another value")
2026 tests: list[TestSpec] = [
2027 TestSpec(
2028 name="[TGT_TG001] trie.get(id_abc) (value for existing ID)",
2029 action=trie.get,
2030 args=[id_abc],
2031 expected=TrieEntry(ident=id_abc, key='abc', value='another value')
2032 ),
2033 TestSpec(
2034 name="[TGT_TG002] trie.get('abc') (value for key 'abc')",
2035 action=trie.get,
2036 args=['abc'],
2037 expected=TrieEntry(ident=id_abc, key='abc', value='another value')
2038 ),
2039 TestSpec(
2040 name="[TGT_TG003] trie.remove('abc') (remove key 'abc' from trie)",
2041 action=trie.remove,
2042 args=['abc'],
2043 expected=None
2044 ),
2045 TestSpec(
2046 name=("[TGT_TG004] trie.get('abc') (non-existent key after removal, default is None"),
2047 action=trie.get,
2048 args=['abc'],
2049 expected=None
2050 ),
2051 TestSpec(
2052 name=("[TGT_TG005] trie.get(id_abc) (non-existent TrieId after removal, default is None)"),
2053 action=trie.get,
2054 args=[id_abc],
2055 expected=None
2056 ),
2057 TestSpec(
2058 name="[TGT_TG006] trie.get(set('abc')) (bad key type -> default value None)",
2059 action=trie.get,
2060 args=[set('abc')],
2061 expected=None
2062 ),
2063 TestSpec(
2064 name="[TGT_TG007] trie.get('a') (Non-existent partial key -> default value None)",
2065 action=trie.get,
2066 args=['a'],
2067 expected=None
2068 ),
2069 TestSpec(
2070 name="[TGT_TG008] trie.get('ab').value == 'value for ab'",
2071 action=lambda trie, key: trie[key].value, # type: ignore[reportUnknownMemberType]
2072 args=[trie, 'ab'],
2073 expected='value for ab'
2074 ),
2075 TestSpec(
2076 name="[TGT_TG009] trie.get(id_ab).value == 'value for ab'",
2077 action=lambda trie, key: trie[key].value, # type: ignore[reportUnknownMemberType]
2078 args=[trie, id_ab],
2079 expected='value for ab'
2080 ),
2082 TestSpec(
2083 name=("[TGT_TG010] trie.get('abc', 'bleh') (non-existent key after removal, default is 'bleh'"),
2084 action=trie.get,
2085 args=['abc', 'bleh'],
2086 expected='bleh'
2087 ),
2088 TestSpec(
2089 name=("[TGT_TG011] trie.get(id_abc, 'bleh') (non-existent TrieId after removal, default is 'bleh')"),
2090 action=trie.get,
2091 args=[id_abc, 'bleh'],
2092 expected='bleh'
2093 ),
2094 TestSpec(
2095 name="[TGT_TG012] trie.get(set('abc'), 'bleh') (bad key type -> default value 'bleh')",
2096 action=trie.get,
2097 args=[set('abc'), 'bleh'],
2098 expected='bleh'
2099 ),
2100 TestSpec(
2101 name="[TGT_TG013] trie.get('a', 'bleh') (Non-existent partial key -> default value 'bleh')",
2102 action=trie.get,
2103 args=['a', 'bleh'],
2104 expected='bleh'
2105 )
2106 ]
2107 run_tests_list(self, tests)
2109 @pytest.mark.order(after='test_remove')
2110 @pytest.mark.dependency(name='test_keys', depends=[
2111 'test_create_trie', 'test_add', 'test_contains_dunder', 'test_remove'])
2112 def test_keys(self) -> None:
2113 """Test the keys method of GeneralizedTrie.
2115 This test checks the functionality of the keys method, which should
2116 return an iterable of TrieId objects representing the keys in the trie.
2118 The test includes scenarios for an empty trie, adding keys, and
2119 removing keys. It verifies that the keys method returns the expected
2120 TrieId objects in the correct order."""
2121 trie: GeneralizedTrie = GeneralizedTrie()
2123 with self.subTest(msg="[TK001] trie.keys()"):
2124 expect_id_list: list[TrieId] = []
2125 found_id_list: list[TrieId] = list(trie.keys())
2126 self.assertEqual(found_id_list, expect_id_list)
2128 with self.subTest(msg="[TK002] trie.add('abcdef')"):
2129 expect_id: TrieId = TrieId(1)
2130 found_id: TrieId = trie.add("abcdef")
2131 self.assertEqual(found_id, expect_id)
2133 with self.subTest(msg="[TK003] trie.keys()"):
2134 expect_id_list: list[TrieId] = [TrieId(1)]
2135 found_id_list: list[TrieId] = list(trie.keys())
2136 self.assertEqual(found_id_list, expect_id_list)
2138 with self.subTest(msg="[TK004] trie.add('abc')"):
2139 expect_id = TrieId(2)
2140 found_id = trie.add("abc")
2141 self.assertEqual(found_id, expect_id)
2143 with self.subTest(msg="[TK005] trie.keys()"):
2144 expect_id_list = [TrieId(1), TrieId(2)]
2145 found_id_list = list(sorted(trie.keys()))
2146 self.assertEqual(found_id_list, expect_id_list)
2148 with self.assertRaises(TypeError, msg="[TK006] trie.remove('abc')"):
2149 trie.remove(set('abc')) # type: ignore[reportGeneralTypeIssues]
2151 with self.subTest(msg="[TK007] trie.remove(TrieId(1))"):
2152 trie.remove(TrieId(1))
2153 expect_id_list = [TrieId(2)]
2154 found_id_list = list(trie.keys())
2155 self.assertEqual(found_id_list, expect_id_list)
2157 with self.subTest(msg="[TK008] trie.remove(TrieId(2))"):
2158 trie.remove(TrieId(2))
2159 expect_id_list = []
2160 found_id_list = list(trie.keys())
2161 self.assertEqual(found_id_list, expect_id_list)
2163 @pytest.mark.order(after='test_add')
2164 @pytest.mark.dependency(name='test_values', depends=['test_create_trie', 'test_trieid_class', 'test_add'])
2165 def test_values(self) -> None:
2166 """Test the values method of GeneralizedTrie.
2168 This test checks the functionality of the values method, which should
2169 return an iterable of TrieEntry objects representing the values in the trie.
2170 The test includes scenarios for an empty trie, adding entries, and
2171 removing entries. It verifies that the values method returns the expected
2172 TrieEntry objects in the correct order.
2173 It also checks that the values method behaves correctly when entries are
2174 added and removed, ensuring that the trie maintains its integrity."""
2175 trie: GeneralizedTrie = GeneralizedTrie()
2177 with self.subTest(msg="[TV001] trie.values()"):
2178 expect_entries_list: list[TrieEntry] = []
2179 found_entries_list: list[TrieEntry] = list(trie.values())
2180 self.assertEqual(found_entries_list, expect_entries_list)
2182 with self.subTest(msg="[TV002] trie.add('abcdef')"):
2183 expect_id: TrieId = TrieId(1)
2184 found_id: TrieId = trie.add("abcdef")
2185 self.assertEqual(found_id, expect_id)
2187 with self.subTest(msg="[TV003] trie.values()"):
2188 expect_entries_list = [TrieEntry(TrieId(1), 'abcdef')]
2189 found_entries_list = list(trie.values())
2190 self.assertEqual(found_entries_list, expect_entries_list)
2192 with self.subTest(msg="[TV004] trie.add('abc')"):
2193 expect_id = TrieId(2)
2194 found_id = trie.add("abc")
2195 self.assertEqual(found_id, expect_id)
2197 with self.subTest(msg="[TV005] trie.values()"):
2198 expect_entries_list = [TrieEntry(TrieId(1), 'abcdef'), TrieEntry(TrieId(2), 'abc')]
2199 found_entries_list = list(sorted(trie.values()))
2200 self.assertEqual(found_entries_list, expect_entries_list)
2202 with self.subTest(msg="[TV006] trie.remove(TrieId(1))"):
2203 trie.remove(TrieId(1))
2204 expect_entries_list = [TrieEntry(TrieId(2), 'abc')]
2205 found_entries_list = list(trie.values())
2206 self.assertEqual(found_entries_list, expect_entries_list)
2208 with self.subTest(msg="[TV007] trie.remove(TrieId(2))"):
2209 trie.remove(TrieId(2))
2210 expect_entries_list = []
2211 found_entries_list = list(trie.values())
2212 self.assertEqual(found_entries_list, expect_entries_list)
2214 def test_items(self) -> None:
2215 """Test the items method of GeneralizedTrie.
2217 This test checks the functionality of the items method, which should
2218 return an iterable of tuples containing TrieId and TrieEntry objects.
2219 The test includes scenarios for an empty trie, adding entries, and
2220 removing entries. It verifies that the items method returns the expected
2221 tuples in the correct order.
2222 It also checks that the items method behaves correctly when entries are
2223 added and removed, ensuring that the trie maintains its integrity."""
2224 trie: GeneralizedTrie = GeneralizedTrie()
2226 with self.subTest(msg="[TI001] trie.items()"):
2227 expect_items_list: list[tuple[TrieId, TrieEntry]] = []
2228 found_items_list: list[tuple[TrieId, TrieEntry]] = list(trie.items())
2229 self.assertEqual(found_items_list, expect_items_list)
2231 with self.subTest(msg="[TI002] trie.add('abcdef')"):
2232 expect_id: TrieId = TrieId(1)
2233 found_id: TrieId = trie.add("abcdef")
2234 self.assertEqual(found_id, expect_id)
2236 with self.subTest(msg="[TI003] trie.items()"):
2237 expect_items_list = [(TrieId(1), TrieEntry(TrieId(1), 'abcdef'))]
2238 found_items_list = list(sorted(trie.items()))
2239 self.assertEqual(found_items_list, expect_items_list)
2241 with self.subTest(msg="[TI004] trie.add('abc')"):
2242 expect_id = TrieId(2)
2243 found_id = trie.add("abc")
2244 self.assertEqual(found_id, expect_id)
2246 with self.subTest(msg="[TI005] trie.items()"):
2247 expect_items_list = [
2248 (TrieId(1), TrieEntry(TrieId(1), 'abcdef')),
2249 (TrieId(2), TrieEntry(TrieId(2), 'abc'))]
2250 found_items_list = list(sorted(trie.items()))
2251 self.assertEqual(found_items_list, expect_items_list)
2253 with self.subTest(msg="[TI006] trie.remove(TrieId(1))"):
2254 trie.remove(TrieId(1))
2255 expect_items_list = [(TrieId(2), TrieEntry(TrieId(2), 'abc'))]
2256 found_items_list = list(sorted(trie.items()))
2257 self.assertEqual(found_items_list, expect_items_list)
2259 with self.subTest(msg="[TI007] trie.remove(TrieId(2))"):
2260 trie.remove(TrieId(2))
2261 expect_items_list = []
2262 found_items_list = list(sorted(trie.items()))
2263 self.assertEqual(found_items_list, expect_items_list)
2265 def test_iter(self) -> None:
2266 """Test the iteration over GeneralizedTrie."""
2267 trie: GeneralizedTrie = GeneralizedTrie()
2269 with self.subTest(msg="[TITER001] for entry in trie:"):
2270 expect_ids_list: list[TrieId] = []
2271 found_ids_list: list[TrieId] = []
2272 for entry in trie: 2272 ↛ 2273line 2272 didn't jump to line 2273 because the loop on line 2272 never started
2273 found_ids_list.append(entry)
2274 self.assertEqual(found_ids_list, expect_ids_list)
2276 with self.subTest(msg="[TITER002] trie.add('abcdef')"):
2277 expect_id: TrieId = TrieId(1)
2278 found_id: TrieId = trie.add("abcdef")
2279 self.assertEqual(found_id, expect_id)
2281 with self.subTest(msg="[TITER003] for ident in trie:"):
2282 expect_ids_list = [TrieId(1)]
2283 found_ids_list = []
2284 for ident in trie:
2285 found_ids_list.append(ident)
2286 self.assertEqual(sorted(found_ids_list), expect_ids_list)
2288 with self.subTest(msg="[TITER004] trie.add('abc')"):
2289 expect_id = TrieId(2)
2290 found_id = trie.add("abc")
2291 self.assertEqual(found_id, expect_id)
2293 with self.subTest(msg="[TITER005] for entry in trie:"):
2294 expect_ids_list: list[TrieId] = [TrieId(1), TrieId(2)]
2295 found_ids_list: list[TrieId] = []
2296 for entry in trie:
2297 found_ids_list.append(entry)
2298 self.assertEqual(sorted(found_ids_list), expect_ids_list)
2300 @pytest.mark.order(after='test_remove')
2301 @pytest.mark.dependency(name='test_bool', depends=['test_create_trie', 'test_add', 'test_remove'])
2302 def test_bool(self) -> None:
2303 """Test the __bool__ method of GeneralizedTrie.
2305 This test checks the functionality of the __bool__ method, which should
2306 return True if the trie contains any entries, and False if it is empty.
2307 The test includes scenarios for an empty trie, adding entries, and removing
2308 entries. It verifies that the __bool__ method returns the expected boolean
2309 values for each scenario, ensuring that the trie behaves correctly when
2310 checking its truthiness."""
2311 trie = GeneralizedTrie()
2312 tests: list[TestSpec] = [
2313 TestSpec(
2314 name="[TB001] bool(trie)", action=bool, args=[trie], expected=False
2315 ),
2316 TestSpec(
2317 name="[TB002] trie.add('a')", action=trie.add, args=["a"], expected=TrieId(1)
2318 ),
2319 TestSpec(
2320 name="[TB003] bool(trie)", action=bool, args=[trie], expected=True
2321 ),
2322 TestSpec(
2323 name="[TB004] trie.remove(TrieId(1))", action=trie.remove, args=[TrieId(1)], expected=None
2324 ),
2325 TestSpec(
2326 name="[TB005] bool(trie)", action=bool, args=[trie], expected=False
2327 ),
2328 ]
2329 run_tests_list(self, tests)
2331 @pytest.mark.order(after=[
2332 'test_create_trie', 'test_trieid_class', 'test_add', 'test_contains_dunder'])
2333 @pytest.mark.dependency(
2334 name='test_remove',
2335 depends=['test_create_trie', 'test_trieid_class', 'test_add', 'test_contains_dunder'])
2336 def test_remove(self) -> None:
2337 """Test the remove method of GeneralizedTrie."""
2338 trie = GeneralizedTrie()
2339 id_a: TrieId = trie.add("a")
2340 id_ab: TrieId = trie.add("ab")
2341 id_abc: TrieId = trie.add("abc")
2342 id_abcd: TrieId = trie.add("abcd")
2343 id_d: TrieId = trie.add("d")
2344 tests: list[TestSpec] = [
2345 TestSpec(
2346 name="[TGT_TR001] 'abc' in trie (validate 'abc' in trie before deletion)",
2347 action=lambda key: key in trie, # pyright: ignore[reportUnknownLambdaType]
2348 args=['abc'],
2349 ),
2350 # delete 'abc'
2351 TestSpec(
2352 name="[TGT_TR002] trie.remove('abc') (deletes 'abc' from trie)",
2353 action=trie.remove,
2354 args=['abc'],
2355 expected=None
2356 ),
2357 TestSpec(
2358 name="[TGT_TR003] 'abc' not in trie (validate 'abc' not in trie after deletion)",
2359 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2360 args=['abc'],
2361 expected=True
2362 ),
2363 TestSpec(
2364 name="[TGT_TR004] id_abc not in trie (validate id_abc not in trie after deletion)",
2365 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2366 args=[id_abc],
2367 expected=True
2368 ),
2369 TestSpec(
2370 name=("[TGT_TR005] all(key in trie for key in ['a', 'ab', 'abcd', 'd']) "
2371 "in trie (validate all other keys still in trie after deletion)"),
2372 action=lambda trie, keys: all( # pyright: ignore[reportUnknownLambdaType]
2373 key in trie for key in keys), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2374 args=[trie, ['a', 'ab', 'abcd', 'd']],
2375 expected=True
2376 ),
2377 TestSpec(
2378 name=("[TGT_TR006] all(trie_id in trie for trie_id in [id_a, id_ab, id_abcd, id_d]) "
2379 "in trie (validate all other trie ids still in trie after deletion)"),
2380 action=lambda trie, trie_ids: all( # pyright: ignore[reportUnknownLambdaType]
2381 trie_id in trie
2382 for trie_id in trie_ids), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2383 args=[trie, [id_a, id_ab, id_abcd, id_d]],
2384 expected=True
2385 ),
2386 # delete 'd'
2387 TestSpec(
2388 name="[TGT_TR007] trie.remove('d') (deletes 'd' from trie)",
2389 action=trie.remove,
2390 args=['d'],
2391 expected=None
2392 ),
2393 TestSpec(
2394 name="[TGT_TR008] 'd' not in trie (validate 'd' not in trie after deletion)",
2395 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2396 args=['d'],
2397 expected=True
2398 ),
2399 TestSpec(
2400 name="[TGT_TR009] id_d not in trie (validate id_d not in trie after deletion)",
2401 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2402 args=[id_d],
2403 expected=True
2404 ),
2405 TestSpec(
2406 name=("[TGT_TR010] all(key in trie for key in ['ab', 'abcd']) "
2407 "in trie (validate all other keys still in trie after deletion)"),
2408 action=lambda trie, keys: all( # pyright: ignore[reportUnknownLambdaType]
2409 key in trie for key in keys), # pyright: ignore[reportUnknownVariableType]
2410 args=[trie, ['ab', 'abcd']],
2411 expected=True
2412 ),
2413 TestSpec(
2414 name=("[TGT_TR011] all(trie_id in trie for trie_id in [id_ab, id_abcd]) "
2415 "in trie (validate all other trie ids still in trie after deletion)"),
2416 action=lambda trie, trie_ids: all( # pyright: ignore[reportUnknownLambdaType]
2417 trie_id in trie
2418 for trie_id in trie_ids), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2419 args=[trie, [id_a, id_ab, id_abcd]],
2420 expected=True
2421 ),
2422 # delete 'abcd'
2423 TestSpec(
2424 name="[TGT_TR012] trie.remove('abcd') (deletes 'abcd' from trie)",
2425 action=trie.remove,
2426 args=['abcd'],
2427 expected=None
2428 ),
2429 TestSpec(
2430 name="[TGT_TR013] 'abcd' not in trie (validate 'abcd' not in trie after deletion)",
2431 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2432 args=['abcd'],
2433 expected=True
2434 ),
2435 TestSpec(
2436 name="[TGT_TR014] id_abcd not in trie (validate id_abcd not in trie after deletion)",
2437 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2438 args=[id_abcd],
2439 expected=True
2440 ),
2441 TestSpec(
2442 name=("[TGT_TR015] all(key in trie for key in ['ab']) in trie "
2443 "(validate all other keys still in trie after deletion)"),
2444 action=lambda trie, keys: all( # pyright: ignore[reportUnknownLambdaType]
2445 key in trie
2446 for key in keys), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2447 args=[trie, ['ab']],
2448 expected=True
2449 ),
2450 TestSpec(
2451 name=("[TGT_TR016] all(trie_id in trie for trie_id in [id_ab]) "
2452 "in trie (validate all other trie ids still in trie after deletion)"),
2453 action=lambda trie, trie_ids: all( # pyright: ignore[reportUnknownLambdaType]
2454 trie_id in trie
2455 for trie_id in trie_ids), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2456 args=[trie, [id_ab]],
2457 expected=True
2458 ),
2459 # delete 'ab'
2460 TestSpec(
2461 name="[TGT_TR017] trie.remove('ab') (deletes 'ab' from trie)",
2462 action=trie.remove,
2463 args=['ab'],
2464 expected=None
2465 ),
2466 TestSpec(
2467 name="[TGT_TR018] 'ab' not in trie (validate 'ab' not in trie after deletion)",
2468 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2469 args=['ab'],
2470 expected=True
2471 ),
2472 TestSpec(
2473 name="[TGT_TR019] id_ab not in trie (validate id_ab not in trie after deletion)",
2474 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2475 args=[id_ab],
2476 expected=True
2477 ),
2478 TestSpec(
2479 name="[TGT_TR020] trie.remove('a') (deletes 'a' from trie)",
2480 action=trie.remove,
2481 args=['a'],
2482 expected=None
2483 ),
2484 TestSpec(
2485 name="[TGT_TR021] 'a' not in trie (validate 'a' not in trie after deletion)",
2486 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2487 args=['a'],
2488 expected=True
2489 ),
2490 TestSpec(
2491 name="[TGT_TR022] id_a not in trie (validate id_a not in trie after deletion)",
2492 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2493 args=[id_a],
2494 expected=True
2495 ),
2496 TestSpec(
2497 name="[TGT_TR023] len(trie) == 0 (no keys in trie)",
2498 action=len,
2499 args=[trie],
2500 expected=0
2501 ),
2502 # Try to delete 'a' a second time
2503 TestSpec(
2504 name="[TGT_TR024] trie.remove('a') (tried to redelete 'a' from trie)",
2505 action=trie.__delitem__,
2506 args=['a'],
2507 exception=TrieKeyError,
2508 exception_tag=ErrorTag.REMOVAL_KEY_NOT_FOUND
2509 )
2510 ]
2511 run_tests_list(self, tests)
2513 @pytest.mark.order(after=[
2514 'test_create_trie', 'test_trieid_class', 'test_add', 'test_contains_dunder'])
2515 @pytest.mark.dependency(
2516 name='test_delitem',
2517 depends=['test_create_trie', 'test_trieid_class', 'test_add', 'test_contains_dunder'])
2518 def test_delitem_dunder(self) -> None:
2519 """Test the __delitem__ dunder method of GeneralizedTrie."""
2521 trie = GeneralizedTrie()
2522 id_a: TrieId = trie.add("a")
2523 id_ab: TrieId = trie.add("ab")
2524 id_abc: TrieId = trie.add("abc")
2525 id_abcd: TrieId = trie.add("abcd")
2526 id_d: TrieId = trie.add("d")
2527 tests: list[TestSpec] = [
2528 TestSpec(
2529 name="[TGT_TDID01] 'abc' in trie (validate 'abc' in trie before deletion)",
2530 action=lambda key: key in trie, # pyright: ignore[reportUnknownLambdaType]
2531 args=['abc'],
2532 ),
2533 # delete 'abc'
2534 TestSpec(
2535 name="[TGT_TDID02] trie.__delitem__('abc') (deletes 'abc' from trie)",
2536 action=trie.__delitem__,
2537 args=['abc'],
2538 expected=None
2539 ),
2540 TestSpec(
2541 name="[TGT_TDID03] 'abc' not in trie (validate 'abc' not in trie after deletion)",
2542 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2543 args=['abc'],
2544 expected=True
2545 ),
2546 TestSpec(
2547 name="[TGT_TDID04] id_abc not in trie (validate id_abc not in trie after deletion)",
2548 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2549 args=[id_abc],
2550 expected=True
2551 ),
2552 TestSpec(
2553 name=("[TGT_TDID05] all(key in trie for key in ['a', 'ab', 'abcd', 'd']) "
2554 "in trie (validate all other keys still in trie after deletion)"),
2555 action=lambda trie, keys: all( # pyright: ignore[reportUnknownLambdaType]
2556 key in trie for key in keys), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2557 args=[trie, ['a', 'ab', 'abcd', 'd']],
2558 expected=True
2559 ),
2560 TestSpec(
2561 name=("[TGT_TDID06] all(trie_id in trie for trie_id in [id_a, id_ab, id_abcd, id_d]) "
2562 "in trie (validate all other trie ids still in trie after deletion)"),
2563 action=lambda trie, trie_ids: all( # pyright: ignore[reportUnknownLambdaType]
2564 trie_id in trie
2565 for trie_id in trie_ids), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2566 args=[trie, [id_a, id_ab, id_abcd, id_d]],
2567 expected=True
2568 ),
2569 # delete 'd'
2570 TestSpec(
2571 name="[TGT_TDID07] trie.__delitem__('d') (deletes 'd' from trie)",
2572 action=trie.__delitem__,
2573 args=['d'],
2574 expected=None
2575 ),
2576 TestSpec(
2577 name="[TGT_TDID08] 'd' not in trie (validate 'd' not in trie after deletion)",
2578 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2579 args=['d'],
2580 expected=True
2581 ),
2582 TestSpec(
2583 name="[TGT_TDID09] id_d not in trie (validate id_d not in trie after deletion)",
2584 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2585 args=[id_d],
2586 expected=True
2587 ),
2588 TestSpec(
2589 name=("[TGT_TDID10] all(key in trie for key in ['ab', 'abcd']) "
2590 "in trie (validate all other keys still in trie after deletion)"),
2591 action=lambda trie, keys: all( # pyright: ignore[reportUnknownLambdaType]
2592 key in trie for key in keys), # pyright: ignore[reportUnknownVariableType]
2593 args=[trie, ['ab', 'abcd']],
2594 expected=True
2595 ),
2596 TestSpec(
2597 name=("[TGT_TDID11] all(trie_id in trie for trie_id in [id_ab, id_abcd]) "
2598 "in trie (validate all other trie ids still in trie after deletion)"),
2599 action=lambda trie, trie_ids: all( # pyright: ignore[reportUnknownLambdaType]
2600 trie_id in trie
2601 for trie_id in trie_ids), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2602 args=[trie, [id_a, id_ab, id_abcd]],
2603 expected=True
2604 ),
2605 # delete 'abcd'
2606 TestSpec(
2607 name="[TGT_TDID12] trie.__delitem__('abcd') (deletes 'abcd' from trie)",
2608 action=trie.__delitem__,
2609 args=['abcd'],
2610 expected=None
2611 ),
2612 TestSpec(
2613 name="[TGT_TDID13] 'abcd' not in trie (validate 'abcd' not in trie after deletion)",
2614 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2615 args=['abcd'],
2616 expected=True
2617 ),
2618 TestSpec(
2619 name="[TGT_TDID14] id_abcd not in trie (validate id_abcd not in trie after deletion)",
2620 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2621 args=[id_abcd],
2622 expected=True
2623 ),
2624 TestSpec(
2625 name=("[TGT_TDID15] all(key in trie for key in ['ab']) in trie "
2626 "(validate all other keys still in trie after deletion)"),
2627 action=lambda trie, keys: all( # pyright: ignore[reportUnknownLambdaType]
2628 key in trie
2629 for key in keys), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2630 args=[trie, ['ab']],
2631 expected=True
2632 ),
2633 TestSpec(
2634 name=("[TGT_TDID16] all(trie_id in trie for trie_id in [id_ab]) "
2635 "in trie (validate all other trie ids still in trie after deletion)"),
2636 action=lambda trie, trie_ids: all( # pyright: ignore[reportUnknownLambdaType]
2637 trie_id in trie
2638 for trie_id in trie_ids), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2639 args=[trie, [id_ab]],
2640 expected=True
2641 ),
2642 # delete 'ab'
2643 TestSpec(
2644 name="[TGT_TDID17] trie.__delitem__('ab') (deletes 'ab' from trie)",
2645 action=trie.__delitem__,
2646 args=['ab'],
2647 expected=None
2648 ),
2649 TestSpec(
2650 name="[TGT_TDID18] 'ab' not in trie (validate 'ab' not in trie after deletion)",
2651 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2652 args=['ab'],
2653 expected=True
2654 ),
2655 TestSpec(
2656 name="[TGT_TDID19] id_ab not in trie (validate id_ab not in trie after deletion)",
2657 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2658 args=[id_ab],
2659 expected=True
2660 ),
2661 TestSpec(
2662 name="[TGT_TDID20] trie.__delitem__('a') (deletes 'a' from trie)",
2663 action=trie.__delitem__,
2664 args=['a'],
2665 expected=None
2666 ),
2667 TestSpec(
2668 name="[TGT_TDID21] 'a' not in trie (validate 'a' not in trie after deletion)",
2669 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2670 args=['a'],
2671 expected=True
2672 ),
2673 TestSpec(
2674 name="[TGT_TDID22] id_a not in trie (validate id_a not in trie after deletion)",
2675 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2676 args=[id_a],
2677 expected=True
2678 ),
2679 TestSpec(
2680 name="[TGT_TDID23] len(trie) == 0 (no keys in trie)",
2681 action=len,
2682 args=[trie],
2683 expected=0
2684 ),
2685 # Try to delete 'a' a second time
2686 TestSpec(
2687 name="[TGT_TDID24] trie.__delitem__('a') (tried to redelete 'a' from trie)",
2688 action=trie.__delitem__,
2689 args=['a'],
2690 exception=TrieKeyError,
2691 exception_tag=ErrorTag.REMOVAL_KEY_NOT_FOUND
2692 )
2693 ]
2694 run_tests_list(self, tests)
2696 # test using 'del <key>' instead of trie.__delitem__(<key>)
2697 def _helper_for_del(trie: GeneralizedTrie, key: str) -> None:
2698 """Helper function to delete a key from a trie using 'del'."""
2699 del trie[key]
2701 id_a = trie.add("a")
2702 id_abc = trie.add("abc")
2704 tests = [
2705 TestSpec(
2706 name="[TGT_TDID25] 'abc' in trie (validate 'abc' in trie before deletion)",
2707 action=lambda key: key in trie, # pyright: ignore[reportUnknownLambdaType]
2708 args=['abc'],
2709 expected=True
2710 ),
2711 # delete 'abc'
2712 TestSpec(
2713 name="[TGT_TDID26] del trie['abc'] (deletes 'abc' from trie)",
2714 action=_helper_for_del, # pyright: ignore[reportUnknownLambdaType]
2715 args=[trie, 'abc'],
2716 expected=None
2717 ),
2718 TestSpec(
2719 name="[TGT_TDID27] 'abc' not in trie (validate 'abc' not in trie after deletion)",
2720 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2721 args=['abc'],
2722 expected=True
2723 ),
2724 TestSpec(
2725 name="[TGT_TDID28] id_abc not in trie (validate id_abc not in trie after deletion)",
2726 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2727 args=[id_abc],
2728 expected=True
2729 ),
2730 TestSpec(
2731 name="[TGT_TDID29] 'a' in trie (validate 'a' in trie before deletion)",
2732 action=lambda key: key in trie, # pyright: ignore[reportUnknownLambdaType]
2733 args=['a'],
2734 expected=True
2735 ),
2736 # delete 'a' using del trie[id_a]
2737 TestSpec(
2738 name="[TGT_TDID30] del trie[id_a] (deletes 'a' from trie)",
2739 action=_helper_for_del,
2740 args=[trie, id_a],
2741 expected=None
2742 ),
2743 TestSpec(
2744 name="[TGT_TDID31] 'a' not in trie (validate 'a' not in trie after deletion)",
2745 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2746 args=['a'],
2747 expected=True
2748 ),
2749 TestSpec(
2750 name="[TGT_TDID32] id_a not in trie (validate id_a not in trie after deletion)",
2751 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2752 args=[id_a],
2753 expected=True
2754 ),
2755 ]
2756 run_tests_list(self, tests)
2759if __name__ == "__main__":
2760 unittest.main()