<commit_before>// Copyright 2017 <NAME> <<EMAIL>>

//! Triangulate a set of points

/// A two dimentional point.
#[derive(Clone, Copy, Debug)]
pub struct Point {
    x: f64,
    y: f64,
}

impl Point {
    /// Makes a new point from xy coordinates.
    pub fn new(x: f64, y: f64) -> Point {
        Point { x: x, y: y }
    }
}

/// A triangle, represented by indexes into a vertice list.
#[derive(Debug, PartialEq)]
pub struct Triangle(usize, usize, usize);

/// An edge, represented by indexes into a vertice list.
#[derive(Debug, Clone)]
struct Edge(usize, usize);

impl PartialEq for Edge {
    /// Compare edges regardless of directionality.
    fn eq(&self, other: &Edge) -> bool {
        (self.0 == other.1 && self.1 == other.0) || (self.0 == other.0 && self.1 == other.1)
    }
}

/// An indexable view over two slices.
struct TwoSlices<'a, T: 'a>(&'a [T], &'a [T]);

use std::ops::Index;
impl<'a, T: 'a> Index<usize> for TwoSlices<'a, T> {
    type Output = T;
    fn index(&self, index: usize) -> &T {
        if index < self.0.len() {
            &self.0[index]
        } else {
            &self.1[index - self.0.len()]
        }
    }
}

/// Triangulate a given set of points. The returned triangles are indices into the list of points.
pub fn triangulate(points: &[Point]) -> Vec<Triangle> {
    // Make sure we have enough points to do a triangulation.
    let points_count = points.len();
    if points_count < 3 {
        panic!("Can't triangulate less than three points.")
    }
    let max_triangles = points_count * 4;

    // Find the bounds of the space that contains our points.
    let (min_point, max_point) = points.iter().fold((points[0], points[0]), |acc, &p| {
        (Point::new(acc.0.x.min(p.x), acc.0.y.min(p.y)),
         Point::new(acc.1.x.max(p.x), acc.1.y.max(p.y)))
    });
    let delta_point = Point::new(max_point.x - min_point.x, max_point.y - min_point.y);
    let delta_max = delta_point.x.max(delta_point.y);
    let mid_point = Point::new((max_point.x + min_point.x) * 0.5,
                               (max_point.y + min_point.y) * 0.5);

    // Compute the supertriangle, which encompasses all the input points.
    let supertriangle = [Point::new(mid_point.x - 2.0 * delta_max, mid_point.y - delta_max),
                         Point::new(mid_point.x, mid_point.y + 2.0 * delta_max),
                         Point::new(mid_point.x + 2.0 * delta_max, mid_point.y - delta_max)];

    // Make an iterable slice of our points and the supertriangle.
    let all_points = TwoSlices(points, &supertriangle);

    // The list of triangles we're gonna fill, initialized with the super-triangle.
    let mut triangles = vec![Triangle(points_count, points_count + 1, points_count + 2)];

    // Include each of the input point into the mesh.
    for i in 0..points_count {
        // Storage for the edges
        let mut edges = Vec::<Edge>::new();

        {
            let mut j = 0;
            while j < triangles.len() {
                if in_circle(all_points[i],
                             all_points[triangles[j].0],
                             all_points[triangles[j].1],
                             all_points[triangles[j].2]) {
                    edges.push(Edge(triangles[j].0, triangles[j].1));
                    edges.push(Edge(triangles[j].1, triangles[j].2));
                    edges.push(Edge(triangles[j].2, triangles[j].0));
                    triangles.remove(j);
                } else {
                    j += 1;
                }
            }
        }

        // Remove duplicate edges.
        let mut to_remove = Vec::<usize>::new();
        let edges_count = edges.len();
        for (j, ref e1) in edges.iter().enumerate().rev().skip(1) {
            for (k, ref e2) in edges.iter().enumerate().rev().take(edges_count - j - 1) {
                if e1 == e2 {
                    to_remove.push(k);
                    to_remove.push(j);
                    break;
                }
            }
        }
        to_remove.sort();
        for j in to_remove.iter().rev() {
            edges.remove(*j);
        }

        // Form new triangles from the remaining edges. Edges are added in clockwise order.
        {
            let mut j = 0;
            while j < edges.len() {
                if triangles.len() >= max_triangles {
                    panic!("Exceeded maximum edges");
                }
                triangles.push(Triangle(edges[j].0, edges[j].1, i));
                j += 1;
            }
        }
    }

    // Remove triangles with supertriangle vertices
    triangles.retain(|ref t| t.0 < points_count && t.1 < points_count && t.2 < points_count);<commit_msg>Adding triangles from edges is now more idiomatic.<commit_after>// Copyright 2017 <NAME> <<EMAIL>>

//! Triangulate a set of points

/// A two dimentional point.
#[derive(Clone, Copy, Debug)]
pub struct Point {
    x: f64,
    y: f64,
}

impl Point {
    /// Makes a new point from xy coordinates.
    pub fn new(x: f64, y: f64) -> Point {
        Point { x: x, y: y }
    }
}

/// A triangle, represented by indexes into a vertice list.
#[derive(Debug, PartialEq)]
pub struct Triangle(usize, usize, usize);

/// An edge, represented by indexes into a vertice list.
#[derive(Debug, Clone)]
struct Edge(usize, usize);

impl PartialEq for Edge {
    /// Compare edges regardless of directionality.
    fn eq(&self, other: &Edge) -> bool {
        (self.0 == other.1 && self.1 == other.0) || (self.0 == other.0 && self.1 == other.1)
    }
}

/// An indexable view over two slices.
struct TwoSlices<'a, T: 'a>(&'a [T], &'a [T]);

use std::ops::Index;
impl<'a, T: 'a> Index<usize> for TwoSlices<'a, T> {
    type Output = T;
    fn index(&self, index: usize) -> &T {
        if index < self.0.len() {
            &self.0[index]
        } else {
            &self.1[index - self.0.len()]
        }
    }
}

/// Triangulate a given set of points. The returned triangles are indices into the list of points.
pub fn triangulate(points: &[Point]) -> Vec<Triangle> {
    // Make sure we have enough points to do a triangulation.
    let points_count = points.len();
    if points_count < 3 {
        panic!("Can't triangulate less than three points.")
    }
    let max_triangles = points_count * 4;

    // Find the bounds of the space that contains our points.
    let (min_point, max_point) = points.iter().fold((points[0], points[0]), |acc, &p| {
        (Point::new(acc.0.x.min(p.x), acc.0.y.min(p.y)),
         Point::new(acc.1.x.max(p.x), acc.1.y.max(p.y)))
    });
    let delta_point = Point::new(max_point.x - min_point.x, max_point.y - min_point.y);
    let delta_max = delta_point.x.max(delta_point.y);
    let mid_point = Point::new((max_point.x + min_point.x) * 0.5,
                               (max_point.y + min_point.y) * 0.5);

    // Compute the supertriangle, which encompasses all the input points.
    let supertriangle = [Point::new(mid_point.x - 2.0 * delta_max, mid_point.y - delta_max),
                         Point::new(mid_point.x, mid_point.y + 2.0 * delta_max),
                         Point::new(mid_point.x + 2.0 * delta_max, mid_point.y - delta_max)];

    // Make an iterable slice of our points and the supertriangle.
    let all_points = TwoSlices(points, &supertriangle);

    // The list of triangles we're gonna fill, initialized with the super-triangle.
    let mut triangles = vec![Triangle(points_count, points_count + 1, points_count + 2)];

    // Include each of the input point into the mesh.
    for i in 0..points_count {
        // Storage for the edges
        let mut edges = Vec::<Edge>::new();

        {
            let mut j = 0;
            while j < triangles.len() {
                if in_circle(all_points[i],
                             all_points[triangles[j].0],
                             all_points[triangles[j].1],
                             all_points[triangles[j].2]) {
                    edges.push(Edge(triangles[j].0, triangles[j].1));
                    edges.push(Edge(triangles[j].1, triangles[j].2));
                    edges.push(Edge(triangles[j].2, triangles[j].0));
                    triangles.remove(j);
                } else {
                    j += 1;
                }
            }
        }

        // Remove duplicate edges.
        let mut to_remove = Vec::<usize>::new();
        let edges_count = edges.len();
        for (j, ref e1) in edges.iter().enumerate().rev().skip(1) {
            for (k, ref e2) in edges.iter().enumerate().rev().take(edges_count - j - 1) {
                if e1 == e2 {
                    to_remove.push(k);
                    to_remove.push(j);
                    break;
                }
            }
        }
        to_remove.sort();
        for j in to_remove.iter().rev() {
            edges.remove(*j);
        }

        // Form new triangles from the remaining edges. Edges are added in clockwise order.
        triangles.extend(edges.iter().map(|ref e| Triangle(e.0, e.1, i)));
    }

    // Remove triangles with supertriangle vertices
    triangles.retain(|ref t| t.0 < points_count && t.1 < points_count && t.2 < points_count);
{'fraction_non_alphanumeric': 0.1414041994750656, 'fraction_numerical': 0.014873140857392825, 'mean_word_length': 1.886679292929293, 'pattern_counts': {'":': 0, '<': 36, '<?xml version=': 0, '>': 32, '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': '3972508', 'n_tokens_mistral': 3010, 'n_tokens_neox': 2884, 'n_words': 795}