#key-value #search #pair #partial #storage #allowing #tree-search

capillary

Library for HashMap-like storage of key-value pairs, but allowing for step-by-step (partial) search of value

4 releases (breaking)

0.4.0 Jul 12, 2022
0.3.0 Jul 11, 2022
0.2.0 Jun 30, 2022
0.1.0 Jun 29, 2022

#2103 in Data structures

21 downloads per month

MIT license

11KB
213 lines

capillary

Library for HashMap-like storage of key-value pairs, but allowing for step-by-step (partial) search of value.

Internally it uses an implementation of a tree. This makes it possible to search for a value by providing partial steps.

Use case

One use case, that served as inspiration to create this crate, is replacement inside of a string.

For example, we might want to replace all occurances of keys with their values. Naive and inefficient way is to iterate over keys and call string.replace for every key.

The idea behind capillary is to iterate over string once and be able to replace all occurances in a linear manner. Any character can lead either to a valid, or invalid state. That way, part of the key can be used to go towards some (potential) values. As soon as one unique value is reached, it can be returned.


lib.rs:

capillary introduces a Dictionary data structure. It's used for cases where search by partial key is needed.

In particular useful when performing some kind of find and replace in some data.

i.e. one might want to perform find and replace in a string. With capillary::Dictionary it is possible to keep starting a search, and Dictionary will be in default state until some character is part of a valid key. As long as the following characters are part of a valid key, the state of Dictionary will be set to some part of the key towards the value. It is then possible to test if some value is reached, and return it as soon as it gets hit.

Dependencies

~1.5MB
~29K SLoC