rustworkx_core/
distancemap.rs

1// Licensed under the Apache License, Version 2.0 (the "License"); you may
2// not use this file except in compliance with the License. You may obtain
3// a copy of the License at
4//
5//     http://www.apache.org/licenses/LICENSE-2.0
6//
7// Unless required by applicable law or agreed to in writing, software
8// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10// License for the specific language governing permissions and limitations
11// under the License.
12
13//! This module contains the [`DistanceMap`] trait which is used in
14//! [`shortest_path`](crate::shortest_path).
15//!
16//! The trait allows the shortest path functions to support multiple
17//! return types.
18
19use std::hash::Hash;
20
21use petgraph::graph::IndexType;
22
23use crate::dictmap::*;
24use hashbrown::HashMap;
25
26/// A mapping for storing the distances of nodes for shortest path algorithms.
27pub trait DistanceMap<K, V> {
28    /// Create mapping with support for items between 0 and `num_elements - 1`.
29    fn build(num_elements: usize) -> Self;
30
31    /// Get the distance to the item at `pos`. If the distance does not exist,
32    /// the function returns `None`.
33    fn get_item(&self, pos: K) -> Option<&V>;
34
35    /// Insert item at position `pos` with distance `V`.
36    fn put_item(&mut self, pos: K, val: V);
37}
38
39impl<K: IndexType, V: Clone> DistanceMap<K, V> for Vec<Option<V>> {
40    #[inline]
41    fn build(num_elements: usize) -> Self {
42        vec![None; num_elements]
43    }
44
45    #[inline]
46    fn get_item(&self, pos: K) -> Option<&V> {
47        self[pos.index()].as_ref()
48    }
49
50    #[inline]
51    fn put_item(&mut self, pos: K, val: V) {
52        self[pos.index()] = Some(val);
53    }
54}
55
56impl<K: Eq + Hash, V: Clone> DistanceMap<K, V> for DictMap<K, V> {
57    #[inline]
58    fn build(_num_elements: usize) -> Self {
59        DictMap::<K, V>::default()
60    }
61
62    #[inline]
63    fn get_item(&self, pos: K) -> Option<&V> {
64        self.get(&pos)
65    }
66
67    #[inline]
68    fn put_item(&mut self, pos: K, val: V) {
69        self.insert(pos, val);
70    }
71}
72
73impl<K: Eq + Hash, V: Clone> DistanceMap<K, V> for HashMap<K, V> {
74    #[inline]
75    fn build(_num_elements: usize) -> Self {
76        HashMap::<K, V>::default()
77    }
78
79    #[inline]
80    fn get_item(&self, pos: K) -> Option<&V> {
81        self.get(&pos)
82    }
83
84    #[inline]
85    fn put_item(&mut self, pos: K, val: V) {
86        self.insert(pos, val);
87    }
88}
rustworkx_core/distancemap.rs

rustworkx_core/
distancemap.rs
