Trie

A Trie is a prefix tree data structure. It has set-like operations and properties. Instead of storing hashable elements, however, it stores sequences of hashable elements. As well as set operations, the Trie can be searched by prefix. Insertion, deletion, and searching are all O(n), where n is the length of the sequence being searched for.

Trie

Discussion of this specific implementation is available here.

Full documentation is available here.

  • A textual representation of self, suitable for debugging.

    Declaration

    Swift

    public var debugDescription: String

  • Insert a member into the Trie.

    Declaration

    Swift

    public mutating func insert<
    S : SequenceType where S.Generator.Element == Element
    >(seq: S)

  • Create an empty Trie

    Declaration

    Swift

    public init()

  • Construct from an arbitrary sequence of sequences with elements of type Element.

    Declaration

    Swift

    public init<
    S : SequenceType, IS : SequenceType where
    S.Generator.Element == IS,
    IS.Generator.Element == Element
    >(_ seq: S)

  • Construct from an arbitrary sequence with elements of type Element.

    Declaration

    Swift

    public init
    <S : SequenceType where S.Generator.Element == Element>
    (_ seq: S)

  • Return a generator over the members.

    Declaration

    Swift

    public func generate() -> TrieGenerator<Element>

  • Returns the number of members of self.

    • Complexity: O(count)

    Declaration

    Swift

    public var count: Int

  • Returns a Trie of the suffixes of the members of self which start with start.

    let words = ["hello", "hiya", "hell", "jonah", "jolly", "joseph"].map{$0.characters}

let store = Trie(words)

store
  .completions("jo".characters)
  .map(String.init)

// ["lly", "seph", "nah"]

    Declaration

    Swift

    public func completions<
    S : SequenceType where S.Generator.Element == Element
    >(start: S) -> Trie<Element>

  • Remove the member from the Trie and return it if it was present.

    Declaration

    Swift

    public mutating func remove<
    S : SequenceType where S.Generator.Element == Element
    >(seq: S) -> [Element]?

  • Remove the member if it was present, insert it if it was not.

    Declaration

    Swift

    public mutating func XOR<
    S : SequenceType where S.Generator.Element == Element
    >(seq: S)

  • Returns true if the Trie contains a member.

    Declaration

    Swift

    public func contains<
    S : SequenceType where S.Generator.Element == Element
    >(seq: S) -> Bool

  • Insert elements of a Trie into this Trie.

    Declaration

    Swift

    public mutating func unionInPlace(with: Trie<Element>)

  • Return a new Trie with items in both this set and a finite sequence.

    Declaration

    Swift

    public func union(var with: Trie<Element>) -> Trie<Element>

  • Returns a Trie which contains the results of applying transform to the members of self

    Declaration

    Swift

    public func map<S : SequenceType>(@noescape transform: [Element] -> S) -> Trie<S.Generator.Element>

  • Returns a Trie which contains the non-nil results of applying transform to the members of self

    Declaration

    Swift

    public func flatMap<S : SequenceType>(@noescape transform: [Element] -> S?) -> Trie<S.Generator.Element>

  • Returns a Trie which contains the merged results of applying transform to self.

    Declaration

    Swift

    public func flatMap<T>(@noescape transform: [Element] -> Trie<T>) -> Trie<T>

  • Returns a Trie which contains the members of self which satisfy includeElement.

    Declaration

    Swift

    public func filter(@noescape includeElement: [Element] -> Bool) -> Trie<Element>