alphanumeric_sort/

std_functions.rs

use core::cmp::Ordering;
use std::{
    ffi::{CStr, OsStr},
    path::Path,
};

use crate::compare_str;

/// Compare two `OsStr`.
///
/// The alphanumeric algorithm is used only when both values can be converted to UTF-8
/// with `OsStr::to_str`. If either value cannot be converted, this falls back to the
/// native `OsStr` ordering.
#[inline]
pub fn compare_os_str<A: AsRef<OsStr>, B: AsRef<OsStr>>(a: A, b: B) -> Ordering {
    let sa = match a.as_ref().to_str() {
        Some(s) => s,
        None => {
            return compare_os_str_fallback(a, b);
        },
    };

    let sb = match b.as_ref().to_str() {
        Some(s) => s,
        None => {
            return compare_os_str_fallback(a, b);
        },
    };

    compare_str(sa, sb)
}

#[inline]
fn compare_os_str_fallback<A: AsRef<OsStr>, B: AsRef<OsStr>>(a: A, b: B) -> Ordering {
    a.as_ref().cmp(b.as_ref())
}

/// Compare two `CStr`.
///
/// The alphanumeric algorithm is used only when both values can be converted to UTF-8
/// with `CStr::to_str`. If either value cannot be converted, this falls back to the
/// native `CStr` ordering.
#[inline]
pub fn compare_c_str<A: AsRef<CStr>, B: AsRef<CStr>>(a: A, b: B) -> Ordering {
    let sa = match a.as_ref().to_str() {
        Ok(s) => s,
        Err(_) => {
            return compare_c_str_fallback(a, b);
        },
    };

    let sb = match b.as_ref().to_str() {
        Ok(s) => s,
        Err(_) => {
            return compare_c_str_fallback(a, b);
        },
    };

    compare_str(sa, sb)
}

#[inline]
fn compare_c_str_fallback<A: AsRef<CStr>, B: AsRef<CStr>>(a: A, b: B) -> Ordering {
    a.as_ref().cmp(b.as_ref())
}

/// Compare two `Path`.
///
/// The alphanumeric algorithm is used only when both paths can be converted to UTF-8
/// through their `OsStr` representations. If either path cannot be converted, this
/// falls back to the native `OsStr` ordering.
#[inline]
pub fn compare_path<A: AsRef<Path>, B: AsRef<Path>>(a: A, b: B) -> Ordering {
    compare_os_str(a.as_ref(), b.as_ref())
}

/// Sort a slice by an `OsStr` key, but may not preserve the order of equal elements.
///
/// The alphanumeric algorithm is used only if every key can be converted to UTF-8.
/// If any key cannot be converted, the whole slice is sorted by native `OsStr` key
/// ordering.
#[inline]
pub fn sort_slice_unstable_by_os_str_key<A, T: ?Sized + AsRef<OsStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    f: F,
) {
    sort_slice_by_os_str_key_inner(
        slice,
        f,
        ref_index_str_pairs_to_ref_indexes_unstable,
        sort_slice_unstable_by_os_str_key_fallback,
    )
}

/// Sort a slice by an `OsStr` key.
///
/// The alphanumeric algorithm is used only if every key can be converted to UTF-8.
/// If any key cannot be converted, the whole slice is sorted by native `OsStr` key
/// ordering.
#[inline]
pub fn sort_slice_by_os_str_key<A, T: ?Sized + AsRef<OsStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    f: F,
) {
    sort_slice_by_os_str_key_inner(
        slice,
        f,
        ref_index_str_pairs_to_ref_indexes,
        sort_slice_by_os_str_key_fallback,
    )
}

/// Reversely sort a slice by an `OsStr` key, but may not preserve the order of equal elements.
///
/// The alphanumeric algorithm is used only if every key can be converted to UTF-8.
/// If any key cannot be converted, the whole slice is sorted by native `OsStr` key
/// ordering.
#[inline]
pub fn sort_slice_rev_unstable_by_os_str_key<A, T: ?Sized + AsRef<OsStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    f: F,
) {
    sort_slice_by_os_str_key_inner(
        slice,
        f,
        ref_index_str_pairs_to_ref_indexes_rev_unstable,
        sort_slice_rev_unstable_by_os_str_key_fallback,
    )
}

/// Reversely sort a slice by an `OsStr` key.
///
/// The alphanumeric algorithm is used only if every key can be converted to UTF-8.
/// If any key cannot be converted, the whole slice is sorted by native `OsStr` key
/// ordering.
#[inline]
pub fn sort_slice_rev_by_os_str_key<A, T: ?Sized + AsRef<OsStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    f: F,
) {
    sort_slice_by_os_str_key_inner(
        slice,
        f,
        ref_index_str_pairs_to_ref_indexes_rev,
        sort_slice_rev_by_os_str_key_fallback,
    )
}

fn sort_slice_by_os_str_key_inner<A, T: ?Sized + AsRef<OsStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
    ref_index_str_pairs_to_ref_indexes: impl Fn(Vec<(usize, &str)>) -> Vec<usize>,
    fallback: impl Fn(&mut [A], F),
) {
    let mut use_str = true;

    let mut ref_index_str_pairs = Vec::with_capacity(slice.len());

    for (i, p) in slice.iter().enumerate() {
        let s = match f(p).as_ref().to_str() {
            Some(s) => s,
            None => {
                use_str = false;
                break;
            },
        };

        ref_index_str_pairs.push((i, s));
    }

    if use_str {
        let ref_indexes = ref_index_str_pairs_to_ref_indexes(ref_index_str_pairs);

        sort_slice_ref_indexes(slice, ref_indexes);
    } else {
        fallback(slice, f);
    }
}

#[inline]
fn sort_slice_unstable_by_os_str_key_fallback<A, T: ?Sized + AsRef<OsStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
) {
    slice.sort_unstable_by(|a, b| compare_os_str_fallback(f(a), f(b)));
}

#[inline]
fn sort_slice_by_os_str_key_fallback<A, T: ?Sized + AsRef<OsStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
) {
    slice.sort_by(|a, b| compare_os_str_fallback(f(a), f(b)));
}

#[inline]
fn sort_slice_rev_unstable_by_os_str_key_fallback<
    A,
    T: ?Sized + AsRef<OsStr>,
    F: FnMut(&A) -> &T,
>(
    slice: &mut [A],
    mut f: F,
) {
    slice.sort_unstable_by(|a, b| compare_os_str_fallback(f(b), f(a)));
}

#[inline]
fn sort_slice_rev_by_os_str_key_fallback<A, T: ?Sized + AsRef<OsStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
) {
    slice.sort_by(|a, b| compare_os_str_fallback(f(b), f(a)));
}

/// Sort a slice by a `CStr` key, but may not preserve the order of equal elements.
///
/// The alphanumeric algorithm is used only if every key can be converted to UTF-8.
/// If any key cannot be converted, the whole slice is sorted by native `CStr` key
/// ordering.
#[inline]
pub fn sort_slice_unstable_by_c_str_key<A, T: ?Sized + AsRef<CStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    f: F,
) {
    sort_slice_by_c_str_key_inner(
        slice,
        f,
        ref_index_str_pairs_to_ref_indexes_unstable,
        sort_slice_unstable_by_c_str_key_fallback,
    )
}

/// Sort a slice by a `CStr` key.
///
/// The alphanumeric algorithm is used only if every key can be converted to UTF-8.
/// If any key cannot be converted, the whole slice is sorted by native `CStr` key
/// ordering.
#[inline]
pub fn sort_slice_by_c_str_key<A, T: ?Sized + AsRef<CStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    f: F,
) {
    sort_slice_by_c_str_key_inner(
        slice,
        f,
        ref_index_str_pairs_to_ref_indexes,
        sort_slice_by_c_str_key_fallback,
    )
}

/// Reversely sort a slice by a `CStr` key, but may not preserve the order of equal elements.
///
/// The alphanumeric algorithm is used only if every key can be converted to UTF-8.
/// If any key cannot be converted, the whole slice is sorted by native `CStr` key
/// ordering.
#[inline]
pub fn sort_slice_rev_unstable_by_c_str_key<A, T: ?Sized + AsRef<CStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    f: F,
) {
    sort_slice_by_c_str_key_inner(
        slice,
        f,
        ref_index_str_pairs_to_ref_indexes_rev_unstable,
        sort_slice_rev_unstable_by_c_str_key_fallback,
    )
}

/// Reversely sort a slice by a `CStr` key.
///
/// The alphanumeric algorithm is used only if every key can be converted to UTF-8.
/// If any key cannot be converted, the whole slice is sorted by native `CStr` key
/// ordering.
#[inline]
pub fn sort_slice_rev_by_c_str_key<A, T: ?Sized + AsRef<CStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    f: F,
) {
    sort_slice_by_c_str_key_inner(
        slice,
        f,
        ref_index_str_pairs_to_ref_indexes_rev,
        sort_slice_rev_by_c_str_key_fallback,
    )
}

fn sort_slice_by_c_str_key_inner<A, T: ?Sized + AsRef<CStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
    ref_index_str_pairs_to_ref_indexes: impl Fn(Vec<(usize, &str)>) -> Vec<usize>,
    fallback: impl Fn(&mut [A], F),
) {
    let mut use_str = true;

    let mut ref_index_str_pairs = Vec::with_capacity(slice.len());

    for (i, p) in slice.iter().enumerate() {
        let s = match f(p).as_ref().to_str() {
            Ok(s) => s,
            Err(_) => {
                use_str = false;
                break;
            },
        };

        ref_index_str_pairs.push((i, s));
    }

    if use_str {
        let ref_indexes = ref_index_str_pairs_to_ref_indexes(ref_index_str_pairs);

        sort_slice_ref_indexes(slice, ref_indexes);
    } else {
        fallback(slice, f);
    }
}

#[inline]
fn sort_slice_unstable_by_c_str_key_fallback<A, T: ?Sized + AsRef<CStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
) {
    slice.sort_unstable_by(|a, b| compare_c_str_fallback(f(a), f(b)));
}

#[inline]
fn sort_slice_by_c_str_key_fallback<A, T: ?Sized + AsRef<CStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
) {
    slice.sort_by(|a, b| compare_c_str_fallback(f(a), f(b)));
}

#[inline]
fn sort_slice_rev_unstable_by_c_str_key_fallback<A, T: ?Sized + AsRef<CStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
) {
    slice.sort_unstable_by(|a, b| compare_c_str_fallback(f(b), f(a)));
}

#[inline]
fn sort_slice_rev_by_c_str_key_fallback<A, T: ?Sized + AsRef<CStr>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
) {
    slice.sort_by(|a, b| compare_c_str_fallback(f(b), f(a)));
}

/// Sort a slice by a `Path` key, but may not preserve the order of equal elements.
///
/// The alphanumeric algorithm is used only if every key can be converted to UTF-8
/// through its `OsStr` representation. If any key cannot be converted, the whole
/// slice is sorted by native `OsStr` key ordering.
#[inline]
pub fn sort_slice_unstable_by_path_key<A, T: ?Sized + AsRef<Path>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    f: F,
) {
    sort_slice_by_path_key_inner(
        slice,
        f,
        ref_index_str_pairs_to_ref_indexes_unstable,
        sort_slice_unstable_by_path_key_fallback,
    )
}

/// Sort a slice by a `Path` key.
///
/// The alphanumeric algorithm is used only if every key can be converted to UTF-8
/// through its `OsStr` representation. If any key cannot be converted, the whole
/// slice is sorted by native `OsStr` key ordering.
#[inline]
pub fn sort_slice_by_path_key<A, T: ?Sized + AsRef<Path>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    f: F,
) {
    sort_slice_by_path_key_inner(
        slice,
        f,
        ref_index_str_pairs_to_ref_indexes,
        sort_slice_by_path_key_fallback,
    )
}

/// Reversely sort a slice by a `Path` key, but may not preserve the order of equal elements.
///
/// The alphanumeric algorithm is used only if every key can be converted to UTF-8
/// through its `OsStr` representation. If any key cannot be converted, the whole
/// slice is sorted by native `OsStr` key ordering.
#[inline]
pub fn sort_slice_rev_unstable_by_path_key<A, T: ?Sized + AsRef<Path>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    f: F,
) {
    sort_slice_by_path_key_inner(
        slice,
        f,
        ref_index_str_pairs_to_ref_indexes_rev_unstable,
        sort_slice_rev_unstable_by_path_key_fallback,
    )
}

/// Reversely sort a slice by a `Path` key.
///
/// The alphanumeric algorithm is used only if every key can be converted to UTF-8
/// through its `OsStr` representation. If any key cannot be converted, the whole
/// slice is sorted by native `OsStr` key ordering.
#[inline]
pub fn sort_slice_rev_by_path_key<A, T: ?Sized + AsRef<Path>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    f: F,
) {
    sort_slice_by_path_key_inner(
        slice,
        f,
        ref_index_str_pairs_to_ref_indexes_rev,
        sort_slice_rev_by_path_key_fallback,
    )
}

fn sort_slice_by_path_key_inner<A, T: ?Sized + AsRef<Path>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
    ref_index_str_pairs_to_ref_indexes: impl Fn(Vec<(usize, &str)>) -> Vec<usize>,
    fallback: impl Fn(&mut [A], F),
) {
    let mut use_str = true;

    let mut ref_index_str_pairs = Vec::with_capacity(slice.len());

    for (i, p) in slice.iter().enumerate() {
        let s = match f(p).as_ref().to_str() {
            Some(s) => s,
            None => {
                use_str = false;
                break;
            },
        };

        ref_index_str_pairs.push((i, s));
    }

    if use_str {
        let ref_indexes = ref_index_str_pairs_to_ref_indexes(ref_index_str_pairs);

        sort_slice_ref_indexes(slice, ref_indexes);
    } else {
        fallback(slice, f);
    }
}

#[inline]
fn sort_slice_unstable_by_path_key_fallback<A, T: ?Sized + AsRef<Path>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
) {
    slice.sort_unstable_by(|a, b| {
        compare_os_str_fallback(f(a).as_ref().as_os_str(), f(b).as_ref().as_os_str())
    });
}

#[inline]
fn sort_slice_by_path_key_fallback<A, T: ?Sized + AsRef<Path>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
) {
    slice.sort_by(|a, b| {
        compare_os_str_fallback(f(a).as_ref().as_os_str(), f(b).as_ref().as_os_str())
    });
}

#[inline]
fn sort_slice_rev_unstable_by_path_key_fallback<A, T: ?Sized + AsRef<Path>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
) {
    slice.sort_unstable_by(|a, b| {
        compare_os_str_fallback(f(b).as_ref().as_os_str(), f(a).as_ref().as_os_str())
    });
}

#[inline]
fn sort_slice_rev_by_path_key_fallback<A, T: ?Sized + AsRef<Path>, F: FnMut(&A) -> &T>(
    slice: &mut [A],
    mut f: F,
) {
    slice.sort_by(|a, b| {
        compare_os_str_fallback(f(b).as_ref().as_os_str(), f(a).as_ref().as_os_str())
    });
}

// Direct std slice sorting

/// Sort an `OsStr` slice.
///
/// The alphanumeric algorithm is used only if every item can be converted to UTF-8.
/// If any item cannot be converted, the whole slice is sorted by native `OsStr`
/// ordering.
#[inline]
pub fn sort_os_str_slice<S: AsRef<OsStr>>(slice: &mut [S]) {
    sort_slice_unstable_by_os_str_key(slice, |e| e.as_ref())
}

/// Reversely sort an `OsStr` slice.
///
/// The alphanumeric algorithm is used only if every item can be converted to UTF-8.
/// If any item cannot be converted, the whole slice is sorted by native `OsStr`
/// ordering.
#[inline]
pub fn sort_os_str_slice_rev<S: AsRef<OsStr>>(slice: &mut [S]) {
    sort_slice_rev_unstable_by_os_str_key(slice, |e| e.as_ref())
}

/// Sort a `CStr` slice.
///
/// The alphanumeric algorithm is used only if every item can be converted to UTF-8.
/// If any item cannot be converted, the whole slice is sorted by native `CStr`
/// ordering.
#[inline]
pub fn sort_c_str_slice<S: AsRef<CStr>>(slice: &mut [S]) {
    sort_slice_unstable_by_c_str_key(slice, |e| e.as_ref())
}

/// Reversely sort a `CStr` slice.
///
/// The alphanumeric algorithm is used only if every item can be converted to UTF-8.
/// If any item cannot be converted, the whole slice is sorted by native `CStr`
/// ordering.
#[inline]
pub fn sort_c_str_slice_rev<S: AsRef<CStr>>(slice: &mut [S]) {
    sort_slice_rev_unstable_by_c_str_key(slice, |e| e.as_ref())
}

/// Sort a `Path` slice.
///
/// The alphanumeric algorithm is used only if every item can be converted to UTF-8
/// through its `OsStr` representation. If any item cannot be converted, the whole
/// slice is sorted by native `OsStr` ordering.
#[inline]
pub fn sort_path_slice<P: AsRef<Path>>(slice: &mut [P]) {
    sort_slice_unstable_by_path_key(slice, |e| e.as_ref())
}

/// Reversely sort a `Path` slice.
///
/// The alphanumeric algorithm is used only if every item can be converted to UTF-8
/// through its `OsStr` representation. If any item cannot be converted, the whole
/// slice is sorted by native `OsStr` ordering.
#[inline]
pub fn sort_path_slice_rev<P: AsRef<Path>>(slice: &mut [P]) {
    sort_slice_rev_unstable_by_path_key(slice, |e| e.as_ref())
}

// Permutation helpers

#[inline]
fn ref_index_str_pairs_to_ref_indexes_unstable(
    mut ref_index_str_pairs: Vec<(usize, &str)>,
) -> Vec<usize> {
    ref_index_str_pairs.sort_unstable_by(|a, b| compare_str(a.1, b.1));

    ref_index_str_pairs_to_ref_indexes_inner(ref_index_str_pairs)
}

#[inline]
fn ref_index_str_pairs_to_ref_indexes(mut ref_index_str_pairs: Vec<(usize, &str)>) -> Vec<usize> {
    ref_index_str_pairs.sort_by(|a, b| compare_str(a.1, b.1));

    ref_index_str_pairs_to_ref_indexes_inner(ref_index_str_pairs)
}

#[inline]
fn ref_index_str_pairs_to_ref_indexes_rev_unstable(
    mut ref_index_str_pairs: Vec<(usize, &str)>,
) -> Vec<usize> {
    ref_index_str_pairs.sort_unstable_by(|a, b| compare_str(b.1, a.1));

    ref_index_str_pairs_to_ref_indexes_inner(ref_index_str_pairs)
}

#[inline]
fn ref_index_str_pairs_to_ref_indexes_rev(
    mut ref_index_str_pairs: Vec<(usize, &str)>,
) -> Vec<usize> {
    ref_index_str_pairs.sort_by(|a, b| compare_str(b.1, a.1));

    ref_index_str_pairs_to_ref_indexes_inner(ref_index_str_pairs)
}

#[inline]
fn ref_index_str_pairs_to_ref_indexes_inner(ref_index_str_pairs: Vec<(usize, &str)>) -> Vec<usize> {
    ref_index_str_pairs.into_iter().map(|(i, _)| i).collect()
}

#[inline]
fn sort_slice_ref_indexes<S>(slice: &mut [S], mut permutation: Vec<usize>) {
    // Cycle Decomposition
    for i in 0..permutation.len() {
        let mut current = i;

        while permutation[current] != i {
            let next = permutation[current];

            slice.swap(current, next);

            permutation[current] = current;
            current = next;
        }

        permutation[current] = current;
    }
}