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
88

// Licensed under the Apache License, Version 2.0 (the "License"); you may
// not use this file except in compliance with the License. You may obtain
// a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations
// under the License.

//! This module contains the [`DistanceMap`] trait which is used in
//! [`shortest_path`](crate::shortest_path).
//!
//! The trait allows the shortest path functions to support multiple
//! return types.

use std::hash::Hash;

use petgraph::graph::IndexType;

use crate::dictmap::*;
use hashbrown::HashMap;

/// A mapping for storing the distances of nodes for shortest path algorithms.
pub trait DistanceMap<K, V> {
    /// Create mapping with support for items between 0 and `num_elements - 1`.
    fn build(num_elements: usize) -> Self;

    /// Get the distance to the item at `pos`. If the distance does not exist,
    /// the function returns `None`.
    fn get_item(&self, pos: K) -> Option<&V>;

    /// Insert item at position `pos` with distance `V`.
    fn put_item(&mut self, pos: K, val: V);
}

impl<K: IndexType, V: Clone> DistanceMap<K, V> for Vec<Option<V>> {
    #[inline]
    fn build(num_elements: usize) -> Self {
        vec![None; num_elements]
    }

    #[inline]
    fn get_item(&self, pos: K) -> Option<&V> {
        self[pos.index()].as_ref()
    }

    #[inline]
    fn put_item(&mut self, pos: K, val: V) {
        self[pos.index()] = Some(val);
    }
}

impl<K: Eq + Hash, V: Clone> DistanceMap<K, V> for DictMap<K, V> {
    #[inline]
    fn build(_num_elements: usize) -> Self {
        DictMap::<K, V>::default()
    }

    #[inline]
    fn get_item(&self, pos: K) -> Option<&V> {
        self.get(&pos)
    }

    #[inline]
    fn put_item(&mut self, pos: K, val: V) {
        self.insert(pos, val);
    }
}

impl<K: Eq + Hash, V: Clone> DistanceMap<K, V> for HashMap<K, V> {
    #[inline]
    fn build(_num_elements: usize) -> Self {
        HashMap::<K, V>::default()
    }

    #[inline]
    fn get_item(&self, pos: K) -> Option<&V> {
        self.get(&pos)
    }

    #[inline]
    fn put_item(&mut self, pos: K, val: V) {
        self.insert(pos, val);
    }
}