1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309
//! Transitive iterator and utilities
//!
//! This micro-crate provides [TransIter] and [TransPrioQueue], iterators
//! suitable for navigating DAGs. The iterators may be used for iterating over
//! all nodes of some recursive structure or, more generally, implement a
//! transitive closure. It requires a recursion function which yields an
//! iterator over the next items or nodes.
//!
//! The iterators may be created via associated functions such as the obligatory
//! [TransIter::new]. However, the canonical way to create a [TransIter] or
//! [TransPrioQueue] would be by using the [IntoTransIter] trait, which provides
//! the [trans_iter_with](IntoTransIter::trans_iter_with) and
//! [trans_prio_queue_with](IntoTransIter::trans_prio_queue_with) functions.
//! This library provides a blanket implementation for item types.
//!
//! For types with an obvious or inherent relation to associated items, users
//! may choose to implement the [AutoTransIter] trait. It provides the more
//! convenient [trans_iter](AutoTransIter::trans_iter) function which does not
//! require a recursion function to be supplied for each call.
use std::iter::FromIterator;
/// Transitive iterator
///
/// The iterator yields all elements which are transitively reachable from an
/// initial set of items through a given recursion function, including those
/// initial items. Items discovered through a call to the recursion function
/// will only be yielded after the item passed in that call. I.e. if the
/// recursion function yields the "children" of a node, a node will only be
/// yielded after its "parent".
///
/// By default, the iterator will yield siblings, i.e. the items yielded by a
/// single call to the recursion function, grouped together. This behavior can
/// be changed by calling [depth_first](TransIter::depth_first) or
/// [depth_first_unordered](TransIter::depth_first_unordered).
///
/// Note that the iterator itself will not filter items which are reachable via
/// multiple paths. Generally, this iterator is not suitable for navigating
/// potentially cyclic structures on its own. For such structures, consider
/// implementing the necessary filtering in the recursion function supplied
/// during iterator creation.
///
/// # Example
///
/// ```
/// let names: Vec<_> = transiter::TransIter::new(
/// String::new(),
/// |s| { let s = s.clone(); ["a", "b", "c"].iter().map(move |c| s.clone() + c)}
/// ).take(10).collect();
/// assert_eq!(names, vec!["", "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc"]);
/// ```
#[derive(Clone, Debug)]
pub struct TransIter<F: FnMut(&T) -> I, I: IntoIterator<Item = T>, T> {
get_next: F,
queue: std::collections::VecDeque<T>,
mode: Mode,
}
impl<F: FnMut(&T) -> I, I: IntoIterator<Item = T>, T> TransIter<F, I, T> {
/// Create a new transitive iterator
///
/// The iterator will yield all elements which are transitively reachable
/// from the `initial` item through the given `recursion` function,
/// including the `initial` itself.
pub fn new(initial: T, recursion: F) -> Self {
Self {get_next: recursion, queue: std::iter::once(initial).collect(), mode: Default::default()}
}
/// Create a new transitive iterator with multiple initial items
///
/// The iterator will yield all elements which are transitively reachable
/// from the `initial` set of items through the given `recursion` function,
/// including the items in the initial set.
pub fn new_multi(initial: impl IntoIterator<Item = T>, recursion: F) -> Self {
Self {get_next: recursion, queue: FromIterator::from_iter(initial), mode: Default::default()}
}
/// Make this iterator iterate breadth first
///
/// The iterator will yield siblings grouped together, in the order they
/// were yielded by the `Iterator` returned by the recursion function.
///
/// This is the default mode.
pub fn breadth_first(self) -> Self {
Self {mode: Mode::BreadthFirst, ..self}
}
/// Make this iterator iterate depth first
///
/// After yielding an item, the iterator will yield all the items reachable
/// from that item before yielding the items next sibling.
///
/// Siblings will be yielded in the order they were yielded by the
/// `Iterator` returned by the recursion function. Note that preserving the
/// order inhibits some additional cost. Consider using
/// `depth_first_unordered` instead.
pub fn depth_first(self) -> Self {
Self {mode: Mode::DepthFirst, ..self}
}
/// Make this iterator iterate depth first, without preserving sibling order
///
/// After yielding an item, the iterator will yield all the items reachable
/// from that item before yielding the items next sibling.
///
/// The order of the siblings is not preserved, i.e. it may differ from the
/// order they were yielded by the `Iterator` returned by the recursion
/// function.
pub fn depth_first_unordered(self) -> Self {
Self {mode: Mode::DepthFirstUnordered, ..self}
}
/// Convert this iterator into a [TransPrioQueue]
///
/// The [TransPrioQueue] will yield the same items the [TransIter] would.
pub fn into_trans_prio_queue(self) -> TransPrioQueue<F, I, T> where T: Ord {
TransPrioQueue::new_multi(self.queue, self.get_next)
}
}
impl<F: FnMut(&T) -> I, I: IntoIterator<Item = T>, T> Iterator for TransIter<F, I, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
let res = self.queue.pop_front();
res.as_ref().map(&mut self.get_next).map(|items| match self.mode {
Mode::BreadthFirst => self.queue.extend(items),
Mode::DepthFirst => {
let mut items = Vec::from_iter(items);
self.queue.reserve(items.len());
while let Some(i) = items.pop() {
self.queue.push_front(i);
}
},
Mode::DepthFirstUnordered => {
let items = items.into_iter();
self.queue.reserve(items.size_hint().0);
items.for_each(|i| self.queue.push_front(i))
},
});
res
}
}
#[derive(Copy, Clone, Debug)]
enum Mode {
BreadthFirst,
DepthFirst,
DepthFirstUnordered,
}
impl Default for Mode {
fn default() -> Self {
Self::BreadthFirst
}
}
/// Transitive priority queue
///
/// This iterator yields all elements which are transitively reachable from an
/// initial set of items through a given recursion function, including those
/// initial items. Items discovered through a call to the recursion function
/// will be enqueued and only yielded after the item passed in that call. I.e.
/// if the recursion function yields the "children" of a node, a node will only
/// be yielded after its "parent".
///
/// Of the currently enqueued items, the queue will always yield the greatest
/// one as defined via the item type's implementation of [Ord].
///
/// Note that the iterator itself will not filter items which are reachable via
/// multiple paths. Generally, this iterator is not suitable for navigating
/// potentially cyclic structures on its own. For such structures, consider
/// implementing the necessary filtering in the recursion function supplied
/// during iterator creation.
#[derive(Clone, Debug)]
pub struct TransPrioQueue<F: FnMut(&T) -> I, I: IntoIterator<Item = T>, T: Ord> {
get_next: F,
data: std::collections::BinaryHeap<T>,
}
impl<F: FnMut(&T) -> I, I: IntoIterator<Item = T>, T: Ord> TransPrioQueue<F, I, T> {
/// Create a new transitive priority queue
///
/// The queue will yield all elements which are transitively reachable
/// from the `initial` item through the given `recursion` function,
/// including the `initial` itself.
pub fn new(initial: T, recursion: F) -> Self {
Self {get_next: recursion, data: std::iter::once(initial).collect()}
}
/// Create a new transitive priority queue with multiple initial items
///
/// The queue will yield all elements which are transitively reachable
/// from the `initial` set of items through the given `recursion` function,
/// including the items in the initial set.
pub fn new_multi(initial: impl IntoIterator<Item = T>, recursion: F) -> Self {
Self {get_next: recursion, data: FromIterator::from_iter(initial)}
}
}
impl<F: FnMut(&T) -> I, I: IntoIterator<Item = T>, T: Ord> Iterator for TransPrioQueue<F, I, T> {
type Item = T;
fn next(&mut self) -> Option<T> {
let res = self.data.pop();
res.as_ref().map(&mut self.get_next).map(|items| self.data.extend(items));
res
}
}
/// Create a [TransIter] directly from some value
///
/// This trait defines the [trans_iter_with](IntoTransIter::trans_iter_with)
/// function which, when called on a value, returns a [TransIter] with an
/// initial set derived from that value.
///
/// # Example
///
/// ```
/// use transiter::IntoTransIter;
///
/// let names: Vec<_> = String::new()
/// .trans_iter_with(|s| { let s = s.clone(); ["a", "b", "c"].iter().map(move |c| s.clone() + c)})
/// .take(10)
/// .collect();
/// assert_eq!(names, vec!["", "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc"]);
/// ```
pub trait IntoTransIter<T> {
/// Create a [TransIter] from this value
///
/// Create a [TransIter] with an initial set derived from this value and
/// the given recursion function.
fn trans_iter_with<F: FnMut(&T) -> I, I: IntoIterator<Item = T>>(
self,
recursion: F
) -> TransIter<F, I, T>;
/// Create a [TransPrioQueue] from this value
///
/// Create a [TransPrioQueue] with an initial set derived from this value
/// and the given recursion function.
fn trans_prio_queue_with<F: FnMut(&T) -> I, I: IntoIterator<Item = T>>(
self,
recursion: F
) -> TransPrioQueue<F, I, T>
where Self: Sized,
T: Ord,
{
self.trans_iter_with(recursion).into_trans_prio_queue()
}
}
impl<T> IntoTransIter<T> for T {
fn trans_iter_with<F: FnMut(&T) -> I, I: IntoIterator<Item = T>>(
self,
recursion: F
) -> TransIter<F, I, T> {
TransIter::new(self, recursion)
}
}
/// Create a [TransIter] directly from some value, with type-specific recursion
///
/// This trait defines the [trans_iter](AutoTransIter::trans_iter) function
/// which, when called on a value, returns a [TransIter] with an initial set
/// derived from that value.
///
/// Users may implement this trait for types with inherent and/or obvious
/// relations to other items of the same type such as recursive/tree-like
/// structures. In order to avoid deep copying, consider implementing this trait
/// for references of your types rather than for structs and enums directly.
pub trait AutoTransIter<T>: IntoTransIter<T> + Sized {
/// Type of the iterator returned by `recurse`
type RecIter: IntoIterator<Item = T>;
/// Retrieve the "next" items reachable from a given item
fn recurse(item: &T) -> Self::RecIter;
/// Create a [TransIter] from this value
///
/// Create a [TransIter] with an initial set derived from this value and the
/// type specific recursion function.
fn trans_iter(self) -> TransIter<fn(&T) -> Self::RecIter, Self::RecIter, T> {
self.trans_iter_with(Self::recurse)
}
/// Create a [TransPrioQueue] from this value
///
/// Create a [TransPrioQueue] with an initial set derived from this value
/// and the type specific recursion function.
fn trans_prio_queue(self) -> TransPrioQueue<fn(&T) -> Self::RecIter, Self::RecIter, T> where T: Ord {
self.trans_prio_queue_with(Self::recurse)
}
}
#[cfg(test)]
#[macro_use(quickcheck)]
extern crate quickcheck_macros;
#[cfg(test)]
mod tests;