Struct PathPrefixTree

pub struct PathPrefixTree<V> { /* private fields */ }

A PathPrefixTree is a tree data structure optimized for indexing/searching a directory hierarchy in various ways. In particular, it is efficient to ask:

• If a path is contained in the tree
• The nearest ancestor contained in the tree for a given path

Furthermore, the structure of the tree is very compact, only requiring branching where multiple paths with the same prefix diverge. As a result, the depth of the tree is typically much less than the depth of the corresponding directory hierarchy, and is always bounded by the depth of the directory structure itself.

This data structure is lexicographically ordered, and can be reified as a flat set of paths, or traversed like a tree.

Implementations

impl<V> PathPrefixTree<V>

pub fn new() -> Self

Get a new, empty PathPrefixTree

pub fn insert<P: AsRef<Path>>(&mut self, path: P, value: V)

Insert path in this tree with the given value associated with the resulting node.

If path is already contained in this tree (using the definition of containment as described in contains), then this operation will replace the value for that node.

pub fn try_insert<P: AsRef<Path>>( &mut self, path: P, value: V, ) -> Result<(), TryInsertError>

Try to insert path in this tree with the given value associated with the resulting node.

If path is already contained in this tree (using the definition of containment as described in contains), then this operation will replace the value for that node, unless the file type for that node is in conflict, in which case an error will be returned.

pub fn clear(&mut self)

Reset this tree to its default, empty state.

pub fn contains<P: AsRef<Path>>(&self, path: P) -> bool

Returns true if path has been inserted in this tree.

pub fn get<P: AsRef<Path>>(&self, path: P) -> Option<&V>

Get a reference to the data associated with path, if present in the tree

pub fn get_mut<P: AsRef<Path>>(&mut self, path: P) -> Option<&mut V>

Get a mutable reference to the data associated with path, if present in the tree

pub fn nearest_ancestor<P: AsRef<Path>>(&self, path: P) -> Option<Entry<'_, V>>

Get the nearest entry in the tree which is an ancestor of path

pub fn iter(&self) -> impl Iterator<Item = Entry<'_, V>> + '_

Iterate over all of the entries inserted in this tree.

pub fn files(&self) -> impl Iterator<Item = Entry<'_, V>> + '_

Iterate over all of the entries inserted in this tree, with a path that refers to a file.

This is like iter, but does not emit entries for directories.

pub fn children<P: AsRef<Path>>( &self, path: P, max_depth: Option<usize>, ) -> impl Iterator<Item = Entry<'_, V>> + '_

Iterate over all entries in the tree which are descendants of path.

If max_depth is set, the search is restricted to entries with a path containing no more than max_depth additional path components than path itself.

For example, with a tree containing /foo/bar, /foo/bar/baz and /foo/bar/baz/qux, calling this function with /foo/bar and a max depth of 2, will only return /foo/bar/baz, not foo/bar/baz/qux, since the latter is 2 levels deeper in the hierarchy.

Trait Implementations

impl<V: Clone> Clone for PathPrefixTree<V>

fn clone(&self) -> Self

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<V> Default for PathPrefixTree<V>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, V> FromIterator<&'a Path> for PathPrefixTree<V>

where V: Default,

fn from_iter<T>(iter: T) -> Self

where T: IntoIterator<Item = &'a Path>,

Creates a value from an iterator.

impl<'a, V> FromIterator<&'a str> for PathPrefixTree<V>

where V: Default,

fn from_iter<T>(iter: T) -> Self

where T: IntoIterator<Item = &'a str>,

Creates a value from an iterator.

impl<V, P> FromIterator<(P, V)> for PathPrefixTree<V>

where P: AsRef<Path>,

fn from_iter<T>(iter: T) -> Self

where T: IntoIterator<Item = (P, V)>,

Creates a value from an iterator.