mapgraph/graph/
iter.rs

1//! Contains the iterator and walker types that may be returned by methods on [`Graph`] and
2//! [`FrozenGraph`].
3
4use super::{Edge, Edges, FrozenGraph, Graph, IntKeyMap, Map, Node};
5use core::{fmt::Debug, iter::FusedIterator, marker::PhantomData};
6
7macro_rules! impl_drain_edges {
8    ($name:ident, $word:literal, $word2:literal, $next:ident, $unlink:ident, $node_field:ident, $other_node_field:ident) => {
9        #[doc = concat!(
10            "A draining iterator over the ", $word, " edges of a node. The iterator yields a tuple with ",
11            "the index of the ", $word, " node and the weight of the edge.\n\n"
12        )]
13        /// Dropping an iterator will cause some edges to be left in place. Which edges will stay is
14        /// implementation defined.
15        #[derive(Debug)]
16        pub struct $name<'graph, N, E, NI, EI, NM, EM>
17        where
18            NI: Copy + Eq + Debug + 'static,
19            EI: Copy + Eq + Debug + 'static,
20            NM: Map<Node<N, EI>, Key = NI>,
21            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
22        {
23            pub(super) graph: &'graph mut Graph<N, E, NI, EI, NM, EM>,
24            pub(super) next_edge_index: Option<EI>,
25        }
26
27        impl<'graph, N, E, NI, EI, NM, EM> Iterator for $name<'graph, N, E, NI, EI, NM, EM>
28        where
29            NI: Copy + Eq + Debug + 'static,
30            EI: Copy + Eq + Debug + 'static,
31            NM: Map<Node<N, EI>, Key = NI>,
32            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
33        {
34            type Item = (NI, E);
35
36            fn next(&mut self) -> Option<Self::Item> {
37                let next_edge_index = self.next_edge_index?;
38
39                // Since we're draining an edges chain here anyway, we only need to unlink the
40                // edge from the other edges chain.
41                let edge = self.graph.edges.map.remove(next_edge_index).unwrap();
42                self.graph.$unlink(next_edge_index, &edge);
43
44                self.next_edge_index = edge.$next;
45                self.graph.nodes[edge.$other_node_field].$next = edge.$next;
46
47                Some((edge.$node_field, edge.weight))
48            }
49        }
50
51        impl<'graph, N, E, NI, EI, NM, EM> FusedIterator
52            for $name<'graph, N, E, NI, EI, NM, EM>
53        where
54            NI: Copy + Eq + Debug + 'static,
55            EI: Copy + Eq + Debug + 'static,
56            NM: Map<Node<N, EI>, Key = NI>,
57            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
58        {
59        }
60    };
61}
62
63impl_drain_edges!(
64    DrainOutgoingEdges,
65    "outgoing",
66    "destination",
67    next_outgoing_edge,
68    unlink_edge_from_incoming_list,
69    to,
70    from
71);
72impl_drain_edges!(
73    DrainIncomingEdges,
74    "incoming",
75    "source",
76    next_incoming_edge,
77    unlink_edge_from_outgoing_list,
78    from,
79    to
80);
81
82macro_rules! impl_node_weights {
83    ($name:ident, $word:literal, $iter:ident, $item:ty, $weight:ident) => {
84        #[doc = concat!($word, " iterator over the [`Graph`]'s nodes' weights.")]
85        #[derive(Debug)]
86        pub struct $name<'graph, N, NI, EI, NM>
87        where
88            N: 'graph,
89            NI: Copy + Eq + Debug + 'static,
90            EI: Copy + Eq + Debug + 'static,
91            NM: Map<Node<N, EI>, Key = NI> + 'graph,
92        {
93            pub(super) inner: NM::$iter<'graph>,
94        }
95
96        impl<'graph, N, NI, EI, NM> Iterator for $name<'graph, N, NI, EI, NM>
97        where
98            N: 'graph,
99            NI: Copy + Eq + Debug + 'static,
100            EI: Copy + Eq + Debug + 'static,
101            NM: Map<Node<N, EI>, Key = NI> + 'graph,
102        {
103            type Item = (NM::Key, $item);
104
105            #[inline]
106            fn next(&mut self) -> Option<Self::Item> {
107                self.inner
108                    .next()
109                    .map(|(index, node)| (index, node.$weight()))
110            }
111
112            #[inline]
113            fn size_hint(&self) -> (usize, Option<usize>) {
114                self.inner.size_hint()
115            }
116        }
117
118        impl<'graph, N, NI, EI, NM> ExactSizeIterator for $name<'graph, N, NI, EI, NM>
119        where
120            N: 'graph,
121            NI: Copy + Eq + Debug + 'static,
122            EI: Copy + Eq + Debug + 'static,
123            NM: Map<Node<N, EI>, Key = NI> + 'graph,
124            NM::$iter<'graph>: ExactSizeIterator,
125        {
126            #[inline]
127            fn len(&self) -> usize {
128                self.inner.len()
129            }
130        }
131
132        impl<'graph, N, NI, EI, NM> FusedIterator for $name<'graph, N, NI, EI, NM>
133        where
134            N: 'graph,
135            NI: Copy + Eq + Debug + 'static,
136            EI: Copy + Eq + Debug + 'static,
137            NM: Map<Node<N, EI>, Key = NI> + 'graph,
138            NM::$iter<'graph>: FusedIterator,
139        {
140        }
141
142        impl<'graph, N, NI, EI, NM> DoubleEndedIterator for $name<'graph, N, NI, EI, NM>
143        where
144            N: 'graph,
145            NI: Copy + Eq + Debug + 'static,
146            EI: Copy + Eq + Debug + 'static,
147            NM: Map<Node<N, EI>, Key = NI> + 'graph,
148            NM::$iter<'graph>: DoubleEndedIterator,
149        {
150            fn next_back(&mut self) -> Option<Self::Item> {
151                self.inner
152                    .next_back()
153                    .map(|(index, node)| (index, node.$weight()))
154            }
155        }
156    };
157}
158
159impl_node_weights!(NodeWeights, "An immutable", Iter, &'graph N, weight);
160impl_node_weights!(
161    NodeWeightsMut,
162    "A mutable",
163    IterMut,
164    &'graph mut N,
165    weight_mut
166);
167
168macro_rules! impl_edge_weights {
169    ($name:ident, $word:literal, $iter:ident, $item:ty, $weight:ident) => {
170        #[doc = concat!($word, " iterator over the [`Graph`]'s edges' weights.")]
171        #[derive(Debug)]
172        pub struct $name<'graph, E, NI, EI, EM>
173        where
174            E: 'graph,
175            NI: Copy + Eq + Debug + 'static,
176            EI: Copy + Eq + Debug + 'static,
177            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + 'graph,
178        {
179            pub(super) inner: EM::$iter<'graph>,
180        }
181
182        impl<'graph, E, NI, EI, EM> Iterator for $name<'graph, E, NI, EI, EM>
183        where
184            E: 'graph,
185            NI: Copy + Eq + Debug + 'static,
186            EI: Copy + Eq + Debug + 'static,
187            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + 'graph,
188        {
189            type Item = (EM::Key, $item);
190
191            #[inline]
192            fn next(&mut self) -> Option<Self::Item> {
193                self.inner
194                    .next()
195                    .map(|(index, edge)| (index, edge.$weight()))
196            }
197
198            #[inline]
199            fn size_hint(&self) -> (usize, Option<usize>) {
200                self.inner.size_hint()
201            }
202        }
203
204        impl<'graph, E, NI, EI, EM> ExactSizeIterator for $name<'graph, E, NI, EI, EM>
205        where
206            E: 'graph,
207            NI: Copy + Eq + Debug + 'static,
208            EI: Copy + Eq + Debug + 'static,
209            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + 'graph,
210            EM::$iter<'graph>: ExactSizeIterator,
211        {
212            #[inline]
213            fn len(&self) -> usize {
214                self.inner.len()
215            }
216        }
217
218        impl<'graph, E, NI, EI, EM> FusedIterator for $name<'graph, E, NI, EI, EM>
219        where
220            E: 'graph,
221            NI: Copy + Eq + Debug + 'static,
222            EI: Copy + Eq + Debug + 'static,
223            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + 'graph,
224            EM::$iter<'graph>: FusedIterator,
225        {
226        }
227    };
228}
229
230impl_edge_weights!(EdgeWeights, "An immutable", Iter, &'graph E, weight);
231impl_edge_weights!(
232    EdgeWeightsMut,
233    "A mutable",
234    IterMut,
235    &'graph mut E,
236    weight_mut
237);
238
239macro_rules! impl_edges_iter {
240    ($name:ident, $word:literal, $next:ident) => {
241        #[doc = concat!("Iterator over ", $word, "s of a graph's node.\n")]
242        /// This iterator yields a tuple containing both the edge index and a reference to its
243        /// [`Edge`] structure.
244        #[derive(Debug)]
245        pub struct $name<'graph, E, NI, EI, EM>
246        where
247            NI: Copy + Eq + Debug + 'static,
248            EI: Copy + Eq + Debug + 'static,
249            EM: Map<Edge<E, NI, EI>, Key = EI>,
250        {
251            edges: &'graph EM,
252            next: Option<EI>,
253            _phantom: PhantomData<(E, NI, EI)>,
254        }
255
256        impl<'graph, E, NI, EI, EM> $name<'graph, E, NI, EI, EM>
257        where
258            E: 'graph,
259            NI: Copy + Eq + Debug + 'static,
260            EI: Copy + Eq + Debug + 'static,
261            EM: Map<Edge<E, NI, EI>, Key = EI> + 'graph,
262        {
263            pub(super) fn new(edges: &'graph EM, next: Option<EI>) -> Self {
264                $name {
265                    edges,
266                    next,
267                    _phantom: Default::default(),
268                }
269            }
270        }
271
272        impl<'graph, E, NI, EI, EM> Iterator for $name<'graph, E, NI, EI, EM>
273        where
274            E: 'graph,
275            NI: Copy + Eq + Debug + 'static,
276            EI: Copy + Eq + Debug + 'static,
277            EM: Map<Edge<E, NI, EI>, Key = EI> + 'graph,
278        {
279            type Item = (EI, &'graph Edge<E, NI, EI>);
280
281            #[inline]
282            fn next(&mut self) -> Option<Self::Item> {
283                let next = self.next;
284                if let Some(idx) = next {
285                    let edge = self.edges.get(idx).unwrap();
286                    self.next = edge.$next;
287                    Some((idx, edge))
288                } else {
289                    None
290                }
291            }
292        }
293    };
294}
295
296impl_edges_iter!(Inputs, "input", next_incoming_edge);
297impl_edges_iter!(Outputs, "output", next_outgoing_edge);
298
299macro_rules! impl_neighbours_iter {
300    ($name:ident, $word:literal, $next:ident, $node:ident) => {
301        #[doc = concat!(
302            "Iterator over ", $word, "s of a graph node.\n\n",
303            "Emits tuples containing ", $word, "s' node indices and immutable references to ",
304            "their weights."
305        )]
306        #[derive(Debug)]
307        pub struct $name<'graph, N, E, NI, EI, NM, EM>
308        where
309            NI: Copy + Eq + Debug + 'static,
310            EI: Copy + Eq + Debug + 'static,
311            NM: Map<Node<N, EI>, Key = NI>,
312            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
313        {
314            pub(super) graph: &'graph FrozenGraph<N, E, NI, EI, NM, EM>,
315            pub(super) next: Option<EI>,
316        }
317
318        impl<'graph, N, E, NI, EI, NM, EM> Iterator for $name<'graph, N, E, NI, EI, NM, EM>
319        where
320            N: 'graph,
321            E: 'graph,
322            NI: Copy + Eq + Debug + 'static,
323            EI: Copy + Eq + Debug + 'static,
324            NM: Map<Node<N, EI>, Key = NI> + 'graph,
325            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI> + 'graph,
326        {
327            type Item = (NI, &'graph N);
328
329            #[inline]
330            fn next(&mut self) -> Option<Self::Item> {
331                let next = self.next;
332                next.map(|index| {
333                    let edge = self.graph.edges.get(index).unwrap();
334                    self.next = edge.$next;
335
336                    let node_index = edge.$node;
337                    let node = self.graph.nodes.get(node_index).unwrap();
338                    (node_index, &node.weight)
339                })
340            }
341        }
342    };
343}
344
345impl_neighbours_iter!(Successors, "successor", next_outgoing_edge, to);
346impl_neighbours_iter!(Predecessors, "predecessor", next_incoming_edge, from);
347
348/// A walker is an alternative for an iterator that accepts a reference to a graph on each call
349/// to its `walk_next` methods instead of storing a reference to the graph as an iterator would
350/// do.
351///
352/// Walkers provide an ability to arbitrarily mutate graphs during traversals without exposing
353/// the internal implementation of the graph.
354pub trait Walker<N, E, NI, EI, NM, EM>
355where
356    NI: Copy + Eq + Debug + 'static,
357    EI: Copy + Eq + Debug + 'static,
358    NM: Map<Node<N, EI>, Key = NI>,
359    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
360{
361    /// The item returned by the walker.
362    type Item<'a>
363    where
364        N: 'a,
365        E: 'a,
366        EM: 'a,
367        NM: 'a;
368
369    /// Retrieve the next item from the walker if any.
370    fn walk_next<'a>(
371        &mut self,
372        graph: &'a FrozenGraph<N, E, NI, EI, NM, EM>,
373    ) -> Option<Self::Item<'a>>;
374}
375
376/// A walker is an alternative for an iterator that accepts a reference to a graph on each call
377/// to its `walk_next` methods instead of storing a reference to the graph as an iterator would
378/// do.
379///
380/// Walkers provide an ability to arbitrarily mutate graphs during traversals without exposing
381/// the internal implementation of the graph.
382pub trait WalkerMut<N, E, NI, EI, NM, EM>
383where
384    NI: Copy + Eq + Debug + 'static,
385    EI: Copy + Eq + Debug + 'static,
386    NM: Map<Node<N, EI>, Key = NI>,
387    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
388    Self: Walker<N, E, NI, EI, NM, EM>,
389{
390    /// Retrieve the next item from the walker if any.
391    fn walk_next_mut<'a>(
392        &mut self,
393        graph: &'a mut FrozenGraph<N, E, NI, EI, NM, EM>,
394    ) -> Option<Self::Item<'a>>;
395}
396
397/// A walker is an alternative for an iterator that accepts a reference to a graph on each call
398/// to its `walk_next` methods instead of storing a reference to the graph as an iterator would
399/// do.
400///
401/// Walkers provide an ability to arbitrarily mutate graphs during traversals without exposing
402/// the internal implementation of the graph.
403pub trait EdgesWalker<E, NI, EI, EM>
404where
405    NI: Copy + Eq + Debug + 'static,
406    EI: Copy + Eq + Debug + 'static,
407    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
408{
409    /// The item returned by the walker.
410    type Item<'a>
411    where
412        E: 'a,
413        EM: 'a;
414
415    /// Retrieve the next item from the walker if any.
416    fn walk_edges_next<'a>(&mut self, edges: &'a Edges<E, NI, EI, EM>) -> Option<Self::Item<'a>>;
417}
418
419/// A walker is an alternative for an iterator that accepts a reference to a graph on each call
420/// to its `walk_next` methods instead of storing a reference to the graph as an iterator would
421/// do.
422///
423/// Walkers provide an ability to arbitrarily mutate graphs during traversals without exposing
424/// the internal implementation of the graph.
425pub trait EdgesWalkerMut<E, NI, EI, EM>
426where
427    NI: Copy + Eq + Debug + 'static,
428    EI: Copy + Eq + Debug + 'static,
429    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
430    Self: EdgesWalker<E, NI, EI, EM>,
431{
432    /// Retrieve the next item from the walker if any.
433    fn walk_edges_next_mut<'a>(
434        &mut self,
435        edges: &'a mut Edges<E, NI, EI, EM>,
436    ) -> Option<Self::Item<'a>>;
437}
438
439macro_rules! impl_walk_neighbours {
440    ($name:ident, $word:literal, $next:ident, $node:ident) => {
441        #[doc = concat!("A \"walker\" over the ", $word, "s of a node.")]
442        #[derive(Clone, Debug)]
443        pub struct $name<EI: Copy + Eq + Debug + 'static> {
444            pub(super) next: Option<EI>,
445        }
446
447        impl<N, E, NI, EI, NM, EM> Walker<N, E, NI, EI, NM, EM> for $name<EI>
448        where
449            NI: Copy + Eq + Debug + 'static,
450            EI: Copy + Eq + Debug + 'static,
451            NM: Map<Node<N, EI>, Key = NI>,
452            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
453        {
454            type Item<'a> = NI where N: 'a, E: 'a, EM: 'a, NM: 'a;
455
456            fn walk_next<'a>(
457                &mut self,
458                graph: &'a FrozenGraph<N, E, NI, EI, NM, EM>,
459            ) -> Option<Self::Item<'a>> {
460                let cur_index = self.next?;
461                let edge = graph.edges.get(cur_index).unwrap();
462                self.next = edge.$next;
463                Some(edge.$node)
464            }
465        }
466
467        impl<E, NI, EI, EM> EdgesWalker<E, NI, EI, EM> for $name<EI>
468        where
469            NI: Copy + Eq + Debug + 'static,
470            EI: Copy + Eq + Debug + 'static,
471            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
472        {
473            type Item<'a> = NI where E: 'a, EM: 'a;
474
475            fn walk_edges_next<'a>(
476                &mut self,
477                edges: &'a Edges<E, NI, EI, EM>,
478            ) -> Option<Self::Item<'a>> {
479                let cur_index = self.next?;
480                let edge = edges.get(cur_index).unwrap();
481                self.next = edge.$next;
482                Some(edge.$node)
483            }
484        }
485    };
486}
487
488impl_walk_neighbours!(WalkSuccessors, "successor", next_outgoing_edge, to);
489impl_walk_neighbours!(WalkPredecessors, "predecessor", next_incoming_edge, from);
490
491macro_rules! impl_walk_edges {
492    ($name:ident, $word:literal, $next:ident) => {
493        #[doc = concat!("A \"walker\" over the ", $word, " edges of a node.")]
494        #[derive(Clone, Debug)]
495        pub struct $name<EI: Copy + Eq + Debug + 'static> {
496            pub(super) next: Option<EI>,
497        }
498
499        impl<N, E, NI, EI, NM, EM> Walker<N, E, NI, EI, NM, EM> for $name<EI>
500        where
501            NI: Copy + Eq + Debug + 'static,
502            EI: Copy + Eq + Debug + 'static,
503            NM: Map<Node<N, EI>, Key = NI>,
504            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
505        {
506            type Item<'a> = (EI, &'a Edge<E, NI, EI>) where N: 'a, E: 'a, EM: 'a, NM: 'a;
507
508            fn walk_next<'a>(
509                &mut self,
510                graph: &'a FrozenGraph<N, E, NI, EI, NM, EM>,
511            ) -> Option<Self::Item<'a>> {
512                let cur_index = self.next?;
513                let edge = &graph.edges[cur_index];
514                self.next = edge.$next;
515                Some((cur_index, edge))
516            }
517        }
518
519        impl<E, NI, EI, EM> EdgesWalker<E, NI, EI, EM> for $name<EI>
520        where
521            NI: Copy + Eq + Debug + 'static,
522            EI: Copy + Eq + Debug + 'static,
523            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
524        {
525            type Item<'a> = (EI, &'a Edge<E, NI, EI>) where E: 'a, EM: 'a;
526
527            fn walk_edges_next<'a>(
528                &mut self,
529                edges: &'a Edges<E, NI, EI, EM>,
530            ) -> Option<Self::Item<'a>> {
531                let cur_index = self.next?;
532                let edge = &edges[cur_index];
533                self.next = edge.$next;
534                Some((cur_index, edge))
535            }
536        }
537
538        impl<E, NI, EI, EM> EdgesWalkerMut<E, NI, EI, EM> for $name<EI>
539        where
540            NI: Copy + Eq + Debug + 'static,
541            EI: Copy + Eq + Debug + 'static,
542            EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
543        {
544            fn walk_edges_next_mut<'a>(
545                &mut self,
546                edges: &'a mut Edges<E, NI, EI, EM>,
547            ) -> Option<Self::Item<'a>> {
548                let cur_index = self.next?;
549                let edge = &mut edges[cur_index];
550                self.next = edge.$next;
551                Some((cur_index, edge))
552            }
553        }
554    };
555}
556
557impl_walk_edges!(WalkOutputs, "outgoing", next_outgoing_edge);
558impl_walk_edges!(WalkInputs, "incoming", next_incoming_edge);
mapgraph/graph/iter.rs

mapgraph/graph/
iter.rs
