prty_bitgraph 0.1.1

extern crate fnv;

use super::Graph;
use self::fnv::FnvHashSet as HashSet;


#[derive(Default)]
pub struct SparseGraph {
    to_from: Vec<Vec<usize>>,
    from_to: Vec<HashSet<usize>>,
}

impl SparseGraph {
    pub fn new(len: usize) -> SparseGraph {
        let to_from = vec![Default::default(); len];
        let from_to = vec![Default::default(); len];
        SparseGraph { to_from, from_to }
    }
    pub fn iter_from_nobox<'a>(&'a self, from: usize) -> impl Iterator<Item = &usize> + 'a {
        self.from_to[from].iter()
    }
}

impl Graph for SparseGraph {
    type Node = usize;
    fn nb_nodes(&self) -> usize {
        self.to_from.len()
    }
    fn nodes(&self) -> Box<Iterator<Item = Self::Node>> {
        Box::new((0..self.nb_nodes()).into_iter())
    }
    fn get(&self, from: &Self::Node, to: &Self::Node) -> bool {
        self.from_to[*from].contains(to)
    }
    fn set_edge(&mut self, from: &Self::Node, to: &Self::Node, b: bool) {
        let to = *to;
        let from = *from;
        if b {
            if self.from_to[from].insert(to) {
                self.to_from[to].push(from);
            }
        } else {
            if self.from_to[from].remove(&to) {
                let v = &mut self.to_from[to];
                let idx = v.iter().position(|e| *e == from).unwrap();
                let item = v.swap_remove(idx);
                debug_assert!(item == from);
            }
        }
    }
    fn clear_all_to(&mut self, to: &Self::Node) {
        for node in self.to_from[*to].drain(..) {
            self.from_to[node].remove(&to);
        }
    }
    fn clear_all_from(&mut self, _: &Self::Node) {
        panic!("Not yet implemented")
    }
    fn add_all_to<I>(&mut self, to: &Self::Node, from: I)
    where
        I: IntoIterator<Item = Self::Node>,
    {
        let ft = &mut self.from_to;
        self.to_from[*to].extend(from.into_iter().filter(|from| ft[*from].insert(*to)));
    }
    fn iter_from<'a>(&'a self, from: Self::Node) -> Box<'a + Iterator<Item = Self::Node>> {
        Box::new(self.from_to[from].iter().cloned())
    }
    fn iter_to<'a>(&'a self, to: Self::Node) -> Box<'a + Iterator<Item = Self::Node>> {
        Box::new(self.to_from[to].iter().cloned())
    }
    fn has_from<'a>(&'a self, from: &Self::Node) -> bool {
        self.from_to[*from].len() != 0
    }
    fn has_to<'a>(&'a self, to: &Self::Node) -> bool {
        self.to_from[*to].len() != 0
    }
    fn drain_from_and_clear_all_to_drained<'a>(&'a mut self, from: Self::Node) -> Box<'a + Iterator<Item = Self::Node>> {
        use util::FinishIteratorExt;
        let nodes_from = ::std::mem::replace(&mut self.from_to[from], HashSet::default());
        Box::new(nodes_from.into_iter().inspect(move |node| self.clear_all_to(node)).finish())
    }
}