This is an attempt to implement a trie in Swift with a generic key. Instead of using just strings as keys, this trie can be keyed by any object that can generate its own prefixes. This is accomplished by using a protocol to define a trie key that can return a generator of Hashable
s. We need Hashable
s because the prefixes will be stored in a Dictionary
.
The TrieNode
class will be a private implementation detail. It helps to separate the implementation into TrieNode
and the wrapper for a few reasons:
- If we want to extend the trie to implement some common Swift collection protocols, many of those don't make sense for every node.
- We want references for nodes but the wrapper struct can help us simulate value semantics.