<commit_before>use std::cmp::Ordering;

/// The dominance relation.

pub trait Dominate {

    /// If `self` dominates `other`, return `Less`.
    /// If `other` dominates `self`, return `Greater`.
    /// If neither `self` nor `other` dominates the other, `Equal`.

    fn dominate(&self, other: &Self) -> Ordering {
        if self.dominates(other) {
            Ordering::Less
        } else if other.dominates(self) {
            Ordering::Greater
        } else {
            Ordering::Equal
        }
    }

    /// Returns true if `self` dominates `other`.

    fn dominates(&self, other: &Self) -> bool {
        match self.dominate(other) {
            Ordering::Less => true,
            _ => false
        }
    }
}

/// Perform a non dominated sort of the `solutions`.
///
/// Stop after we have found `n` solutions. As we include the whole pareto front, there are
/// probably more solutions returned.

pub fn fast_non_dominated_sort<P: Dominate>(solutions: &[P], n: usize) -> Vec<Vec<usize>> {
    let mut fronts: Vec<Vec<usize>> = Vec::new();
    let mut current_front = Vec::new();

    let mut domination_count: Vec<usize> = (0..solutions.len()).map(|_| 0).collect();
    let mut dominated_solutions: Vec<Vec<usize>> = (0..solutions.len())
                                                       .map(|_| Vec::new())
                                                       .collect();
    let mut found_solutions: usize = 0;

    for (i, p) in solutions.iter().enumerate() {
        for (j, q) in solutions.iter().enumerate() {
            if i == j {
                continue;
            }
            match p.dominate(q) {
                Ordering::Less => {
                    // p dominates q
                    // Add `q` to the set of solutions dominated by `p`.
                    dominated_solutions[i].push(j);
                }
                Ordering::Greater => {
                    // q dominates p
                    // Increment domination counter of `p`.
                    domination_count[i] += 1;
                }
                _ => {}
            }
        }

        if domination_count[i] == 0 {
            // `p` belongs to the first front as it is not dominated by any
            // other solution.
            current_front.push(i);
        }
    }

    while !current_front.is_empty() {
        found_solutions += current_front.len();
        if found_solutions >= n {
            fronts.push(current_front);<commit_msg>Half the total number of iterations by using symmetry<commit_after>use std::cmp::Ordering;

/// The dominance relation.

pub trait Dominate {

    /// If `self` dominates `other`, return `Less`.
    /// If `other` dominates `self`, return `Greater`.
    /// If neither `self` nor `other` dominates the other, `Equal`.

    fn dominate(&self, other: &Self) -> Ordering {
        if self.dominates(other) {
            Ordering::Less
        } else if other.dominates(self) {
            Ordering::Greater
        } else {
            Ordering::Equal
        }
    }

    /// Returns true if `self` dominates `other`.

    fn dominates(&self, other: &Self) -> bool {
        match self.dominate(other) {
            Ordering::Less => true,
            _ => false
        }
    }
}

/// Perform a non dominated sort of the `solutions`.
///
/// Stop after we have found `n` solutions. As we include the whole pareto front, there are
/// probably more solutions returned.

pub fn fast_non_dominated_sort<P: Dominate>(solutions: &[P], n: usize) -> Vec<Vec<usize>> {
    let mut fronts: Vec<Vec<usize>> = Vec::new();
    let mut current_front = Vec::new();

    let mut domination_count: Vec<usize> = (0..solutions.len()).map(|_| 0).collect();
    let mut dominated_solutions: Vec<Vec<usize>> = (0..solutions.len())
                                                       .map(|_| Vec::new())
                                                       .collect();
    let mut found_solutions: usize = 0;

    for i in 0 .. solutions.len() {
        for j in i+1 .. solutions.len() {
            let p = &solutions[i];
            let q = &solutions[j];

            match p.dominate(q) {
                Ordering::Less => {
                    // p dominates q
                    // Add `q` to the set of solutions dominated by `p`.
                    dominated_solutions[i].push(j);
                    // q is dominated by p
                    domination_count[j] += 1;
                }
                Ordering::Greater => {
                    // p is dominated by q
                    // Add `p` to the set of solutions dominated by `q`.
                    dominated_solutions[j].push(i);
                    // q dominates p
                    // Increment domination counter of `p`.
                    domination_count[i] += 1;
                }
                _ => {}
            }
        }

        if domination_count[i] == 0 {
            // `p` belongs to the first front as it is not dominated by any
            // other solution.
            current_front.push(i);
        }
    }

    while !current_front.is_empty() {
        found_solutions += current_front.len();
        if found_solutions >= n {
            fronts.push(current_front);
{'fraction_non_alphanumeric': 0.12586074980872228, 'fraction_numerical': 0.002869166029074216, 'mean_word_length': 1.4781990521327015, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 37, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4580185', 'n_tokens_mistral': 1478, 'n_tokens_neox': 1398, 'n_words': 416}