Trie

A Trie data structure.

A trie is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.

In this implementation they key is a String.

In this implementation unique reference stored in the value dictionary for a given key is a String.

Data Model

type alias Trie a =

Trie a

Trie data model.

Create

empty : Trie a

An empty Trie

Modify

add : ( String, a ) -> String -> Trie a -> Trie a

Add reference and values with key to Trie.

updatedTrie =
    Trie.add ( "refid123", ( "ValueStored", 42.34 ) ) "someword" Trie.empty

remove : String -> String -> Trie a -> Trie a

Remove values for key and reference from Trie.

This removes the reference from the correct values list. If the key does not exist nothing changes. If the ref is not found in the values for the key nothing changes.

An example but does not do anything.

updatedTrie =
    Trie.remove "for" "refid125" Trie.empty

An example that adds something then removes it.

trie1 =
    Trie.add ( "refid123", ( "ValueStored", 42.34 ) ) "someword" Trie.empty


trie2 =
    Trie.remove "someword" "refid123" Trie.trie1

If you remove all references you add the trie will become empty again.

Query

has : String -> Trie a -> Bool

Checks whether key is contained within a Trie.

A key must have values for it be considered present in Trie.

get : String -> Trie a -> Maybe (Dict String a)

Return values for a key if found.

getNode : String -> Trie a -> Maybe (Trie a)

Return Trie node if found.

This will return Nothing.

maybeNode =
    Trie.getNode "for" Trie.empty

This will return the node containing the values for the word "someword". It will contains "refid123" in the dictionary point at ("ValueStored", 42.34).

trie1 =
    Trie.add ( "refid123", ( "ValueStored", 42.34 ) ) "someword" Trie.empty


maybeNode =
    Trie.getNode "someword" trie1

valueCount : String -> Trie a -> Int

Return number of values stored at Trie location.

expand : String -> Trie a -> List String

Find all the possible suffixes of the passed key using keys currently in the store.

This returns a List of all keys from starting key down. The definition of a key that exists is one that has documents defined for it.

Given this setup

    trie1 = Trie.add ("refid121", 1) "ab" Trie.empty
    trie2 = Trie.add ("refid122", 2) "ac" trie1
    trie3 = Trie.add ("refid123", 3) "acd" trie2

This

    Trie.expand "a" trie3

Returns

[ "ab", "acd", "ac" ]

This

    Trie.expand "ac" trie3

Returns

[ "acd", "ac" ]

isEmpty : Trie a -> Bool

Returns True if Trie is empty

Get data values from node

getValues : Trie a -> Maybe (Dict String a)

Return the values stored if there are any

rluiten/trie/2.1.1