Trie

A trie implementation combined cedar trie and immutable trie. The trie is able to modify initially. When the trie is determined and not required to be modified, it is allowed to be frozen to achieve a better performance. When it is saved, the saved binary file is always frozen trie binary.

APIs

class pyis.python.ops.Trie(self: ops.Trie) → None

A Trie implementation which combined Cedar trie and immutable trie together. Initially, it is allowed to modify its content. After doing “Freeze” operation, the trie is frozen and not allowed to modify, to achieve better performace.

contains(self: ops.Trie, key: str) → bool

Check if a key in the trie.

Parameters

key (str) – The key to search.

Returns

True if the trie contains the key, otherwise False.

Return type

result (bool)

erase(self: ops.Trie, key: str) → None

Erase a specific key from the trie. Throws RuntimeError if the trie is frozen.

Parameters

key (str) – The key to erase.

freeze(self: ops.Trie) → None

Make the trie frozen.

insert(self: ops.Trie, key: str, value: int) → None

Insert a key-value pair into the trie. Throws RuntimeError if the trie is frozen.

Parameters

• key (str) –

• value (int) –

items(self: ops.Trie) → List[Tuple[str, int]]

Get all key-value pair in the trie.

Returns

All key-value pairs in the trie.

Return type

data (List[Tuple[str, int]])

load(self: ops.Trie, path: str) → None

Load from a binary trie file generated by immutable trie or trie. The trie will be frozen after loaded.

Parameters

path (str) – Path to the binary file.

lookup(self: ops.Trie, key: str) → int

Lookup a specific key-value pair from the trie. Throws RuntimeError if not found.

Parameters

key (str) – The key to lookup.

Returns

The corrsponding value if pair exists.

Return type

value (int)

save(self: ops.Trie, path: str) → None

Save the trie into a binary file. The trie saved will be frozen, thus, it will be a frozen trie when it is loaded. However, the orignal trie (the trie which is being saved) will not be frozen.

Parameters

path (str) – Path to the binary file.

Example

# Copyright (c) Microsoft Corporation. All rights reserved.
# Licensed under the MIT license.

from pyis.python import ops
import os

trie = ops.Trie()
trie.insert("Alpha", 1)
trie.insert("Beta", 2)

1 == trie.lookup("Alpha")
2 == trie.lookup("Beta")
        
trie.lookup("Gamma") # Raises RuntimeError

os.makedirs('tmp',511,True)

trie.save('tmp/trie.bin')

trie2 = ops.Trie()

trie2.load('tmp/trie.bin')
        
trie.items() == trie2.items()
trie.freeze()
trie.items() == trie2.items()

trie.insert("Delta" ,1) # Raises RuntimeError