fera-graph 0.1.1

// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.

use graph::*;

use bit_vec::BitVec;

pub type BitVecVertexSet<G> = BitVecSet<VertexIndexProp<G>>;
pub type BitVecEdgeSet<G> = BitVecSet<EdgeIndexProp<G>>;

#[derive(Clone)]
pub struct BitVecSet<P> {
    len: usize,
    index: P,
    data: BitVec,
}

impl<T, P> Set<T> for BitVecSet<P>
    where T: Copy,
          P: PropGet<T, Output = usize>,
{
    fn insert(&mut self, item: T) -> bool {
        let i = self.index.get(item);
        // pre condition to insert: do not contains item
        !self.data[i] && {
            self.data.set(i, true);
            self.len += 1;
            true
        }
    }

    fn remove(&mut self, item: T) -> bool {
        let i = self.index.get(item);
        // pre condition to remove: contains item
        self.data[i] && {
            self.data.set(i, false);
            self.len -= 1;
            false
        }
    }

    fn contains(&self, item: T) -> bool {
        self.data[self.index.get(item)]
    }

    fn len(&self) -> usize {
        self.len
    }
}

impl<G> VertexSet<G> for BitVecVertexSet<G>
    where G: VertexList + VertexIndex
{
    fn new_vertex_set(g: &G) -> Self {
        BitVecSet {
            len: 0,
            index: g.vertex_index(),
            data: BitVec::with_capacity(g.num_vertices())
        }
    }
}

impl<G> EdgeSet<G> for BitVecEdgeSet<G>
    where G: EdgeList + EdgeIndex
{
    fn new_edge_set(g: &G) -> Self {
        BitVecSet {
            len: 0,
            index: g.edge_index(),
            data: BitVec::with_capacity(g.num_edges())
        }
    }
}