use std::cmp::Ordering;
use std::collections::HashMap;
use std::collections::hash_map::{
Keys,
};
use std::collections::hash_map::Iter as HashmapIter;
use std::hash::{self, Hash};
use std::iter::Cloned;
use std::iter::FromIterator;
use std::slice::{
Iter,
};
use std::fmt;
use std::ops::{Index, IndexMut, Deref};
use IntoWeightedEdge;
#[derive(Clone)]
pub struct GraphMap<N, E> {
nodes: HashMap<N, Vec<N>>,
edges: HashMap<(N, N), E>,
}
impl<N: Eq + Hash + fmt::Debug, E: fmt::Debug> fmt::Debug for GraphMap<N, E> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.nodes.fmt(f)
}
}
#[inline]
fn edge_key<N: Copy + Ord>(a: N, b: N) -> (N, N) {
if a <= b { (a, b) } else { (b, a) }
}
pub trait NodeTrait : Copy + Ord + Hash {}
impl<N> NodeTrait for N where N: Copy + Ord + Hash {}
impl<N, E> GraphMap<N, E>
where N: NodeTrait
{
pub fn new() -> Self {
GraphMap {
nodes: HashMap::new(),
edges: HashMap::new(),
}
}
pub fn with_capacity(nodes: usize, edges: usize) -> Self {
GraphMap {
nodes: HashMap::with_capacity(nodes),
edges: HashMap::with_capacity(edges),
}
}
pub fn capacity(&self) -> (usize, usize) {
(self.nodes.capacity(), self.edges.capacity())
}
pub fn from_edges<I>(iterable: I) -> Self
where I: IntoIterator,
I::Item: IntoWeightedEdge<E, NodeId=N>
{
Self::from_iter(iterable)
}
pub fn node_count(&self) -> usize {
self.nodes.len()
}
pub fn edge_count(&self) -> usize {
self.edges.len()
}
pub fn clear(&mut self) {
self.nodes.clear();
self.edges.clear();
}
pub fn add_node(&mut self, n: N) -> N {
self.nodes.entry(n).or_insert(Vec::new());
n
}
pub fn remove_node(&mut self, n: N) -> bool {
let successors = match self.nodes.remove(&n) {
None => return false,
Some(sus) => sus,
};
for succ in successors.into_iter() {
self.remove_single_edge(&succ, &n);
self.edges.remove(&edge_key(n, succ));
}
true
}
pub fn contains_node(&self, n: N) -> bool {
self.nodes.contains_key(&n)
}
pub fn add_edge(&mut self, a: N, b: N, weight: E) -> Option<E> {
if let old @ Some(_) = self.edges.insert(edge_key(a, b), weight) {
old
} else {
self.nodes.entry(a)
.or_insert_with(|| Vec::with_capacity(1))
.push(b);
if a != b {
self.nodes.entry(b)
.or_insert_with(|| Vec::with_capacity(1))
.push(a);
}
None
}
}
fn remove_single_edge(&mut self, a: &N, b: &N) -> bool {
match self.nodes.get_mut(a) {
None => false,
Some(sus) => {
match sus.iter().position(|elt| elt == b) {
Some(index) => { sus.swap_remove(index); true }
None => false,
}
}
}
}
pub fn remove_edge(&mut self, a: N, b: N) -> Option<E> {
let exist1 = self.remove_single_edge(&a, &b);
let exist2 = if a != b { self.remove_single_edge(&b, &a) } else { exist1 };
let weight = self.edges.remove(&edge_key(a, b));
debug_assert!(exist1 == exist2 && exist1 == weight.is_some());
weight
}
pub fn contains_edge(&self, a: N, b: N) -> bool {
self.edges.contains_key(&edge_key(a, b))
}
pub fn nodes(&self) -> Nodes<N> {
Nodes{iter: self.nodes.keys().cloned()}
}
pub fn neighbors(&self, from: N) -> Neighbors<N> {
Neighbors{iter:
match self.nodes.get(&from) {
Some(neigh) => neigh.iter(),
None => [].iter(),
}.cloned()
}
}
pub fn edges(&self, from: N) -> Edges<N, E> {
Edges {
from: from,
iter: self.neighbors(from),
edges: &self.edges,
}
}
pub fn edge_weight(&self, a: N, b: N) -> Option<&E> {
self.edges.get(&edge_key(a, b))
}
pub fn edge_weight_mut(&mut self, a: N, b: N) -> Option<&mut E> {
self.edges.get_mut(&edge_key(a, b))
}
pub fn all_edges(&self) -> AllEdges<N, E> {
AllEdges {
inner: self.edges.iter()
}
}
}
impl<N, E, Item> FromIterator<Item> for GraphMap<N, E>
where Item: IntoWeightedEdge<E, NodeId=N>,
N: NodeTrait,
{
fn from_iter<I>(iterable: I) -> Self
where I: IntoIterator<Item=Item>,
{
let iter = iterable.into_iter();
let (low, _) = iter.size_hint();
let mut g = Self::with_capacity(0, low);
g.extend(iter);
g
}
}
impl<N, E, Item> Extend<Item> for GraphMap<N, E>
where Item: IntoWeightedEdge<E, NodeId=N>,
N: NodeTrait,
{
fn extend<I>(&mut self, iterable: I)
where I: IntoIterator<Item=Item>,
{
let iter = iterable.into_iter();
let (low, _) = iter.size_hint();
self.edges.reserve(low);
for elt in iter {
let (source, target, weight) = elt.into_weighted_edge();
self.add_edge(source, target, weight);
}
}
}
macro_rules! iterator_wrap {
($name: ident <$($typarm:tt),*> where { $($bounds: tt)* }
item: $item: ty,
iter: $iter: ty,
) => (
pub struct $name <$($typarm),*> where $($bounds)* {
iter: $iter,
}
impl<$($typarm),*> Iterator for $name <$($typarm),*>
where $($bounds)*
{
type Item = $item;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
self.iter.next()
}
#[inline]
fn size_hint(&self) -> (usize, Option<usize>) {
self.iter.size_hint()
}
}
);
}
iterator_wrap! {
Nodes <'a, N> where { N: 'a + NodeTrait }
item: N,
iter: Cloned<Keys<'a, N, Vec<N>>>,
}
impl<'a, N: 'a + NodeTrait> ExactSizeIterator for Nodes<'a, N> { }
iterator_wrap! {
Neighbors <'a, N> where { N: 'a + NodeTrait }
item: N,
iter: Cloned<Iter<'a, N>>,
}
impl<'a, N: 'a + NodeTrait> DoubleEndedIterator for Neighbors<'a, N> {
fn next_back(&mut self) -> Option<Self::Item> {
self.iter.next_back()
}
}
impl<'a, N: 'a + NodeTrait> ExactSizeIterator for Neighbors<'a, N> { }
impl<'a, N: 'a + NodeTrait> Clone for Neighbors<'a, N> {
fn clone(&self) -> Self {
Neighbors {
iter: self.iter.clone(),
}
}
}
pub struct Edges<'a, N, E: 'a> where N: 'a + NodeTrait {
from: N,
edges: &'a HashMap<(N, N), E>,
iter: Neighbors<'a, N>,
}
impl<'a, N, E> Iterator for Edges<'a, N, E>
where N: 'a + NodeTrait, E: 'a
{
type Item = (N, &'a E);
fn next(&mut self) -> Option<(N, &'a E)>
{
match self.iter.next() {
None => None,
Some(b) => {
let a = self.from;
match self.edges.get(&edge_key(a, b)) {
None => unreachable!(),
Some(edge) => {
Some((b, edge))
}
}
}
}
}
}
pub struct AllEdges<'a, N, E: 'a> where N: 'a + NodeTrait {
inner: HashmapIter<'a, (N, N), E>
}
impl<'a, N, E> Iterator for AllEdges<'a, N, E>
where N: 'a + NodeTrait, E: 'a
{
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))
}
}
}
impl<N, E> Index<(N, N)> for GraphMap<N, E>
where N: NodeTrait
{
type Output = E;
fn index(&self, index: (N, N)) -> &E
{
self.edge_weight(index.0, index.1).expect("GraphMap::index: no such edge")
}
}
impl<N, E> IndexMut<(N, N)> for GraphMap<N, E>
where N: NodeTrait
{
fn index_mut(&mut self, index: (N, N)) -> &mut E
{
self.edge_weight_mut(index.0, index.1).expect("GraphMap::index: no such edge")
}
}
impl<N, E> Default for GraphMap<N, E>
where N: NodeTrait,
{
fn default() -> Self { GraphMap::new() }
}
pub struct Ptr<'b, T: 'b>(pub &'b T);
impl<'b, T> Copy for Ptr<'b, T> {}
impl<'b, T> Clone for Ptr<'b, T>
{
fn clone(&self) -> Self { *self }
}
fn ptr_eq<T>(a: *const T, b: *const T) -> bool {
a == b
}
impl<'b, T> PartialEq for Ptr<'b, T>
{
fn eq(&self, other: &Ptr<'b, T>) -> bool {
ptr_eq(self.0, other.0)
}
}
impl<'b, T> PartialOrd for Ptr<'b, T>
{
fn partial_cmp(&self, other: &Ptr<'b, T>) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl<'b, T> Ord for Ptr<'b, T>
{
fn cmp(&self, other: &Ptr<'b, T>) -> Ordering {
let a = self.0 as *const _;
let b = other.0 as *const _;
a.cmp(&b)
}
}
impl<'b, T> Deref for Ptr<'b, T> {
type Target = T;
fn deref(&self) -> &T {
self.0
}
}
impl<'b, T> Eq for Ptr<'b, T> {}
impl<'b, T> Hash for Ptr<'b, T>
{
fn hash<H: hash::Hasher>(&self, st: &mut H)
{
let ptr = (self.0) as *const T;
ptr.hash(st)
}
}
impl<'b, T: fmt::Debug> fmt::Debug for Ptr<'b, T> {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
self.0.fmt(f)
}
}