//! Provides functionality to get `n` items from a `&mut [T]`.
//!
//! This library can provide significant performance increase compared to sorting the whole list
//! when `n` is relatively small.
//!
//! ```text
//! N = 100, LEN = 1_000_000, RANGE = 1_000_000:
//! test max           ... bench:   1,000,216 ns/iter (+/- 41,060)
//! test max_unstable  ... bench:     997,303 ns/iter (+/- 36,817)
//! test sort          ... bench:  61,034,315 ns/iter (+/- 1,042,745)
//! test sort_unstable ... bench:  30,451,385 ns/iter (+/- 289,475)
//! ```

#![cfg_attr(not(feature = "use_std"), no_std)]
#![doc(html_root_url = "https://docs.rs/out/0.5.4")]
#![deny(
    bad_style,
    bare_trait_objects,
    missing_debug_implementations,
    missing_docs,
    unused_import_braces,
    unused_qualifications
)]

#[cfg(not(feature = "use_std"))]
use core::cmp::Ordering;
#[cfg(not(feature = "use_std"))]
use core::mem;
#[cfg(not(feature = "use_std"))]
use core::slice;
#[cfg(feature = "use_std")]
use std::cmp::Ordering;
#[cfg(feature = "use_std")]
use std::mem;
#[cfg(feature = "use_std")]
use std::slice;

/// Get the `n` largest items.
///
/// # Examples
/// ```
/// let mut v = [-5, 4, 1, -3, 2];
/// let max = out::max(&mut v, 3);
/// assert_eq!(max, [1, 2, 4]);
/// ```
#[inline]
#[cfg(feature = "use_std")]
pub fn max<T: Ord>(v: &mut [T], n: usize) -> &mut [T] {
    max_by(v, n, |a, b| a.cmp(b))
}

/// Get the `n` largest items.
///
/// # Examples
/// ```
/// let mut v = [-5, 4, 1, -3, 2];
/// let max = out::max_unstable(&mut v, 3);
/// assert_eq!(max, [1, 2, 4]);
/// ```
#[inline]
pub fn max_unstable<T: Ord>(v: &mut [T], n: usize) -> &mut [T] {
    max_unstable_by(v, n, |a, b| a.cmp(b))
}

/// Get the `n` largest items.
///
/// # Examples
/// ```
/// let mut v = [-5, 4, 1, -3, 2];
/// let min = out::max_by(&mut v, 3, |a, b| b.cmp(a));
/// assert_eq!(min, [1, -3, -5]);
/// ```
#[inline]
#[cfg(feature = "use_std")]
pub fn max_by<T>(v: &mut [T], n: usize, mut f: impl FnMut(&T, &T) -> Ordering) -> &mut [T] {
    if n == 0 {
        return &mut [];
    }
    let (mut max, mut v) = v.split_at_mut(n);
    max.sort_by(&mut f);
    let mut i = 0;
    while i < v.len() {
        if f(&v[i], &max[0]) != Ordering::Greater {
            i += 1;
        } else if f(&v[i], &max[n - 1]) != Ordering::Less && i < v.len() - 1 {
            v.swap(i, 0);
            unsafe {
                shift_slice_right(&mut max, &mut v, 1);
            }
        } else if f(&v[i], &max[n / 2]) == Ordering::Greater && i < v.len() - 1 {
            v.swap(i, 0);
            let mut j = n - 1;
            mem::swap(&mut max[j], &mut v[0]);
            while j > 0 && f(&max[j], &max[j - 1]) != Ordering::Greater {
                max.swap(j, j - 1);
                j -= 1;
            }
            unsafe {
                shift_slice_right(&mut max, &mut v, 1);
            }
        } else {
            let mut j = 0;
            mem::swap(&mut v[i], &mut max[j]);
            while j < n - 1 && f(&max[j], &max[j + 1]) == Ordering::Greater {
                max.swap(j, j + 1);
                j += 1;
            }
            i += 1;
        }
    }
    max
}

/// Get the `n` largest items.
///
/// # Examples
/// ```
/// let mut v = [-5, 4, 1, -3, 2];
/// let min = out::max_unstable_by(&mut v, 3, |a, b| b.cmp(a));
/// assert_eq!(min, [1, -3, -5]);
/// ```
#[inline]
pub fn max_unstable_by<T>(
    v: &mut [T],
    n: usize,
    mut f: impl FnMut(&T, &T) -> Ordering,
) -> &mut [T] {
    if n == 0 {
        return &mut [];
    }
    let (mut max, mut v) = v.split_at_mut(n);
    max.sort_unstable_by(&mut f);
    let mut i = 0;
    while i < v.len() {
        if f(&v[i], &max[0]) != Ordering::Greater {
            i += 1;
        } else if f(&v[i], &max[n - 1]) != Ordering::Less && i < v.len() - 1 {
            v.swap(i, 0);
            unsafe {
                shift_slice_right(&mut max, &mut v, 1);
            }
        } else if f(&v[i], &max[n / 2]) == Ordering::Greater && i < v.len() - 1 {
            v.swap(i, 0);
            let mut j = n - 1;
            mem::swap(&mut max[j], &mut v[0]);
            while j > 0 && f(&max[j], &max[j - 1]) == Ordering::Less {
                max.swap(j, j - 1);
                j -= 1;
            }
            unsafe {
                shift_slice_right(&mut max, &mut v, 1);
            }
        } else {
            let mut j = 0;
            mem::swap(&mut v[i], &mut max[j]);
            while j < n - 1 && f(&max[j], &max[j + 1]) == Ordering::Greater {
                max.swap(j, j + 1);
                j += 1;
            }
            i += 1;
        }
    }
    max
}

/// Get the `n` largest items decided by a key generated by `f`.
///
/// # Examples
/// ```
/// let mut v = [-5_i32, 4, 1, -3, 2];
/// let max = out::max_by_key(&mut v, 3, |a| a.abs());
/// assert_eq!(max, [-3, 4, -5]);
/// ```
#[inline]
#[cfg(feature = "use_std")]
pub fn max_by_key<T, K: Ord>(v: &mut [T], n: usize, mut f: impl FnMut(&T) -> K) -> &mut [T] {
    max_by(v, n, |a, b| f(a).cmp(&f(b)))
}

/// Get the `n` largest items decided by a key generated by `f`.
///
/// # Examples
/// ```
/// let mut v = [-5_i32, 4, 1, -3, 2];
/// let max = out::max_unstable_by_key(&mut v, 3, |a| a.abs());
/// assert_eq!(max, [-3, 4, -5]);
/// ```
#[inline]
pub fn max_unstable_by_key<T, K: Ord>(
    v: &mut [T],
    n: usize,
    mut f: impl FnMut(&T) -> K,
) -> &mut [T] {
    max_unstable_by(v, n, |a, b| f(a).cmp(&f(b)))
}

#[inline]
unsafe fn shift_slice_right<T>(left: &mut &mut [T], right: &mut &mut [T], count: usize) {
    let len = left.len();
    let ptr = left.as_mut_ptr();
    *left = slice::from_raw_parts_mut(ptr.add(count), len);
    let len = right.len();
    let ptr = right.as_mut_ptr();
    *right = slice::from_raw_parts_mut(ptr.add(count), len - count);
}