swc_fast_graph/
digraph.rs

1//! `GraphMap<N, E, Ty>` is a graph datastructure where node values are mapping
2//! keys.
3
4#![allow(dead_code)] // We don't want to modify copied source code.
5
6use std::{
7    cmp::Ordering,
8    fmt,
9    hash::{self, Hash},
10    iter::Cloned,
11    marker::PhantomData,
12    ops::Deref,
13    slice::Iter,
14};
15
16use indexmap::{
17    map::{Iter as IndexMapIter, IterMut as IndexMapIterMut, Keys},
18    IndexMap,
19};
20use petgraph::{
21    graph::{node_index, Graph},
22    visit::{
23        GraphBase, IntoNeighbors, IntoNeighborsDirected, IntoNodeIdentifiers, NodeCount,
24        NodeIndexable, Visitable,
25    },
26    Directed, Direction, EdgeType, Incoming, IntoWeightedEdge, Outgoing, Undirected,
27};
28use rustc_hash::{FxBuildHasher, FxHashSet};
29
30/// A `GraphMap` with directed edges.
31///
32/// For example, an edge from *1* to *2* is distinct from an edge from *2* to
33/// *1*.
34pub type FastDiGraphMap<N, E> = FastGraphMap<N, E, Directed>;
35
36/// `GraphMap<N, E, Ty>` is a graph datastructure using an associative array
37/// of its node weights `N`.
38///
39/// It uses an combined adjacency list and sparse adjacency matrix
40/// representation, using **O(|V| + |E|)** space, and allows testing for edge
41/// existence in constant time.
42///
43/// `GraphMap` is parameterized over:
44///
45/// - Associated data `N` for nodes and `E` for edges, called *weights*.
46/// - The node weight `N` must implement `Copy` and will be used as node
47///   identifier, duplicated into several places in the data structure. It must
48///   be suitable as a hash table key (implementing `Eq + Hash`). The node type
49///   must also implement `Ord` so that the implementation can order the pair
50///   (`a`, `b`) for an edge connecting any two nodes `a` and `b`.
51/// - `E` can be of arbitrary type.
52/// - Edge type `Ty` that determines whether the graph edges are directed or
53///   undirected.
54///
55/// You can use the type aliases `UnGraphMap` and `DiGraphMap` for convenience.
56///
57/// `GraphMap` does not allow parallel edges, but self loops are allowed.
58///
59/// Depends on crate feature `graphmap` (default).
60#[derive(Clone)]
61pub struct FastGraphMap<N, E, Ty> {
62    nodes: IndexMap<N, Vec<(N, CompactDirection)>, FxBuildHasher>,
63    edges: IndexMap<(N, N), E, FxBuildHasher>,
64    ty: PhantomData<Ty>,
65}
66
67impl<N: Eq + Hash + fmt::Debug, E: fmt::Debug, Ty: EdgeType> fmt::Debug for FastGraphMap<N, E, Ty> {
68    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
69        self.nodes.fmt(f)
70    }
71}
72
73/// A trait group for `GraphMap`'s node identifier.
74pub trait NodeTrait: Copy + Ord + Hash {}
75impl<N> NodeTrait for N where N: Copy + Ord + Hash {}
76
77// non-repr(usize) version of Direction
78#[derive(Copy, Clone, Debug, PartialEq, Eq)]
79enum CompactDirection {
80    Outgoing,
81    Incoming,
82}
83
84impl From<Direction> for CompactDirection {
85    fn from(d: Direction) -> Self {
86        match d {
87            Outgoing => CompactDirection::Outgoing,
88            Incoming => CompactDirection::Incoming,
89        }
90    }
91}
92
93impl PartialEq<Direction> for CompactDirection {
94    fn eq(&self, rhs: &Direction) -> bool {
95        (*self as usize) == (*rhs as usize)
96    }
97}
98
99impl<N, E, Ty> FastGraphMap<N, E, Ty>
100where
101    N: NodeTrait,
102    Ty: EdgeType,
103{
104    /// Create a new `GraphMap`
105    pub fn new() -> Self {
106        Self::default()
107    }
108
109    /// Create a new `GraphMap` with estimated capacity.
110    pub fn with_capacity(nodes: usize, edges: usize) -> Self {
111        FastGraphMap {
112            nodes: IndexMap::with_capacity_and_hasher(nodes, Default::default()),
113            edges: IndexMap::with_capacity_and_hasher(edges, Default::default()),
114            ty: PhantomData,
115        }
116    }
117
118    /// Return the current node and edge capacity of the graph.
119    pub fn capacity(&self) -> (usize, usize) {
120        (self.nodes.capacity(), self.edges.capacity())
121    }
122
123    /// Use their natural order to map the node pair (a, b) to a canonical edge
124    /// id.
125    #[inline]
126    fn edge_key(a: N, b: N) -> (N, N) {
127        if Ty::is_directed() || a <= b {
128            (a, b)
129        } else {
130            (b, a)
131        }
132    }
133
134    /// Whether the graph has directed edges.
135    pub fn is_directed(&self) -> bool {
136        Ty::is_directed()
137    }
138
139    /// Create a new `GraphMap` from an iterable of edges.
140    ///
141    /// Node values are taken directly from the list.
142    /// Edge weights `E` may either be specified in the list,
143    /// or they are filled with default values.
144    ///
145    /// Nodes are inserted automatically to match the edges.
146    ///
147    /// ```
148    /// use petgraph::graphmap::UnGraphMap;
149    ///
150    /// // Create a new undirected GraphMap.
151    /// // Use a type hint to have `()` be the edge weight type.
152    /// let gr = UnGraphMap::<_, ()>::from_edges(&[
153    ///     (0, 1), (0, 2), (0, 3),
154    ///     (1, 2), (1, 3),
155    ///     (2, 3),
156    /// ]);
157    /// ```
158    pub fn from_edges<I>(iterable: I) -> Self
159    where
160        I: IntoIterator,
161        I::Item: IntoWeightedEdge<E, NodeId = N>,
162    {
163        Self::from_iter(iterable)
164    }
165
166    /// Return the number of nodes in the graph.
167    pub fn node_count(&self) -> usize {
168        self.nodes.len()
169    }
170
171    /// Return the number of edges in the graph.
172    pub fn edge_count(&self) -> usize {
173        self.edges.len()
174    }
175
176    /// Remove all nodes and edges
177    pub fn clear(&mut self) {
178        self.nodes.clear();
179        self.edges.clear();
180    }
181
182    /// Add node `n` to the graph.
183    pub fn add_node(&mut self, n: N) -> N {
184        self.nodes.entry(n).or_default();
185        n
186    }
187
188    /// Return `true` if node `n` was removed.
189    ///
190    /// Computes in **O(V)** time, due to the removal of edges with other nodes.
191    pub fn remove_node(&mut self, n: N) -> bool {
192        let links = match self.nodes.swap_remove(&n) {
193            None => return false,
194            Some(sus) => sus,
195        };
196        for (succ, _) in links {
197            // remove all successor links
198            self.remove_single_edge(&succ, &n, Incoming);
199            // Remove all edge values
200            self.edges.swap_remove(&Self::edge_key(n, succ));
201        }
202        true
203    }
204
205    /// Return `true` if the node is contained in the graph.
206    pub fn contains_node(&self, n: N) -> bool {
207        self.nodes.contains_key(&n)
208    }
209
210    /// Add an edge connecting `a` and `b` to the graph, with associated
211    /// data `weight`. For a directed graph, the edge is directed from `a`
212    /// to `b`.
213    ///
214    /// Inserts nodes `a` and/or `b` if they aren't already part of the graph.
215    ///
216    /// Return `None` if the edge did not previously exist, otherwise,
217    /// the associated data is updated and the old value is returned
218    /// as `Some(old_weight)`.
219    ///
220    /// ```
221    /// // Create a GraphMap with directed edges, and add one edge to it
222    /// use petgraph::graphmap::DiGraphMap;
223    ///
224    /// let mut g = DiGraphMap::new();
225    /// g.add_edge("x", "y", -1);
226    /// assert_eq!(g.node_count(), 2);
227    /// assert_eq!(g.edge_count(), 1);
228    /// assert!(g.contains_edge("x", "y"));
229    /// assert!(!g.contains_edge("y", "x"));
230    /// ```
231    pub fn add_edge(&mut self, a: N, b: N, weight: E) -> Option<E> {
232        if let old @ Some(_) = self.edges.insert(Self::edge_key(a, b), weight) {
233            old
234        } else {
235            // insert in the adjacency list if it's a new edge
236            self.nodes
237                .entry(a)
238                .or_insert_with(|| Vec::with_capacity(1))
239                .push((b, CompactDirection::Outgoing));
240            if a != b {
241                // self loops don't have the Incoming entry
242                self.nodes
243                    .entry(b)
244                    .or_insert_with(|| Vec::with_capacity(1))
245                    .push((a, CompactDirection::Incoming));
246            }
247            None
248        }
249    }
250
251    /// Remove edge relation from a to b
252    ///
253    /// Return `true` if it did exist.
254    fn remove_single_edge(&mut self, a: &N, b: &N, dir: Direction) -> bool {
255        match self.nodes.get_mut(a) {
256            None => false,
257            Some(sus) => {
258                if Ty::is_directed() {
259                    match sus
260                        .iter()
261                        .position(|elt| elt == &(*b, CompactDirection::from(dir)))
262                    {
263                        Some(index) => {
264                            sus.swap_remove(index);
265                            true
266                        }
267                        None => false,
268                    }
269                } else {
270                    match sus.iter().position(|elt| &elt.0 == b) {
271                        Some(index) => {
272                            sus.swap_remove(index);
273                            true
274                        }
275                        None => false,
276                    }
277                }
278            }
279        }
280    }
281
282    /// Remove edge from `a` to `b` from the graph and return the edge weight.
283    ///
284    /// Return `None` if the edge didn't exist.
285    ///
286    /// ```
287    /// // Create a GraphMap with undirected edges, and add and remove an edge.
288    /// use petgraph::graphmap::UnGraphMap;
289    ///
290    /// let mut g = UnGraphMap::new();
291    /// g.add_edge("x", "y", -1);
292    ///
293    /// let edge_data = g.remove_edge("y", "x");
294    /// assert_eq!(edge_data, Some(-1));
295    /// assert_eq!(g.edge_count(), 0);
296    /// ```
297    pub fn remove_edge(&mut self, a: N, b: N) -> Option<E> {
298        let exist1 = self.remove_single_edge(&a, &b, Outgoing);
299        let exist2 = if a != b {
300            self.remove_single_edge(&b, &a, Incoming)
301        } else {
302            exist1
303        };
304        let weight = self.edges.shift_remove(&Self::edge_key(a, b));
305        debug_assert!(exist1 == exist2 && exist1 == weight.is_some());
306        weight
307    }
308
309    /// Return `true` if the edge connecting `a` with `b` is contained in the
310    /// graph.
311    pub fn contains_edge(&self, a: N, b: N) -> bool {
312        self.edges.contains_key(&Self::edge_key(a, b))
313    }
314
315    /// Return an iterator over the nodes of the graph.
316    ///
317    /// Iterator element type is `N`.
318    pub fn nodes(&self) -> Nodes<N> {
319        Nodes {
320            iter: self.nodes.keys().cloned(),
321        }
322    }
323
324    /// Return an iterator of all nodes with an edge starting from `a`.
325    ///
326    /// - `Directed`: Outgoing edges from `a`.
327    /// - `Undirected`: All edges from or to `a`.
328    ///
329    /// Produces an empty iterator if the node doesn't exist.<br>
330    /// Iterator element type is `N`.
331    pub fn neighbors(&self, a: N) -> Neighbors<N, Ty> {
332        Neighbors {
333            iter: match self.nodes.get(&a) {
334                Some(neigh) => neigh.iter(),
335                None => [].iter(),
336            },
337            ty: self.ty,
338        }
339    }
340
341    /// Return an iterator of all neighbors that have an edge between them and
342    /// `a`, in the specified direction.
343    /// If the graph's edges are undirected, this is equivalent to
344    /// *.neighbors(a)*.
345    ///
346    /// - `Directed`, `Outgoing`: All edges from `a`.
347    /// - `Directed`, `Incoming`: All edges to `a`.
348    /// - `Undirected`: All edges from or to `a`.
349    ///
350    /// Produces an empty iterator if the node doesn't exist.<br>
351    /// Iterator element type is `N`.
352    pub fn neighbors_directed(&self, a: N, dir: Direction) -> NeighborsDirected<N, Ty> {
353        NeighborsDirected {
354            iter: match self.nodes.get(&a) {
355                Some(neigh) => neigh.iter(),
356                None => [].iter(),
357            },
358            start_node: a,
359            dir,
360            ty: self.ty,
361        }
362    }
363
364    /// Return an iterator of target nodes with an edge starting from `a`,
365    /// paired with their respective edge weights.
366    ///
367    /// - `Directed`: Outgoing edges from `a`.
368    /// - `Undirected`: All edges from or to `a`.
369    ///
370    /// Produces an empty iterator if the node doesn't exist.<br>
371    /// Iterator element type is `(N, &E)`.
372    pub fn edges(&self, from: N) -> Edges<N, E, Ty> {
373        Edges {
374            from,
375            iter: self.neighbors(from),
376            edges: &self.edges,
377        }
378    }
379
380    /// Return a reference to the edge weight connecting `a` with `b`, or
381    /// `None` if the edge does not exist in the graph.
382    pub fn edge_weight(&self, a: N, b: N) -> Option<&E> {
383        self.edges.get(&Self::edge_key(a, b))
384    }
385
386    /// Return a mutable reference to the edge weight connecting `a` with `b`,
387    /// or `None` if the edge does not exist in the graph.
388    pub fn edge_weight_mut(&mut self, a: N, b: N) -> Option<&mut E> {
389        self.edges.get_mut(&Self::edge_key(a, b))
390    }
391
392    /// Return an iterator over all edges of the graph with their weight in
393    /// arbitrary order.
394    ///
395    /// Iterator element type is `(N, N, &E)`
396    pub fn all_edges(&self) -> AllEdges<N, E, Ty> {
397        AllEdges {
398            inner: self.edges.iter(),
399            ty: self.ty,
400        }
401    }
402
403    /// Return an iterator over all edges of the graph in arbitrary order, with
404    /// a mutable reference to their weight.
405    ///
406    /// Iterator element type is `(N, N, &mut E)`
407    pub fn all_edges_mut(&mut self) -> AllEdgesMut<N, E, Ty> {
408        AllEdgesMut {
409            inner: self.edges.iter_mut(),
410            ty: self.ty,
411        }
412    }
413
414    /// Return a `Graph` that corresponds to this `GraphMap`.
415    ///
416    /// 1. Note that node and edge indices in the `Graph` have nothing in common
417    ///    with the `GraphMap`s node weights `N`. The node weights `N` are used
418    ///    as node weights in the resulting `Graph`, too.
419    /// 2. Note that the index type is user-chosen.
420    ///
421    /// Computes in **O(|V| + |E|)** time (average).
422    ///
423    /// **Panics** if the number of nodes or edges does not fit with
424    /// the resulting graph's index type.
425    pub fn into_graph<Ix>(self) -> Graph<N, E, Ty, Ix>
426    where
427        Ix: petgraph::graph::IndexType,
428    {
429        // assuming two successive iterations of the same hashmap produce the same order
430        let mut gr = Graph::with_capacity(self.node_count(), self.edge_count());
431        for (&node, _) in &self.nodes {
432            gr.add_node(node);
433        }
434        for ((a, b), edge_weight) in self.edges {
435            let (ai, _, _) = self.nodes.get_full(&a).unwrap();
436            let (bi, _, _) = self.nodes.get_full(&b).unwrap();
437            gr.add_edge(node_index(ai), node_index(bi), edge_weight);
438        }
439        gr
440    }
441}
442
443/// Create a new `GraphMap` from an iterable of edges.
444impl<N, E, Ty, Item> FromIterator<Item> for FastGraphMap<N, E, Ty>
445where
446    Item: IntoWeightedEdge<E, NodeId = N>,
447    N: NodeTrait,
448    Ty: EdgeType,
449{
450    fn from_iter<I>(iterable: I) -> Self
451    where
452        I: IntoIterator<Item = Item>,
453    {
454        let iter = iterable.into_iter();
455        let (low, _) = iter.size_hint();
456        let mut g = Self::with_capacity(0, low);
457        g.extend(iter);
458        g
459    }
460}
461
462/// Extend the graph from an iterable of edges.
463///
464/// Nodes are inserted automatically to match the edges.
465impl<N, E, Ty, Item> Extend<Item> for FastGraphMap<N, E, Ty>
466where
467    Item: IntoWeightedEdge<E, NodeId = N>,
468    N: NodeTrait,
469    Ty: EdgeType,
470{
471    fn extend<I>(&mut self, iterable: I)
472    where
473        I: IntoIterator<Item = Item>,
474    {
475        let iter = iterable.into_iter();
476        let (low, _) = iter.size_hint();
477        self.edges.reserve(low);
478
479        for elt in iter {
480            let (source, target, weight) = elt.into_weighted_edge();
481            self.add_edge(source, target, weight);
482        }
483    }
484}
485
486macro_rules! iterator_wrap {
487    ($name: ident <$($typarm:tt),*> where { $($bounds: tt)* }
488     item: $item: ty,
489     iter: $iter: ty,
490     ) => (
491        pub struct $name <$($typarm),*> where $($bounds)* {
492            iter: $iter,
493        }
494        impl<$($typarm),*> Iterator for $name <$($typarm),*>
495            where $($bounds)*
496        {
497            type Item = $item;
498            #[inline]
499            fn next(&mut self) -> Option<Self::Item> {
500                self.iter.next()
501            }
502
503            #[inline]
504            fn size_hint(&self) -> (usize, Option<usize>) {
505                self.iter.size_hint()
506            }
507        }
508    );
509}
510
511iterator_wrap! {
512    Nodes <'a, N> where { N: 'a + NodeTrait }
513    item: N,
514    iter: Cloned<Keys<'a, N, Vec<(N, CompactDirection)>>>,
515}
516
517pub struct Neighbors<'a, N, Ty = Undirected>
518where
519    N: 'a,
520    Ty: EdgeType,
521{
522    iter: Iter<'a, (N, CompactDirection)>,
523    ty: PhantomData<Ty>,
524}
525
526impl<N, Ty> Iterator for Neighbors<'_, N, Ty>
527where
528    N: NodeTrait,
529    Ty: EdgeType,
530{
531    type Item = N;
532
533    fn next(&mut self) -> Option<N> {
534        if Ty::is_directed() {
535            (&mut self.iter)
536                .filter_map(|&(n, dir)| if dir == Outgoing { Some(n) } else { None })
537                .next()
538        } else {
539            self.iter.next().map(|&(n, _)| n)
540        }
541    }
542}
543
544pub struct NeighborsDirected<'a, N, Ty>
545where
546    N: 'a,
547    Ty: EdgeType,
548{
549    iter: Iter<'a, (N, CompactDirection)>,
550    start_node: N,
551    dir: Direction,
552    ty: PhantomData<Ty>,
553}
554
555impl<N, Ty> Iterator for NeighborsDirected<'_, N, Ty>
556where
557    N: NodeTrait,
558    Ty: EdgeType,
559{
560    type Item = N;
561
562    fn next(&mut self) -> Option<N> {
563        if Ty::is_directed() {
564            let self_dir = self.dir;
565            let start_node = self.start_node;
566            (&mut self.iter)
567                .filter_map(move |&(n, dir)| {
568                    if dir == self_dir || n == start_node {
569                        Some(n)
570                    } else {
571                        None
572                    }
573                })
574                .next()
575        } else {
576            self.iter.next().map(|&(n, _)| n)
577        }
578    }
579}
580
581pub struct Edges<'a, N, E: 'a, Ty>
582where
583    N: 'a + NodeTrait,
584    Ty: EdgeType,
585{
586    from: N,
587    edges: &'a IndexMap<(N, N), E, FxBuildHasher>,
588    iter: Neighbors<'a, N, Ty>,
589}
590
591impl<'a, N, E, Ty> Iterator for Edges<'a, N, E, Ty>
592where
593    N: 'a + NodeTrait,
594    E: 'a,
595    Ty: EdgeType,
596{
597    type Item = (N, N, &'a E);
598
599    fn next(&mut self) -> Option<Self::Item> {
600        match self.iter.next() {
601            None => None,
602            Some(b) => {
603                let a = self.from;
604                match self.edges.get(&FastGraphMap::<N, E, Ty>::edge_key(a, b)) {
605                    None => unreachable!(),
606                    Some(edge) => Some((a, b, edge)),
607                }
608            }
609        }
610    }
611}
612
613pub struct AllEdges<'a, N, E: 'a, Ty>
614where
615    N: 'a + NodeTrait,
616{
617    inner: IndexMapIter<'a, (N, N), E>,
618    ty: PhantomData<Ty>,
619}
620
621impl<'a, N, E, Ty> Iterator for AllEdges<'a, N, E, Ty>
622where
623    N: 'a + NodeTrait,
624    E: 'a,
625    Ty: EdgeType,
626{
627    type Item = (N, N, &'a E);
628
629    fn next(&mut self) -> Option<Self::Item> {
630        self.inner.next().map(|(&(a, b), v)| (a, b, v))
631    }
632
633    fn size_hint(&self) -> (usize, Option<usize>) {
634        self.inner.size_hint()
635    }
636
637    fn count(self) -> usize {
638        self.inner.count()
639    }
640
641    fn nth(&mut self, n: usize) -> Option<Self::Item> {
642        self.inner
643            .nth(n)
644            .map(|(&(n1, n2), weight)| (n1, n2, weight))
645    }
646
647    fn last(self) -> Option<Self::Item> {
648        self.inner
649            .last()
650            .map(|(&(n1, n2), weight)| (n1, n2, weight))
651    }
652}
653
654impl<'a, N, E, Ty> DoubleEndedIterator for AllEdges<'a, N, E, Ty>
655where
656    N: 'a + NodeTrait,
657    E: 'a,
658    Ty: EdgeType,
659{
660    fn next_back(&mut self) -> Option<Self::Item> {
661        self.inner
662            .next_back()
663            .map(|(&(n1, n2), weight)| (n1, n2, weight))
664    }
665}
666
667pub struct AllEdgesMut<'a, N, E: 'a, Ty>
668where
669    N: 'a + NodeTrait,
670{
671    inner: IndexMapIterMut<'a, (N, N), E>,
672    ty: PhantomData<Ty>,
673}
674
675impl<'a, N, E, Ty> Iterator for AllEdgesMut<'a, N, E, Ty>
676where
677    N: 'a + NodeTrait,
678    E: 'a,
679    Ty: EdgeType,
680{
681    type Item = (N, N, &'a mut E);
682
683    fn next(&mut self) -> Option<Self::Item> {
684        self.inner
685            .next()
686            .map(|(&(n1, n2), weight)| (n1, n2, weight))
687    }
688
689    fn size_hint(&self) -> (usize, Option<usize>) {
690        self.inner.size_hint()
691    }
692
693    fn count(self) -> usize {
694        self.inner.count()
695    }
696
697    fn nth(&mut self, n: usize) -> Option<Self::Item> {
698        self.inner
699            .nth(n)
700            .map(|(&(n1, n2), weight)| (n1, n2, weight))
701    }
702
703    fn last(self) -> Option<Self::Item> {
704        self.inner
705            .last()
706            .map(|(&(n1, n2), weight)| (n1, n2, weight))
707    }
708}
709
710impl<'a, N, E, Ty> DoubleEndedIterator for AllEdgesMut<'a, N, E, Ty>
711where
712    N: 'a + NodeTrait,
713    E: 'a,
714    Ty: EdgeType,
715{
716    fn next_back(&mut self) -> Option<Self::Item> {
717        self.inner
718            .next_back()
719            .map(|(&(n1, n2), weight)| (n1, n2, weight))
720    }
721}
722
723/// Create a new empty `GraphMap`.
724impl<N, E, Ty> Default for FastGraphMap<N, E, Ty>
725where
726    N: NodeTrait,
727    Ty: EdgeType,
728{
729    fn default() -> Self {
730        FastGraphMap::with_capacity(0, 0)
731    }
732}
733
734/// A reference that is hashed and compared by its pointer value.
735///
736/// `Ptr` is used for certain configurations of `GraphMap`,
737/// in particular in the combination where the node type for
738/// `GraphMap` is something of type for example `Ptr(&Cell<T>)`,
739/// with the `Cell<T>` being `TypedArena` allocated.
740pub struct Ptr<'b, T: 'b>(pub &'b T);
741
742impl<T> Copy for Ptr<'_, T> {}
743impl<T> Clone for Ptr<'_, T> {
744    fn clone(&self) -> Self {
745        *self
746    }
747}
748
749fn ptr_eq<T>(a: *const T, b: *const T) -> bool {
750    a == b
751}
752
753impl<'b, T> PartialEq for Ptr<'b, T> {
754    /// Ptr compares by pointer equality, i.e if they point to the same value
755    fn eq(&self, other: &Ptr<'b, T>) -> bool {
756        ptr_eq(self.0, other.0)
757    }
758}
759
760impl<'b, T> PartialOrd for Ptr<'b, T> {
761    fn partial_cmp(&self, other: &Ptr<'b, T>) -> Option<Ordering> {
762        Some(self.cmp(other))
763    }
764}
765
766impl<'b, T> Ord for Ptr<'b, T> {
767    /// Ptr is ordered by pointer value, i.e. an arbitrary but stable and total
768    /// order.
769    fn cmp(&self, other: &Ptr<'b, T>) -> Ordering {
770        let a: *const T = self.0;
771        let b: *const T = other.0;
772        a.cmp(&b)
773    }
774}
775
776impl<T> Deref for Ptr<'_, T> {
777    type Target = T;
778
779    fn deref(&self) -> &T {
780        self.0
781    }
782}
783
784impl<T> Eq for Ptr<'_, T> {}
785
786impl<T> Hash for Ptr<'_, T> {
787    fn hash<H: hash::Hasher>(&self, st: &mut H) {
788        let ptr = (self.0) as *const T;
789        ptr.hash(st)
790    }
791}
792
793impl<T: fmt::Debug> fmt::Debug for Ptr<'_, T> {
794    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
795        self.0.fmt(f)
796    }
797}
798
799pub struct NodeIdentifiers<'a, N, E: 'a, Ty>
800where
801    N: 'a + NodeTrait,
802{
803    iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
804    ty: PhantomData<Ty>,
805    edge_ty: PhantomData<E>,
806}
807
808impl<'a, N, E, Ty> Iterator for NodeIdentifiers<'a, N, E, Ty>
809where
810    N: 'a + NodeTrait,
811    E: 'a,
812    Ty: EdgeType,
813{
814    type Item = N;
815
816    fn next(&mut self) -> Option<Self::Item> {
817        self.iter.next().map(|(&n, _)| n)
818    }
819}
820
821pub struct NodeReferences<'a, N, E: 'a, Ty>
822where
823    N: 'a + NodeTrait,
824{
825    iter: IndexMapIter<'a, N, Vec<(N, CompactDirection)>>,
826    ty: PhantomData<Ty>,
827    edge_ty: PhantomData<E>,
828}
829
830impl<'a, N, E, Ty> Iterator for NodeReferences<'a, N, E, Ty>
831where
832    N: 'a + NodeTrait,
833    E: 'a,
834    Ty: EdgeType,
835{
836    type Item = (N, &'a N);
837
838    fn next(&mut self) -> Option<Self::Item> {
839        self.iter.next().map(|(n, _)| (*n, n))
840    }
841}
842
843impl<N, E, Ty> NodeCount for FastGraphMap<N, E, Ty>
844where
845    N: Copy + PartialEq,
846{
847    fn node_count(&self) -> usize {
848        self.nodes.len()
849    }
850}
851
852impl<N, E, Ty> GraphBase for FastGraphMap<N, E, Ty>
853where
854    N: Copy + PartialEq,
855{
856    type EdgeId = (N, N);
857    type NodeId = N;
858}
859
860impl<N, E, Ty> Visitable for FastGraphMap<N, E, Ty>
861where
862    N: Copy + Ord + Hash,
863    Ty: EdgeType,
864{
865    type Map = FxHashSet<N>;
866
867    fn visit_map(&self) -> FxHashSet<N> {
868        FxHashSet::with_capacity_and_hasher(self.node_count(), Default::default())
869    }
870
871    fn reset_map(&self, map: &mut Self::Map) {
872        map.clear();
873    }
874}
875
876impl<'a, N: 'a, E, Ty> IntoNeighbors for &'a FastGraphMap<N, E, Ty>
877where
878    N: Copy + Ord + Hash,
879    Ty: EdgeType,
880{
881    type Neighbors = Neighbors<'a, N, Ty>;
882
883    fn neighbors(self, n: Self::NodeId) -> Self::Neighbors {
884        self.neighbors(n)
885    }
886}
887
888impl<'a, N: 'a, E, Ty> IntoNeighborsDirected for &'a FastGraphMap<N, E, Ty>
889where
890    N: Copy + Ord + Hash,
891    Ty: EdgeType,
892{
893    type NeighborsDirected = NeighborsDirected<'a, N, Ty>;
894
895    fn neighbors_directed(self, n: N, dir: Direction) -> Self::NeighborsDirected {
896        self.neighbors_directed(n, dir)
897    }
898}
899
900impl<'a, N, E: 'a, Ty> IntoNodeIdentifiers for &'a FastGraphMap<N, E, Ty>
901where
902    N: NodeTrait,
903    Ty: EdgeType,
904{
905    type NodeIdentifiers = NodeIdentifiers<'a, N, E, Ty>;
906
907    fn node_identifiers(self) -> Self::NodeIdentifiers {
908        NodeIdentifiers {
909            iter: self.nodes.iter(),
910            ty: self.ty,
911            edge_ty: PhantomData,
912        }
913    }
914}
915
916impl<N, E, Ty> NodeIndexable for FastGraphMap<N, E, Ty>
917where
918    N: NodeTrait,
919    Ty: EdgeType,
920{
921    fn node_bound(&self) -> usize {
922        self.node_count()
923    }
924
925    fn to_index(&self, ix: Self::NodeId) -> usize {
926        let (i, _, _) = self.nodes.get_full(&ix).unwrap();
927        i
928    }
929
930    fn from_index(&self, ix: usize) -> Self::NodeId {
931        assert!(
932            ix < self.nodes.len(),
933            "The requested index {} is out-of-bounds.",
934            ix
935        );
936        let (&key, _) = self.nodes.get_index(ix).unwrap();
937        key
938    }
939}
swc_fast_graph/digraph.rs

swc_fast_graph/
digraph.rs
