rs-graph 0.7.0

/*
 * Copyright (c) 2017 Frank Fischer <frank-fischer@shadow-soft.de>
 *
 * This program is free software: you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see  <http://www.gnu.org/licenses/>
 */

//! This module provides vectors that can be indexed by nodes, edges or arcs.

use graph::{IndexGraph, IndexNetwork};

use std::ops::{Index, IndexMut, Deref};
use std::marker::PhantomData;
use std::mem;
use std::slice::IterMut;
use std::fmt;

/// A mapper of graph items to indices.
pub trait GraphIndexer {
    type Graph;
    type Item;

    fn index(g: &Self::Graph, item: Self::Item) -> usize;

    fn num_items(g: &Self::Graph) -> usize;
}

/// A borrowed slice indexed by items of a graph.
pub struct GraphSlice<'a, 'b, G, Idx, T>
    where G: 'a,
          Idx: GraphIndexer<Graph=G>,
          T: 'b,
{
    g: &'a G,
    data: &'b [T],
    phantom: PhantomData<Idx>,
}

/// A mutable borrowed slice indexed by items of a graph.
pub struct GraphSliceMut<'a, 'b, G, Idx, T>
    where G: 'a,
          Idx: GraphIndexer<Graph=G>,
          T: 'b,
{
    g: &'a G,
    data: &'b mut [T],
    phantom: PhantomData<Idx>,
}

/// An owned vector indexed by items of a graph.
pub struct GraphVec<'a, G, Idx, T>
    where G: 'a,
          Idx: GraphIndexer<Graph=G>
{
    g: &'a G,
    data: Vec<T>,
    phantom: PhantomData<Idx>,
}

impl<'a, G, Idx, T> Clone for GraphVec<'a, G, Idx, T>
    where G: 'a,
          Idx: GraphIndexer<Graph=G>,
          T: Clone,
{
    fn clone(&self) -> Self {
        GraphVec {
            g: self.g,
            data: self.data.clone(),
            phantom: PhantomData,
        }
    }
}

impl<'a, G, Idx, T> fmt::Debug for GraphVec<'a, G, Idx, T>
    where G: 'a,
          Idx: GraphIndexer<Graph=G>,
          T: fmt::Debug,
{
    fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        self.data.fmt(fmt)
    }
}

impl<'a, 'b, G, Idx, T> fmt::Debug for GraphSlice<'a, 'b, G, Idx, T>
    where G: 'a,
          Idx: GraphIndexer<Graph=G>,
          T: 'b + fmt::Debug,
{
    fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        self.data.fmt(fmt)
    }
}

impl<'a, 'b, G, Idx, T> fmt::Debug for GraphSliceMut<'a, 'b, G, Idx, T>
    where G: 'a,
          Idx: GraphIndexer<Graph=G>,
          T: 'b + fmt::Debug,
{
    fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
        self.data.fmt(fmt)
    }
}

impl<'a, 'b, G, Idx, T> Deref for GraphSliceMut<'a, 'b, G, Idx, T>
    where G: 'a,
          Idx: GraphIndexer<Graph=G>
{
    type Target = GraphSliceMut<'a, 'b, G, Idx, T>;
    fn deref(&self) -> &Self::Target {
        unsafe {
            mem::transmute(&self)
        }
    }
}

impl<'a, 'b, G, Idx, T> GraphSlice<'a, 'b, G, Idx, T>
    where G: 'a,
          Idx: GraphIndexer<Graph=G>
{
    pub fn new(g: &'a G, data: &'b [T]) -> GraphSlice<'a, 'b, G, Idx, T> {
        assert_eq!(Idx::num_items(g), data.len(),
                   "Slice must have size {}", Idx::num_items(g));
        GraphSlice {
            g: g,
            data: data,
            phantom: PhantomData,
        }
    }

    /// Apply `f` to all elements and return a new vector.
    pub fn map<F, R>(&self, f: F) -> GraphVec<'a, G, Idx, R>
        where F: Fn(&T) -> R
    {
        GraphVec {
            g: self.g,
            data: self.data.iter().map(f).collect(),
            phantom: PhantomData,
        }
    }
}

impl<'a, 'b, G, Idx, T> GraphSliceMut<'a, 'b, G, Idx, T>
    where G: 'a,
          Idx: GraphIndexer<Graph=G>
{
    pub fn new(g: &'a G, data: &'b mut [T]) -> GraphSliceMut<'a, 'b, G, Idx, T> {
        assert_eq!(Idx::num_items(g), data.len(),
                   "Slice must have size {}", Idx::num_items(g));
        GraphSliceMut {
            g: g,
            data: data,
            phantom: PhantomData,
        }
    }

    /// Return a mutable iterator over all elements.
    pub fn iter_mut(&mut self) -> IterMut<T> {
        self.data.iter_mut()
    }
}

impl<'a, G, Idx, T> GraphVec<'a, G, Idx, T>
    where G: 'a,
          Idx: GraphIndexer<Graph=G>
{
    pub fn from_vec(g: &'a G, values: Vec<T>) -> Self {
        assert_eq!(Idx::num_items(g), values.len(),
                   "Vector must have size {}", Idx::num_items(g));
        GraphVec {
            g: g,
            data: values,
            phantom: PhantomData,
        }
    }

    pub fn as_slice<'s>(&'s self) -> GraphSlice<'a, 's, G, Idx, T>
        where 'a: 's,
    {
        GraphSlice {
            g: self.g,
            data: self.data.as_slice(),
            phantom: PhantomData,
        }
    }

    pub fn as_mut_slice<'b>(&'a mut self) -> GraphSliceMut<'a, 'b, G, Idx, T>
        where 'a: 'b
    {
        GraphSliceMut {
            g: self.g,
            data: self.data.as_mut_slice(),
            phantom: PhantomData,
        }
    }

    /// Set all elements to x.
    pub fn reset(&mut self, x: T)
        where T: Clone
    {
        let n = self.data.len();
        self.data.clear();
        self.data.resize(n, x);
    }

    /// Apply `f` to all elements and return a new vector.
    pub fn map<F, R>(&self, f: F) -> GraphVec<'a, G, Idx, R>
        where F: Fn(&T) -> R
    {
        GraphVec {
            g: self.g,
            data: self.data.iter().map(f).collect(),
            phantom: PhantomData,
        }
    }

    /// Apply `f` to all elements and return a new vector.
    pub fn map_into<F, R>(self, f: F) -> GraphVec<'a, G, Idx, R>
        where F: Fn(T) -> R
    {
        GraphVec {
            g: self.g,
            data: self.data.into_iter().map(f).collect(),
            phantom: PhantomData,
        }
    }

    /// Return a mutable iterator over all elements.
    pub fn iter_mut(&mut self) -> IterMut<T> {
        self.data.iter_mut()
    }
}

impl<'a, 'b, G, Idx, T> Index<Idx::Item> for GraphSlice<'a, 'b, G, Idx, T>
    where Idx: GraphIndexer<Graph=G>
{
    type Output = T;
    fn index(&self, u: Idx::Item) -> &T {
        &self.data[Idx::index(self.g, u)]
    }
}

impl<'a, 'b, G, Idx, T> Index<Idx::Item> for GraphSliceMut<'a, 'b, G, Idx, T>
    where Idx: GraphIndexer<Graph=G>
{
    type Output = T;
    fn index(&self, u: Idx::Item) -> &T {
        &self.data[Idx::index(self.g, u)]
    }
}

impl<'a, 'b, G, Idx, T> IndexMut<Idx::Item> for GraphSliceMut<'a, 'b, G, Idx, T>
    where Idx: GraphIndexer<Graph=G>
{
    fn index_mut(&mut self, u: Idx::Item) -> &mut T {
        &mut self.data[Idx::index(self.g, u)]
    }
}

impl<'a, G, Idx, T> Index<Idx::Item> for GraphVec<'a, G, Idx, T>
    where Idx: GraphIndexer<Graph=G>
{
    type Output = T;
    fn index(&self, u: Idx::Item) -> &T {
        &self.data[Idx::index(self.g, u)]
    }
}

impl<'a, G, Idx, T> IndexMut<Idx::Item> for GraphVec<'a, G, Idx, T>
    where Idx: GraphIndexer<Graph=G>
{
    fn index_mut(&mut self, u: Idx::Item) -> &mut T {
        &mut self.data[Idx::index(self.g, u)]
    }
}

impl<'a, 'b, G, Idx, T> Deref for GraphSlice<'a, 'b, G, Idx, T>
    where Idx: GraphIndexer<Graph=G>
{
    type Target = [T];

    fn deref(&self) -> &[T] {
        self.data
    }
}

impl<'a, G, Idx, T> Deref for GraphVec<'a, G, Idx, T>
    where Idx: GraphIndexer<Graph=G>
{
    type Target = [T];

    fn deref(&self) -> &[T] {
        &self.data
    }
}

/// Indexer for nodes.
pub struct GraphNodeIndexer<'a, G: 'a>(PhantomData<&'a G>);

impl<'a, G: 'a> GraphIndexer for GraphNodeIndexer<'a, G>
    where G: IndexGraph<'a>
{
    type Graph = G;
    type Item = G::Node;

    fn index(g: &G, u: G::Node) -> usize {
        g.node_id(u)
    }

    fn num_items(g: &Self::Graph) -> usize {
        g.num_nodes()
    }
}

/// Indexer for edges.
pub struct GraphEdgeIndexer<'a, G: 'a>(PhantomData<&'a G>);

impl<'a, G: 'a> GraphIndexer for GraphEdgeIndexer<'a, G>
    where G: IndexGraph<'a>
{
    type Graph = G;
    type Item = G::Edge;

    fn index(g: &G, u: G::Edge) -> usize {
        g.edge_id(u)
    }

    fn num_items(g: &Self::Graph) -> usize {
        g.num_edges()
    }
}

/// Indexer for biedges of a network.
pub struct GraphBiEdgeIndexer<'a, G: 'a>(PhantomData<&'a G>);

impl<'a, G: 'a> GraphIndexer for GraphBiEdgeIndexer<'a, G>
    where G: IndexNetwork<'a>
{
    type Graph = G;
    type Item = G::Edge;

    fn index(g: &G, u: G::Edge) -> usize {
        g.biedge_id(u)
    }

    fn num_items(g: &Self::Graph) -> usize {
        g.num_edges() * 2
    }
}

/// Slice of a node indexed vector.
pub type NodeSlice<'a, 'b, G, T> = GraphSlice<'a, 'b, G, GraphNodeIndexer<'a, G>, T>;

/// Mutable slice of a node indexed vector.
pub type NodeSliceMut<'a, 'b, G, T> = GraphSliceMut<'a, 'b, G, GraphNodeIndexer<'a, G>, T>;

/// Node indexed vector.
pub type NodeVec<'a, G, T> = GraphVec<'a, G, GraphNodeIndexer<'a, G>, T>;


/// Slice of a edge indexed vector.
pub type EdgeSlice<'a, 'b, G, T> = GraphSlice<'a, 'b, G, GraphEdgeIndexer<'a, G>, T>;

/// Mutable slice of a edge indexed vector.
pub type EdgeSliceMut<'a, 'b, G, T> = GraphSliceMut<'a, 'b, G, GraphEdgeIndexer<'a, G>, T>;

/// Edge indexed vector.
pub type EdgeVec<'a, G, T> = GraphVec<'a, G, GraphEdgeIndexer<'a, G>, T>;


/// Slice of a biedge indexed vector.
pub type BiEdgeSlice<'a, 'b, G, T> = GraphSlice<'a, 'b, G, GraphBiEdgeIndexer<'a, G>, T>;

/// Mutable slice of a biedge indexed vector.
pub type BiEdgeSliceMut<'a, 'b, G, T> = GraphSliceMut<'a, 'b, G, GraphBiEdgeIndexer<'a, G>, T>;

/// biedge indexed vector.
pub type BiEdgeVec<'a, G, T> = GraphVec<'a, G, GraphBiEdgeIndexer<'a, G>, T>;


#[cfg(test)]
mod tests {
    use {Graph, LinkedListGraph};
    use classes::peterson;

    #[test]
    fn test_iter() {
        let g = peterson::<LinkedListGraph>();
        let mut weights = edgevec![&g, (0..g.num_edges()).collect()];

        for (i, &x) in weights.iter().enumerate() {
            assert_eq!(i,x);
        }

        for x in weights.iter_mut() {
            *x = *x + 1;
        }

        for (i, &x) in weights.iter().enumerate() {
            assert_eq!(i + 1, x);
        }
    }

    #[test]
    fn test_map() {
        let g = peterson::<LinkedListGraph>();
        let weights = edgevec![&g, (0..g.num_edges()).collect()];

        let new_weights = weights.map(|i| i+1);
        for e in g.edges() {
            assert_eq!(weights[e] + 1, new_weights[e]);
        }

        let new_weights = new_weights.map_into(|i| i * 2);
        for e in g.edges() {
            assert_eq!(2 * (weights[e] + 1), new_weights[e]);
        }
    }
}