src/librustc_data_structures/graph/tests.rs

   1 use crate::fx::FxHashMap;
   2 use std::cmp::max;
   3 use std::slice;
   4 use std::iter;
   5
   6 use super::*;
   7
   8 pub struct TestGraph {
   9     num_nodes: usize,
  10     start_node: usize,
  11     successors: FxHashMap<usize, Vec<usize>>,
  12     predecessors: FxHashMap<usize, Vec<usize>>,
  13 }
  14
  15 impl TestGraph {
  16     pub fn new(start_node: usize, edges: &[(usize, usize)]) -> Self {
  17         let mut graph = TestGraph {
  18             num_nodes: start_node + 1,
  19             start_node,
  20             successors: FxHashMap::default(),
  21             predecessors: FxHashMap::default(),
  22         };
  23         for &(source, target) in edges {
  24             graph.num_nodes = max(graph.num_nodes, source + 1);
  25             graph.num_nodes = max(graph.num_nodes, target + 1);
  26             graph.successors.entry(source).or_default().push(target);
  27             graph.predecessors.entry(target).or_default().push(source);
  28         }
  29         for node in 0..graph.num_nodes {
  30             graph.successors.entry(node).or_default();
  31             graph.predecessors.entry(node).or_default();
  32         }
  33         graph
  34     }
  35 }
  36
  37 impl DirectedGraph for TestGraph {
  38     type Node = usize;
  39 }
  40
  41 impl WithStartNode for TestGraph {
  42     fn start_node(&self) -> usize {
  43         self.start_node
  44     }
  45 }
  46
  47 impl WithNumNodes for TestGraph {
  48     fn num_nodes(&self) -> usize {
  49         self.num_nodes
  50     }
  51 }
  52
  53 impl WithPredecessors for TestGraph {
  54     fn predecessors(&self,
  55                     node: usize)
  56                     -> <Self as GraphPredecessors<'_>>::Iter {
  57         self.predecessors[&node].iter().cloned()
  58     }
  59 }
  60
  61 impl WithSuccessors for TestGraph {
  62     fn successors(&self, node: usize) -> <Self as GraphSuccessors<'_>>::Iter {
  63         self.successors[&node].iter().cloned()
  64     }
  65 }
  66
  67 impl<'graph> GraphPredecessors<'graph> for TestGraph {
  68     type Item = usize;
  69     type Iter = iter::Cloned<slice::Iter<'graph, usize>>;
  70 }
  71
  72 impl<'graph> GraphSuccessors<'graph> for TestGraph {
  73     type Item = usize;
  74     type Iter = iter::Cloned<slice::Iter<'graph, usize>>;
  75 }