Struct PathPrefixTree

Source
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>

Source

pub fn new() -> Self

Get a new, empty PathPrefixTree

Source

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.

Source

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.

Source

pub fn clear(&mut self)

Reset this tree to its default, empty state.

Source

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

Returns true if path has been inserted in this tree.

Source

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

Source

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

Source

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

Source

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

Iterate over all of the entries inserted in this tree.

Source

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.

Source

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>

Source§

fn clone(&self) -> Self

Returns a copy of the value. Read more
1.0.0 · Source§

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

Performs copy-assignment from source. Read more
Source§

impl<V> Default for PathPrefixTree<V>

Source§

fn default() -> Self

Returns the “default value” for a type. Read more
Source§

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

Source§

fn from_iter<T>(iter: T) -> Self
where T: IntoIterator<Item = &'a Path>,

Creates a value from an iterator. Read more
Source§

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

Source§

fn from_iter<T>(iter: T) -> Self
where T: IntoIterator<Item = &'a str>,

Creates a value from an iterator. Read more
Source§

impl<V, P> FromIterator<(P, V)> for PathPrefixTree<V>
where P: AsRef<Path>,

Source§

fn from_iter<T>(iter: T) -> Self
where T: IntoIterator<Item = (P, V)>,

Creates a value from an iterator. Read more

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> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> IntoEither for T

Source§

fn into_either(self, into_left: bool) -> Either<Self, Self>

Converts 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 more
Source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
where F: FnOnce(&Self) -> bool,

Converts 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
Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.