use self::Direction::{Incoming, Outgoing};
use crate::graph::{Directed, Graph, Undirected};
use crate::node::NodeTrait;
use crate::traverse::Neighbors;
use indexmap::map::Iter as IndexMapIter;
use indexmap::IndexMap;
use std::marker::PhantomData;
pub trait EdgeType {
fn is_directed() -> bool;
}
impl EdgeType for Directed {
#[inline]
fn is_directed() -> bool {
true
}
}
impl EdgeType for Undirected {
#[inline]
fn is_directed() -> bool {
false
}
}
pub struct Edges<'a, N, E: 'a, Ty>
where
N: 'a + NodeTrait,
Ty: EdgeType,
{
from: N,
edges: &'a IndexMap<(N, N), E>,
iter: Neighbors<'a, N, Ty>,
}
impl<'a, N, E, Ty> Edges<'a, N, E, Ty>
where
N: 'a + NodeTrait,
Ty: EdgeType,
{
pub fn new(from: N, edges: &'a IndexMap<(N, N), E>, iter: Neighbors<'a, N, Ty>) -> Self {
Self { from, edges, iter }
}
}
impl<'a, N, E, Ty> Iterator for Edges<'a, N, E, Ty>
where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType,
{
type Item = (N, N, &'a E);
fn next(&mut self) -> Option<Self::Item> {
match self.iter.next() {
None => None,
Some(b) => {
let a = self.from;
match self.edges.get(&Graph::<N, E, Ty>::edge_key(a, b)) {
None => unreachable!(),
Some(edge) => Some((a, b, edge)),
}
}
}
}
}
pub struct AllEdges<'a, N, E: 'a, Ty> {
inner: IndexMapIter<'a, (N, N), E>,
ty: PhantomData<Ty>,
}
impl<'a, N, E, Ty> AllEdges<'a, N, E, Ty>
where
N: 'a + NodeTrait,
{
pub fn new(inner: IndexMapIter<'a, (N, N), E>, ty: PhantomData<Ty>) -> Self {
Self { inner, ty }
}
}
impl<'a, N, E, Ty> Iterator for AllEdges<'a, N, E, Ty>
where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType,
{
type Item = (N, N, &'a E);
fn next(&mut self) -> Option<Self::Item> {
match self.inner.next() {
None => None,
Some((&(a, b), v)) => Some((a, b, v)),
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.inner.size_hint()
}
fn count(self) -> usize {
self.inner.count()
}
fn nth(&mut self, n: usize) -> Option<Self::Item> {
self.inner
.nth(n)
.map(|(&(n1, n2), weight)| (n1, n2, weight))
}
fn last(self) -> Option<Self::Item> {
self.inner
.last()
.map(|(&(n1, n2), weight)| (n1, n2, weight))
}
}
impl<'a, N, E, Ty> DoubleEndedIterator for AllEdges<'a, N, E, Ty>
where
N: 'a + NodeTrait,
E: 'a,
Ty: EdgeType,
{
fn next_back(&mut self) -> Option<Self::Item> {
self.inner
.next_back()
.map(|(&(n1, n2), weight)| (n1, n2, weight))
}
}
pub trait IntoWeightedEdge<E> {
type NodeId;
fn into_weighted_edge(self) -> (Self::NodeId, Self::NodeId, E);
}
impl<Ix, E> IntoWeightedEdge<E> for (Ix, Ix)
where
E: Default,
{
type NodeId = Ix;
fn into_weighted_edge(self) -> (Ix, Ix, E) {
let (s, t) = self;
(s, t, E::default())
}
}
impl<Ix, E> IntoWeightedEdge<E> for (Ix, Ix, E) {
type NodeId = Ix;
fn into_weighted_edge(self) -> (Ix, Ix, E) {
self
}
}
impl<'a, Ix, E> IntoWeightedEdge<E> for (Ix, Ix, &'a E)
where
E: Clone,
{
type NodeId = Ix;
fn into_weighted_edge(self) -> (Ix, Ix, E) {
let (a, b, c) = self;
(a, b, c.clone())
}
}
impl<'a, Ix, E> IntoWeightedEdge<E> for &'a (Ix, Ix)
where
Ix: Copy,
E: Default,
{
type NodeId = Ix;
fn into_weighted_edge(self) -> (Ix, Ix, E) {
let (s, t) = *self;
(s, t, E::default())
}
}
impl<'a, Ix, E> IntoWeightedEdge<E> for &'a (Ix, Ix, E)
where
Ix: Copy,
E: Clone,
{
type NodeId = Ix;
fn into_weighted_edge(self) -> (Ix, Ix, E) {
self.clone()
}
}
#[derive(Copy, Debug, PartialEq, PartialOrd, Ord, Eq, Hash)]
#[repr(usize)]
pub enum Direction {
Outgoing = 0,
Incoming = 1,
}
copyclone!(Direction);
impl Direction {
#[inline]
pub fn opposite(self) -> Direction {
match self {
Outgoing => Incoming,
Incoming => Outgoing,
}
}
#[inline]
pub fn index(self) -> usize {
(self as usize) & 0x1
}
}
#[derive(Copy, Clone, Debug, PartialEq)]
pub enum CompactDirection {
Outgoing,
Incoming,
}
impl From<Direction> for CompactDirection {
fn from(d: Direction) -> Self {
match d {
Outgoing => CompactDirection::Outgoing,
Incoming => CompactDirection::Incoming,
}
}
}
impl PartialEq<Direction> for CompactDirection {
fn eq(&self, rhs: &Direction) -> bool {
(*self as usize) == (*rhs as usize)
}
}
#[cfg(test)]
mod tests {
use crate::edge::{AllEdges, CompactDirection, Direction, EdgeType, Edges, IntoWeightedEdge};
use crate::graph::{Directed, Undirected};
use crate::traverse::Neighbors;
use indexmap::IndexMap;
use std::cmp::PartialEq;
use std::marker::PhantomData;
#[test]
fn edge_type_is_directed() {
assert_eq!(Directed::is_directed(), true);
assert_eq!(Undirected::is_directed(), false);
}
#[test]
fn edges_new() {
let from: u32 = 1;
let edges: IndexMap<(u32, u32), f32> = IndexMap::new();
let node_neighbors: Vec<(u32, CompactDirection)> = vec![];
let iter = node_neighbors.iter();
let neighbors: Neighbors<u32, Directed> = Neighbors::new(iter, PhantomData);
Edges::new(from, &edges, neighbors);
}
#[test]
fn edges_next() {
let from: u32 = 1;
let mut edges: IndexMap<(u32, u32), f32> = IndexMap::with_capacity(3);
edges.insert((2, 1), 2.0);
edges.insert((1, 3), 3.0);
edges.insert((1, 4), 4.0);
let node_neighbors: Vec<(u32, CompactDirection)> = vec![
(2, CompactDirection::Incoming),
(3, CompactDirection::Outgoing),
(4, CompactDirection::Outgoing),
];
let neighbors: Neighbors<u32, Directed> =
Neighbors::new(node_neighbors.iter(), PhantomData);
let mut edges = Edges::new(from, &edges, neighbors);
assert_eq!(edges.next(), Some((1, 3, &3.0)));
assert_eq!(edges.next(), Some((1, 4, &4.0)));
assert_eq!(edges.next(), None);
}
#[test]
#[should_panic]
fn edges_next_unreachable() {
let from: u32 = 1;
let edges: IndexMap<(u32, u32), f32> = IndexMap::new();
let node_neighbors: Vec<(u32, CompactDirection)> = vec![(2, CompactDirection::Incoming)];
let neighbors: Neighbors<u32, Directed> =
Neighbors::new(node_neighbors.iter(), PhantomData);
let mut edges = Edges::new(from, &edges, neighbors);
assert_eq!(edges.next(), Some((1, 2, &0.0)));
}
#[test]
fn all_edges_new() {
let _all_edges: AllEdges<u32, f32, Directed> =
AllEdges::new(IndexMap::new().iter(), PhantomData);
}
#[test]
fn all_edges_next() {
let mut edges: IndexMap<(u32, u32), f32> = IndexMap::with_capacity(3);
edges.insert((2, 1), 2.0);
edges.insert((1, 3), 3.0);
edges.insert((1, 4), 4.0);
let mut all_edges: AllEdges<u32, f32, Directed> = AllEdges::new(edges.iter(), PhantomData);
assert_eq!(all_edges.next(), Some((2, 1, &2.0)));
assert_eq!(all_edges.next(), Some((1, 3, &3.0)));
assert_eq!(all_edges.next(), Some((1, 4, &4.0)));
assert_eq!(all_edges.next(), None);
}
#[test]
fn all_edges_size_hint() {
let mut edges: IndexMap<(u32, u32), f32> = IndexMap::with_capacity(3);
edges.insert((2, 1), 2.0);
edges.insert((1, 3), 3.0);
edges.insert((1, 4), 4.0);
let mut all_edges: AllEdges<u32, f32, Directed> = AllEdges::new(edges.iter(), PhantomData);
assert_eq!(all_edges.size_hint(), (3, Some(3)));
all_edges.next();
assert_eq!(all_edges.size_hint(), (2, Some(2)));
all_edges.next();
assert_eq!(all_edges.size_hint(), (1, Some(1)));
all_edges.next();
assert_eq!(all_edges.size_hint(), (0, Some(0)));
}
#[test]
fn all_edges_count() {
let mut edges: IndexMap<(u32, u32), f32> = IndexMap::with_capacity(3);
edges.insert((2, 1), 2.0);
edges.insert((1, 3), 3.0);
edges.insert((1, 4), 4.0);
let all_edges: AllEdges<u32, f32, Directed> = AllEdges::new(edges.iter(), PhantomData);
assert_eq!(all_edges.count(), 3);
}
#[test]
fn all_edges_nth() {
let mut edges: IndexMap<(u32, u32), f32> = IndexMap::with_capacity(3);
edges.insert((2, 1), 2.0);
edges.insert((1, 3), 3.0);
edges.insert((1, 4), 4.0);
let mut all_edges: AllEdges<u32, f32, Directed> = AllEdges::new(edges.iter(), PhantomData);
assert_eq!(all_edges.nth(2), Some((1, 4, &4.0)));
assert_eq!(all_edges.nth(0), None);
}
#[test]
fn all_edges_last() {
let mut edges: IndexMap<(u32, u32), f32> = IndexMap::with_capacity(3);
edges.insert((2, 1), 2.0);
edges.insert((1, 3), 3.0);
edges.insert((1, 4), 4.0);
let all_edges: AllEdges<u32, f32, Directed> = AllEdges::new(edges.iter(), PhantomData);
assert_eq!(all_edges.last(), Some((1, 4, &4.0)));
}
#[test]
fn all_edges_next_back() {
let mut edges: IndexMap<(u32, u32), f32> = IndexMap::with_capacity(3);
edges.insert((2, 1), 2.0);
edges.insert((1, 3), 3.0);
edges.insert((1, 4), 4.0);
let mut all_edges: AllEdges<u32, f32, Directed> = AllEdges::new(edges.iter(), PhantomData);
assert_eq!(all_edges.next_back(), Some((1, 4, &4.0)));
assert_eq!(all_edges.next_back(), Some((1, 3, &3.0)));
assert_eq!(all_edges.next_back(), Some((2, 1, &2.0)));
assert_eq!(all_edges.next_back(), None);
}
#[test]
fn into_weighted_edge() {
assert_eq!((1, 2).into_weighted_edge(), (1, 2, f32::default()));
assert_eq!((1, 2, 3).into_weighted_edge(), (1, 2, 3));
assert_eq!((1, 2, &3).into_weighted_edge(), (1, 2, 3));
assert_eq!((&(1, 2)).into_weighted_edge(), (1, 2, f32::default()));
assert_eq!((&(1, 2, 3)).into_weighted_edge(), (1, 2, 3));
}
#[test]
fn direction_opposite() {
assert_eq!(Direction::Incoming.opposite(), Direction::Outgoing);
assert_eq!(Direction::Outgoing.opposite(), Direction::Incoming);
}
#[test]
fn direction_index() {
assert_eq!(Direction::Incoming.index(), Direction::Incoming as usize);
assert_eq!(Direction::Outgoing.index(), Direction::Outgoing as usize);
}
#[test]
fn direction_clone() {
assert_eq!(Direction::Incoming.clone(), Direction::Incoming);
assert_eq!(Direction::Outgoing.clone(), Direction::Outgoing);
}
#[test]
fn compact_direction_from() {
assert_eq!(
CompactDirection::from(Direction::Incoming),
CompactDirection::Incoming
);
assert_eq!(
CompactDirection::from(Direction::Outgoing),
CompactDirection::Outgoing
);
}
#[test]
fn compact_direction_partial_equal_with_direction() {
assert_eq!(CompactDirection::Incoming.eq(&Direction::Incoming), true);
assert_eq!(CompactDirection::Incoming.eq(&Direction::Outgoing), false);
assert_eq!(CompactDirection::Outgoing.eq(&Direction::Outgoing), true);
assert_eq!(CompactDirection::Outgoing.eq(&Direction::Incoming), false);
}
}