Trie

public struct Trie<Key, Value> : Sendable where Key : Collection, Key : Sendable, Value : Sendable, Key.Element : Hashable, Key.Element : Sendable
extension Trie: CustomStringConvertible
extension Trie: Equatable where Value: Equatable
extension Trie: Hashable where Value: Hashable

A trie (a.k.a. prefix tree).

Show on GitHub

  • A node representing either one of the strings in a trie or a prefix thereof.

    See more

    Declaration

    Swift

    fileprivate struct Node : Sendable
    extension Trie.Node: Equatable where Value: Equatable
    extension Trie.Node: Hashable where Value: Hashable
    Show on GitHub

  • The nodes in the trie, the first of which is the root.

    Declaration

    Swift

    fileprivate var nodes: [Node]
    Show on GitHub

  • Creates an empty trie.

    Declaration

    Swift

    public init()
    Show on GitHub

  • The number of key/value pairs in self.

    Declaration

    Swift

    public var count: Int { get }
    Show on GitHub

  • true iff self is empty.

    Declaration

    Swift

    public var isEmpty: Bool { get }
    Show on GitHub

  • Returns a collection with the key/value pairs in self.

    Declaration

    Swift

    public var elements: Elements { get }
    Show on GitHub

  • Returns a pair (n, i) such that key[..<i] is the longest key prefix contained in self and n is a sub-trie mapping the keys prefixed by key[..<i] to their corresponding value in self.

    If key is fully contained in one of the keys in self, then i is key.endIndex and n is the result of self[prefix: key]. If key shares no prefix with any of the keys stored in self, then i is key.startIndex and n is equal to self.

    Declaration

    Swift

    public func longestPrefix<K: Collection & Sendable>(
  startingWith key: K
) -> (trie: SubTrie<Key, Value>, position: K.Index) where K.Element == Key.Element
    Show on GitHub

  • Accesses the value associated with key.

    Declaration

    Swift

    public subscript<K>(key: K) -> Value? where K : Collection, Key.Element == K.Element { get set }
    Show on GitHub

  • Returns a sub-trie mapping the keys prefixed by key to their corresponding value in self, or nil if self contains no key starting with by key.

    Declaration

    Swift

    public subscript<K: Collection & Sendable>(
  prefix key: K
) -> SubTrie<Key, Value>? where K.Element == Key.Element
    Show on GitHub

  • Returns the node corresponding to the longest prefix shared with key looked up from root.

    Declaration

    Swift

    fileprivate func longestPrefix<K: Collection>(
  startingWith key: K, from root: Node.Identifier
) -> (node: Node.Identifier, position: K.Index) where K.Element == Key.Element
    Show on GitHub

  • Returns the node corresponding to key looked up from root.

    Declaration

    Swift

    fileprivate func find<K: Collection>(
  _ key: K, from root: Node.Identifier
) -> Node.Identifier? where K.Element == Key.Element
    Show on GitHub

  • A collection containing the elements of a Trie or SubTrie, in some arbitrary order.

    See more

    Declaration

    Swift

    public struct Elements : Collection
    Show on GitHub

  • Declaration

    Swift

    public var description: String { get }
    Show on GitHub

Available where Value: Equatable

Available where Value: Hashable