#prefix #string #key-prefix #prefix-tree #string-key

prefix-range

Compute bounds for prefix string queries for BTreeSet/BTreeMap::range

1 unstable release

0.1.0 Jan 14, 2024

#2518 in Algorithms

Download history 13/week @ 2024-06-30 74/week @ 2024-07-07 33/week @ 2024-07-14 55/week @ 2024-07-21 46/week @ 2024-07-28 38/week @ 2024-08-04 16/week @ 2024-08-11 23/week @ 2024-08-18 55/week @ 2024-08-25 67/week @ 2024-09-01 49/week @ 2024-09-08 18/week @ 2024-09-15

189 downloads per month

MIT license

7KB
71 lines

Compute bounds for prefix string queries for BTreeSet/BTreeMap::range

[ crates.io ] [ lib.rs ] [ docs.rs ]

If you have a BTreeSet or BTreeMap with string keys and want to find all entries with a given prefix, the standard library (as of Rust 1.75) doesn't offer any built in methods to do so.

You could use something like the following:

let iterator = mymap.range(Bounds::Included("myprefix"),
                           Bounds::Excluded("myprefiy"));

This issue is finding the upper bound myprefiy. You have to deal with UTF-8 encoding, invalid code points etc. That is what the code in this library solves.

The code is taken from a blog post by Jimmy Hartzell, and slightly tweaked:

  • To work in no-std (still needs alloc though)
  • To work with BTreeMaps (not just BTreeSets).

A huge thanks to Jimmy Hartzell for solving the problem already (though they never published it as a crate reusable by others).

See the crate documentation for usage examples.

MSRV

The code is simple, and will likely compile on quite old versions, though nothing older than 1.65 is being actively tested.

No runtime deps