#![allow(clippy::manual_is_multiple_of)]

use dyntri_core::triangulation::CausalTriangulation2D;
use rand::{Rng, seq::IteratorRandom};
use serde::{Deserialize, Serialize};
use thinset::SparseSet;

use super::{
    reconstruction::reconstruct_causal_triangulation2d,
    triangle::{Orientation, Triangle},
};

/// `Triangulation` struct with a fixed-length `Triangle` list,
/// and an order-four list.
/// This fixed-volume implementation is meant to be used with the
/// 'flip' and 'relocate' Markov-chain moves.
#[derive(Debug, Clone, Serialize, Deserialize)]
#[serde(from = "SerializableTriangulation", into = "SerializableTriangulation")]
pub struct FixedTriangulation {
    pub ntime: u16,                   // Number of timeslices
    pub triangles: Vec<Triangle>,     // List of all triangles, representing the triangulation
    pub order_four: SparseSet<usize>, // Set of all order four vertices, labelled by the upper right triangle
}

#[derive(Debug, Clone, Serialize, Deserialize)]
struct SerializableTriangulation {
    ntime: u16,
    triangles: Vec<Triangle>,
}

impl From<FixedTriangulation> for SerializableTriangulation {
    fn from(value: FixedTriangulation) -> Self {
        Self {
            ntime: value.ntime,
            triangles: value.triangles,
        }
    }
}

impl From<SerializableTriangulation> for FixedTriangulation {
    fn from(value: SerializableTriangulation) -> Self {
        let ntriangles = value.triangles.len();
        let mut triangulation = Self {
            ntime: value.ntime,
            triangles: value.triangles,
            order_four: SparseSet::with_capacity(ntriangles / 2),
        };
        for label in 0..triangulation.triangles.len() {
            if triangulation.is_order_four(label) {
                triangulation.order_four.insert(label);
            }
        }
        triangulation
    }
}

impl FixedTriangulation {
    pub fn reconstruct_causal_triangulation2d(&self) -> CausalTriangulation2D {
        reconstruct_causal_triangulation2d(self)
    }
}

/// Implementations for the creation of new [FixedTriangulation]s
impl FixedTriangulation {
    /// Create a new fixed-size flat [`FixedTriangulation`] with `tlen` timeslices
    /// and`vertex_len` vertices in each.
    pub fn new(vertex_len: usize, ntime: u16) -> FixedTriangulation {
        let ntime = ntime as usize; // Cast `ntime` for calculations
        let start_length = 2 * vertex_len; // Determine construction L (number of triangles per slice)
        let size = start_length * ntime; // Determine N

        let mut triangles: Vec<Triangle> = Vec::with_capacity(size);
        for t in 0..ntime {
            for i in 0..start_length {
                let left = t * start_length + (i + (start_length - 1)) % start_length;
                let right = t * start_length + (i + 1) % start_length;
                #[allow(clippy::collapsible_else_if)]
                // TODO: This nested if statement is one unreadable mess
                let (center, orientation) = if (i + t) % 2 == 0 {
                    if t == ntime - 1 {
                        if ntime % 2 == 0 {
                            (i, Orientation::Down)
                        } else {
                            (i + 1, Orientation::Down)
                        }
                    } else {
                        ((t + 1) * start_length + i, Orientation::Down)
                    }
                } else {
                    if t == 0 {
                        if ntime % 2 == 0 {
                            ((ntime - 1) * start_length + i, Orientation::Up)
                        } else {
                            ((ntime - 1) * start_length + i - 1, Orientation::Up)
                        }
                    } else {
                        ((t - 1) * start_length + i, Orientation::Up)
                    }
                };
                triangles.push(Triangle {
                    left,
                    center,
                    right,
                    orientation,
                });
            }
        }

        let order_four = SparseSet::with_capacity(triangles.len());

        FixedTriangulation {
            ntime: ntime as u16,
            triangles,
            order_four,
        }
    }
}

/// Implementation of the Markov-chain Monte Carlo moves
impl FixedTriangulation {
    /// Attempt flipping a pair of `Triangle`s given by the right `Triangle` `Label`,
    /// returning if the pair was actually flipped.
    ///
    /// Note: not every pair of triangles can be flipped, if this is not possible this function
    /// changes nothing and returns `false`.
    pub fn flip(&mut self, label: usize) -> bool {
        if self.is_flip_pair(label) {
            self.flip_centers(label, Self::add_order_four);
            true
        } else {
            false
        }
    }

    /// Update the connectivity for flipping a `Triangle` pair, labelled by right `Triangle`.
    ///
    /// This flip is performed by by keeping left left, and right right, but flipping the orientations
    /// and updating the `center` neighbours; so effectively _flipping the `center`s_
    /// Alternatively one can change left to right and visa versa, and update the connectivity accordingly;
    /// NOTE that this also affects the possible update of what `Triangle` becomes the flip pair.
    fn flip_centers(
        &mut self,
        right: usize,
        add_order_four: fn(&mut FixedTriangulation, usize) -> bool,
    ) {
        // Find flip pair neighbour
        let left = self.triangles[right].left;

        // Flip orientations
        let orientation_left = self.triangles[left].orientation;
        self.triangles[left].orientation = self.triangles[right].orientation;
        self.triangles[right].orientation = orientation_left;

        // Flip `center` neighbour connectivity
        let neighbour_left = self.triangles[left].center; // Find old timelike neighbours
        let neighbour_right = self.triangles[right].center;
        self.triangles[left].center = neighbour_right; // Set new neighbours
        self.triangles[right].center = neighbour_left;
        self.triangles[neighbour_left].center = right;
        self.triangles[neighbour_right].center = left;

        // Re-evaluate the order_four list
        let slice_neighbour_right = self.triangles[right].right; // Right spacelike of the right triangle of the pair
        match orientation_left {
            Orientation::Up => {
                // Up-Down -> Down-Up
                let neighbour_top_right = self.triangles[neighbour_right].right; // Top right triangle
                self.order_four.remove(neighbour_top_right); // These two could have been order four,
                self.order_four.remove(left); // but certainly are not after the flip.
                add_order_four(self, neighbour_right); // These two could have become order four after
                add_order_four(self, slice_neighbour_right); // the flip, but can't have been before.
            }
            Orientation::Down => {
                // Down-Up -> Up-Down
                let neighbour_top_right = self.triangles[neighbour_left].right; // Top right triangle
                self.order_four.remove(neighbour_left); // These two could have been order four,
                self.order_four.remove(slice_neighbour_right); // but certainly are not after the flip.
                add_order_four(self, neighbour_top_right); // These two could have become order four after
                add_order_four(self, left); // the flip, but can't have been before.
            }
        }
    }

    /// Check if `label` is order four, based on connectivity.
    /// If this is so add it to `order_four` list, and return if it is.
    pub fn add_order_four(triangulation: &mut FixedTriangulation, label: usize) -> bool {
        if triangulation.is_order_four(label) {
            triangulation.order_four.insert(label);
            true
        } else {
            false
        }
    }

    /// Relocate move which moves a shard `from` order four `to` the
    /// right of a new shard.
    ///
    /// So `from` should label a `Triangle` marking an order four vertex,
    /// and `to` should label any shard to the right of which one wants
    /// to move to.
    /// NOTE that this function check whether `from` indeed marks an
    /// order-four vertex, if not it `panic`s.
    ///
    /// Also note that if `from` points to the same shard as `to` no relocation happens,
    /// and no change is made to the triangulation.
    pub fn relocate(&mut self, from: usize, to: usize) {
        // Check that `from` labels an order four vertex
        assert!(self.order_four.contains(from));
        self.relocate_checkless(from, to);
    }

    /// Relocate move, which moves a shard `from` order four `to` the
    /// right of a new shard.
    ///
    /// So `from` should label a `Triangle` marking an order four vertex,
    /// and `to` should label any shard to the right of which one wants
    /// to move to.
    /// NOTE that this function DOES NOT check whether `from` indeed marks an
    /// order-four vertex, if not this function can break the `Triangulation`.
    /// When unsure use [`relocate()`](FixedTriangulation::relocate()) instead.
    ///
    /// Also note that if `from` points to the same shard as `to` no relocation happens,
    /// and no change is made to the triangulation.
    fn relocate_checkless(&mut self, from: usize, to: usize) {
        // Identify the `to` shard
        let (to_up, to_down) = match self.triangles[to].orientation {
            Orientation::Up => (to, self.triangles[to].center),
            Orientation::Down => (self.triangles[to].center, to),
        };

        // Simply return and do nothing is `from` shard
        if from == to_up {
            return;
        }

        // Identify shard triangles
        let shard_up = from;
        let shard_down = self.triangles[shard_up].center;

        // Identify the old neighbours
        let old_left_up = self.triangles[shard_up].left;
        let old_left_down = self.triangles[shard_down].left;
        let old_right_up = self.triangles[shard_up].right;
        let old_right_down = self.triangles[shard_down].right;

        // Move the shard out, patching the neighours
        self.triangles[old_left_up].right = old_right_up;
        self.triangles[old_left_down].right = old_right_down;
        self.triangles[old_right_up].left = old_left_up;
        self.triangles[old_right_down].left = old_left_down;

        // Identify the new neighbours
        let new_left_up = to_up;
        let new_left_down = to_down;
        let new_right_up = self.triangles[new_left_up].right;
        let new_right_down = self.triangles[new_left_down].right;

        // Move the shard into the right of `to`.
        self.triangles[new_left_up].right = shard_up;
        self.triangles[new_left_down].right = shard_down;
        self.triangles[new_right_up].left = shard_up;
        self.triangles[new_right_down].left = shard_down;

        self.triangles[shard_up].left = new_left_up;
        self.triangles[shard_up].right = new_right_up;
        self.triangles[shard_down].left = new_left_down;
        self.triangles[shard_down].right = new_right_down;

        // Note that no updating of the order four list is necessary,
        // because no neigbouring triangles get their order-fourness changed,
        // and the triangle itself moves along so stays order four.
    }
}

/// Implementations for sampling the triangulation
impl FixedTriangulation {
    /// Sample a random `Triangle` from `Triangulation` by `Label`
    ///
    /// This sampling makes use of the sampling of `LabelledList`,
    /// making it less efficient that the samplings of [`sample_flip()`](FixedTriangulation::sample_flip())
    /// and [`sample_order_four()`](FixedTriangulation::sample_order_four())
    pub fn sample_triangle<R: Rng + ?Sized>(&self, rng: &mut R) -> usize {
        rng.random_range(0..self.triangles.len())
    }

    /// Sample a random vertex of order four by the `Label` of the `Triangle`
    /// at the top right of the vertex, returning `None` if no such order-four vertices exist.
    ///
    /// This sampling makes use of an extra list, making this sampling very efficient.
    pub fn sample_order_four<R: Rng + ?Sized>(&self, rng: &mut R) -> Option<usize> {
        self.order_four.iter().choose(rng)
    }
}

/// Implementation of check for special types of structures
impl FixedTriangulation {
    /// Check if connectivity of given `Up` `Label` matches that of
    /// one marking an order four vertex.
    ///
    /// NOTE that the given `Label` must point to an `Up`-`Triangle`
    /// otherwise one could get **false positives**; use
    /// [`is_order_four()`](FixedTriangulation::is_order_four()) for a safe
    /// check, which also checks the orientation.
    /// This is because the used convention is to mark the order four
    /// vertex with the upper right `Triangle`.
    /// This check does assume the `Triangulation` connectivity
    /// itself is correct.
    pub fn is_up_order_four(&self, label: usize) -> bool {
        // Check if 'left-down' is the same as 'down-left'
        let left = self.triangles[label].left;
        let down = self.triangles[label].center;
        self.triangles[left].center == self.triangles[down].left
    }

    /// Check if connectivity of given `Label` matches that of
    /// one marking an order four vertex.
    ///
    /// Note that the used convention is to mark the order four
    /// vertex with the upper right `Triangle`.
    /// This check does assume the `Triangulation` connectivity
    /// itself is correct.
    pub fn is_order_four(&self, label: usize) -> bool {
        if self.triangles[label].orientation == Orientation::Down {
            return false;
        }
        self.is_up_order_four(label)
    }

    /// Returns whether the `Triangle` pair given by the `Label` of the right `Triangle`
    /// forms a flip_pair, which is to say the orientations are opposite.
    pub fn is_flip_pair(&self, label: usize) -> bool {
        let left = self.triangles[label].left;
        self.triangles[label].orientation != self.triangles[left].orientation
    }
}

#[cfg(test)]
mod tests {
    // Note some of these test use RNG, which is done with a reproducable RNG using a fixed seed
    use super::*;

    /// Implementations for `Triangulation` verification
    impl FixedTriangulation {
        /// Perform possible check to assess the validity of the `Triangulation`.
        ///
        /// If the `Triangulation` is not valid something has gone wrong in construction,
        /// and unexpected behaviour can occur, so this function `panic`s.
        /// The validity is assessed by [`assert_biconnectivity()`](Triangulation::assert_biconnectivity()),
        /// [`assert_order_four()`](Triangulation::assert_order_four()),
        /// and [`assert_flip_pair()`](Triangulation::assert_flip_pair()).
        pub fn assert_triangulation(&self) {
            self.assert_biconnectivity();
            self.assert_order_four();
        }

        /// Check whether all set connections of Triangles, are correctly set in reverse, `panic`s if not.
        fn assert_biconnectivity(&self) {
            let triangles = &self.triangles;
            for (label, _) in triangles.iter().enumerate() {
                // Get all neighbours
                let neighbour_left = triangles[label].left;
                let neighbour_center = triangles[label].center;
                let neighbour_right = triangles[label].right;
                // Check connections of neighbours to original triangle
                assert_eq!(
                    triangles[neighbour_left].right, label,
                    "Connection between {} and left neighbour {} is not correct",
                    label, neighbour_left
                );
                assert_ne!(
                    triangles[label].orientation, triangles[neighbour_center].orientation,
                    "Timelike coupling on non Up-Down pair {} and {}",
                    label, neighbour_center
                );
                assert_eq!(
                    triangles[neighbour_center].center, label,
                    "Connection between {} {:?} and center neighbour {} is not correct",
                    label, triangles[label], neighbour_center
                );
                assert_eq!(
                    triangles[neighbour_right].left, label,
                    "Connection between {} and right neighbour {} is not correct",
                    label, neighbour_right
                );
            }
        }

        /// Check whether order_four list is correct and complete, `panic`s if not.
        fn assert_order_four(&self) {
            // First check if `order_four` list doesn't contain non-existent triangles
            for label in self.order_four.iter() {
                assert!(
                    label < self.triangles.len(),
                    "A non-existent Triangle is present in the order four list."
                );
            }

            // Check all Triangles for order four-ness and compare to order four list
            for (label, _) in self.triangles.iter().enumerate() {
                if self.is_order_four(label) {
                    assert!(
                        self.order_four.contains(label),
                        "Triangle {} is order four, but not in the order_four list",
                        label
                    );
                } else {
                    assert!(
                        !self.order_four.contains(label),
                        "Triangle {} is not order four, but is in the order_four list",
                        label
                    );
                }
            }
        }
    }

    #[test]
    fn triangulation_construction() {
        let triangulation = FixedTriangulation::new(1000, 10);
        triangulation.assert_triangulation();
        assert_eq!(
            triangulation.order_four.len(),
            0,
            "Triangulation started out with some order four Triangles"
        );
    }
}
