use crate::traits::{Directed, DirectedEdge, GraphSize, GraphType, Undirected};
use std::iter::Filter;
pub struct FilteredGraph<'a, G, P>
where
G: GraphType<'a>,
P: for<'r> Fn(&'r G::Edge) -> bool,
{
graph: &'a G,
predicate: P,
}
#[derive(Clone)]
pub struct Filtered<I>(I);
pub struct FilterNeighIter<'a, I, P> {
it: I,
predicate: &'a P,
}
impl<'a, I, P, N, E> Iterator for FilterNeighIter<'a, I, P>
where
P: for<'r> Fn(&'r E) -> bool,
I: Iterator<Item = (E, N)>,
{
type Item = (E, N);
fn next(&mut self) -> Option<Self::Item> {
while let Some((e, v)) = self.it.next() {
if (self.predicate)(&e) {
return Some((e, v));
}
}
None
}
}
impl<'a, G, P> GraphType<'a> for FilteredGraph<'a, G, P>
where
G: GraphType<'a>,
P: 'a + for<'r> Fn(&'r G::Edge) -> bool,
{
type Node = G::Node;
type Edge = G::Edge;
}
impl<'a, G, P> GraphSize<'a> for FilteredGraph<'a, G, P>
where
G: GraphSize<'a>,
P: 'a + for<'r> Fn(&'r G::Edge) -> bool,
{
type NodeIter = G::NodeIter;
type EdgeIter = Filter<G::EdgeIter, &'a P>;
fn num_nodes(&self) -> usize {
self.graph.num_nodes()
}
fn num_edges(&self) -> usize {
self.graph.edges().filter(&self.predicate).count()
}
fn nodes(&'a self) -> Self::NodeIter {
self.graph.nodes()
}
fn edges(&'a self) -> Self::EdgeIter {
self.graph.edges().filter(&self.predicate)
}
}
impl<'a, G, P> Undirected<'a> for FilteredGraph<'a, G, P>
where
G: Undirected<'a>,
P: 'a + for<'r> Fn(&'r G::Edge) -> bool,
{
type Neigh = Filtered<G::Neigh>;
fn enodes(&'a self, e: Self::Edge) -> (Self::Node, Self::Node) {
debug_assert!((self.predicate)(&e), "Edge has been filtered");
self.graph.enodes(e)
}
fn first_neigh(&'a self, u: Self::Node) -> Option<Self::Neigh> {
let mut cur = self.graph.first_neigh(u);
while let Some(it) = cur {
if (self.predicate)(&self.graph.get_neigh(&it).0) {
return Some(Filtered(it));
}
cur = self.graph.next_neigh(it);
}
None
}
fn next_neigh(&'a self, it: Self::Neigh) -> Option<Self::Neigh> {
let mut cur = self.graph.next_neigh(it.0);
while let Some(it) = cur {
if (self.predicate)(&self.graph.get_neigh(&it).0) {
return Some(Filtered(it));
}
cur = self.graph.next_neigh(it);
}
None
}
fn get_neigh(&'a self, it: &Self::Neigh) -> (Self::Edge, Self::Node) {
self.graph.get_neigh(&it.0)
}
}
pub struct FilterDirectedIter<'a, I, P> {
it: I,
predicate: &'a P,
}
impl<'a, I, P, N, D, E> Iterator for FilterDirectedIter<'a, I, P>
where
P: for<'r> Fn(&'r E) -> bool,
I: Iterator<Item = (D, N)>,
D: DirectedEdge<Edge = E>,
{
type Item = (D, N);
fn next(&mut self) -> Option<Self::Item> {
while let Some((e, v)) = self.it.next() {
if (self.predicate)(&e.edge()) {
return Some((e, v));
}
}
None
}
}
impl<'a, G, P> Directed<'a> for FilteredGraph<'a, G, P>
where
G: Directed<'a>,
P: 'a + for<'r> Fn(&'r G::Edge) -> bool,
{
type OutEdge = Filtered<G::OutEdge>;
type InEdge = Filtered<G::InEdge>;
type IncidentEdge = Filtered<G::IncidentEdge>;
type DirectedEdge = G::DirectedEdge;
fn src(&'a self, e: Self::Edge) -> Self::Node {
debug_assert!((self.predicate)(&e), "Edge has been filtered");
self.graph.src(e)
}
fn snk(&'a self, e: Self::Edge) -> Self::Node {
debug_assert!((self.predicate)(&e), "Edge has been filtered");
self.graph.snk(e)
}
fn first_out(&'a self, u: Self::Node) -> Option<Self::OutEdge> {
let mut cur = self.graph.first_out(u);
while let Some(it) = cur {
if (self.predicate)(&self.graph.get_out(&it).0) {
return Some(Filtered(it));
}
cur = self.graph.next_out(it);
}
None
}
fn next_out(&'a self, it: Self::OutEdge) -> Option<Self::OutEdge> {
let mut cur = self.graph.next_out(it.0);
while let Some(it) = cur {
if (self.predicate)(&self.graph.get_out(&it).0) {
return Some(Filtered(it));
}
cur = self.graph.next_out(it);
}
None
}
fn get_out(&'a self, it: &Self::OutEdge) -> (Self::Edge, Self::Node) {
self.graph.get_out(&it.0)
}
fn first_in(&'a self, u: Self::Node) -> Option<Self::InEdge> {
let mut cur = self.graph.first_in(u);
while let Some(it) = cur {
if (self.predicate)(&self.graph.get_in(&it).0) {
return Some(Filtered(it));
}
cur = self.graph.next_in(it);
}
None
}
fn next_in(&'a self, it: Self::InEdge) -> Option<Self::InEdge> {
let mut cur = self.graph.next_in(it.0);
while let Some(it) = cur {
if (self.predicate)(&self.graph.get_in(&it).0) {
return Some(Filtered(it));
}
cur = self.graph.next_in(it);
}
None
}
fn get_in(&'a self, it: &Self::InEdge) -> (Self::Edge, Self::Node) {
self.graph.get_in(&it.0)
}
fn first_incident(&'a self, u: Self::Node) -> Option<Self::IncidentEdge> {
let mut cur = self.graph.first_incident(u);
while let Some(it) = cur {
if (self.predicate)(&self.graph.get_incident(&it).0.edge()) {
return Some(Filtered(it));
}
cur = self.graph.next_incident(it);
}
None
}
fn next_incident(&'a self, it: Self::IncidentEdge) -> Option<Self::IncidentEdge> {
let mut cur = self.graph.next_incident(it.0);
while let Some(it) = cur {
if (self.predicate)(&self.graph.get_incident(&it).0.edge()) {
return Some(Filtered(it));
}
cur = self.graph.next_incident(it);
}
None
}
fn get_incident(&'a self, it: &Self::IncidentEdge) -> (Self::DirectedEdge, Self::Node) {
self.graph.get_incident(&it.0)
}
}
pub fn filter<'a, G, P>(graph: &'a G, predicate: P) -> FilteredGraph<'a, G, P>
where
G: GraphType<'a>,
P: for<'r> Fn(&'r G::Edge) -> bool,
{
FilteredGraph { graph, predicate }
}