Coverage for tests/gentrie/test_gentri.py: 100%
458 statements
« prev ^ index » next coverage.py v7.6.10, created at 2025-08-20 09:57 -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) # pyright: ignore # pylint: disable=unnecessary-dunder-call # noqa: E501
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 @pytest.mark.order(after=['test_create_trie', 'test_add'])
1557 @pytest.mark.dependency(name='test_trie_str', depends=['test_create_trie', 'test_add'])
1558 def test_trie_str(self) -> None:
1559 """Test the string representation of GeneralizedTrie.
1561 This test checks the output of the __str__ method of GeneralizedTrie
1562 for various string inputs. It verifies that the string representation
1563 correctly reflects the structure of the trie, including the children,
1564 parent nodes, and trie IDs.
1566 The test includes multiple scenarios with different string lengths
1567 and ensures that the output matches the expected format."""
1568 trie = GeneralizedTrie()
1569 found: str = dedent(str(trie))
1570 expected: str = dedent("""\
1571 {
1572 trie number = 0
1573 trie index = dict_keys([])
1574 }""")
1575 self.assertEqual(found, expected, msg='[TSTR001] str(trie)')
1577 test_string = 'a'
1578 self.assertIsInstance(test_string, TrieKeyToken)
1579 self.assertIsInstance(test_string, Iterable)
1581 trie.add(test_string)
1582 found: str = dedent(str(trie))
1583 expected: str = dedent("""\
1584 {
1585 trie number = 1
1586 children = {
1587 'a' = {
1588 parent = root node
1589 node token = 'a'
1590 trie id = TrieId(1)
1591 }
1592 }
1593 trie index = dict_keys([TrieId(1)])
1594 }""")
1595 self.assertEqual(found, expected, msg='[TSTR002] str(trie)')
1597 trie = GeneralizedTrie()
1598 test_string = 'ab'
1599 trie.add(test_string)
1600 found = dedent(str(trie))
1601 expected = dedent("""\
1602 {
1603 trie number = 1
1604 children = {
1605 'a' = {
1606 parent = root node
1607 node token = 'a'
1608 children = {
1609 'b' = {
1610 parent = 'a'
1611 node token = 'b'
1612 trie id = TrieId(1)
1613 }
1614 }
1615 }
1616 }
1617 trie index = dict_keys([TrieId(1)])
1618 }""")
1619 self.assertEqual(found, expected, msg='[TSTR003] str(trie))')
1621 trie = GeneralizedTrie()
1622 test_string = 'abc'
1623 trie.add(test_string)
1624 found = dedent(str(trie))
1625 expected = dedent("""\
1626 {
1627 trie number = 1
1628 children = {
1629 'a' = {
1630 parent = root node
1631 node token = 'a'
1632 children = {
1633 'b' = {
1634 parent = 'a'
1635 node token = 'b'
1636 children = {
1637 'c' = {
1638 parent = 'b'
1639 node token = 'c'
1640 trie id = TrieId(1)
1641 }
1642 }
1643 }
1644 }
1645 }
1646 }
1647 trie index = dict_keys([TrieId(1)])
1648 }""")
1649 self.assertEqual(found, expected, msg='[TSTR004] str(trie))')
1651 @pytest.mark.order(after=['test_create_trie', 'test_add', 'test_remove'])
1652 @pytest.mark.dependency(name='test_getitem_dunder', depends=['test_create_trie', 'test_add', 'test_remove'])
1653 def test_getitem_dunder(self) -> None:
1654 """Test the __getitem__ dunder method of GeneralizedTrie.
1656 This test checks whether the trie correctly retrieves values for
1657 existing keys and raises the appropriate errors for non-existing
1658 keys or invalid key types."""
1659 trie: GeneralizedTrie = GeneralizedTrie()
1660 id_ab: TrieId = trie.add("ab", "value for ab")
1661 id_abc: TrieId = trie.add("abc", "another value")
1662 tests: list[TestSpec] = [
1663 TestSpec(
1664 name="[TGT_TGID001] trie.__getitem__(id_abc) (value for existing ID)",
1665 action=trie.__getitem__,
1666 args=[id_abc],
1667 expected=TrieEntry(ident=id_abc, key='abc', value='another value')
1668 ),
1669 TestSpec(
1670 name="[TGT_TGID002] trie.__getitem__('abc') (value for key 'abc')",
1671 action=trie.__getitem__,
1672 args=['abc'],
1673 expected=TrieEntry(ident=id_abc, key='abc', value='another value')
1674 ),
1675 TestSpec(
1676 name="[TGT_TGID003] trie.remove('abc') (remove key 'abc' from trie)",
1677 action=trie.remove,
1678 args=['abc'],
1679 expected=None
1680 ),
1681 TestSpec(
1682 name=("[TGT_TGID004] trie.__getitem__('abc') (non-existent key after removal, "
1683 "TrieKeyError, GETITEM_KEY_NOT_FOUND)"),
1684 action=trie.__getitem__,
1685 args=['abc'],
1686 exception=TrieKeyError,
1687 exception_tag=ErrorTag.GETITEM_KEY_NOT_FOUND
1688 ),
1689 TestSpec(
1690 name=("[TGT_TGID005] trie.__getitem__(id_abc) (non-existent TrieId "
1691 "after removal, TrieKeyError, GETITEM_ID_NOT_FOUND)"),
1692 action=trie.__getitem__,
1693 args=[id_abc],
1694 exception=TrieKeyError,
1695 exception_tag=ErrorTag.GETITEM_ID_NOT_FOUND
1696 ),
1697 TestSpec(
1698 name=("[TGT_TGID006] trie.__getitem__('abc') (Non-existent key, "
1699 "TrieKeyError, GETITEM_KEY_NOT_FOUND)"),
1700 action=trie.__getitem__,
1701 args=['abc'],
1702 exception=TrieKeyError,
1703 exception_tag=ErrorTag.GETITEM_KEY_NOT_FOUND
1704 ),
1705 TestSpec(
1706 name="[TGT_TGID007] trie.__getitem__(set('a')) (TrieTypeError, GETITEM_INVALID_KEY_TYPE)",
1707 action=trie.__getitem__,
1708 args=[set('abc')],
1709 exception=TrieTypeError,
1710 exception_tag=ErrorTag.GETITEM_INVALID_KEY_TYPE
1711 ),
1712 TestSpec(
1713 name="[TGT_TGID008] trie.__getitem__('a') (Non-existent key, TrieKeyError, GETITEM_NOT_TERMINAL)",
1714 action=trie.__getitem__,
1715 args=['a'],
1716 exception=TrieKeyError,
1717 exception_tag=ErrorTag.GETITEM_NOT_TERMINAL
1718 ),
1719 TestSpec(
1720 name="[TGT_TGID009] trie['ab'].value == 'value for ab'",
1721 action=lambda trie, key: trie[key].value, # type: ignore[reportUnknownMemberType]
1722 args=[trie, 'ab'],
1723 expected='value for ab'
1724 ),
1725 TestSpec(
1726 name="[TGT_TGID010] trie[id_ab].value == 'value for ab'",
1727 action=lambda trie, key: trie[key].value, # type: ignore[reportUnknownMemberType]
1728 args=[trie, id_ab],
1729 expected='value for ab'
1730 )
1731 ]
1732 run_tests_list(self, tests)
1734 @pytest.mark.order(after=['test_create_trie', 'test_contains_dunder', 'test_getitem_dunder'])
1735 @pytest.mark.dependency(name='test_setitem_dunder',
1736 depends=['test_create_trie', 'test_contains_dunder', 'test_getitem_dunder'])
1737 def test_setitem_dunder(self) -> None:
1738 """Test the __setitem__ dunder method of GeneralizedTrie.
1740 The __setitem__ dunder method allows assigning values to keys in the trie using
1741 the square bracket notation: trie[<key>] = <value>
1742 """
1743 def _helper_assignment(trie: GeneralizedTrie, key: str, value: str) -> None:
1744 """Helper function to assign a value to a key in the trie.
1746 Args:
1747 trie (GeneralizedTrie): The trie to modify.
1748 key (str): The key to assign the value to.
1749 value (str): The value to assign to the key.
1750 """
1751 trie[key] = value
1753 trie: GeneralizedTrie = GeneralizedTrie()
1755 tests: list[TestSpec] = [
1756 TestSpec(
1757 name="[TGT_TSID001] trie.__setitem__('a', 'value')",
1758 action=trie.__setitem__,
1759 args=['a', 'value'],
1760 expected=None
1761 ),
1762 TestSpec(
1763 name="[TGT_TSID002] 'a' in trie (verify successful insertion with __setitem__)",
1764 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1765 args=['a'],
1766 expected=True
1767 ),
1768 TestSpec(
1769 name="[TGT_TSID003] trie.__setitem__('a', 'value2') (Key already exists, update value)",
1770 action=trie.__setitem__,
1771 args=['a', 'value2'],
1772 expected=None
1773 ),
1774 TestSpec(
1775 name="[TGT_TSID004] trie['a'].value == 'value2' (Key already exists, updated value)",
1776 action=lambda trie, key: trie[key].value, # type: ignore[reportUnknownMemberType]
1777 args=[trie, 'a'],
1778 expected='value2'
1779 ),
1780 TestSpec(
1781 name="[TGT_TSID005] trie['ab'] = 'value3' (Key does not exist, insert new value)",
1782 action=_helper_assignment,
1783 args=[trie, 'ab', 'value3'],
1784 expected=None
1785 ),
1786 TestSpec(
1787 name="[TGT_TSID006] 'ab' in trie (verify successful insertion using trie['ab'] = 'value3')",
1788 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1789 args=['ab'],
1790 expected=True
1791 ),
1792 TestSpec(
1793 name="[TGT_TSID007] trie['ab'] = 'value4' (Key already exists, update value)",
1794 action=_helper_assignment,
1795 args=[trie, 'ab', 'value4'],
1796 expected=None
1797 ),
1798 TestSpec(
1799 name="[TGT_TSID008] trie['ab'].value == 'value4' (Key already exists, updated value)",
1800 action=lambda trie, key: trie[key].value, # type: ignore[reportUnknownMemberType]
1801 args=[trie, 'ab'],
1802 expected='value4'
1803 ),
1804 ]
1805 run_tests_list(self, tests)
1807 @pytest.mark.order(after=['test_create_trie', 'test_add'])
1808 @pytest.mark.dependency(name='test_contains_dunder', depends=['test_create_trie', 'test_add'])
1809 def test_contains_dunder(self) -> None:
1810 """Test the __contains__ dundermethod of GeneralizedTrie.
1812 This test checks whether the trie correctly identifies the presence
1813 or absence of various keys.
1815 The test verifies that the __contains__ dunder method returns the expected
1816 boolean values for each key, ensuring that the trie behaves correctly
1817 when checking for membership."""
1818 trie: GeneralizedTrie = GeneralizedTrie()
1820 tests: list[TestSpec] = [
1821 TestSpec(
1822 name="[TGT_TC001] trie.__contains__() - wrong number of arguments (TypeError)",
1823 action=trie.__contains__,
1824 args=[],
1825 exception=TypeError,
1826 ),
1827 TestSpec(
1828 name="[TGT_TC002] trie.__contains__('a') (false)",
1829 action=trie.__contains__,
1830 args=['a'],
1831 expected=False
1832 ),
1833 TestSpec(
1834 name="[TGT_TC003] 'a' in trie (false)",
1835 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1836 args=['a'],
1837 expected=False
1838 ),
1839 TestSpec(
1840 name="[TGT_TC004] ['a'] in trie (false)",
1841 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1842 args=[['a']],
1843 expected=False
1844 )
1845 ]
1846 run_tests_list(self, tests)
1848 id_a: TrieId = trie.add('a')
1849 tests = [
1850 TestSpec(
1851 name="[TGT_TC005] trie.__contains__('a') (true)",
1852 action=trie.__contains__,
1853 args=['a'],
1854 expected=True
1855 ),
1856 TestSpec(
1857 name="[TGT_TC006] 'a' in trie (true)",
1858 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1859 args=['a'],
1860 expected=True
1861 ),
1862 TestSpec(
1863 name="[TGT_TC007] ['a'] in trie (true)",
1864 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1865 args=[['a']],
1866 expected=True
1867 ),
1868 TestSpec(
1869 name="[TGT_TC008] trie.__contains__(id_a) (true)",
1870 action=trie.__contains__,
1871 args=[id_a],
1872 expected=True
1873 ),
1874 TestSpec(
1875 name="[TGT_TC009] id_a in trie (true)",
1876 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1877 args=[id_a],
1878 expected=True
1879 ),
1880 TestSpec(
1881 name="[TGT_TC010] trie.__contains__('b') (false)",
1882 action=trie.__contains__,
1883 args=['b'],
1884 expected=False
1885 ),
1886 TestSpec(
1887 name="[TGT_TC011] trie.__contains__(['b']) (false)",
1888 action=trie.__contains__,
1889 args=[['b']],
1890 expected=False
1891 ),
1892 TestSpec(
1893 name="[TGT_TC012] 'b' in trie (false)",
1894 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1895 args=['b'],
1896 expected=False
1897 ),
1898 ]
1899 run_tests_list(self, tests)
1901 # Test with different types of keys and a new trie
1902 trie = GeneralizedTrie()
1903 id_list_1: TrieId = trie.add([1])
1904 id_list_none: TrieId = trie.add([None])
1905 tests = [
1906 TestSpec(
1907 name="[TGT_TC013] trie.__contains__(1) (false, int(1) not a valid key type)",
1908 action=trie.__contains__,
1909 args=[1],
1910 expected=False
1911 ),
1912 TestSpec(
1913 name="[TGT_TC014] 1 in trie (false, int(1) not a valid key type)",
1914 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1915 args=[1],
1916 expected=False
1917 ),
1918 TestSpec(
1919 name="[TGT_TC015] trie.__contains__([1]) (true)",
1920 action=trie.__contains__,
1921 args=[[1]],
1922 expected=True
1923 ),
1924 TestSpec(
1925 name="[TGT_TC016] [1] in trie (true)",
1926 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1927 args=[[1]],
1928 expected=True
1929 ),
1930 TestSpec(
1931 name="[TGT_TC0017] trie.__contains__(id_list_1) (true)",
1932 action=trie.__contains__,
1933 args=[id_list_1],
1934 expected=True
1935 ),
1936 TestSpec(
1937 name="[TGT_TC0018] id_list_1 in trie (true)",
1938 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1939 args=[id_list_1],
1940 expected=True
1941 ),
1942 TestSpec(
1943 name="[TGT_TC019] trie.__contains__(None) (false, None is not a valid key type)",
1944 action=trie.__contains__,
1945 args=[None],
1946 expected=False
1947 ),
1948 TestSpec(
1949 name="[TGT_TC020] None in trie (false, None is not a valid key type)",
1950 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1951 args=[None],
1952 expected=False
1953 ),
1954 TestSpec(
1955 name="[TGT_TC021] trie.__contains__([None]) (true)",
1956 action=trie.__contains__,
1957 args=[[None]],
1958 expected=True
1959 ),
1960 TestSpec(
1961 name="[TGT_TC022] [None] in trie (true)",
1962 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1963 args=[[None]],
1964 expected=True
1965 ),
1966 TestSpec(
1967 name="[TGT_TC023] trie.__contains__(id_list_none) (true)",
1968 action=trie.__contains__,
1969 args=[id_list_none],
1970 expected=True
1971 ),
1972 TestSpec(
1973 name="[TGT_TC024] id_list_none in trie (true)",
1974 action=lambda key: key in trie, # type: ignore[reportUnknownMemberType]
1975 args=[id_list_none],
1976 expected=True
1977 ),
1978 ]
1979 run_tests_list(self, tests)
1981 # String key tests
1982 trie = GeneralizedTrie()
1983 id_str_abc: TrieId = trie.add('abc')
1984 tests = [
1985 TestSpec(
1986 name="[TGT_TC027] trie.__contains__('abcd') (false, 'abcd' not in trie)",
1987 action=trie.__contains__,
1988 args=['abcd'],
1989 expected=False
1990 ),
1991 TestSpec(
1992 name="[TGT_TC028] trie.__contains__('abc') (true, 'abc' in trie)",
1993 action=trie.__contains__,
1994 args=['abc'],
1995 expected=True
1996 ),
1997 TestSpec(
1998 name="[TGT_TC029] trie.__contains__(id_str_abc) (true, TrieId id_str_abc in trie)",
1999 action=trie.__contains__,
2000 args=[id_str_abc],
2001 expected=True
2002 ),
2003 TestSpec(
2004 name="[TGT_TC030] trie.__contains__('ab') (false, prefix 'ab' not a key in trie)",
2005 action=trie.__contains__,
2006 args=['ab'],
2007 expected=False
2008 ),
2009 TestSpec(
2010 name="[TGT_TC031] trie.__contains__('a') (false, prefix 'a' not a key in trie)",
2011 action=trie.__contains__,
2012 args=['a'],
2013 expected=False
2014 ),
2015 TestSpec(
2016 name="[TGT_TC032] trie.__contains__('') (false, empty string not a key in trie)",
2017 action=trie.__contains__,
2018 args=[''],
2019 expected=False
2020 ),
2022 ]
2023 run_tests_list(self, tests)
2025 @pytest.mark.order(after=['test_create_trie', 'test_add', 'test_remove'])
2026 @pytest.mark.dependency(name='test_get', depends=['test_create_trie', 'test_add', 'test_remove'])
2027 def test_get(self) -> None:
2028 """Test the get method of GeneralizedTrie.
2030 This test checks whether the trie correctly retrieves values for
2031 existing keys, applies default values or raises the appropriate errors for non-existing
2032 keys or invalid key types."""
2033 trie: GeneralizedTrie = GeneralizedTrie()
2034 id_ab: TrieId = trie.add("ab", "value for ab")
2035 id_abc: TrieId = trie.add("abc", "another value")
2036 tests: list[TestSpec] = [
2037 TestSpec(
2038 name="[TGT_TG001] trie.get(id_abc) (value for existing ID)",
2039 action=trie.get,
2040 args=[id_abc],
2041 expected=TrieEntry(ident=id_abc, key='abc', value='another value')
2042 ),
2043 TestSpec(
2044 name="[TGT_TG002] trie.get('abc') (value for key 'abc')",
2045 action=trie.get,
2046 args=['abc'],
2047 expected=TrieEntry(ident=id_abc, key='abc', value='another value')
2048 ),
2049 TestSpec(
2050 name="[TGT_TG003] trie.remove('abc') (remove key 'abc' from trie)",
2051 action=trie.remove,
2052 args=['abc'],
2053 expected=None
2054 ),
2055 TestSpec(
2056 name=("[TGT_TG004] trie.get('abc') (non-existent key after removal, default is None"),
2057 action=trie.get,
2058 args=['abc'],
2059 expected=None
2060 ),
2061 TestSpec(
2062 name=("[TGT_TG005] trie.get(id_abc) (non-existent TrieId after removal, default is None)"),
2063 action=trie.get,
2064 args=[id_abc],
2065 expected=None
2066 ),
2067 TestSpec(
2068 name="[TGT_TG006] trie.get(set('abc')) (bad key type -> default value None)",
2069 action=trie.get,
2070 args=[set('abc')],
2071 expected=None
2072 ),
2073 TestSpec(
2074 name="[TGT_TG007] trie.get('a') (Non-existent partial key -> default value None)",
2075 action=trie.get,
2076 args=['a'],
2077 expected=None
2078 ),
2079 TestSpec(
2080 name="[TGT_TG008] trie.get('ab').value == 'value for ab'",
2081 action=lambda trie, key: trie[key].value, # type: ignore[reportUnknownMemberType]
2082 args=[trie, 'ab'],
2083 expected='value for ab'
2084 ),
2085 TestSpec(
2086 name="[TGT_TG009] trie.get(id_ab).value == 'value for ab'",
2087 action=lambda trie, key: trie[key].value, # type: ignore[reportUnknownMemberType]
2088 args=[trie, id_ab],
2089 expected='value for ab'
2090 ),
2092 TestSpec(
2093 name=("[TGT_TG010] trie.get('abc', 'bleh') (non-existent key after removal, default is 'bleh'"),
2094 action=trie.get,
2095 args=['abc', 'bleh'],
2096 expected='bleh'
2097 ),
2098 TestSpec(
2099 name=("[TGT_TG011] trie.get(id_abc, 'bleh') (non-existent TrieId after removal, default is 'bleh')"),
2100 action=trie.get,
2101 args=[id_abc, 'bleh'],
2102 expected='bleh'
2103 ),
2104 TestSpec(
2105 name="[TGT_TG012] trie.get(set('abc'), 'bleh') (bad key type -> default value 'bleh')",
2106 action=trie.get,
2107 args=[set('abc'), 'bleh'],
2108 expected='bleh'
2109 ),
2110 TestSpec(
2111 name="[TGT_TG013] trie.get('a', 'bleh') (Non-existent partial key -> default value 'bleh')",
2112 action=trie.get,
2113 args=['a', 'bleh'],
2114 expected='bleh'
2115 )
2116 ]
2117 run_tests_list(self, tests)
2119 @pytest.mark.order(after='test_remove')
2120 @pytest.mark.dependency(name='test_keys', depends=[
2121 'test_create_trie', 'test_add', 'test_contains_dunder', 'test_remove'])
2122 def test_keys(self) -> None:
2123 """Test the keys method of GeneralizedTrie.
2125 This test checks the functionality of the keys method, which should
2126 return an iterable of TrieId objects representing the keys in the trie.
2128 The test includes scenarios for an empty trie, adding keys, and
2129 removing keys. It verifies that the keys method returns the expected
2130 TrieId objects in the correct order."""
2131 trie: GeneralizedTrie = GeneralizedTrie()
2133 with self.subTest(msg="[TK001] trie.keys()"):
2134 expect_id_list: list[TrieId] = []
2135 found_id_list: list[TrieId] = list(trie.keys())
2136 self.assertEqual(found_id_list, expect_id_list)
2138 with self.subTest(msg="[TK002] trie.add('abcdef')"):
2139 expect_id: TrieId = TrieId(1)
2140 found_id: TrieId = trie.add("abcdef")
2141 self.assertEqual(found_id, expect_id)
2143 with self.subTest(msg="[TK003] trie.keys()"):
2144 expect_id_list: list[TrieId] = [TrieId(1)]
2145 found_id_list: list[TrieId] = list(trie.keys())
2146 self.assertEqual(found_id_list, expect_id_list)
2148 with self.subTest(msg="[TK004] trie.add('abc')"):
2149 expect_id = TrieId(2)
2150 found_id = trie.add("abc")
2151 self.assertEqual(found_id, expect_id)
2153 with self.subTest(msg="[TK005] trie.keys()"):
2154 expect_id_list = [TrieId(1), TrieId(2)]
2155 found_id_list = list(sorted(trie.keys()))
2156 self.assertEqual(found_id_list, expect_id_list)
2158 with self.assertRaises(TypeError, msg="[TK006] trie.remove('abc')"):
2159 trie.remove(set('abc')) # type: ignore[reportGeneralTypeIssues]
2161 with self.subTest(msg="[TK007] trie.remove(TrieId(1))"):
2162 trie.remove(TrieId(1))
2163 expect_id_list = [TrieId(2)]
2164 found_id_list = list(trie.keys())
2165 self.assertEqual(found_id_list, expect_id_list)
2167 with self.subTest(msg="[TK008] trie.remove(TrieId(2))"):
2168 trie.remove(TrieId(2))
2169 expect_id_list = []
2170 found_id_list = list(trie.keys())
2171 self.assertEqual(found_id_list, expect_id_list)
2173 @pytest.mark.order(after='test_add')
2174 @pytest.mark.dependency(name='test_values', depends=['test_create_trie', 'test_trieid_class', 'test_add'])
2175 def test_values(self) -> None:
2176 """Test the values method of GeneralizedTrie.
2178 This test checks the functionality of the values method, which should
2179 return an iterable of TrieEntry objects representing the values in the trie.
2180 The test includes scenarios for an empty trie, adding entries, and
2181 removing entries. It verifies that the values method returns the expected
2182 TrieEntry objects in the correct order.
2183 It also checks that the values method behaves correctly when entries are
2184 added and removed, ensuring that the trie maintains its integrity."""
2185 trie: GeneralizedTrie = GeneralizedTrie()
2187 with self.subTest(msg="[TV001] trie.values()"):
2188 expect_entries_list: list[TrieEntry] = []
2189 found_entries_list: list[TrieEntry] = list(trie.values())
2190 self.assertEqual(found_entries_list, expect_entries_list)
2192 with self.subTest(msg="[TV002] trie.add('abcdef')"):
2193 expect_id: TrieId = TrieId(1)
2194 found_id: TrieId = trie.add("abcdef")
2195 self.assertEqual(found_id, expect_id)
2197 with self.subTest(msg="[TV003] trie.values()"):
2198 expect_entries_list = [TrieEntry(TrieId(1), 'abcdef')]
2199 found_entries_list = list(trie.values())
2200 self.assertEqual(found_entries_list, expect_entries_list)
2202 with self.subTest(msg="[TV004] trie.add('abc')"):
2203 expect_id = TrieId(2)
2204 found_id = trie.add("abc")
2205 self.assertEqual(found_id, expect_id)
2207 with self.subTest(msg="[TV005] trie.values()"):
2208 expect_entries_list = [TrieEntry(TrieId(1), 'abcdef'), TrieEntry(TrieId(2), 'abc')]
2209 found_entries_list = list(sorted(trie.values()))
2210 self.assertEqual(found_entries_list, expect_entries_list)
2212 with self.subTest(msg="[TV006] trie.remove(TrieId(1))"):
2213 trie.remove(TrieId(1))
2214 expect_entries_list = [TrieEntry(TrieId(2), 'abc')]
2215 found_entries_list = list(trie.values())
2216 self.assertEqual(found_entries_list, expect_entries_list)
2218 with self.subTest(msg="[TV007] trie.remove(TrieId(2))"):
2219 trie.remove(TrieId(2))
2220 expect_entries_list = []
2221 found_entries_list = list(trie.values())
2222 self.assertEqual(found_entries_list, expect_entries_list)
2224 def test_items(self) -> None:
2225 """Test the items method of GeneralizedTrie.
2227 This test checks the functionality of the items method, which should
2228 return an iterable of tuples containing TrieId and TrieEntry objects.
2229 The test includes scenarios for an empty trie, adding entries, and
2230 removing entries. It verifies that the items method returns the expected
2231 tuples in the correct order.
2232 It also checks that the items method behaves correctly when entries are
2233 added and removed, ensuring that the trie maintains its integrity."""
2234 trie: GeneralizedTrie = GeneralizedTrie()
2236 with self.subTest(msg="[TI001] trie.items()"):
2237 expect_items_list: list[tuple[TrieId, TrieEntry]] = []
2238 found_items_list: list[tuple[TrieId, TrieEntry]] = list(trie.items())
2239 self.assertEqual(found_items_list, expect_items_list)
2241 with self.subTest(msg="[TI002] trie.add('abcdef')"):
2242 expect_id: TrieId = TrieId(1)
2243 found_id: TrieId = trie.add("abcdef")
2244 self.assertEqual(found_id, expect_id)
2246 with self.subTest(msg="[TI003] trie.items()"):
2247 expect_items_list = [(TrieId(1), TrieEntry(TrieId(1), 'abcdef'))]
2248 found_items_list = list(sorted(trie.items()))
2249 self.assertEqual(found_items_list, expect_items_list)
2251 with self.subTest(msg="[TI004] trie.add('abc')"):
2252 expect_id = TrieId(2)
2253 found_id = trie.add("abc")
2254 self.assertEqual(found_id, expect_id)
2256 with self.subTest(msg="[TI005] trie.items()"):
2257 expect_items_list = [
2258 (TrieId(1), TrieEntry(TrieId(1), 'abcdef')),
2259 (TrieId(2), TrieEntry(TrieId(2), 'abc'))]
2260 found_items_list = list(sorted(trie.items()))
2261 self.assertEqual(found_items_list, expect_items_list)
2263 with self.subTest(msg="[TI006] trie.remove(TrieId(1))"):
2264 trie.remove(TrieId(1))
2265 expect_items_list = [(TrieId(2), TrieEntry(TrieId(2), 'abc'))]
2266 found_items_list = list(sorted(trie.items()))
2267 self.assertEqual(found_items_list, expect_items_list)
2269 with self.subTest(msg="[TI007] trie.remove(TrieId(2))"):
2270 trie.remove(TrieId(2))
2271 expect_items_list = []
2272 found_items_list = list(sorted(trie.items()))
2273 self.assertEqual(found_items_list, expect_items_list)
2275 def test_iter(self) -> None:
2276 """Test the iteration over GeneralizedTrie."""
2277 trie: GeneralizedTrie = GeneralizedTrie()
2279 with self.subTest(msg="[TITER001] for entry in trie:"):
2280 expect_ids_list: list[TrieId] = []
2281 found_ids_list: list[TrieId] = []
2282 found_ids_list.extend([ident for ident in trie]) # pylint: disable=unnecessary-comprehension
2283 self.assertEqual(found_ids_list, expect_ids_list)
2285 with self.subTest(msg="[TITER002] trie.add('abcdef')"):
2286 expect_id: TrieId = TrieId(1)
2287 found_id: TrieId = trie.add("abcdef")
2288 self.assertEqual(found_id, expect_id)
2290 with self.subTest(msg="[TITER003] for ident in trie:"):
2291 expect_ids_list = [TrieId(1)]
2292 found_ids_list = []
2293 for ident in trie:
2294 found_ids_list.append(ident)
2295 self.assertEqual(sorted(found_ids_list), expect_ids_list)
2297 with self.subTest(msg="[TITER004] trie.add('abc')"):
2298 expect_id = TrieId(2)
2299 found_id = trie.add("abc")
2300 self.assertEqual(found_id, expect_id)
2302 with self.subTest(msg="[TITER005] for entry in trie:"):
2303 expect_ids_list: list[TrieId] = [TrieId(1), TrieId(2)]
2304 found_ids_list: list[TrieId] = []
2305 for entry in trie:
2306 found_ids_list.append(entry)
2307 self.assertEqual(sorted(found_ids_list), expect_ids_list)
2309 @pytest.mark.order(after='test_remove')
2310 @pytest.mark.dependency(name='test_bool', depends=['test_create_trie', 'test_add', 'test_remove'])
2311 def test_bool(self) -> None:
2312 """Test the __bool__ method of GeneralizedTrie.
2314 This test checks the functionality of the __bool__ method, which should
2315 return True if the trie contains any entries, and False if it is empty.
2316 The test includes scenarios for an empty trie, adding entries, and removing
2317 entries. It verifies that the __bool__ method returns the expected boolean
2318 values for each scenario, ensuring that the trie behaves correctly when
2319 checking its truthiness."""
2320 trie = GeneralizedTrie()
2321 tests: list[TestSpec] = [
2322 TestSpec(
2323 name="[TB001] bool(trie)", action=bool, args=[trie], expected=False
2324 ),
2325 TestSpec(
2326 name="[TB002] trie.add('a')", action=trie.add, args=["a"], expected=TrieId(1)
2327 ),
2328 TestSpec(
2329 name="[TB003] bool(trie)", action=bool, args=[trie], expected=True
2330 ),
2331 TestSpec(
2332 name="[TB004] trie.remove(TrieId(1))", action=trie.remove, args=[TrieId(1)], expected=None
2333 ),
2334 TestSpec(
2335 name="[TB005] bool(trie)", action=bool, args=[trie], expected=False
2336 ),
2337 ]
2338 run_tests_list(self, tests)
2340 @pytest.mark.order(after=[
2341 'test_create_trie', 'test_trieid_class', 'test_add', 'test_contains_dunder'])
2342 @pytest.mark.dependency(
2343 name='test_remove',
2344 depends=['test_create_trie', 'test_trieid_class', 'test_add', 'test_contains_dunder'])
2345 def test_remove(self) -> None:
2346 """Test the remove method of GeneralizedTrie."""
2347 trie = GeneralizedTrie()
2348 id_a: TrieId = trie.add("a")
2349 id_ab: TrieId = trie.add("ab")
2350 id_abc: TrieId = trie.add("abc")
2351 id_abcd: TrieId = trie.add("abcd")
2352 id_d: TrieId = trie.add("d")
2353 tests: list[TestSpec] = [
2354 TestSpec(
2355 name="[TGT_TR001] 'abc' in trie (validate 'abc' in trie before deletion)",
2356 action=lambda key: key in trie, # pyright: ignore[reportUnknownLambdaType]
2357 args=['abc'],
2358 ),
2359 # delete 'abc'
2360 TestSpec(
2361 name="[TGT_TR002] trie.remove('abc') (deletes 'abc' from trie)",
2362 action=trie.remove,
2363 args=['abc'],
2364 expected=None
2365 ),
2366 TestSpec(
2367 name="[TGT_TR003] 'abc' not in trie (validate 'abc' not in trie after deletion)",
2368 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2369 args=['abc'],
2370 expected=True
2371 ),
2372 TestSpec(
2373 name="[TGT_TR004] id_abc not in trie (validate id_abc not in trie after deletion)",
2374 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2375 args=[id_abc],
2376 expected=True
2377 ),
2378 TestSpec(
2379 name=("[TGT_TR005] all(key in trie for key in ['a', 'ab', 'abcd', 'd']) "
2380 "in trie (validate all other keys still in trie after deletion)"),
2381 action=lambda trie, keys: all( # pyright: ignore[reportUnknownLambdaType]
2382 key in trie for key in keys), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2383 args=[trie, ['a', 'ab', 'abcd', 'd']],
2384 expected=True
2385 ),
2386 TestSpec(
2387 name=("[TGT_TR006] all(trie_id in trie for trie_id in [id_a, id_ab, id_abcd, id_d]) "
2388 "in trie (validate all other trie ids still in trie after deletion)"),
2389 action=lambda trie, trie_ids: all( # pyright: ignore[reportUnknownLambdaType]
2390 trie_id in trie
2391 for trie_id in trie_ids), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2392 args=[trie, [id_a, id_ab, id_abcd, id_d]],
2393 expected=True
2394 ),
2395 # delete 'd'
2396 TestSpec(
2397 name="[TGT_TR007] trie.remove('d') (deletes 'd' from trie)",
2398 action=trie.remove,
2399 args=['d'],
2400 expected=None
2401 ),
2402 TestSpec(
2403 name="[TGT_TR008] 'd' not in trie (validate 'd' not in trie after deletion)",
2404 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2405 args=['d'],
2406 expected=True
2407 ),
2408 TestSpec(
2409 name="[TGT_TR009] id_d not in trie (validate id_d not in trie after deletion)",
2410 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2411 args=[id_d],
2412 expected=True
2413 ),
2414 TestSpec(
2415 name=("[TGT_TR010] all(key in trie for key in ['ab', 'abcd']) "
2416 "in trie (validate all other keys still in trie after deletion)"),
2417 action=lambda trie, keys: all( # pyright: ignore[reportUnknownLambdaType]
2418 key in trie for key in keys), # pyright: ignore[reportUnknownVariableType]
2419 args=[trie, ['ab', 'abcd']],
2420 expected=True
2421 ),
2422 TestSpec(
2423 name=("[TGT_TR011] all(trie_id in trie for trie_id in [id_ab, id_abcd]) "
2424 "in trie (validate all other trie ids still in trie after deletion)"),
2425 action=lambda trie, trie_ids: all( # pyright: ignore[reportUnknownLambdaType]
2426 trie_id in trie
2427 for trie_id in trie_ids), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2428 args=[trie, [id_a, id_ab, id_abcd]],
2429 expected=True
2430 ),
2431 # delete 'abcd'
2432 TestSpec(
2433 name="[TGT_TR012] trie.remove('abcd') (deletes 'abcd' from trie)",
2434 action=trie.remove,
2435 args=['abcd'],
2436 expected=None
2437 ),
2438 TestSpec(
2439 name="[TGT_TR013] 'abcd' not in trie (validate 'abcd' not in trie after deletion)",
2440 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2441 args=['abcd'],
2442 expected=True
2443 ),
2444 TestSpec(
2445 name="[TGT_TR014] id_abcd not in trie (validate id_abcd not in trie after deletion)",
2446 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2447 args=[id_abcd],
2448 expected=True
2449 ),
2450 TestSpec(
2451 name=("[TGT_TR015] all(key in trie for key in ['ab']) in trie "
2452 "(validate all other keys still in trie after deletion)"),
2453 action=lambda trie, keys: all( # pyright: ignore[reportUnknownLambdaType]
2454 key in trie
2455 for key in keys), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2456 args=[trie, ['ab']],
2457 expected=True
2458 ),
2459 TestSpec(
2460 name=("[TGT_TR016] all(trie_id in trie for trie_id in [id_ab]) "
2461 "in trie (validate all other trie ids still in trie after deletion)"),
2462 action=lambda trie, trie_ids: all( # pyright: ignore[reportUnknownLambdaType]
2463 trie_id in trie
2464 for trie_id in trie_ids), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2465 args=[trie, [id_ab]],
2466 expected=True
2467 ),
2468 # delete 'ab'
2469 TestSpec(
2470 name="[TGT_TR017] trie.remove('ab') (deletes 'ab' from trie)",
2471 action=trie.remove,
2472 args=['ab'],
2473 expected=None
2474 ),
2475 TestSpec(
2476 name="[TGT_TR018] 'ab' not in trie (validate 'ab' not in trie after deletion)",
2477 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2478 args=['ab'],
2479 expected=True
2480 ),
2481 TestSpec(
2482 name="[TGT_TR019] id_ab not in trie (validate id_ab not in trie after deletion)",
2483 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2484 args=[id_ab],
2485 expected=True
2486 ),
2487 TestSpec(
2488 name="[TGT_TR020] trie.remove('a') (deletes 'a' from trie)",
2489 action=trie.remove,
2490 args=['a'],
2491 expected=None
2492 ),
2493 TestSpec(
2494 name="[TGT_TR021] 'a' not in trie (validate 'a' not in trie after deletion)",
2495 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2496 args=['a'],
2497 expected=True
2498 ),
2499 TestSpec(
2500 name="[TGT_TR022] id_a not in trie (validate id_a not in trie after deletion)",
2501 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2502 args=[id_a],
2503 expected=True
2504 ),
2505 TestSpec(
2506 name="[TGT_TR023] len(trie) == 0 (no keys in trie)",
2507 action=len,
2508 args=[trie],
2509 expected=0
2510 ),
2511 # Try to delete 'a' a second time
2512 TestSpec(
2513 name="[TGT_TR024] trie.remove('a') (tried to redelete 'a' from trie)",
2514 action=trie.__delitem__,
2515 args=['a'],
2516 exception=TrieKeyError,
2517 exception_tag=ErrorTag.REMOVAL_KEY_NOT_FOUND
2518 )
2519 ]
2520 run_tests_list(self, tests)
2522 @pytest.mark.order(after=[
2523 'test_create_trie', 'test_trieid_class', 'test_add', 'test_contains_dunder'])
2524 @pytest.mark.dependency(
2525 name='test_delitem',
2526 depends=['test_create_trie', 'test_trieid_class', 'test_add', 'test_contains_dunder'])
2527 def test_delitem_dunder(self) -> None:
2528 """Test the __delitem__ dunder method of GeneralizedTrie."""
2530 trie = GeneralizedTrie()
2531 id_a: TrieId = trie.add("a")
2532 id_ab: TrieId = trie.add("ab")
2533 id_abc: TrieId = trie.add("abc")
2534 id_abcd: TrieId = trie.add("abcd")
2535 id_d: TrieId = trie.add("d")
2536 tests: list[TestSpec] = [
2537 TestSpec(
2538 name="[TGT_TDID01] 'abc' in trie (validate 'abc' in trie before deletion)",
2539 action=lambda key: key in trie, # pyright: ignore[reportUnknownLambdaType]
2540 args=['abc'],
2541 ),
2542 # delete 'abc'
2543 TestSpec(
2544 name="[TGT_TDID02] trie.__delitem__('abc') (deletes 'abc' from trie)",
2545 action=trie.__delitem__,
2546 args=['abc'],
2547 expected=None
2548 ),
2549 TestSpec(
2550 name="[TGT_TDID03] 'abc' not in trie (validate 'abc' not in trie after deletion)",
2551 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2552 args=['abc'],
2553 expected=True
2554 ),
2555 TestSpec(
2556 name="[TGT_TDID04] id_abc not in trie (validate id_abc not in trie after deletion)",
2557 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2558 args=[id_abc],
2559 expected=True
2560 ),
2561 TestSpec(
2562 name=("[TGT_TDID05] all(key in trie for key in ['a', 'ab', 'abcd', 'd']) "
2563 "in trie (validate all other keys still in trie after deletion)"),
2564 action=lambda trie, keys: all( # pyright: ignore[reportUnknownLambdaType]
2565 key in trie for key in keys), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2566 args=[trie, ['a', 'ab', 'abcd', 'd']],
2567 expected=True
2568 ),
2569 TestSpec(
2570 name=("[TGT_TDID06] all(trie_id in trie for trie_id in [id_a, id_ab, id_abcd, id_d]) "
2571 "in trie (validate all other trie ids still in trie after deletion)"),
2572 action=lambda trie, trie_ids: all( # pyright: ignore[reportUnknownLambdaType]
2573 trie_id in trie
2574 for trie_id in trie_ids), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2575 args=[trie, [id_a, id_ab, id_abcd, id_d]],
2576 expected=True
2577 ),
2578 # delete 'd'
2579 TestSpec(
2580 name="[TGT_TDID07] trie.__delitem__('d') (deletes 'd' from trie)",
2581 action=trie.__delitem__,
2582 args=['d'],
2583 expected=None
2584 ),
2585 TestSpec(
2586 name="[TGT_TDID08] 'd' not in trie (validate 'd' not in trie after deletion)",
2587 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2588 args=['d'],
2589 expected=True
2590 ),
2591 TestSpec(
2592 name="[TGT_TDID09] id_d not in trie (validate id_d not in trie after deletion)",
2593 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2594 args=[id_d],
2595 expected=True
2596 ),
2597 TestSpec(
2598 name=("[TGT_TDID10] all(key in trie for key in ['ab', 'abcd']) "
2599 "in trie (validate all other keys still in trie after deletion)"),
2600 action=lambda trie, keys: all( # pyright: ignore[reportUnknownLambdaType]
2601 key in trie for key in keys), # pyright: ignore[reportUnknownVariableType]
2602 args=[trie, ['ab', 'abcd']],
2603 expected=True
2604 ),
2605 TestSpec(
2606 name=("[TGT_TDID11] all(trie_id in trie for trie_id in [id_ab, id_abcd]) "
2607 "in trie (validate all other trie ids still in trie after deletion)"),
2608 action=lambda trie, trie_ids: all( # pyright: ignore[reportUnknownLambdaType]
2609 trie_id in trie
2610 for trie_id in trie_ids), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2611 args=[trie, [id_a, id_ab, id_abcd]],
2612 expected=True
2613 ),
2614 # delete 'abcd'
2615 TestSpec(
2616 name="[TGT_TDID12] trie.__delitem__('abcd') (deletes 'abcd' from trie)",
2617 action=trie.__delitem__,
2618 args=['abcd'],
2619 expected=None
2620 ),
2621 TestSpec(
2622 name="[TGT_TDID13] 'abcd' not in trie (validate 'abcd' not in trie after deletion)",
2623 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2624 args=['abcd'],
2625 expected=True
2626 ),
2627 TestSpec(
2628 name="[TGT_TDID14] id_abcd not in trie (validate id_abcd not in trie after deletion)",
2629 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2630 args=[id_abcd],
2631 expected=True
2632 ),
2633 TestSpec(
2634 name=("[TGT_TDID15] all(key in trie for key in ['ab']) in trie "
2635 "(validate all other keys still in trie after deletion)"),
2636 action=lambda trie, keys: all( # pyright: ignore[reportUnknownLambdaType]
2637 key in trie
2638 for key in keys), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2639 args=[trie, ['ab']],
2640 expected=True
2641 ),
2642 TestSpec(
2643 name=("[TGT_TDID16] all(trie_id in trie for trie_id in [id_ab]) "
2644 "in trie (validate all other trie ids still in trie after deletion)"),
2645 action=lambda trie, trie_ids: all( # pyright: ignore[reportUnknownLambdaType]
2646 trie_id in trie
2647 for trie_id in trie_ids), # pyright: ignore[reportUnknownLambdaType, reportUnknownVariableType]
2648 args=[trie, [id_ab]],
2649 expected=True
2650 ),
2651 # delete 'ab'
2652 TestSpec(
2653 name="[TGT_TDID17] trie.__delitem__('ab') (deletes 'ab' from trie)",
2654 action=trie.__delitem__,
2655 args=['ab'],
2656 expected=None
2657 ),
2658 TestSpec(
2659 name="[TGT_TDID18] 'ab' not in trie (validate 'ab' not in trie after deletion)",
2660 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2661 args=['ab'],
2662 expected=True
2663 ),
2664 TestSpec(
2665 name="[TGT_TDID19] id_ab not in trie (validate id_ab not in trie after deletion)",
2666 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2667 args=[id_ab],
2668 expected=True
2669 ),
2670 TestSpec(
2671 name="[TGT_TDID20] trie.__delitem__('a') (deletes 'a' from trie)",
2672 action=trie.__delitem__,
2673 args=['a'],
2674 expected=None
2675 ),
2676 TestSpec(
2677 name="[TGT_TDID21] 'a' not in trie (validate 'a' not in trie after deletion)",
2678 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2679 args=['a'],
2680 expected=True
2681 ),
2682 TestSpec(
2683 name="[TGT_TDID22] id_a not in trie (validate id_a not in trie after deletion)",
2684 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2685 args=[id_a],
2686 expected=True
2687 ),
2688 TestSpec(
2689 name="[TGT_TDID23] len(trie) == 0 (no keys in trie)",
2690 action=len,
2691 args=[trie],
2692 expected=0
2693 ),
2694 # Try to delete 'a' a second time
2695 TestSpec(
2696 name="[TGT_TDID24] trie.__delitem__('a') (tried to redelete 'a' from trie)",
2697 action=trie.__delitem__,
2698 args=['a'],
2699 exception=TrieKeyError,
2700 exception_tag=ErrorTag.REMOVAL_KEY_NOT_FOUND
2701 )
2702 ]
2703 run_tests_list(self, tests)
2705 # test using 'del <key>' instead of trie.__delitem__(<key>)
2706 def _helper_for_del(trie: GeneralizedTrie, key: str) -> None:
2707 """Helper function to delete a key from a trie using 'del'."""
2708 del trie[key]
2710 id_a = trie.add("a")
2711 id_abc = trie.add("abc")
2713 tests = [
2714 TestSpec(
2715 name="[TGT_TDID25] 'abc' in trie (validate 'abc' in trie before deletion)",
2716 action=lambda key: key in trie, # pyright: ignore[reportUnknownLambdaType]
2717 args=['abc'],
2718 expected=True
2719 ),
2720 # delete 'abc'
2721 TestSpec(
2722 name="[TGT_TDID26] del trie['abc'] (deletes 'abc' from trie)",
2723 action=_helper_for_del, # pyright: ignore[reportUnknownLambdaType]
2724 args=[trie, 'abc'],
2725 expected=None
2726 ),
2727 TestSpec(
2728 name="[TGT_TDID27] 'abc' not in trie (validate 'abc' not in trie after deletion)",
2729 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2730 args=['abc'],
2731 expected=True
2732 ),
2733 TestSpec(
2734 name="[TGT_TDID28] id_abc not in trie (validate id_abc not in trie after deletion)",
2735 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2736 args=[id_abc],
2737 expected=True
2738 ),
2739 TestSpec(
2740 name="[TGT_TDID29] 'a' in trie (validate 'a' in trie before deletion)",
2741 action=lambda key: key in trie, # pyright: ignore[reportUnknownLambdaType]
2742 args=['a'],
2743 expected=True
2744 ),
2745 # delete 'a' using del trie[id_a]
2746 TestSpec(
2747 name="[TGT_TDID30] del trie[id_a] (deletes 'a' from trie)",
2748 action=_helper_for_del,
2749 args=[trie, id_a],
2750 expected=None
2751 ),
2752 TestSpec(
2753 name="[TGT_TDID31] 'a' not in trie (validate 'a' not in trie after deletion)",
2754 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2755 args=['a'],
2756 expected=True
2757 ),
2758 TestSpec(
2759 name="[TGT_TDID32] id_a not in trie (validate id_a not in trie after deletion)",
2760 action=lambda key: key not in trie, # pyright: ignore[reportUnknownLambdaType]
2761 args=[id_a],
2762 expected=True
2763 ),
2764 ]
2765 run_tests_list(self, tests)
2768if __name__ == "__main__":
2769 unittest.main()