Skip to content
FutureBlitz

    Install

    Import std.collections.trie

    std.collections.trie

    A prefix tree of String keys, which finds the keys that start with a prefix.

    Trie<V>: String keys and their values in a tree with a node for each prefix of the keys' bytes, so the keys with a prefix, or the longest key a text starts with, are found by going down the prefix alone. The keys go in the order of their bytes, which is their code points' order.

    std/collections/trie.fb

    Types

    Trie class 

    @DebugEntries Public Class Trie<V> Implements Iterable<(String, V)>, Cloneable, Defaultable

    A Map from Strings that finds the keys that start with a prefix.

    Examples

    Local words = Trie<Int>()
words.Add("car", 1)
words.Add("cart", 2)
words.Add("dog", 3)
Expect(words.KeysWithPrefix("car") == ["car", "cart"])
Expect(words.LongestPrefixOf("carton") == "cart")
Expect(words.HasPrefix("do") && !words.HasPrefix("x"))

    std/collections/trie.fb, line 59

    • Public New() constructor #

      A new, empty Trie.

    • Public Property Count: Int property #

      How many entries it holds.

    • Public Method Add(key: String, value: V) method #

      Adds an entry, or gives an existing key its new value.

    • Public Method Get(key: String): V? method #

      The key's value, or Null when it isn't there.

    • Public Method Get(key: String, fallback: V): V method #

      The key's value, or fallback when it isn't there.

    • @PanicsAtCaller Operator [](key: String): V operator #

      The key's value. A key that isn't there panics.

    • Operator []=(key: String, value: V) operator #

      Gives the key a value, adding it when it isn't there.

    • Public Method Contains(key: String): Bool method #

      Whether key has an entry.

    • Public Method Remove(key: String): Bool method #

      Removes the key's entry, and tells whether there was one.

    • Public Method Clear() method #

      Takes every entry out.

    • Public Method HasPrefix(prefix: String): Bool method #

      Whether a key starts with prefix, as every key starts with "", so an empty Trie has none. Every node but the root is on the way to a key, since Remove takes out what only its key needed.

    • Public Method KeysWithPrefix(prefix: String): String[] method #

      The keys that start with prefix, in order, in a new array.

    • Public Method LongestPrefixOf(text: String): String? method #

      The longest key that text starts with, or Null when none does.

    • Public Method Keys(): String[] method #

      The keys, in order.

    • Public Method Values(): V[] method #

      The values, in their keys' order.

    • Public Static Method DefaultValue(): Trie<V> static method #

      A new, empty Trie.

    • Public Method Clone(): Trie<V> method #

      A new Trie with the same entries.

    • Public Method Iterate(): TrieIterator<V> method #

      Each key and its value, in order, for 'For key, value In trie'. Giving a key a new value while going over them is fine, but adding or removing one panics.

    TrieIterator struct 

    Public Struct TrieIterator<V> Implements Iterator<(String, V)>

    The entries of a Trie, in the order of their keys' bytes, which a For loop goes over.

    std/collections/trie.fb, line 254

    • @PanicsAtCaller Public ByRef Method Next(): (String, V)? method #

      The next key and its value, in the order of the keys' bytes, or Null after the last. Panics when the Trie changed since the loop began.

    Extends

    Trie extend 

    Extend Trie<V> Implements Equatable

    Compares Tries with == and !=, where their values can be compared.

    std/collections/trie.fb, line 294

    • Operator ==(a: Trie<V>, b: Trie<V>): Bool operator #

      Whether the two have the same keys, each with an equal value.

    Trie extend 

    Extend Trie<V> Implements Printable

    Shows a Trie in a string, as its ToString writes it.

    std/collections/trie.fb, line 311

    • Public Method ToString(): String method #

      Its entries, in order, as "{car: 1, cart: 2}".

    Report an issue with this page or with FutureBlitz on GitHub.