<commit_before>use std::collections::HashMap;

use bit_set::BitSet;
use cgmath::{BaseFloat, Point3, Vector3};
use cgmath::prelude::*;

use {Aabb3, Plane, Ray3};
use prelude::*;
use primitive::util::barycentric_point;

#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "eders", derive(Serialize, Deserialize))]
enum PolyhedronMode {
    VertexOnly,
    HalfEdge,
}

#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "eders", derive(Serialize, Deserialize))]
struct Vertex<S> {
    position: Point3<S>,
    edge: usize,
    ready: bool,
}

#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "eders", derive(Serialize, Deserialize))]
struct Edge {
    target_vertex: usize,
    left_face: usize,
    next_edge: usize,
    previous_edge: usize,
    twin_edge: usize,
    ready: bool,
}

#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "eders", derive(Serialize, Deserialize))]
struct Face<S>
where
    S: BaseFloat,
{
    edge: usize,
    vertices: (usize, usize, usize),
    plane: Plane<S>,
    ready: bool,
}

/// Convex polyhedron primitive.
///
/// Can contain any number of vertices, but a high number of vertices will
/// affect performance of course. It is recommended for high vertex counts, to also provide the
/// faces, this will cause the support function to use hill climbing on a half edge structure,
/// resulting in better performance. The breakpoint is around 250 vertices, but the face version is
/// only marginally slower on lower vertex counts (about 1-2%), while for higher vertex counts it's
/// about 2-5 times faster.
///
///
#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "eders", derive(Serialize, Deserialize))]
pub struct ConvexPolyhedron<S>
where
    S: BaseFloat,
{
    mode: PolyhedronMode,
    vertices: Vec<Vertex<S>>,
    edges: Vec<Edge>,
    faces: Vec<Face<S>>,
    bound: Aabb3<S>,
}

impl<S> ConvexPolyhedron<S>
where
    S: BaseFloat,
{
    /// Create a new convex polyhedron from the given vertices.
    pub fn new(vertices: Vec<Point3<S>>) -> Self {
        Self {
            mode: PolyhedronMode::VertexOnly,
            vertices: vertices
                .iter()
                .map(|v| Vertex {
                    position: v.clone(),
                    edge: 0,
                    ready: true,
                })
                .collect(),
            edges: Vec::default(),
            faces: Vec::default(),
            bound: vertices
                .iter()
                .fold(Aabb3::zero(), |bound, p| bound.grow(*p)),
        }
    }

    /// Create a new convex polyhedron from the given vertices and faces.
    pub fn new_with_faces(vertices: Vec<Point3<S>>, faces: Vec<(usize, usize, usize)>) -> Self {
        let (vertices, edges, faces) = build_half_edges(&vertices, &faces);
        Self {
            mode: PolyhedronMode::HalfEdge,
            bound: vertices
                .iter()
                .fold(Aabb3::zero(), |bound, p| bound.grow(p.position)),
            vertices,
            edges,
            faces,
        }
    }

    /// Create a new convex polyhedron from the given vertices and faces. Will remove any duplicate
    /// vertices.
    pub fn new_with_faces_dedup(
        vertices: Vec<Point3<S>>,
        faces: Vec<(usize, usize, usize)>,
    ) -> Self {
        let (vertices, map) = dedup_vertices(vertices);
        Self::new_with_faces(vertices, dedup_faces(faces, map))
    }

    /// Return an iterator that will yield tuples of the 3 vertices of each face
    pub fn faces_iter(&self) -> FaceIterator<S> {
        assert_eq!(self.mode, PolyhedronMode::HalfEdge);
        FaceIterator::new(self)
    }

    #[inline]
    fn brute_force_support_point(&self, direction: Vector3<S>) -> Point3<S> {
        let (p, _) = self.vertices
            .iter()
            .map(|v| (v.position, v.position.dot(direction)))
            .fold(
                (Point3::origin(), S::neg_infinity()),
                |(max_p, max_dot), (v, dot)| {
                    if dot > max_dot {
                        (v.clone(), dot)
                    } else {
                        (max_p, max_dot)
                    }
                },
            );
        p
    }

    #[inline]
    fn hill_climb_support_point(&self, direction: Vector3<S>) -> Point3<S> {
        let mut best_index = 0;
        let mut best_dot = self.vertices[best_index].position.dot(direction);

        loop {
            let previous_best_dot = best_dot;
            let mut edge_index = self.vertices[best_index].edge;
            let start_edge_index = edge_index;

            loop {
                let vertex_index = self.edges[edge_index].target_vertex;

                let dot = self.vertices[vertex_index].position.dot(direction);
                if dot > best_dot {
                    best_index = vertex_index;
                    best_dot = dot;
                }

                edge_index = self.edges[self.edges[edge_index].twin_edge].next_edge;
                if start_edge_index == edge_index {
                    break;
                }
            }

            if best_dot == previous_best_dot {
                break;
            }
        }

        self.vertices[best_index].position.clone()
    }
}

/// Iterate over polyhedron faces.
/// Yields a tuple with the positions of the 3 vertices of each face
pub struct FaceIterator<'a, S: 'a>
where
    S: BaseFloat,
{
    polyhedron: &'a ConvexPolyhedron<S>,
    current: usize,
}

impl<'a, S: 'a> FaceIterator<'a, S>
where
    S: BaseFloat,
{
    pub fn new(polyhedron: &'a ConvexPolyhedron<S>) -> Self {
        Self {
            polyhedron,
            current: 0,
        }
    }
}

impl<'a, S> Iterator for FaceIterator<'a, S>
where
    S: BaseFloat,
{
    type Item = (&'a Point3<S>, &'a Point3<S>, &'a Point3<S>);
<commit_msg>fix: Removing public constructor for FaceIterator, should only be accessible via .<commit_after>use std::collections::HashMap;

use bit_set::BitSet;
use cgmath::{BaseFloat, Point3, Vector3};
use cgmath::prelude::*;

use {Aabb3, Plane, Ray3};
use prelude::*;
use primitive::util::barycentric_point;

#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "eders", derive(Serialize, Deserialize))]
enum PolyhedronMode {
    VertexOnly,
    HalfEdge,
}

#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "eders", derive(Serialize, Deserialize))]
struct Vertex<S> {
    position: Point3<S>,
    edge: usize,
    ready: bool,
}

#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "eders", derive(Serialize, Deserialize))]
struct Edge {
    target_vertex: usize,
    left_face: usize,
    next_edge: usize,
    previous_edge: usize,
    twin_edge: usize,
    ready: bool,
}

#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "eders", derive(Serialize, Deserialize))]
struct Face<S>
where
    S: BaseFloat,
{
    edge: usize,
    vertices: (usize, usize, usize),
    plane: Plane<S>,
    ready: bool,
}

/// Convex polyhedron primitive.
///
/// Can contain any number of vertices, but a high number of vertices will
/// affect performance of course. It is recommended for high vertex counts, to also provide the
/// faces, this will cause the support function to use hill climbing on a half edge structure,
/// resulting in better performance. The breakpoint is around 250 vertices, but the face version is
/// only marginally slower on lower vertex counts (about 1-2%), while for higher vertex counts it's
/// about 2-5 times faster.
///
///
#[derive(Debug, Clone, PartialEq)]
#[cfg_attr(feature = "eders", derive(Serialize, Deserialize))]
pub struct ConvexPolyhedron<S>
where
    S: BaseFloat,
{
    mode: PolyhedronMode,
    vertices: Vec<Vertex<S>>,
    edges: Vec<Edge>,
    faces: Vec<Face<S>>,
    bound: Aabb3<S>,
}

impl<S> ConvexPolyhedron<S>
where
    S: BaseFloat,
{
    /// Create a new convex polyhedron from the given vertices.
    pub fn new(vertices: Vec<Point3<S>>) -> Self {
        Self {
            mode: PolyhedronMode::VertexOnly,
            vertices: vertices
                .iter()
                .map(|v| Vertex {
                    position: v.clone(),
                    edge: 0,
                    ready: true,
                })
                .collect(),
            edges: Vec::default(),
            faces: Vec::default(),
            bound: vertices
                .iter()
                .fold(Aabb3::zero(), |bound, p| bound.grow(*p)),
        }
    }

    /// Create a new convex polyhedron from the given vertices and faces.
    pub fn new_with_faces(vertices: Vec<Point3<S>>, faces: Vec<(usize, usize, usize)>) -> Self {
        let (vertices, edges, faces) = build_half_edges(&vertices, &faces);
        Self {
            mode: PolyhedronMode::HalfEdge,
            bound: vertices
                .iter()
                .fold(Aabb3::zero(), |bound, p| bound.grow(p.position)),
            vertices,
            edges,
            faces,
        }
    }

    /// Create a new convex polyhedron from the given vertices and faces. Will remove any duplicate
    /// vertices.
    pub fn new_with_faces_dedup(
        vertices: Vec<Point3<S>>,
        faces: Vec<(usize, usize, usize)>,
    ) -> Self {
        let (vertices, map) = dedup_vertices(vertices);
        Self::new_with_faces(vertices, dedup_faces(faces, map))
    }

    /// Return an iterator that will yield tuples of the 3 vertices of each face
    pub fn faces_iter(&self) -> FaceIterator<S> {
        assert_eq!(self.mode, PolyhedronMode::HalfEdge);
        FaceIterator {
            polyhedron: self,
            current: 0,
        }
    }

    #[inline]
    fn brute_force_support_point(&self, direction: Vector3<S>) -> Point3<S> {
        let (p, _) = self.vertices
            .iter()
            .map(|v| (v.position, v.position.dot(direction)))
            .fold(
                (Point3::origin(), S::neg_infinity()),
                |(max_p, max_dot), (v, dot)| {
                    if dot > max_dot {
                        (v.clone(), dot)
                    } else {
                        (max_p, max_dot)
                    }
                },
            );
        p
    }

    #[inline]
    fn hill_climb_support_point(&self, direction: Vector3<S>) -> Point3<S> {
        let mut best_index = 0;
        let mut best_dot = self.vertices[best_index].position.dot(direction);

        loop {
            let previous_best_dot = best_dot;
            let mut edge_index = self.vertices[best_index].edge;
            let start_edge_index = edge_index;

            loop {
                let vertex_index = self.edges[edge_index].target_vertex;

                let dot = self.vertices[vertex_index].position.dot(direction);
                if dot > best_dot {
                    best_index = vertex_index;
                    best_dot = dot;
                }

                edge_index = self.edges[self.edges[edge_index].twin_edge].next_edge;
                if start_edge_index == edge_index {
                    break;
                }
            }

            if best_dot == previous_best_dot {
                break;
            }
        }

        self.vertices[best_index].position.clone()
    }
}

/// Iterate over polyhedron faces.
/// Yields a tuple with the positions of the 3 vertices of each face
pub struct FaceIterator<'a, S: 'a>
where
    S: BaseFloat,
{
    polyhedron: &'a ConvexPolyhedron<S>,
    current: usize,
}

impl<'a, S> Iterator for FaceIterator<'a, S>
where
    S: BaseFloat,
{
    type Item = (&'a Point3<S>, &'a Point3<S>, &'a Point3<S>);

{'fraction_non_alphanumeric': 0.1235906331309627, 'fraction_numerical': 0.005377276669557675, 'mean_word_length': 2.0930793991416308, 'pattern_counts': {'":': 0, '<': 72, '<?xml version=': 0, '>': 89, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '213778', 'n_tokens_mistral': 3589, 'n_tokens_neox': 3523, 'n_words': 943}