//! 切片选择
//!
//! 该模块包含 `slice::select_nth_unstable` 的实现。
//! 它使用基于 Orson Peters 的模式失败快速排序的 introselect 算法，发表于: <https://github.com/orlp/pdqsort>
//!
//!
//! 用于 introselect 的回退算法是使用 Tukey's 的 Ninther 进行 pivot 选择的中位数的中位数。
//! 将其用作后备可确保 O(n) 最坏情况下的运行时间具有比使用堆排序作为后备更好的性能。
//!

use crate::cmp;
use crate::mem::{self, SizedTypeProperties};
use crate::slice::sort::{
    break_patterns, choose_pivot, insertion_sort_shift_left, partition, partition_equal,
};

// 对于不超过此长度的切片，将其简单排序可能会更快。
// 定义在模块作用域，因为它被用在多个函数中。
const MAX_INSERTION: usize = 10;

fn partition_at_index_loop<'a, T, F>(
    mut v: &'a mut [T],
    mut index: usize,
    is_less: &mut F,
    mut pred: Option<&'a T>,
) where
    F: FnMut(&T, &T) -> bool,
{
    // 限制迭代次数并回退到快速确定性选择，以确保 O(n) 最坏情况下的运行时间。
    // 此限制需要为常量，因为像在 `sort` 中使用 `ilog2(len)` 会导致 O(n log n) 时间复杂度。
    // 限制的确切值是任意选择的，但对于大多数输入来说，错误的 pivot 选择应该相对较少，因此通常无论如何都不应达到限制。
    //
    //
    //
    let mut limit = 16;

    // 如果最后一个分区合理平衡，则为 true。
    let mut was_balanced = true;

    loop {
        if v.len() <= MAX_INSERTION {
            if v.len() > 1 {
                insertion_sort_shift_left(v, 1, is_less);
            }
            return;
        }

        if limit == 0 {
            median_of_medians(v, is_less, index);
            return;
        }

        // 如果最后一个分区不平衡，请尝试通过改组一些元素来破坏切片中的模式。
        // 希望这次我们选择一个更好的支点。
        if !was_balanced {
            break_patterns(v);
            limit -= 1;
        }

        // 选择一个 pivot
        let (pivot, _) = choose_pivot(v, is_less);

        // 如果选择的枢轴等于前一个枢轴，则它是切片中的最小元素。
        // 将切片划分为等于和大于枢轴的元素。
        // 当切片包含许多重复元素时，通常会遇到这种情况。
        if let Some(p) = pred {
            if !is_less(p, &v[pivot]) {
                let mid = partition_equal(v, pivot, is_less);

                // 如果我们通过了索引，那么我们就很好。
                if mid > index {
                    return;
                }

                // 否则，继续对大于枢轴的元素进行排序。
                v = &mut v[mid..];
                index = index - mid;
                pred = None;
                continue;
            }
        }

        let (mid, _) = partition(v, pivot, is_less);
        was_balanced = cmp::min(mid, v.len() - mid) >= v.len() / 8;

        // 将切片分为 `left`，`pivot` 和 `right`。
        let (left, right) = v.split_at_mut(mid);
        let (pivot, right) = right.split_at_mut(1);
        let pivot = &pivot[0];

        if mid < index {
            v = right;
            index = index - mid - 1;
            pred = Some(pivot);
        } else if mid > index {
            v = left;
        } else {
            // 如果 mid == index，那么我们就完成了，因为 partition() 保证 mid 之后的所有元素都大于或等于 mid。
            //
            return;
        }
    }
}

/// 使用给定比较器函数返回切片中最小元素索引的辅助函数
///
fn min_index<T, F: FnMut(&T, &T) -> bool>(slice: &[T], is_less: &mut F) -> Option<usize> {
    slice
        .iter()
        .enumerate()
        .reduce(|acc, t| if is_less(t.1, acc.1) { t } else { acc })
        .map(|(i, _)| i)
}

/// 使用给定比较器函数返回切片中最大元素索引的辅助函数
///
fn max_index<T, F: FnMut(&T, &T) -> bool>(slice: &[T], is_less: &mut F) -> Option<usize> {
    slice
        .iter()
        .enumerate()
        .reduce(|acc, t| if is_less(acc.1, t.1) { t } else { acc })
        .map(|(i, _)| i)
}

/// 重新排序切片，以使 `index` 处的元素处于其最终排序位置。
pub fn partition_at_index<T, F>(
    v: &mut [T],
    index: usize,
    mut is_less: F,
) -> (&mut [T], &mut T, &mut [T])
where
    F: FnMut(&T, &T) -> bool,
{
    if index >= v.len() {
        panic!("partition_at_index index {} greater than length of slice {}", index, v.len());
    }

    if T::IS_ZST {
        // 零大小类型的排序没有有意义的行为。什么也不做。
    } else if index == v.len() - 1 {
        // 查找最大元素并将其放置在数组的最后一个位置。
        // 我们可以在这里自由使用 `unwrap()`，因为我们知道 v 不能为空。
        let max_idx = max_index(v, &mut is_less).unwrap();
        v.swap(max_idx, index);
    } else if index == 0 {
        // 查找 min 元素并将其放置在数组的第一个位置。
        // 我们可以在这里自由使用 `unwrap()`，因为我们知道 v 不能为空。
        let min_idx = min_index(v, &mut is_less).unwrap();
        v.swap(min_idx, index);
    } else {
        partition_at_index_loop(v, index, &mut is_less, None);
    }

    let (left, right) = v.split_at_mut(index);
    let (pivot, right) = right.split_at_mut(1);
    let pivot = &mut pivot[0];
    (left, pivot, right)
}

/// 选择算法在保证的 O(n) 时间内从切片中选择第 k 个元素。
/// 这本质上是一个使用 Tukey's Ninther 进行 pivot 选择的快速选择
fn median_of_medians<T, F: FnMut(&T, &T) -> bool>(mut v: &mut [T], is_less: &mut F, mut k: usize) {
    // 由于此函数不是公开的，因此永远不应使用越界索引调用它。
    debug_assert!(k < v.len());

    // 如果 T 为 ZST，则 `partition_at_index` 将提前返回。
    debug_assert!(!T::IS_ZST);

    // 我们现在知道 `k < v.len() <= isize::MAX`
    loop {
        if v.len() <= MAX_INSERTION {
            if v.len() > 1 {
                insertion_sort_shift_left(v, 1, is_less);
            }
            return;
        }

        // `median_of_{minima,maxima}` 无法处理 first/last 元素的极端情况，所以我们在这里捕获它们并进行线性搜索。
        //
        if k == v.len() - 1 {
            // 查找最大元素并将其放置在数组的最后一个位置。
            // 我们可以在这里自由使用 `unwrap()`，因为我们知道 v 不能为空。
            let max_idx = max_index(v, is_less).unwrap();
            v.swap(max_idx, k);
            return;
        } else if k == 0 {
            // 查找 min 元素并将其放置在数组的第一个位置。
            // 我们可以在这里自由使用 `unwrap()`，因为我们知道 v 不能为空。
            let min_idx = min_index(v, is_less).unwrap();
            v.swap(min_idx, k);
            return;
        }

        let p = median_of_ninthers(v, is_less);

        if p == k {
            return;
        } else if p > k {
            v = &mut v[..p];
        } else {
            // 由于 `p < k < v.len()`，`p + 1` 不会溢出并且是切片的有效索引。
            //
            v = &mut v[p + 1..];
            k -= p + 1;
        }
    }
}

// 针对 `k` 位于切片中间某处的情况进行了优化。选择尽可能接近切片中值的 pivot。
// 有关该算法如何运行的更多详细信息，请参见论文 <https://drops.dagstuhl.de/opus/volltexte/2017/7612/pdf/LIPIcs-SEA-2017-24.pdf>。
//
fn median_of_ninthers<T, F: FnMut(&T, &T) -> bool>(v: &mut [T], is_less: &mut F) -> usize {
    // 使用 `saturating_mul` 这样乘法就不会在 16 位平台上溢出。
    let frac = if v.len() <= 1024 {
        v.len() / 12
    } else if v.len() <= 128_usize.saturating_mul(1024) {
        v.len() / 64
    } else {
        v.len() / 1024
    };

    let pivot = frac / 2;
    let lo = v.len() / 2 - pivot;
    let hi = frac + lo;
    let gap = (v.len() - 9 * frac) / 4;
    let mut a = lo - 4 * frac - gap;
    let mut b = hi + gap;
    for i in lo..hi {
        ninther(v, is_less, a, i - frac, b, a + 1, i, b + 1, a + 2, i + frac, b + 2);
        a += 3;
        b += 3;
    }

    median_of_medians(&mut v[lo..lo + frac], is_less, pivot);
    partition(v, lo + pivot, is_less).0
}

/// 在索引 a..i 处围绕 9 个元素移动，使得 `v[d]` 包含 9 个元素的中值，其他元素围绕它进行分区。
///
///
fn ninther<T, F: FnMut(&T, &T) -> bool>(
    v: &mut [T],
    is_less: &mut F,
    a: usize,
    mut b: usize,
    c: usize,
    mut d: usize,
    e: usize,
    mut f: usize,
    g: usize,
    mut h: usize,
    i: usize,
) {
    b = median_idx(v, is_less, a, b, c);
    h = median_idx(v, is_less, g, h, i);
    if is_less(&v[h], &v[b]) {
        mem::swap(&mut b, &mut h);
    }
    if is_less(&v[f], &v[d]) {
        mem::swap(&mut d, &mut f);
    }
    if is_less(&v[e], &v[d]) {
        // 没做什么
    } else if is_less(&v[f], &v[e]) {
        d = f;
    } else {
        if is_less(&v[e], &v[b]) {
            v.swap(e, b);
        } else if is_less(&v[h], &v[e]) {
            v.swap(e, h);
        }
        return;
    }
    if is_less(&v[d], &v[b]) {
        d = b;
    } else if is_less(&v[h], &v[d]) {
        d = h;
    }

    v.swap(d, e);
}

/// 返回指向 3 个元素 `v[a]`、`v[b]` 和 `v[c]` 的中值的索引
///
fn median_idx<T, F: FnMut(&T, &T) -> bool>(
    v: &[T],
    is_less: &mut F,
    mut a: usize,
    b: usize,
    mut c: usize,
) -> usize {
    if is_less(&v[c], &v[a]) {
        mem::swap(&mut a, &mut c);
    }
    if is_less(&v[c], &v[b]) {
        return c;
    }
    if is_less(&v[b], &v[a]) {
        return a;
    }
    b
}