# Lab #7: Tries & String Prefixes

### Objective

During this activity, students will be able to:

• Implement various operations for the trie (prefix tree) data structure.

## Description

This activity must be developed in the pre-assigned teams of two.

Starting from the code in the tries.py file created in class, add the methods described below to the Trie class:

•  def __len__(self) -> int: 

Magic method that returns the total number of keys contained in this trie.

Examples:

>>> t: Trie[int] = Trie()
>>> len(t)
0
>>> t.insert('bit', 0)
>>> t.insert('bicycle', 2)
>>> t.insert('byte', 8)
>>> len(t)
3
>>> t.insert('byte', 16)
>>> len(t)
3
>>> t.remove('bit')
True
>>> t.remove('bye')
False
>>> len(t)
2

•  def items(self) -> list[tuple[str, T]]: 

Returns a list of tuples, where each tuple contains a key from the trie together with its associated value. The tuples should be in key ascending order.

Example:

>>> t: Trie[int] = Trie()
>>> t.insert('bit', 0)
>>> t.insert('byte', 8)
>>> t.insert('bicycle', 2)
>>> t.items()
[('bicycle', 2), ('bit', 0), ('byte', 8)]

•  def prefixes(self) -> dict[str, set[str]]: 

Returns a dictionary $$d$$ of prefixes taken from this trie $$t$$. Every key $$k$$ in $$d$$ must exist as a key in $$t$$. The associated value of each $$k$$ must be an nonempty set of all keys from $$t$$ that have $$k$$ as a proper prefix.

Example:

>>> t: Trie[int] = Trie()
>>> t.insert('hello', 1)
>>> t.insert('a', 2)
>>> t.insert('hellen', 3)
>>> t.insert('an', 4)
>>> t.insert('he', 5)
>>> t.insert('ant', 6)
>>> t.insert('help', 7)
>>> t.insert('antivirus', 8)
>>> t.insert('at', 9)
>>> t.insert('hell', 10)
>>> t.insert('antilope', 11)
>>> t.insert('her', 12)
>>> t.insert('antique', 13)
>>> t.prefixes()
{'a': {'at', 'antilope', 'antique', 'ant', 'antivirus', 'an'},
'an': {'antivirus', 'antilope', 'ant', 'antique'},
'ant': {'antivirus', 'antilope', 'antique'},
'he': {'her', 'hellen', 'hello', 'hell', 'help'},
'hell': {'hellen', 'hello'}}


Test your code using the following unit tests:

# File: tries_test.py_compile

from unittest import TestCase, main
from tries import Trie

class TestTries(TestCase):

def test_len(self):
t: Trie[int] = Trie()
self.assertEqual(0, len(t))
t.insert('bit', 0)
self.assertEqual(1, len(t))
t.insert('bicycle', 2)
self.assertEqual(2, len(t))
t.insert('bit', 1)
self.assertEqual(2, len(t))
t.insert('byte', 8)
self.assertEqual(3, len(t))
t.insert('byte', 16)
self.assertEqual(3, len(t))
self.assertTrue(t.remove('bit'))
self.assertEqual(2, len(t))
self.assertFalse(t.remove('bit'))
self.assertEqual(2, len(t))
self.assertTrue(t.remove('bicycle'))
self.assertEqual(1, len(t))
self.assertTrue(t.remove('byte'))
self.assertEqual(0, len(t))
self.assertFalse(t.remove('byte'))

def test_items(self):
t: Trie[int] = Trie()
self.assertEqual([], t.items())
t.insert('hello', 1)
self.assertEqual([('hello', 1)], t.items())
t.insert('a', 2)
self.assertEqual([('a', 2), ('hello', 1)], t.items())
t.insert('hellen', 3)
self.assertEqual([('a', 2), ('hellen', 3), ('hello', 1)],
t.items())
t.insert('an', 4)
self.assertEqual([('a', 2), ('an', 4), ('hellen', 3),
('hello', 1)],
t.items())
t.insert('he', 5)
self.assertEqual([('a', 2), ('an', 4), ('he', 5),
('hellen', 3), ('hello', 1)],
t.items())
t.insert('ant', 6)
self.assertEqual([('a', 2), ('an', 4), ('ant', 6),
('he', 5), ('hellen', 3), ('hello', 1)],
t.items())
t.insert('help', 7)
self.assertEqual([('a', 2), ('an', 4), ('ant', 6),
('he', 5), ('hellen', 3), ('hello', 1),
('help', 7)],
t.items())
t.insert('antivirus', 8)
self.assertEqual([('a', 2),  ('an', 4), ('ant', 6),
('antivirus', 8), ('he', 5), ('hellen', 3),
('hello', 1), ('help', 7)],
t.items())
t.insert('at', 9)
self.assertEqual([('a', 2), ('an', 4), ('ant', 6),
('antivirus', 8), ('at', 9), ('he', 5),
('hellen', 3), ('hello', 1), ('help', 7)],
t.items())
t.insert('hell', 10)
self.assertEqual([('a', 2), ('an', 4), ('ant', 6),
('antivirus', 8), ('at', 9), ('he', 5),
('hell', 10), ('hellen', 3), ('hello', 1),
('help', 7)],
t.items())
t.insert('antilope', 11)
self.assertEqual([('a', 2), ('an', 4), ('ant', 6),
('antilope', 11), ('antivirus', 8),
('at', 9), ('he', 5), ('hell', 10),
('hellen', 3), ('hello', 1), ('help', 7)],
t.items())
t.insert('her', 12)
self.assertEqual([('a', 2), ('an', 4), ('ant', 6),
('antilope', 11), ('antivirus', 8),
('at', 9), ('he', 5), ('hell', 10),
('hellen', 3), ('hello', 1),
('help', 7), ('her', 12)],
t.items())
t.insert('antique', 13)
self.assertEqual([('a', 2), ('an', 4), ('ant', 6),
('antilope', 11), ('antique', 13),
('antivirus', 8), ('at', 9), ('he', 5),
('hell', 10), ('hellen', 3), ('hello', 1),
('help', 7), ('her', 12)],
t.items())

def test_prefixes(self):
t: Trie[int] = Trie()
self.assertEqual({}, t.prefixes())
t.insert('hello', 1)
self.assertEqual({}, t.prefixes())
t.insert('a', 2)
self.assertEqual({}, t.prefixes())
t.insert('hellen', 3)
self.assertEqual({}, t.prefixes())
t.insert('an', 4)
self.assertEqual({'a': {'an'}}, t.prefixes())
t.insert('he', 5)
self.assertEqual({'a': {'an'}, 'he': {'hellen', 'hello'}},
t.prefixes())
t.insert('ant', 6)
self.assertEqual({'an': {'ant'}, 'a': {'an', 'ant'},
'he': {'hellen', 'hello'}},
t.prefixes())
t.insert('help', 7)
self.assertEqual({'an': {'ant'}, 'a': {'ant', 'an'},
'he': {'hello', 'hellen', 'help'}},
t.prefixes())
t.insert('antivirus', 8)
self.assertEqual({'a': {'antivirus', 'ant', 'an'},
'an': {'antivirus', 'ant'},
'ant': {'antivirus'},
'he': {'hello', 'hellen', 'help'}},
t.prefixes())
t.insert('at', 9)
self.assertEqual({'a': {'at', 'antivirus', 'an', 'ant'},
'an': {'antivirus', 'ant'},
'ant': {'antivirus'},
'he': {'help', 'hello', 'hellen'}},
t.prefixes())
t.insert('hell', 10)
self.assertEqual({'a': {'an', 'at', 'antivirus', 'ant'},
'an': {'antivirus', 'ant'},
'ant': {'antivirus'},
'he': {'hello', 'hell', 'help', 'hellen'},
'hell': {'hello', 'hellen'}},
t.prefixes())
t.insert('antilope', 11)
self.assertEqual({'a': {'antilope', 'ant', 'antivirus',
'an', 'at'},
'an': {'antilope', 'ant', 'antivirus'},
'ant': {'antilope', 'antivirus'},
'he': {'hello', 'hellen', 'help', 'hell'},
'hell': {'hellen', 'hello'}},
t.prefixes())
t.insert('her', 12)
self.assertEqual({'a': {'an', 'at', 'antilope', 'ant',
'antivirus'},
'an': {'antivirus', 'antilope', 'ant'},
'ant': {'antivirus', 'antilope'},
'he': {'hellen', 'hello', 'hell', 'her',
'help'},
'hell': {'hellen', 'hello'}},
t.prefixes())
t.insert('antique', 13)
self.assertEqual({'a': {'antilope', 'at', 'antique',
'antivirus', 'an', 'ant'},
'an': {'antilope', 'antique', 'antivirus',
'ant'},
'ant': {'antilope', 'antique',
'antivirus'},
'he': {'her', 'hello', 'hell', 'help',
'hellen'},
'hell': {'hellen', 'hello'}},
t.prefixes())

if __name__ == '__main__':
main()


Finally, make sure no type or PEP 8 style errors are produced by using the mypy and pycodestyle linters. You can incorporate these tools into VS Code or you can run them at the terminal.

## Deliverables

Place in a comment at the top of the tries.py source file the authorsâ€™ personal information (student ID and name), for example:

#----------------------------------------------------------
# Lab #7: Tries & String Prefixes
#
# Date: 08-Nov-2022
# Authors:
#           A01770771 Kamala Khan
#           A01777771 Carol Danvers
#----------------------------------------------------------


To deliver the tries.py file, please provide the following information: