prefix_array

This crate provides the PrefixArray and PrefixArraySet datastructures that implement some Map-like and Set-like interfaces, while also being capable of querying data based on what it starts with (its prefix).

prefix_array boasts zero memory overhead, log n searching, and searching on subsets of the main array. This crate also has the advantage of cache locality over a tree type datastructure.

no_std Support

This crate is no_std capable, but has the std feature enabled by default (currently this adds From impls for HashMap and HashSet).

License

This crate is licensed under MPL-2.0 (less common for rust crates), broadly this implies that you may use this crate in a closed source project, and statically link it, but any modifications to the crate itself must be made public. This is not legal advice.

lib.rs:

prefix_array is a crate consisting of datastructures that aid in querying data based on prefixes of string keys, the main feature being searching and refining on subgroups with common prefixes.

Use PrefixArray when you want a HashMap-like structure, and PrefixArraySet for a HashSet-like structure.

Creating a PrefixArray(Set)

For creating a new collection, ideally you can use the FromIterator implementation, this has O(n log n) complexity and with an ExactSizeIterator will allocate once. If you cannot use FromIterator it is recommended to use PrefixArray(Set)::from_vec_lossy instead, as this is what FromIterator calls under the hood.

It is ill advised to use insert in a loop to create a PrefixArray(Set), as this has O(n^2) complexity.

For an already partially filled PrefixArray(Set) that you wish to insert multiple items into, consider the Extend implementation, which is specifically designed for this purpose.

If you have a partially filled PrefixArray(Set) and need to call Extend multiple times, but can share state between each call, consider using ScratchSpace and the extend_with method. This can avoid excessive allocations that the Extend method would otherwise have (as it needs to allocate to insert many items at once).

Basic usage

use prefix_array::PrefixArray;

// construct a new prefix array from an iterator
let arr = PrefixArray::from_iter([("abcde", 123), ("absgh", 1234)]);

// borrow a subslice of all data with the prefix 'ab'
let mut subslice = arr.find_all_with_prefix("ab");

assert_eq!(subslice.len(), 2);

// we can refine the subslice
subslice = subslice.find_all_with_prefix("abc");

assert_eq!(subslice.len(), 1);

// and find when something doesn't exist
assert!(subslice.find_all_with_prefix("ba").is_empty());