use crate::traits::refs::{GraphSizeRef, IndexGraphRef};
use crate::traits::{GraphIter, GraphIterator};
use std::marker::PhantomData;
use std::ops::{Index, IndexMut};
pub trait Indexer: Clone {
type Idx;
type Iter: GraphIterator<Self, Item = Self::Idx>;
fn num_items(&self) -> usize;
fn index(&self, i: Self::Idx) -> usize;
fn iter(&self) -> GraphIter<Self, Self::Iter>
where
Self: Sized;
}
pub type IndexerIter<'a, I> = GraphIter<'a, I, <I as Indexer>::Iter>;
pub trait GraphIndexer<G>: Indexer {
fn new(g: G) -> Self;
}
pub struct ItemVec<I, T> {
indexer: I,
data: Vec<T>,
}
impl<I, T> ItemVec<I, T>
where
I: Indexer,
{
pub fn from_indexer(indexer: I, value: T) -> Self
where
T: Clone,
{
ItemVec {
data: vec![value; indexer.num_items()],
indexer,
}
}
pub fn from_indexer_with<F>(indexer: I, f: F) -> Self
where
F: Fn(I::Idx) -> T,
{
ItemVec {
data: indexer.iter().map(f).collect(),
indexer,
}
}
pub fn from_indexer_and_vec(indexer: I, values: Vec<T>) -> Self {
assert_eq!(values.len(), indexer.num_items());
ItemVec { data: values, indexer }
}
pub fn new<G>(g: G, value: T) -> Self
where
G: Clone,
I: GraphIndexer<G>,
T: Clone,
{
Self::from_indexer(I::new(g), value)
}
pub fn new_with<G, F>(g: G, f: F) -> Self
where
I: GraphIndexer<G>,
F: Fn(I::Idx) -> T,
{
Self::from_indexer_with(I::new(g), f)
}
pub fn new_from_vec<G>(g: G, values: Vec<T>) -> Self
where
I: GraphIndexer<G>,
{
Self::from_indexer_and_vec(I::new(g), values)
}
pub fn iter(&self) -> std::iter::Zip<IndexerIter<I>, std::slice::Iter<T>> {
self.indexer.iter().zip(self.data.iter())
}
pub fn iter_mut(&mut self) -> std::iter::Zip<IndexerIter<I>, std::slice::IterMut<T>> {
self.indexer.iter().zip(self.data.iter_mut())
}
pub fn map<F>(&self, f: F) -> Self
where
I: Clone,
F: Fn((I::Idx, &T)) -> T,
{
Self::from_indexer_and_vec(self.indexer.clone(), self.iter().map(f).collect())
}
pub fn reset(&mut self, value: T)
where
T: Clone,
{
for u in self.indexer.iter() {
self.data[self.indexer.index(u)] = value.clone();
}
}
}
impl<I, T> Index<I::Idx> for ItemVec<I, T>
where
I: Indexer,
{
type Output = T;
fn index(&self, i: I::Idx) -> &T {
&self.data[self.indexer.index(i)]
}
}
impl<'a, I, T> IndexMut<I::Idx> for ItemVec<I, T>
where
I: Indexer,
{
fn index_mut(&mut self, i: I::Idx) -> &mut T {
&mut self.data[self.indexer.index(i)]
}
}
#[derive(Clone, Copy)]
pub struct NodeIndexer<'g, G>(pub G, PhantomData<&'g G>);
#[derive(Clone)]
pub struct IndexerIt<I>(I);
impl<'g, G, I> GraphIterator<NodeIndexer<'g, G>> for IndexerIt<I>
where
I: GraphIterator<G>,
{
type Item = I::Item;
fn next(&mut self, indexer: &NodeIndexer<'g, G>) -> Option<Self::Item> {
self.0.next(&indexer.0)
}
fn size_hint(&self, indexer: &NodeIndexer<'g, G>) -> (usize, Option<usize>) {
self.0.size_hint(&indexer.0)
}
fn count(self, indexer: &NodeIndexer<'g, G>) -> usize {
self.0.count(&indexer.0)
}
}
impl<'a, G> Indexer for NodeIndexer<'a, G>
where
G: IndexGraphRef<'a> + Clone,
{
type Idx = G::Node;
type Iter = IndexerIt<G::NodeIt>;
fn num_items(&self) -> usize {
self.0.num_nodes()
}
fn index(&self, u: G::Node) -> usize {
self.0.node_id(u)
}
fn iter(&self) -> GraphIter<Self, Self::Iter> {
GraphIter(IndexerIt(GraphSizeRef::nodes_iter(&self.0)), self)
}
}
impl<'a, G> GraphIndexer<G> for NodeIndexer<'a, G>
where
G: IndexGraphRef<'a> + Clone,
{
fn new(g: G) -> Self {
NodeIndexer(g, PhantomData)
}
}
#[derive(Clone, Copy)]
pub struct EdgeIndexer<'g, G>(pub G, PhantomData<&'g G>);
impl<'g, G, I> GraphIterator<EdgeIndexer<'g, G>> for IndexerIt<I>
where
I: GraphIterator<G>,
{
type Item = I::Item;
fn next(&mut self, indexer: &EdgeIndexer<'g, G>) -> Option<Self::Item> {
self.0.next(&indexer.0)
}
fn size_hint(&self, indexer: &EdgeIndexer<'g, G>) -> (usize, Option<usize>) {
self.0.size_hint(&indexer.0)
}
fn count(self, indexer: &EdgeIndexer<'g, G>) -> usize {
self.0.count(&indexer.0)
}
}
impl<'a, G> Indexer for EdgeIndexer<'a, G>
where
G: IndexGraphRef<'a> + Clone,
{
type Idx = G::Edge;
type Iter = IndexerIt<G::EdgeIt>;
fn num_items(&self) -> usize {
self.0.num_edges()
}
fn index(&self, e: G::Edge) -> usize {
self.0.edge_id(e)
}
fn iter(&self) -> GraphIter<Self, Self::Iter> {
GraphIter(IndexerIt(GraphSizeRef::edges_iter(&self.0)), self)
}
}
impl<'a, G> GraphIndexer<G> for EdgeIndexer<'a, G>
where
G: 'a + IndexGraphRef<'a> + Clone,
{
fn new(g: G) -> Self {
EdgeIndexer(g, PhantomData)
}
}
pub type NodeVec<'g, G, T> = ItemVec<NodeIndexer<'g, G>, T>;
pub type EdgeVec<'g, G, T> = ItemVec<EdgeIndexer<'g, G>, T>;
#[cfg(test)]
mod tests {
use super::*;
use crate::classes::peterson;
use crate::traits::*;
use crate::LinkedListGraph;
#[test]
fn test_iter() {
let g = peterson::<LinkedListGraph>();
let mut weights = EdgeVec::new_with(&g, |e| g.edge_id(e));
for (i, (_, &x)) in weights.iter().enumerate() {
assert_eq!(i, x);
}
for (_, x) in weights.iter_mut() {
*x = *x + 1;
}
for (i, (_, &x)) in weights.iter().enumerate() {
assert_eq!(i + 1, x);
}
}
#[test]
fn test_map() {
let g = peterson::<LinkedListGraph>();
let weights = EdgeVec::new_with(&g, |e| g.edge_id(e));
let new_weights = weights.map(|(_, i)| i + 1);
for e in g.edges() {
assert_eq!(weights[e] + 1, new_weights[e]);
}
let new_weights = new_weights.map(|(_, i)| i * 2);
for e in g.edges() {
assert_eq!(2 * (weights[e] + 1), new_weights[e]);
}
}
}