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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106

use DirectedWeightedGraph;
use collections::Map;
use std::iter;

pub struct MapGraph<M>(M);

impl<M> From<M> for MapGraph<M> {
    fn from(map: M) -> Self {
        MapGraph(map)
    }
}

impl<M> MapGraph<M> {
    /// Returns the inner `Map` of this graph.
    pub fn unwrap(self) -> M {
        let MapGraph(graph) = self;
        graph
    }
}

// This implementation requires the key to be cloned.
impl<'m, N, W, M> DirectedWeightedGraph<'m, N, W> for MapGraph<M>
where
    M: Map<'m, (N, N), W>,
    N: 'm + Eq + Clone,
    W: 'm,
{
    type AllWeightedEdges = iter::Map<M::Iter, fn((&'m (N, N), &'m W)) -> (&'m N, &'m N, &'m W)>;
    type AllWeightedEdgesMut = iter::Map<
        M::IterMut,
        fn((&'m (N, N), &'m mut W)) -> (&'m N, &'m N, &'m mut W),
    >;

    fn all_edges(&'m self) -> Self::AllWeightedEdges {
        fn map_weighted_edge<'m, N, W>(
            (&(ref source, ref sink), weight): (&'m (N, N), &'m W),
        ) -> (&'m N, &'m N, &'m W) {
            (source, sink, weight)
        }

        let &MapGraph(ref map) = self;

        map.iter().map(map_weighted_edge)

    }

    fn all_edges_mut(&'m mut self) -> Self::AllWeightedEdgesMut {
        fn map_weighted_edge_mut<'m, N, W>(
            (&(ref source, ref sink), &mut ref mut weight): (&'m (N, N), &'m mut W),
        ) -> (&'m N, &'m N, &'m mut W) {
            (source, sink, weight)
        }

        let &mut MapGraph(ref mut map) = self;

        map.iter_mut().map(map_weighted_edge_mut)
    }

    fn add_edge(&'m mut self, source: N, sink: N, weight: W) -> Option<(N, N, W)> {
        let &mut MapGraph(ref mut map) = self;

        map.insert((source, sink), weight)
            .map(|((source, sink), value)| (source, sink, value))
    }

    // Clones the key!
    fn remove_edge(&'m mut self, source: &N, sink: &N) -> Option<(N, N, W)> {
        let &mut MapGraph(ref mut map) = self;
        let key = (source.clone(), sink.clone());

        map.remove(&key)
            .map(|((source, sink), value)| (source, sink, value))
    }

    // Clones the key!
    fn edge_weight(&'m self, source: &N, sink: &N) -> Option<&W> {
        let &MapGraph(ref map) = self;
        map.get(&(source.clone(), sink.clone()))
    }

    // Clones the key!
    fn edge_weight_mut(&'m mut self, source: &N, sink: &N) -> Option<&mut W> {
        let &mut MapGraph(ref mut map) = self;
        map.get_mut(&(source.clone(), sink.clone()))
    }
}


// pub struct AllWeightedEdges<Iter> {
//     iter: Iter,
// }

// impl<'m, N, W, Iter> Iterator for AllWeightedEdges<Iter>
// where
//     Iter: Iterator<Item = (&'m (N, N), &'m W)>,
//     N: 'm,
//     W: 'm,
// {
//     type Item = (&'m N, &'m N, &'m W);

//     fn next(&mut self) -> Option<Self::Item> {
//         self.iter
//             .next()
//             .map(|(&(ref source, ref sink), weight)| (source, sink, weight))
//     }
// }