ptrie 0.7.0

Generic trie data structure implementation (prefix tree) with support for different key and value types, and functions to search for common prefixes or postfixes.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

<h1 align="center">
  🎄 Prefix Trie
</h1>

<p align="center">
    <a href="https://crates.io/crates/ptrie">
        <img alt="Crates.io" src="https://img.shields.io/crates/v/ptrie" />
    </a>
    <a href="https://github.com/vemonet/ptrie/actions/workflows/test.yml">
        <img alt="Test" src="https://github.com/vemonet/ptrie/actions/workflows/test.yml/badge.svg" />
    </a>
    <a href="https://github.com/vemonet/ptrie/actions/workflows/release.yml">
        <img alt="Release" src="https://github.com/vemonet/ptrie/actions/workflows/release.yml/badge.svg" />
    </a>
    <a href="https://docs.rs/ptrie">
        <img alt="Documentation" src="https://docs.rs/ptrie/badge.svg" />
    </a>
    <a href="https://codecov.io/gh/vemonet/ptrie/branch/main">
        <img src="https://codecov.io/gh/vemonet/ptrie/branch/main/graph/badge.svg" alt="Codecov status" />
    </a>
    <a href="https://github.com/vemonet/ptrie/blob/main/LICENSE">
        <img alt="MIT license" src="https://img.shields.io/badge/License-MIT-brightgreen.svg" />
    </a>
</p>

`PTrie` is a generic implementation of the [trie data structure](https://en.wikipedia.org/wiki/Trie) with no dependencies, tailored for easy and efficient prefix and postfix search within a collection of objects, such as strings.

The structure is defined as `Trie<K, V>`, where `K` represents the type of keys in each node (an iterator of the chain to index), and `V` is the type of the associated values (any object to which the key points to).

## 💭 Motivation

The trie is particularly effective for operations involving common  prefix identification and retrieval, making it a good choice for  applications that require fast and efficient prefix-based search  functionalities.

## 🚀 Usage

Results are sorted in ascending order of their length.

### ✨ Find prefixes

You can return all prefixes in the trie that matches a given string, or directly retrieve the longest prefix.

```rust
use ptrie::Trie;

let mut trie = Trie::new();

trie.insert("a".bytes(), "A");
trie.insert("ab".bytes(), "AB");
trie.insert("abc".bytes(), "ABC");
trie.insert("abcde".bytes(), "ABCDE");

let prefixes = trie.find_prefixes("abcd".bytes());
assert_eq!(prefixes, vec![&"A", &"AB", &"ABC"]);

let longest = trie.find_longest_prefix("abcd".bytes());
assert_eq!(longest, Some("ABC").as_ref());
```

### 🔍 Find postfixes

You can also find all postfixes in the trie, e.g. all strings which have the given string as a prefix, and extends it.

```rust
use ptrie::Trie;

let mut trie = Trie::new();

trie.insert("app".bytes(), "App");
trie.insert("apple".bytes(), "Apple");
trie.insert("applet".bytes(), "Applet");
trie.insert("apricot".bytes(), "Apricot");

let strings = trie.find_postfixes("app".bytes());
assert_eq!(strings, vec![&"App", &"Apple", &"Applet"]);
```

### 🔑 Key-based retrieval functions

The crate provides functions to check for the existence of a key, to retrieve the associated value, or iterate the trie nodes.

```rust
use ptrie::Trie;

let mut trie = Trie::new();
trie.insert("app".bytes(), "App");
trie.insert("applet".bytes(), "Applet");

assert!(trie.contains_key("app".bytes()));
assert!(!trie.contains_key("not_existing_key".bytes()));
assert_eq!(trie.get("app".bytes()), Some("App").as_ref());
assert_eq!(trie.get("none".bytes()), None.as_ref());

for (k, v) in trie.iter() {
    println!("kv: {:?} {}", k, v);
}
```

## 🏷️ Features

The `serde` feature adds Serde `Serialize` and `Deserialize` traits to the `Trie` and `TrieNode` struct.

```toml
ptrie = { version = "0.6", features = ["serde"] }
```

## 🛠️ Contributing

Contributions are welcome, checkout the [`CONTRIBUTING.md`](https://github.com/vemonet/ptrie/blob/main/CONTRIBUTING.md) for instructions to run the project in development.

## 📜 Changelog

Changelog available in the [`CHANGELOG.md`](https://github.com/vemonet/ptrie/blob/main/CHANGELOG.md).

## ⚖️ License

[MIT License](https://opensource.org/licenses/MIT)