TrieHard (TrieHard v0.2.7)

View Source

A blazing fast, memory-efficient Trie (prefix tree) implementation for Elixir with autocomplete support, powered by the trie_hard_rs Rust library.

Features

  • Fast operations: Sub-microsecond autocomplete performance
  • Memory efficient: Shared prefix storage
  • Unicode support: Full UTF-8 character support
  • Generic values: Store any Erlang term as values
  • Batch operations: Efficient bulk insertions
  • Thread-safe: Concurrent access support

Example

iex> trie = TrieHard.new()
iex> TrieHard.insert(trie, "cat", :feline)
:ok
iex> TrieHard.insert(trie, "car", %{type: "vehicle", wheels: 4})
:ok
iex> TrieHard.insert(trie, "card", {"payment", "plastic"})
:ok
iex> TrieHard.get(trie, "cat")
{:ok, :feline}
iex> {:ok, results} = TrieHard.auto_complete(trie, "ca", 10)
iex> Enum.sort(results)
["car", "card", "cat"]

Summary

Types

key()
trie()
value()

Functions

add_word_list(trie, words)

Efficiently inserts multiple words at once.

auto_complete(trie, prefix, max_results \\ 10)

Returns words that start with the given prefix, up to max_results.

count_prefix(trie, prefix)

Returns the number of words with a given prefix.

delete(trie, key)

Removes a key and its associated value from the trie.

get(trie, key)

Retrieves a value by exact key match.

insert(trie, key, value)

Inserts a key-value pair into the trie.

new()

Creates a new empty Trie.

prefix_search(trie, prefix)

Checks if any words in the trie start with the given prefix.

Types

key()

@type key() :: String.t()

trie()

@type trie() :: reference()

value()

@type value() :: term()

Functions

add_word_list(trie, words)

@spec add_word_list(trie(), [String.t()]) :: :ok | :error

Efficiently inserts multiple words at once.

Each word will be inserted with itself as the value.

Parameters

  • trie - The trie reference
  • words - List of words to insert

Examples

iex> trie = TrieHard.new()
iex> TrieHard.add_word_list(trie, ["cat", "car", "card"])
:ok
iex> TrieHard.get(trie, "cat")
{:ok, "cat"}

auto_complete(trie, prefix, max_results \\ 10)

@spec auto_complete(trie(), String.t(), non_neg_integer()) ::
  {:ok, [String.t()]} | {:error, []}

Returns words that start with the given prefix, up to max_results.

Parameters

  • trie - The trie reference
  • prefix - The prefix to search for
  • max_results - Maximum number of results to return (default: 10)

Returns

  • {:ok, [String.t()]} - List of matching words
  • {:error, []} on internal error

Examples

iex> trie = TrieHard.new()
iex> TrieHard.insert(trie, "cat", "1")
:ok
iex> TrieHard.insert(trie, "car", "2")
:ok
iex> TrieHard.insert(trie, "card", "3")
:ok
iex> {:ok, results} = TrieHard.auto_complete(trie, "ca", 2)
iex> length(results) <= 2
true

count_prefix(trie, prefix)

@spec count_prefix(trie(), String.t()) :: {:ok, non_neg_integer()} | {:error, 0}

Returns the number of words with a given prefix.

This is a convenience function that uses auto_complete with unlimited results.

Examples

iex> trie = TrieHard.new()
iex> TrieHard.add_word_list(trie, ["cat", "car", "card", "dog"])
:ok
iex> TrieHard.count_prefix(trie, "ca")
{:ok, 3}
iex> TrieHard.count_prefix(trie, "do")
{:ok, 1}

delete(trie, key)

@spec delete(trie(), key()) :: :ok | :error

Removes a key and its associated value from the trie.

Parameters

  • trie - The trie reference
  • key - The key to remove

Examples

iex> trie = TrieHard.new()
iex> TrieHard.insert(trie, "hello", "world")
:ok
iex> TrieHard.delete(trie, "hello")
:ok
iex> TrieHard.get(trie, "hello")
{:not_found, nil}

get(trie, key)

@spec get(trie(), key()) :: {:ok, value()} | {:not_found, nil} | {:error, nil}

Retrieves a value by exact key match.

Parameters

  • trie - The trie reference
  • key - The key to look up

Returns

  • {:ok, value} if the key exists
  • {:not_found, nil} if the key doesn't exist
  • {:error, nil} on internal error

Examples

iex> trie = TrieHard.new()
iex> TrieHard.insert(trie, "hello", "world")
:ok
iex> TrieHard.get(trie, "hello")
{:ok, "world"}
iex> TrieHard.insert(trie, "data", {:ok, %{id: 123}})
:ok
iex> TrieHard.get(trie, "data")
{:ok, {:ok, %{id: 123}}}
iex> TrieHard.get(trie, "missing")
{:not_found, nil}

insert(trie, key, value)

@spec insert(trie(), key(), value()) :: :ok | :error

Inserts a key-value pair into the trie.

Parameters

  • trie - The trie reference
  • key - The key to insert (string)
  • value - The value to associate with the key (any Erlang term)

Examples

iex> trie = TrieHard.new()
iex> TrieHard.insert(trie, "hello", "world")
:ok
iex> TrieHard.insert(trie, "config", %{timeout: 5000, retry: true})
:ok
iex> TrieHard.insert(trie, "data", {:ok, [1, 2, 3]})
:ok

new()

@spec new() :: trie()

Creates a new empty Trie.

Examples

iex> trie = TrieHard.new()
iex> is_reference(trie)
true

prefix_search(trie, prefix)

@spec prefix_search(trie(), String.t()) :: {:ok, boolean()} | {:error, false}

Checks if any words in the trie start with the given prefix.

Parameters

  • trie - The trie reference
  • prefix - The prefix to search for

Returns

  • {:ok, true} if words with the prefix exist
  • {:ok, false} if no words with the prefix exist
  • {:error, false} on internal error

Examples

iex> trie = TrieHard.new()
iex> TrieHard.insert(trie, "cat", "feline")
:ok
iex> TrieHard.prefix_search(trie, "ca")
{:ok, true}
iex> TrieHard.prefix_search(trie, "dog")
{:ok, false}