pub struct PathPrefixTree<V> { /* private fields */ }
Expand description
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§
Source§impl<V> PathPrefixTree<V>
impl<V> PathPrefixTree<V>
Sourcepub fn new() -> Self
pub fn new() -> Self
Get a new, empty PathPrefixTree
Sourcepub fn insert<P: AsRef<Path>>(&mut self, path: P, value: V)
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.
Sourcepub fn try_insert<P: AsRef<Path>>(
&mut self,
path: P,
value: V,
) -> Result<(), TryInsertError>
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.
Sourcepub fn contains<P: AsRef<Path>>(&self, path: P) -> bool
pub fn contains<P: AsRef<Path>>(&self, path: P) -> bool
Returns true if path
has been inserted in this tree.
Sourcepub fn get<P: AsRef<Path>>(&self, path: P) -> Option<&V>
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
Sourcepub fn get_mut<P: AsRef<Path>>(&mut self, path: P) -> Option<&mut V>
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
Sourcepub fn nearest_ancestor<P: AsRef<Path>>(&self, path: P) -> Option<Entry<'_, V>>
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
Sourcepub fn iter(&self) -> impl Iterator<Item = Entry<'_, V>> + '_
pub fn iter(&self) -> impl Iterator<Item = Entry<'_, V>> + '_
Iterate over all of the entries inserted in this tree.
Sourcepub fn files(&self) -> impl Iterator<Item = Entry<'_, V>> + '_
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.
Sourcepub fn children<P: AsRef<Path>>(
&self,
path: P,
max_depth: Option<usize>,
) -> impl Iterator<Item = Entry<'_, V>> + '_
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§
Source§impl<V: Clone> Clone for PathPrefixTree<V>
impl<V: Clone> Clone for PathPrefixTree<V>
Source§impl<V> Default for PathPrefixTree<V>
impl<V> Default for PathPrefixTree<V>
Source§impl<'a, V> FromIterator<&'a Path> for PathPrefixTree<V>where
V: Default,
impl<'a, V> FromIterator<&'a Path> for PathPrefixTree<V>where
V: Default,
Source§impl<'a, V> FromIterator<&'a str> for PathPrefixTree<V>where
V: Default,
impl<'a, V> FromIterator<&'a str> for PathPrefixTree<V>where
V: Default,
Source§impl<V, P> FromIterator<(P, V)> for PathPrefixTree<V>
impl<V, P> FromIterator<(P, V)> for PathPrefixTree<V>
Auto Trait Implementations§
impl<V> Freeze for PathPrefixTree<V>
impl<V> RefUnwindSafe for PathPrefixTree<V>where
V: RefUnwindSafe,
impl<V> Send for PathPrefixTree<V>where
V: Send,
impl<V> Sync for PathPrefixTree<V>where
V: Sync,
impl<V> Unpin for PathPrefixTree<V>where
V: Unpin,
impl<V> UnwindSafe for PathPrefixTree<V>where
V: UnwindSafe,
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
Source§impl<T> IntoEither for T
impl<T> IntoEither for T
Source§fn into_either(self, into_left: bool) -> Either<Self, Self>
fn into_either(self, into_left: bool) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left
is true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read moreSource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
self
into a Left
variant of Either<Self, Self>
if into_left(&self)
returns true
.
Converts self
into a Right
variant of Either<Self, Self>
otherwise. Read more