par_dfs/sync/
mod.rs

1pub mod bfs;
2pub mod dfs;
3#[cfg(feature = "rayon")]
4#[cfg_attr(docsrs, doc(cfg(feature = "rayon")))]
5pub mod par;
6mod queue;
7
8pub use bfs::{Bfs, FastBfs};
9pub use dfs::{Dfs, FastDfs};
10
11use std::hash::Hash;
12use std::iter::{IntoIterator, Iterator};
13
14/// Extend a queue with the contents of an [`Iterator`].
15///
16/// Queues to be used by [`FastNode`] must implement this trait.
17///
18/// [`FastNode`]: trait@crate::sync::FastNode
19/// [`Iterator`]: trait@std::iter::Iterator
20pub trait ExtendQueue<I, E> {
21    /// Add single item with given depth to the queue.
22    fn add(&mut self, item: Result<I, E>);
23
24    /// Extend the queue with the contents of an [`Iterator`].
25    ///
26    /// [`Iterator`]: trait@std::iter::Iterator
27    fn add_all<Iter>(&mut self, iter: Iter)
28    where
29        Iter: IntoIterator<Item = Result<I, E>>;
30}
31
32/// A Queue that can be split and allows removing elements
33/// from the front or back.
34pub(crate) trait Queue<I, E> {
35    /// Returns the number of items in the queue
36    fn len(&self) -> usize;
37
38    /// Returns `true` if the queue is empty
39    fn is_empty(&self) -> bool {
40        self.len() == 0
41    }
42
43    /// Pops the last item from the queue and returns it,
44    /// or [`None`] if it is empty.
45    ///
46    /// [`None`]: type@std::option::Option::None
47    fn pop_back(&mut self) -> Option<(usize, Result<I, E>)>;
48
49    /// Pops the first item from the queue and returns it,
50    /// or [`None`] if it is empty.
51    ///
52    /// [`None`]: type@std::option::Option::None
53    fn pop_front(&mut self) -> Option<(usize, Result<I, E>)>;
54
55    #[must_use]
56    /// Splits the queue into two at the given index.
57    /// Returns a newly allocated queue containing the elements in
58    /// the range `[at, len)`.
59    /// After the call, the original vector will be left containing
60    /// the elements `[0, at)` with its previous capacity unchanged.
61    ///
62    /// # Panics
63    ///   
64    /// Panics if `at > self.len()`
65    fn split_off(&mut self, at: usize) -> Self;
66
67    /// Add single item with given depth to the queue.
68    fn add(&mut self, depth: usize, item: Result<I, E>);
69
70    /// Extend the queue with the contents of an [`Iterator`].
71    ///
72    /// [`Iterator`]: trait@std::iter::Iterator
73    fn add_all<Iter>(&mut self, depth: usize, iter: Iter)
74    where
75        Iter: IntoIterator<Item = Result<I, E>>;
76}
77
78/// A boxed [`Iterator`] of [`Node`]s.
79///
80/// [`Iterator`]: trait@std::iter::Iterator
81/// [`Node`]: trait@crate::sync::Node
82pub type NodeIter<I, E> = Result<Box<dyn Iterator<Item = Result<I, E>>>, E>;
83
84/// A node with produces an [`Iterator`] of children [`Node`]s
85/// for a given depth.
86///
87/// [`Iterator`]: trait@std::iter::Iterator
88/// [`Node`]: trait@crate::sync::Node
89pub trait Node
90where
91    Self: Hash + Eq + Clone + std::fmt::Debug,
92{
93    /// The type of the error when producing children fails.
94    type Error: std::fmt::Debug;
95
96    /// Returns an [`Iterator`] over its children [`Node`]s.
97    ///
98    /// # Errors
99    ///
100    /// Should return [`Self::Error`] if the iterator cannot be crated.
101    ///
102    /// [`Iterator`]: trait@std::iter::Iterator
103    /// [`Node`]: trait@crate::sync::Node
104    /// [`Self::Error`]: type@crate::async::Node::Error
105    fn children(&self, depth: usize) -> NodeIter<Self, Self::Error>;
106}
107
108/// A node which adds children [`Node`]s to a queue in place.
109pub trait FastNode
110where
111    Self: Hash + Eq + Clone + std::fmt::Debug,
112{
113    /// The type of the error when adding children fails.
114    type Error: std::fmt::Debug;
115
116    /// Callback for adding children [`Node`]s to a queue
117    /// implementing [`ExtendQueue`].
118    ///
119    /// # Errors
120    ///
121    /// Should return `Self::Error` if the children could not be added.
122    ///
123    /// [`ExtendQueue`]: trait@crate::sync::ExtendQueue
124    /// [`Node`]: trait@crate::sync::Node
125    /// [`Self::Error`]: type@crate::async::Node::Error
126    fn add_children<E>(&self, depth: usize, queue: &mut E) -> Result<(), Self::Error>
127    where
128        E: ExtendQueue<Self, Self::Error>;
129}
par_dfs/sync/mod.rs

par_dfs/sync/
mod.rs
