futures_dagtask/
graph.rs

1use std::mem;
2use std::hash::{ Hash, BuildHasher };
3use std::vec::IntoIter;
4use std::collections::HashMap;
5use std::collections::hash_map::RandomState;
6use num_traits::{ CheckedAdd, One };
7
8
9pub struct Graph<N, I = u32, S = RandomState> {
10    map: HashMap<Index<I>, (N, Vec<Index<I>>), S>,
11    pub(crate) last: Index<I>
12}
13
14impl<N, I, S> Default for Graph<N, I, S>
15where
16    I: Default + Hash + PartialEq + Eq,
17    S: Default + BuildHasher
18{
19    fn default() -> Graph<N, I, S> {
20        Graph { map: HashMap::default(), last: Index(Default::default()) }
21    }
22}
23
24impl<N, I, S> Graph<N, I, S>
25where
26    I: CheckedAdd + One + Hash + PartialEq + Eq + Clone,
27    S: BuildHasher
28{
29    pub fn add_node(&mut self, node: N) -> Result<Index<I>, N> {
30        match self.last.next() {
31            Some(index) => {
32                self.map.insert(index.clone(), (node, Vec::new()));
33                Ok(index)
34            },
35            None => Err(node)
36        }
37    }
38
39    pub fn contains(&self, index: &Index<I>) -> bool {
40        self.map.contains_key(index)
41    }
42
43    pub fn add_edge(&mut self, parent: &Index<I>, next: Index<I>) -> Option<()> {
44        self.map.get_mut(parent)
45            .map(|(_, sum)| sum.push(next))
46    }
47
48    pub fn remove_node(&mut self, index: &Index<I>) -> Option<N> {
49        self.map.remove(index)
50            .map(|(n, _)| n)
51    }
52
53    pub fn get_node_mut(&mut self, index: &Index<I>) -> Option<&mut N> {
54        self.map.get_mut(index)
55            .map(|(n, _)| n)
56    }
57
58    pub fn walk(&mut self, index: &Index<I>) -> IntoIter<Index<I>> {
59        self.map.get_mut(index)
60            .map(|(_, arr)| mem::replace(arr, Vec::new()))
61            .unwrap_or_else(Vec::new)
62            .into_iter()
63    }
64}
65
66#[derive(Hash, PartialEq, Eq, PartialOrd, Ord, Copy, Clone, Debug)]
67pub struct Index<I = u32>(I);
68
69impl<I> Index<I>
70where I: CheckedAdd + One
71{
72    #[inline]
73    fn next(&mut self) -> Option<Index<I>> {
74        Some(mem::replace(self, Index(self.0.checked_add(&I::one())?)))
75    }
76}
futures_dagtask/graph.rs

futures_dagtask/
graph.rs
