use crate::traits::mdg::MultiDiGraph;
use std::collections::hash_map::{Entry, Iter as MapIter};
use std::collections::hash_set::Iter as SetIter;
use std::collections::{HashMap, HashSet};
use std::hash::Hash;
pub struct HashMultiDiGraph<NI, ND, EI, ED>
where
NI: Eq + Hash,
EI: Eq + Hash,
{
nodes: HashMap<NI, HashNodeEntry<ND, EI>>,
edges: HashMap<EI, HashEdgeEntry<ED, NI>>,
}
struct HashNodeEntry<ND, EI> {
in_edge_ids: HashSet<EI>,
out_edge_ids: HashSet<EI>,
data: ND,
}
struct HashEdgeEntry<ED, NI> {
from_id: NI,
to_id: NI,
data: ED,
}
impl<'a, NI, ND, EI, ED> HashMultiDiGraph<NI, ND, EI, ED>
where
NI: Eq + Hash,
EI: Eq + Hash,
{
pub fn new() -> Self {
Self {
nodes: Default::default(),
edges: Default::default(),
}
}
}
impl<'a, NI, ND, EI, ED> MultiDiGraph<'a, NI, ND, EI, ED> for HashMultiDiGraph<NI, ND, EI, ED>
where
NI: 'a + Clone + Eq + Hash,
ND: 'a,
EI: 'a + Clone + Eq + Hash,
ED: 'a,
{
type NodeIter = NodeIter<'a, NI, ND, EI>;
type EdgeIter = EdgeIter<'a, NI, EI, ED>;
type NodeEdgeIter = NodeEdgeIter<'a, NI, EI, ED>;
fn insert_node(&mut self, id: NI, data: ND) -> Result<(), ()> {
match self.nodes.entry(id) {
Entry::Vacant(v) => {
v.insert(HashNodeEntry {
in_edge_ids: Default::default(),
out_edge_ids: Default::default(),
data,
});
Ok(())
}
Entry::Occupied(_) => Err(()),
}
}
fn remove_node(&mut self, id: &NI) -> Option<ND> {
let result = self.nodes.remove(id);
result.map(|entry| {
for in_edge_id in &entry.in_edge_ids {
let in_edge_entry = self
.edges
.remove(in_edge_id)
.expect("broken invariant: node with missing `in` edge");
let from_node_entry = self
.nodes
.get_mut(&in_edge_entry.from_id)
.expect("broken invariant: edge with missing `from` node");
from_node_entry.out_edge_ids.remove(in_edge_id);
}
for out_edge_id in &entry.out_edge_ids {
let out_edge_entry = self
.edges
.remove(out_edge_id)
.expect("broken invariant: node with missing `out` edge");
let to_node_entry = self
.nodes
.get_mut(&out_edge_entry.to_id)
.expect("broken invariant: edge with missing `to` node");
to_node_entry.out_edge_ids.remove(out_edge_id);
}
entry.data
})
}
fn insert_edge(&mut self, from: &NI, to: &NI, id: EI, data: ED) -> Result<(), ()> {
if self.edges.contains_key(&id) {
return Err(());
}
if !self.nodes.contains_key(from) {
return Err(());
}
if !self.nodes.contains_key(to) {
return Err(());
}
self.edges.insert(
id.clone(),
HashEdgeEntry {
from_id: from.clone(),
to_id: to.clone(),
data,
},
);
self.nodes
.get_mut(from)
.unwrap()
.out_edge_ids
.insert(id.clone());
self.nodes
.get_mut(to)
.unwrap()
.in_edge_ids
.insert(id.clone());
Ok(())
}
fn remove_edge(&mut self, id: &EI) -> Option<(NI, NI, ED)> {
self.edges.remove(id).map(|entry| {
let from_node_entry = self
.nodes
.get_mut(&entry.from_id)
.expect("broken invariant: edge with missing `from` node");
if !from_node_entry.out_edge_ids.remove(id) {
panic!("broken invariant: edge not among `out_edges` of its `from` node")
}
let to_node_entry = self
.nodes
.get_mut(&entry.to_id)
.expect("broken invariant: edge with missing `to` node");
if !to_node_entry.out_edge_ids.remove(id) {
panic!("broken invariant: edge not among `in_edges` of its `to` node")
}
(entry.from_id, entry.to_id, entry.data)
})
}
fn nodes(&'a self) -> Self::NodeIter {
NodeIter {
node_iter: self.nodes.iter(),
}
}
fn edges(&'a self) -> Self::EdgeIter {
EdgeIter {
edge_iter: self.edges.iter(),
}
}
fn node_data(&self, id: &NI) -> Option<&ND> {
self.nodes.get(id).map(|entry| &entry.data)
}
fn node_data_mut(&mut self, id: &NI) -> Option<&mut ND> {
self.nodes.get_mut(id).map(|entry| &mut entry.data)
}
fn node_in_edges(&'a self, id: &NI) -> Option<Self::NodeEdgeIter> {
self.nodes.get(id).map(|entry| NodeEdgeIter {
edge_id_iter: entry.in_edge_ids.iter(),
edges: &self.edges,
})
}
fn node_out_edges(&'a self, id: &NI) -> Option<Self::NodeEdgeIter> {
self.nodes.get(id).map(|entry| NodeEdgeIter {
edge_id_iter: entry.out_edge_ids.iter(),
edges: &self.edges,
})
}
fn edge_data(&self, id: &EI) -> Option<&ED> {
self.edges.get(id).map(|entry| &entry.data)
}
fn edge_data_mut(&mut self, id: &EI) -> Option<&mut ED> {
self.edges.get_mut(id).map(|entry| &mut entry.data)
}
}
pub struct NodeIter<'a, NI, ND, EI> {
node_iter: MapIter<'a, NI, HashNodeEntry<ND, EI>>,
}
impl<'a, NI, ND, EI> Iterator for NodeIter<'a, NI, ND, EI> {
type Item = (&'a NI, &'a ND);
fn next(&mut self) -> Option<Self::Item> {
self.node_iter.next().map(|(id, entry)| (id, &entry.data))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.node_iter.size_hint()
}
}
impl<'a, NI, ND, EI> ExactSizeIterator for NodeIter<'a, NI, ND, EI> {
fn len(&self) -> usize {
self.node_iter.len()
}
}
pub struct EdgeIter<'a, NI, EI, ED> {
edge_iter: MapIter<'a, EI, HashEdgeEntry<ED, NI>>,
}
impl<'a, NI, EI, ED> Iterator for EdgeIter<'a, NI, EI, ED> {
type Item = (&'a NI, &'a NI, &'a EI, &'a ED);
fn next(&mut self) -> Option<Self::Item> {
self.edge_iter
.next()
.map(|(id, entry)| (&entry.from_id, &entry.to_id, id, &entry.data))
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.edge_iter.size_hint()
}
}
impl<'a, NI, EI, ED> ExactSizeIterator for EdgeIter<'a, NI, EI, ED> {
fn len(&self) -> usize {
self.edge_iter.len()
}
}
pub struct NodeEdgeIter<'a, NI, EI, ED> {
edge_id_iter: SetIter<'a, EI>,
edges: &'a HashMap<EI, HashEdgeEntry<ED, NI>>,
}
impl<'a, NI, EI, ED> Iterator for NodeEdgeIter<'a, NI, EI, ED>
where
EI: Eq + Hash,
{
type Item = (&'a NI, &'a NI, &'a EI, &'a ED);
fn next(&mut self) -> Option<Self::Item> {
match self.edge_id_iter.next() {
Some(id) => {
let entry = self.edges.get(id).expect("broken invariant: missing edge");
Some((&entry.from_id, &entry.to_id, id, &entry.data))
}
None => None,
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
self.edge_id_iter.size_hint()
}
}
impl<'a, NI, EI, ED> ExactSizeIterator for NodeEdgeIter<'a, NI, EI, ED>
where
EI: Eq + Hash,
{
fn len(&self) -> usize {
self.edge_id_iter.len()
}
}