• Effekt Logo Effekt Library
    • dictionary
      • Trie
        • Empty
        • Leaf
        • Branch1
        • Node1
        • Branch2
        • Node2
        • Branch3
        • Node3
        • Branch4
        • Node4
        • Branch256
        • Node256
      • Dictionary
      • Tagged
      • empty
      • insert
      • insert
      • lookup
      • lookup
      • collect
      • each
      • eachTagged
    • dictionary
      • Jump to source: libraries/common/dictionary.effekt
      Example usage: examples/stdlib/dictionary
      • Trie [A]
        • Internal trie node type.

Nodes with at most four children are `Branch1` ... `Branch4`, holding their
children behind `Ref`s so that descending along an existing path can
update in place without rebuilding the spine. A fifth child promotes the
node to the dense representation (`Branch256` / `Node256`), a full 256-slot
array indexed by the byte, whose cells are mutable themselves.

Invariant: in the sparse representations, `byte1 < byte2 < byte3 < byte4`
(bytes are unsigned), so iteration is in key order in every representation.

`Leaf`, `Node1` ... `Node4` and `Node256` carry a value at this
position; `Branch1` ... `Branch4` and `Branch256` do not.

No `Trie` value is ever shared between two live positions: insertion
mutates through `Ref`s and array cells, so aliasing a subtree would be
unsound.
        • Empty
        • Leaf (value: A)
        • Branch1 (byte: Byte, child: Ref[Trie[A]])
        • Node1 (value: A, byte: Byte, child: Ref[Trie[A]])
        • Branch2 (byte1: Byte, child1: Ref[Trie[A]], byte2: Byte, child2: Ref[Trie[A]])
        • Node2 (value: A, byte1: Byte, child1: Ref[Trie[A]], byte2: Byte, child2: Ref[Trie[A]])
        • Branch3 (byte1: Byte, child1: Ref[Trie[A]], byte2: Byte, child2: Ref[Trie[A]], byte3: Byte, child3: Ref[Trie[A]])
        • Node3 (value: A, byte1: Byte, child1: Ref[Trie[A]], byte2: Byte, child2: Ref[Trie[A]], byte3: Byte, child3: Ref[Trie[A]])
        • Branch4 (byte1: Byte, child1: Ref[Trie[A]], byte2: Byte, child2: Ref[Trie[A]], byte3: Byte, child3: Ref[Trie[A]], byte4: Byte, child4: Ref[Trie[A]])
        • Node4 (value: A, byte1: Byte, child1: Ref[Trie[A]], byte2: Byte, child2: Ref[Trie[A]], byte3: Byte, child3: Ref[Trie[A]], byte4: Byte, child4: Ref[Trie[A]])
        • Branch256 (children: Array[Trie[A]])
        • Node256 (value: A, children: Array[Trie[A]])
      • Dictionary [A]
        • A mutable trie-based dictionary for efficient key-value storage with bytearray keys.

Mutating the dictionary while iterating it (`each`, `eachTagged`) is undefined.
      • Tagged [A] (key: ByteArray, value: A)
        • A record pairing a key with a value for use in streams.
      • empty [A]: Dictionary[A] / {}
      • insert [A] (dictionary: Dictionary[A], key: String, value: A): Unit / {} 
        • Insert a value with a String key.
      • insert [A] (dictionary: Dictionary[A], key: ByteArray, value: A): Unit / {} 
        • Insert a key-value pair into the dictionary with a ByteArray key.
      • lookup [A] (dictionary: Dictionary[A], key: String): Option[A] / {} 
        • Look up a value in the dictionary by string key.
      • lookup [A] (dictionary: Dictionary[A], key: ByteArray): Option[A] / {} 
        • Look up a value in the dictionary by bytearray key.
      • collect [A] { stream: => Unit / {emit[Tagged[A]]} }: Dictionary[A] / {} 
        • Collect key-value pairs from a stream of Tagged elements into a fresh Dictionary.
      • each [A] (dictionary: Dictionary[A]): Unit / {emit[A]} 
        • Emit all values stored in the dictionary as a push stream,
in lexicographic key order (a key before its extensions).
      • eachTagged [A] (dictionary: Dictionary[A]): Unit / {emit[Tagged[A]]} 
        • Emit all key-value pairs stored in the dictionary as a push stream of
Tagged elements, in lexicographic key order (a key before its extensions).