<commit_before>use std::slice;

use super::{Si, Ix, Ixs};
use super::zipsl;

/// Calculate offset from `Ix` stride converting sign properly
#[inline]
pub fn stride_offset(n: Ix, stride: Ix) -> isize
{
    (n as isize) * ((stride as Ixs) as isize)
}

/// Check whether `stride` is strictly positive
#[inline]
pub fn stride_is_positive(stride: Ix) -> bool
{
    (stride as Ixs) > 0
}

/// Return the axis ordering corresponding to the fastest variation
///
/// Assumes that no stride value appears twice. This cannot yield the correct
/// result the strides are not positive.
fn fastest_varying_order<D: Dimension>(strides: &D) -> D
{
    let mut sorted = strides.clone();
    sorted.slice_mut().sort();
    let mut res = strides.clone();
    for (ind, val) in strides.slice().iter().enumerate() {
        // cannot binary search in unsorted...
        let sorted_ind = sorted.slice()
                               .binary_search(val)
                               .expect("should be present");
        res.slice_mut()[sorted_ind] = ind;
    }
    res
}

/// Check whether the given `dim` and `stride` lead to overlapping indices
///
/// There is overlap if, when iterating through the dimensions in the order
/// of maximum variation, the current stride is inferior to the sum of all
/// preceding strides multiplied by their corresponding dimensions.
///
/// The current implementation assumes strides to be positive
pub fn dim_stride_overlap<D: Dimension>(dim: &D, strides: &D) -> bool
{
    let order = fastest_varying_order(strides);

    let mut prev_offset = 1;
    for &ind in order.slice().iter() {
        let s = strides.slice()[ind];
        if (s as isize) < prev_offset {
            return true;
        }
        prev_offset = stride_offset(dim.slice()[ind], s);
    }
    false
}

/// Check whether the given dimension and strides are memory safe
/// to index the provided slice.
///
/// To be safe, no stride may be negative, and the offset corresponding
/// to the last element of each dimension should be smaller than the length
/// of the slice. Also, the strides should not allow a same element to be
/// referenced by two different index.
pub fn can_index_slice<A, D: Dimension>(data: &[A],
                                        dim: &D,
                                        strides: &D
                                       ) -> bool
{
    if strides.slice().iter().cloned().all(stride_is_positive) {
        let mut last_index = dim.clone();
        for mut index in last_index.slice_mut().iter_mut() {
            *index -= 1;
        }
        if let Some(offset) = dim.stride_offset_checked(strides, &last_index) {
            // offset is guaranteed to be positive so no issue converting
            // to usize here
            if (offset as usize) < data.len() {
                return true;
            }
        }
    }
    false
}

/// Trait for the shape and index types of arrays.
///
/// `unsafe` because of the assumptions in the default methods.
///
/// ***Don't implement this trait, it's internal to the crate and will
/// evolve at will.***
pub unsafe trait Dimension : Clone + Eq {
    /// `SliceArg` is the type which is used to specify slicing for this
    /// dimension.
    ///
    /// For the fixed size dimensions (tuples) it is a fixed size array
    /// of the correct size, which you pass by reference. For the `Vec`<commit_msg>integrate overlap check into can_index_slice<commit_after>use std::slice;

use super::{Si, Ix, Ixs};
use super::zipsl;

/// Calculate offset from `Ix` stride converting sign properly
#[inline]
pub fn stride_offset(n: Ix, stride: Ix) -> isize
{
    (n as isize) * ((stride as Ixs) as isize)
}

/// Check whether `stride` is strictly positive
#[inline]
pub fn stride_is_positive(stride: Ix) -> bool
{
    (stride as Ixs) > 0
}

/// Return the axis ordering corresponding to the fastest variation
///
/// Assumes that no stride value appears twice. This cannot yield the correct
/// result the strides are not positive.
fn fastest_varying_order<D: Dimension>(strides: &D) -> D
{
    let mut sorted = strides.clone();
    sorted.slice_mut().sort();
    let mut res = strides.clone();
    for (ind, val) in strides.slice().iter().enumerate() {
        // cannot binary search in unsorted...
        let sorted_ind = sorted.slice()
                               .binary_search(val)
                               .expect("should be present");
        res.slice_mut()[sorted_ind] = ind;
    }
    res
}

/// Check whether the given `dim` and `stride` lead to overlapping indices
///
/// There is overlap if, when iterating through the dimensions in the order
/// of maximum variation, the current stride is inferior to the sum of all
/// preceding strides multiplied by their corresponding dimensions.
///
/// The current implementation assumes strides to be positive
pub fn dim_stride_overlap<D: Dimension>(dim: &D, strides: &D) -> bool
{
    let order = fastest_varying_order(strides);

    let mut prev_offset = 1;
    for &ind in order.slice().iter() {
        let s = strides.slice()[ind];
        if (s as isize) < prev_offset {
            return true;
        }
        prev_offset = stride_offset(dim.slice()[ind], s);
    }
    false
}

/// Check whether the given dimension and strides are memory safe
/// to index the provided slice.
///
/// To be safe, no stride may be negative, and the offset corresponding
/// to the last element of each dimension should be smaller than the length
/// of the slice. Also, the strides should not allow a same element to be
/// referenced by two different index.
pub fn can_index_slice<A, D: Dimension>(data: &[A],
                                        dim: &D,
                                        strides: &D
                                       ) -> bool
{
    if strides.slice().iter().cloned().all(stride_is_positive) {
        let mut last_index = dim.clone();
        for mut index in last_index.slice_mut().iter_mut() {
            *index -= 1;
        }
        if let Some(offset) = dim.stride_offset_checked(strides, &last_index) {
            // offset is guaranteed to be positive so no issue converting
            // to usize here
            if (offset as usize) >= data.len() {
                return false;
            }
            if dim_stride_overlap(dim, strides) {
                return false;
            }
        }
        true
    }
    else {
        false
    }
}

/// Trait for the shape and index types of arrays.
///
/// `unsafe` because of the assumptions in the default methods.
///
/// ***Don't implement this trait, it's internal to the crate and will
/// evolve at will.***
pub unsafe trait Dimension : Clone + Eq {
    /// `SliceArg` is the type which is used to specify slicing for this
    /// dimension.
    ///
    /// For the fixed size dimensions (tuples) it is a fixed size array
    /// of the correct size, which you pass by reference. For the `Vec`
{'fraction_non_alphanumeric': 0.11063031876532525, 'fraction_numerical': 0.0008654262224145391, 'mean_word_length': 2.1633211678832116, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 22, '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': '2308510', 'n_tokens_mistral': 1929, 'n_tokens_neox': 1874, 'n_words': 768}