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

use super::*;
use std::{
    any::type_name,
    fmt::{Debug, Formatter},
    ops::{Bound, Range, RangeBounds},
};

/// # Arguments
///
/// * `index`:
///
/// returns: Option<Cow<Self::Node>>
///
/// # Examples
///
/// ```
/// use graph_theory::GraphEngine;
/// ```
pub struct NodesVisitor<'i, G: GraphEngine + ?Sized> {
    graph: &'i G,
    indexer: Box<dyn DoubleEndedIterator<Item = usize>>,
}

impl<'i, G: GraphEngine + ?Sized> Debug for NodesVisitor<'i, G> {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        let name = type_name::<G>();
        let nodes = self.graph.count_nodes();
        f.debug_struct("NodesVisitor").field("graph", &name).field("nodes", &nodes).finish()
    }
}

impl<'i, G> Iterator for NodesVisitor<'i, G>
where
    G: GraphEngine + ?Sized,
{
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        let index = self.indexer.next()?;
        if self.graph.has_node(index) { Some(index) } else { self.next() }
    }
}

impl<'i, G> DoubleEndedIterator for NodesVisitor<'i, G>
where
    G: GraphEngine + ?Sized,
{
    fn next_back(&mut self) -> Option<Self::Item> {
        let index = self.indexer.next_back()?;
        if self.graph.has_node(index) { Some(index) } else { self.next_back() }
    }
}

impl<'i, G: GraphEngine + ?Sized> NodesVisitor<'i, G> {
    /// Create a custom node visitor
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::GraphEngine;
    /// ```
    pub fn new<I>(graph: &'i G, indexer: I) -> Self
    where
        I: DoubleEndedIterator<Item = usize> + 'static,
    {
        Self { graph, indexer: Box::new(indexer) }
    }
    /// Create a range based node visitor
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{CompleteGraph, NodesVisitor};
    /// let graph = CompleteGraph::new(5);
    /// let mut visitor = NodesVisitor::range(&graph, 1..=2);
    /// assert_eq!(visitor.next(), Some(1));
    /// assert_eq!(visitor.next(), Some(2));
    /// assert_eq!(visitor.next(), None);
    /// ```
    pub fn range<R>(graph: &'i G, range: R) -> Self
    where
        R: RangeBounds<usize>,
    {
        let start = match range.start_bound() {
            Bound::Included(s) => *s,
            Bound::Excluded(s) => *s + 1,
            Bound::Unbounded => 0,
        };
        let end = match range.end_bound() {
            Bound::Included(s) => *s + 1,
            Bound::Excluded(s) => *s,
            Bound::Unbounded => {
                panic!("Upper bound must be specified")
            }
        };
        Self { graph, indexer: Box::new(Range { start, end }) }
    }
    /// Create a index based node visitor
    ///
    /// # Examples
    ///
    /// ```
    /// use graph_theory::{CompleteGraph, NodesVisitor};
    /// let graph = CompleteGraph::new(5);
    /// let mut visitor = NodesVisitor::slice(&graph, &[1, 2]);
    /// assert_eq!(visitor.next(), Some(1));
    /// assert_eq!(visitor.next(), Some(2));
    /// assert_eq!(visitor.next(), None);
    /// ```
    pub fn slice(graph: &'i G, slice: &'static [usize]) -> Self {
        // TODO: allow non static slices
        Self { graph, indexer: Box::new(slice.iter().copied()) }
    }
}