Idiom # 159: Trie

Code

Running Example

ex159 is

  trie
    (
    V type,

    # the codepoint of this tree node, '#' for root. Not strictly needed.
    cp codepoint,

    # children of this node: maps codepoint at this position to sub-trie
    children container.ordered_map codepoint (trie V),

    # value of this node if it contains a value
    val option V
    )

  is

    # create a new trie by adding or replacing mapping (from => to)
    add(from String, to V) =>
      c := cp from
      n :=
        if from.codepoint_length = 1
          ch := (children[c] ? nil => (container.ordered_map codepoint (trie V)).empty
                             | el trie => el.children)
          trie c ch to
        else
          el := (children[c] ? nil    => trie V c
                             | el0 trie => el0)
          el.add (from.substring 1) to
      trie c (children.add c n) val

    # find the value 's' is mapped to by this trie
    find(s String) option V =>
      if s.is_empty
        val
      else
        children[cp s] ? nil    => nil
                       | t trie => t.find (s.substring 1)

  # convenience routine to create empty trie for codepoint 'c'
  trie(V type, cp codepoint) => trie V cp (container.ordered_map codepoint (trie V)).empty nil

  # convenience routine to create empty trie
  trie(V type) => trie V (cp "#")

  # convenience routine to get the first code point from a non-empty string
  cp (s String)
    pre
      debug: !s.is_empty
   => s.as_codepoints.first.get

  # create a dictionary from English to German and fill it with vocabulatry from
  # "one" to "ten":
  #
  e0 := trie String
  e1 := e0.add "one"   "eins"
  e2 := e1.add "two"   "zwei"
  e3 := e2.add "three" "drei"
  e4 := e3.add "four"  "vier"
  e5 := e4.add "five"  "fünf"
  e6 := e5.add "six"   "sechs"
  e7 := e6.add "seven" "sieben"
  e8 := e7.add "eight" "acht"
  e9 := e8.add "nine"  "neun"
  e  := e9.add "ten"   "zehn"

  # show the entry for 's' in the dictionary 'e'
  show (s String) => say "$s \t=> {e.find s}"

  # test the dictionary with valid and invalid lookups:
  show "eleven"
  show "ten"
  show "nine"
  show "eight"
  show "seven"
  show "six"
  show "five"
  show "four"
  show "three"
  show "two"
  show "one"
  show "zero"
What are effects?
last changed: 2024-07-01
next: NYI: Idiom # 160: Detect if 32-bit or 64-bit architecture