hypergraphx 0.0.5

use fixedbitset::FixedBitSet;
use std::{hash::Hash, iter, usize};

use crate::prelude::*;

/// Just a graph.
/// I originally wanted to have this really neat system where no edges are actually stored,
/// but computed on the fly - but then I realised that I couldn't get an iterator over references to
/// edges - which bad.
///
/// Thusly, I must resort to making a complete graph a very inefficient wrapper over an ordinary graph.
/// On the bright side, that means it is mutable with WeightsMut. :'(
pub struct CompleteGraph<N: Clone + Hash + Eq, E: Clone + Hash + Eq> {
    inner: Graph<N, E>,
}

impl_graph_basics_wrapper!(
    CompleteGraph<N, E>,
    Graph<N, E>,
    false
);

impl_weights_wrapper!(
    CompleteGraph<N, E>
);

impl<'a, N: Clone + Eq + Hash + 'a, E: Clone + Eq + Hash + 'a> CompleteGraph<N, E> {
    pub fn add_node(&mut self, weight: N, edges: Vec<E>) -> Result<usize, HypergraphErrors> {
        if edges.len() != self.node_count() {
            return Err(HypergraphErrors::InvariantViolation {
                err: "Require edge to every existing node".to_string(),
            });
        }

        let node = self.inner.add_node(weight);
        self.inner
            .add_edges(edges.into_iter().enumerate().map(|x| (x.1, [node, x.0])))?;

        return Ok(node);
    }

    pub fn add_nodes(
        &mut self,
        weights: impl Iterator<Item = N>,
        edges_it: impl Iterator<Item = Vec<E>>,
    ) -> Result<(), HypergraphErrors> {
        for (weight, edges) in weights.zip(edges_it) {
            self.add_node(weight, edges)?;
        }
        return Ok(());
    }

    pub fn remove_node(
        &mut self,
        node_index: <CompleteGraph<N, E> as GraphBasics<'a>>::NodeIndex,
    ) -> Result<UndirectedNode<N>, HypergraphErrors> {
        self.inner.remove_node(node_index)
    }
}

impl<'a, N: Clone + Eq + Hash + 'a, E: Default + Clone + Eq + Hash + 'a> CompleteGraph<N, E> {
    pub fn add_node_default(&mut self, weight: N) -> HypergraphResult<usize> {
        let node = self.inner.add_node(weight);
        self.inner.add_edges(
            (0..self.node_count())
                .into_iter()
                .map(|x| (E::default(), [node, x])),
        )?;

        return Ok(node);
    }

    pub fn add_nodes_default(
        &mut self,
        weights: impl Iterator<Item = N>,
    ) -> Result<(), HypergraphErrors> {
        for weight in weights {
            self.add_node_default(weight)?;
        }
        return Ok(());
    }
}

pub struct DirectedCompleteGraph<N: Clone + Hash + Eq, E: Clone + Hash + Eq> {
    inner: DiGraph<N, E>,
}

impl_graph_basics_wrapper!(
    DirectedCompleteGraph<N, E>,
    DiGraph<N, E>,
    true
);

impl_weights_wrapper!(
    DirectedCompleteGraph<N, E>
);

impl<'a, N: Clone + Eq + Hash + 'a, E: Clone + Eq + Hash + 'a> DirectedCompleteGraph<N, E> {
    pub fn add_node(
        &mut self,
        weight: N,
        src_edges: Vec<E>,
        dst_edges: Vec<E>,
    ) -> Result<usize, HypergraphErrors> {
        if src_edges.len() != self.node_count() || dst_edges.len() != self.node_count() {
            return Err(HypergraphErrors::InvariantViolation {
                err: "Require edge to and from every existing node".to_string(),
            });
        }

        let node = self.inner.add_node(weight);
        self.inner.add_edges(
            src_edges
                .into_iter()
                .enumerate()
                .map(|x| (x.1, [node], [x.0])),
        )?;
        self.inner.add_edges(
            dst_edges
                .into_iter()
                .enumerate()
                .map(|x| (x.1, [x.0], [node])),
        )?;

        return Ok(node);
    }

    pub fn add_nodes(
        &mut self,
        weights: impl Iterator<Item = N>,
        edges_it: impl Iterator<Item = (Vec<E>, Vec<E>)>,
    ) -> Result<(), HypergraphErrors> {
        for (weight, edges) in weights.zip(edges_it) {
            self.add_node(weight, edges.0, edges.1)?;
        }
        return Ok(());
    }

    pub fn remove_node(
        &mut self,
        node_index: <CompleteGraph<N, E> as GraphBasics<'a>>::NodeIndex,
    ) -> Result<DirectedNode<N>, HypergraphErrors> {
        self.inner.remove_node(node_index)
    }
}

impl<'a, N: Clone + Eq + Hash + 'a, E: Default + Clone + Eq + Hash + 'a>
    DirectedCompleteGraph<N, E>
{
    pub fn add_node_default(&mut self, weight: N) -> HypergraphResult<usize> {
        let node = self.inner.add_node(weight);
        self.inner.add_edges(
            (0..self.node_count())
                .into_iter()
                .map(|x| (E::default(), [node], [x])),
        )?;
        self.inner.add_edges(
            (0..self.node_count())
                .into_iter()
                .map(|x| (E::default(), [x], [node])),
        )?;

        return Ok(node);
    }

    pub fn add_nodes_default(
        &mut self,
        weights: impl Iterator<Item = N>,
    ) -> Result<(), HypergraphErrors> {
        for weight in weights {
            self.add_node_default(weight)?;
        }
        return Ok(());
    }
}

/// Tournaments are unweighted.
pub struct Tournament<N: Clone + Eq + Hash> {
    inner: DiGraph<N, ()>,
    rounds: Vec<FixedBitSet>,
}

#[derive(Debug, Clone, PartialEq, Eq, Copy, Hash)]
pub struct NodePair(u32, u32);
impl Into<usize> for NodePair {
    fn into(self) -> usize {
        (self.0 << u32::BITS + self.1) as usize
    }
}
impl From<usize> for NodePair {
    fn from(value: usize) -> Self {
        NodePair(
            (value >> u32::BITS) as u32,
            (value % (1 << u32::BITS)) as u32,
        )
    }
}

impl<'a, N> GraphBasics<'a> for Tournament<N>
where
    N: Clone + Eq + Hash + 'a,
{
    type NodeRef = <DiGraph<N, ()> as GraphBasics<'a>>::NodeRef;

    type EdgeRef = (usize, usize);

    type NodeIndex = <DiGraph<N, ()> as GraphBasics<'a>>::NodeIndex;

    type EdgeIndex = NodePair;

    fn nodes(&'a self) -> impl Iterator<Item = Self::NodeRef> {
        self.inner.nodes()
    }

    fn node_count(&'a self) -> usize {
        self.inner.node_count()
    }

    fn edges(&'a self) -> impl Iterator<Item = Self::EdgeRef> {
        // let mut out = iter::empty();
        // self.fares.iter().enumerate().rev().for_each(|(i, x)| {
        //     out = out.chain(x.ones().map(|y| (NodePair(i as u32, y as u32), true)));
        // });

        // out

        self.rounds
            .iter()
            .enumerate()
            .map(|(i, x)| {
                x.ones()
                    .map(move |y| ((i, y)))
                    .chain(x.zeroes().map(move |y| ((y, i))))
            })
            .flatten()
    }

    fn edge_count(&'a self) -> usize {
        (self.node_count() * (self.node_count() + 1)) >> 1
    }

    fn is_directed(&self) -> bool {
        true
    }

    fn node(&'a self, node_index: Self::NodeIndex) -> Option<Self::NodeRef> {
        self.inner.node(node_index)
    }

    fn edge(&'a self, edge_index: Self::EdgeIndex) -> Option<Self::EdgeRef> {
        let a = edge_index.0.max(edge_index.1) as usize;
        let b = edge_index.0.min(edge_index.1) as usize;
        if self.rounds[b].contains(a) {
            Some((b, a))
        } else {
            Some((a, b))
        }
    }

    fn node_iter(
        &'a self,
        node_index: impl Iterator<Item = Self::NodeIndex>,
    ) -> impl Iterator<Item = Option<Self::NodeRef>> {
        self.inner.node_iter(node_index)
    }

    fn edge_iter(
        &'a self,
        edge_index: impl Iterator<Item = Self::EdgeIndex>,
    ) -> impl Iterator<Item = Option<Self::EdgeRef>> {
        edge_index.map(|e| self.edge(e))
    }
}

impl<'a, N: 'a> GraphWrapper<'a> for Tournament<N>
where
    DiGraph<N, ()>: GraphBasics<'a>,
    N: 'a + Clone + Eq + Hash,
{
    type Inner = DiGraph<N, ()>;

    fn into_inner(&'a self) -> &'a Self::Inner {
        &self.inner
    }
}

impl<'a, N> Weights<'a, N, ()> for Tournament<N>
where
    N: 'a + Clone + Hash + Eq,
{
    fn node_weights(&'a self) -> impl Iterator<Item = &'a N> + 'a {
        self.inner.node_weights()
    }

    fn edge_weights(&'a self) -> impl Iterator<Item = &'a ()> + 'a {
        iter::empty()
    }

    fn node_weights_mut(&'a mut self) -> impl Iterator<Item = &'a mut N> + 'a {
        self.inner.node_weights_mut()
    }

    fn edge_weights_mut(&'a mut self) -> impl Iterator<Item = &'a mut ()> + 'a {
        iter::empty()
    }

    fn node_weight_mut(
        &'a mut self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> Option<&'a mut N> {
        self.inner.node_weight_mut(node_index)
    }

    fn edge_weight_mut(
        &'a mut self,
        _: <Self as GraphBasics<'a>>::EdgeIndex,
    ) -> Option<&'a mut ()> {
        None
    }

    fn node_weight(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<&'a N> {
        self.inner.node_weight(node_index)
    }

    fn edge_weight(&'a self, _: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<&'a ()> {
        None
    }

    unsafe fn node_weight_unchecked(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> &'a N {
        unsafe { self.inner.node_weight_unchecked(node_index) }
    }

    unsafe fn edge_weight_unchecked(&'a self, _: <Self as GraphBasics<'a>>::EdgeIndex) -> &'a () {
        &()
    }

    unsafe fn node_weight_unchecked_mut(
        &'a mut self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> &'a mut N {
        unsafe { self.inner.node_weight_unchecked_mut(node_index) }
    }

    unsafe fn edge_weight_unchecked_mut(
        &'a mut self,
        _: <Self as GraphBasics<'a>>::EdgeIndex,
    ) -> &'a mut () {
        Box::leak(Box::new(()))
    }

    fn edge_weight_copied(&'a self, edge_index: <Self as GraphBasics<'a>>::EdgeIndex) -> Option<()>
    where
        (): Copy,
    {
        None
    }

    fn node_weight_copied(&'a self, node_index: <Self as GraphBasics<'a>>::NodeIndex) -> Option<N>
    where
        N: Copy,
    {
        self.inner.node_weight_copied(node_index)
    }

    unsafe fn edge_weight_copied_unchecked(
        &'a self,
        edge_index: <Self as GraphBasics<'a>>::EdgeIndex,
    ) -> ()
    where
        (): Copy,
    {
        ()
    }

    unsafe fn node_weight_copied_unchecked(
        &'a self,
        node_index: <Self as GraphBasics<'a>>::NodeIndex,
    ) -> N
    where
        N: Copy,
    {
        unsafe { self.inner.node_weight_copied_unchecked(node_index) }
    }
}

impl<N> Tournament<N>
where
    N: Clone + Eq + Hash,
{
    pub fn add_node(&mut self, weight: N, round: FixedBitSet) -> usize {
        self.rounds.push(round);
        self.inner.add_node(weight)
    }

    pub fn add_nodes(&mut self, weights_and_rounds: impl Iterator<Item = (N, FixedBitSet)>) {
        weights_and_rounds.for_each(|(weight, round)| {
            self.add_node(weight, round);
        });
    }
}