graphlib 0.6.3

Graphlib is a simple and powerful rust library for the graph data-structure.
Documentation 
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

// Copyright 2019 Octavian Oncescu

use crate::vertex_id::VertexId;

#[cfg(not(feature = "no_std"))]
use std::fmt::Debug;

#[cfg(not(feature = "no_std"))]
use std::marker::PhantomData;

#[cfg(feature = "no_std")]
use core::marker::PhantomData;

#[cfg(feature = "no_std")]
use core::mem;

#[cfg(not(feature = "no_std"))]
use std::mem;

#[cfg(not(feature = "no_std"))]
use std::collections::VecDeque;

#[cfg(feature = "no_std")]
use alloc::collections::VecDeque;

/// Iterator that owns the data.
#[derive(Debug)]
pub(crate) struct OwningIterator<'a> {
    iterable: VecDeque<VertexId>,
    cur_idx: usize, // Quite the hack, but it works
    phantom: PhantomData<&'a u8>,
}

impl<'a> OwningIterator<'a> {
    pub fn new(iterable: VecDeque<VertexId>) -> Self {
        OwningIterator {
            iterable,
            cur_idx: 0,
            phantom: PhantomData,
        }
    }
}

impl<'a> Iterator for OwningIterator<'a> {
    type Item = &'a VertexId;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.cur_idx == self.iterable.len() {
            None
        } else {
            let last_idx = self.cur_idx;
            self.cur_idx += 1;

            // Since we cannot annotate the lifetime 'a to &mut self
            // because of the Iterator trait's signature, this seems
            // the only way to make the compiler happy.
            //
            // TODO: If you can make this work with safe Rust, please do.
            unsafe {
                let ptr = &self.iterable[last_idx] as *const VertexId;
                let transmuted = mem::transmute::<*const VertexId, &VertexId>(ptr);
                Some(transmuted)
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_yields_correct_vertex_ids() {
        let ids: VecDeque<VertexId> =
            vec![VertexId::random(), VertexId::random(), VertexId::random()]
                .iter()
                .cloned()
                .collect();
        let mut iter = OwningIterator::new(ids.clone());

        assert_eq!(iter.next(), Some(&ids[0]));
        assert_eq!(iter.next(), Some(&ids[1]));
        assert_eq!(iter.next(), Some(&ids[2]));
        assert_eq!(iter.next(), None);
    }
}