#![warn(missing_docs, clippy::all, clippy::pedantic)]

use ndarray::prelude::*;

use std::ops::{Index, Range};

/// A sorted collection of type `A` elements used to represent the boundaries of intervals, i.e.

/// [`Bins`] on a 1-dimensional axis.

///

/// **Note** that all intervals are left-closed and right-open. See examples below.

///

/// # Examples

///

/// ```

/// use ndarray_stats::histogram::{Bins, Edges};

/// use noisy_float::types::n64;

///

/// let unit_edges = Edges::from(vec![n64(0.), n64(1.)]);

/// let unit_interval = Bins::new(unit_edges);

/// // left-closed

/// assert_eq!(

///     unit_interval.range_of(&n64(0.)).unwrap(),

///     n64(0.)..n64(1.),

/// );

/// // right-open

/// assert_eq!(

///     unit_interval.range_of(&n64(1.)),

///     None

/// );

/// ```

///

/// [`Bins`]: struct.Bins.html

#[derive(Clone, Debug, Eq, PartialEq)]

pub struct Edges<A: Ord> {

    edges: Vec<A>,

}

impl<A: Ord> From<Vec<A>> for Edges<A> {

    /// Converts a `Vec<A>` into an `Edges<A>`, consuming the edges.

    /// The vector will be sorted in increasing order using an unstable sorting algorithm, with

    /// duplicates removed.

    ///

    /// # Current implementation

    ///

    /// The current sorting algorithm is the same as [`std::slice::sort_unstable()`][sort],

    /// which is based on [pattern-defeating quicksort][pdqsort].

    ///

    /// This sort is unstable (i.e., may reorder equal elements), in-place (i.e., does not allocate)

    /// , and O(n log n) worst-case.

    ///

    /// # Examples

    ///

    /// ```

    /// use ndarray::array;

    /// use ndarray_stats::histogram::Edges;

    ///

    /// let edges = Edges::from(array![1, 15, 10, 10, 20]);

    /// // The array gets sorted!

    /// assert_eq!(

    ///     edges[2],

    ///     15

    /// );

    /// ```

    ///

    /// [sort]: https://doc.rust-lang.org/stable/std/primitive.slice.html#method.sort_unstable

    /// [pdqsort]: https://github.com/orlp/pdqsort

    fn from(mut edges: Vec<A>) -> Self {

        // sort the array in-place

        edges.sort_unstable();

        // remove duplicates

        edges.dedup();

        Edges { edges }

    }

}

impl<A: Ord + Clone> From<Array1<A>> for Edges<A> {

    /// Converts an `Array1<A>` into an `Edges<A>`, consuming the 1-dimensional array.

    /// The array will be sorted in increasing order using an unstable sorting algorithm, with

    /// duplicates removed.

    ///

    /// # Current implementation

    ///

    /// The current sorting algorithm is the same as [`std::slice::sort_unstable()`][sort],

    /// which is based on [pattern-defeating quicksort][pdqsort].

    ///

    /// This sort is unstable (i.e., may reorder equal elements), in-place (i.e., does not allocate)

    /// , and O(n log n) worst-case.

    ///

    /// # Examples

    ///

    /// ```

    /// use ndarray_stats::histogram::Edges;

    ///

    /// let edges = Edges::from(vec![1, 15, 10, 20]);

    /// // The vec gets sorted!

    /// assert_eq!(

    ///     edges[1],

    ///     10

    /// );

    /// ```

    ///

    /// [sort]: https://doc.rust-lang.org/stable/std/primitive.slice.html#method.sort_unstable

    /// [pdqsort]: https://github.com/orlp/pdqsort

    fn from(edges: Array1<A>) -> Self {

        let edges = edges.to_vec();

        Self::from(edges)

    }

}

impl<A: Ord> Index<usize> for Edges<A> {

    type Output = A;

    /// Returns a reference to the `i`-th edge in `self`.

    ///

    /// # Panics

    ///

    /// Panics if the index `i` is out of bounds.

    ///

    /// # Examples

    ///

    /// ```

    /// use ndarray_stats::histogram::Edges;

    ///

    /// let edges = Edges::from(vec![1, 5, 10, 20]);

    /// assert_eq!(

    ///     edges[1],

    ///     5

    /// );

    /// ```

    fn index(&self, i: usize) -> &Self::Output {

        &self.edges[i]

    }

}

impl<A: Ord> Edges<A> {

    /// Returns the number of edges in `self`.

    ///

    /// # Examples

    ///

    /// ```

    /// use ndarray_stats::histogram::Edges;

    /// use noisy_float::types::n64;

    ///

    /// let edges = Edges::from(vec![n64(0.), n64(1.), n64(3.)]);

    /// assert_eq!(

    ///     edges.len(),

    ///     3

    /// );

    /// ```

    #[must_use]

    pub fn len(&self) -> usize {

        self.edges.len()

    }

    /// Returns `true` if `self` contains no edges.

    ///

    /// # Examples

    ///

    /// ```

    /// use ndarray_stats::histogram::Edges;

    /// use noisy_float::types::{N64, n64};

    ///

    /// let edges = Edges::<N64>::from(vec![]);

    /// assert_eq!(edges.is_empty(), true);

    ///

    /// let edges = Edges::from(vec![n64(0.), n64(2.), n64(5.)]);

    /// assert_eq!(edges.is_empty(), false);

    /// ```

    #[must_use]

    pub fn is_empty(&self) -> bool {

        self.edges.is_empty()

    }

    /// Returns an immutable 1-dimensional array view of edges.

    ///

    /// # Examples

    ///

    /// ```

    /// use ndarray::array;

    /// use ndarray_stats::histogram::Edges;

    ///

    /// let edges = Edges::from(vec![0, 5, 3]);

    /// assert_eq!(

    ///     edges.as_array_view(),

    ///     array![0, 3, 5].view()

    /// );

    /// ```

    #[must_use]

    pub fn as_array_view(&self) -> ArrayView1<'_, A> {

        ArrayView1::from(&self.edges)

    }

    /// Returns indices of two consecutive `edges` in `self`, if the interval they represent

    /// contains the given `value`, or returns `None` otherwise.

    ///

    /// That is to say, it returns

    /// - `Some((left, right))`, where `left` and `right` are the indices of two consecutive edges

    /// in `self` and `right == left + 1`, if `self[left] <= value < self[right]`;

    /// - `None`, otherwise.

    ///

    /// # Examples

    ///

    /// ```

    /// use ndarray_stats::histogram::Edges;

    ///

    /// let edges = Edges::from(vec![0, 2, 3]);

    /// // `1` is in the interval [0, 2), whose indices are (0, 1)

    /// assert_eq!(

    ///     edges.indices_of(&1),

    ///     Some((0, 1))

    /// );

    /// // `5` is not in any of intervals

    /// assert_eq!(

    ///     edges.indices_of(&5),

    ///     None

    /// );

    /// ```

    pub fn indices_of(&self, value: &A) -> Option<(usize, usize)> {

        // binary search for the correct bin

        let n_edges = self.len();

        match self.edges.binary_search(value) {

            Ok(i) if i == n_edges - 1 => None,

            Ok(i) => Some((i, i + 1)),

            Err(i) => match i {

                0 => None,

                j if j == n_edges => None,

                j => Some((j - 1, j)),

            },

        }

    }

    /// Returns an iterator over the `edges` in `self`.

    pub fn iter(&self) -> impl Iterator<Item = &A> {

        self.edges.iter()

    }

}

/// A sorted collection of non-overlapping 1-dimensional intervals.

///

/// **Note** that all intervals are left-closed and right-open.

///

/// # Examples

///

/// ```

/// use ndarray_stats::histogram::{Edges, Bins};

/// use noisy_float::types::n64;

///

/// let edges = Edges::from(vec![n64(0.), n64(1.), n64(2.)]);

/// let bins = Bins::new(edges);

/// // first bin

/// assert_eq!(

///     bins.index(0),

///     n64(0.)..n64(1.) // n64(1.) is not included in the bin!

/// );

/// // second bin

/// assert_eq!(

///     bins.index(1),

///     n64(1.)..n64(2.)

/// );

/// ```

#[derive(Clone, Debug, Eq, PartialEq)]

pub struct Bins<A: Ord> {

    edges: Edges<A>,

}

impl<A: Ord> Bins<A> {

    /// Returns a `Bins` instance where each bin corresponds to two consecutive members of the given

    /// [`Edges`], consuming the edges.

    ///

    /// [`Edges`]: struct.Edges.html

    #[must_use]

    pub fn new(edges: Edges<A>) -> Self {

        Bins { edges }

    }

    /// Returns the number of bins in `self`.

    ///

    /// # Examples

    ///

    /// ```

    /// use ndarray_stats::histogram::{Edges, Bins};

    /// use noisy_float::types::n64;

    ///

    /// let edges = Edges::from(vec![n64(0.), n64(1.), n64(2.)]);

    /// let bins = Bins::new(edges);

    /// assert_eq!(

    ///     bins.len(),

    ///     2

    /// );

    /// ```

    #[must_use]

    pub fn len(&self) -> usize {

        match self.edges.len() {

            0 => 0,

            n => n - 1,

        }

    }

    /// Returns `true` if the number of bins is zero, i.e. if the number of edges is 0 or 1.

    ///

    /// # Examples

    ///

    /// ```

    /// use ndarray_stats::histogram::{Edges, Bins};

    /// use noisy_float::types::{N64, n64};

    ///

    /// // At least 2 edges is needed to represent 1 interval

    /// let edges = Edges::from(vec![n64(0.), n64(1.), n64(3.)]);

    /// let bins = Bins::new(edges);

    /// assert_eq!(bins.is_empty(), false);

    ///

    /// // No valid interval == Empty

    /// let edges = Edges::<N64>::from(vec![]);

    /// let bins = Bins::new(edges);

    /// assert_eq!(bins.is_empty(), true);

    /// let edges = Edges::from(vec![n64(0.)]);

    /// let bins = Bins::new(edges);

    /// assert_eq!(bins.is_empty(), true);

    /// ```

    #[must_use]

    pub fn is_empty(&self) -> bool {

        self.len() == 0

    }

    /// Returns the index of the bin in `self` that contains the given `value`,

    /// or returns `None` if `value` does not belong to any bins in `self`.

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// use ndarray_stats::histogram::{Edges, Bins};

    ///

    /// let edges = Edges::from(vec![0, 2, 4, 6]);

    /// let bins = Bins::new(edges);

    /// let value = 1;

    /// // The first bin [0, 2) contains `1`

    /// assert_eq!(

    ///     bins.index_of(&1),

    ///     Some(0)

    /// );

    /// // No bin contains 100

    /// assert_eq!(

    ///     bins.index_of(&100),

    ///     None

    /// )

    /// ```

    ///

    /// Chaining [`Bins::index`] and [`Bins::index_of`] to get the boundaries of the bin containing

    /// the value:

    ///

    /// ```

    /// # use ndarray_stats::histogram::{Edges, Bins};

    /// # let edges = Edges::from(vec![0, 2, 4, 6]);

    /// # let bins = Bins::new(edges);

    /// # let value = 1;

    /// assert_eq!(

    ///     // using `Option::map` to avoid panic on index out-of-bounds

    ///     bins.index_of(&1).map(|i| bins.index(i)),

    ///     Some(0..2)

    /// );

    /// ```

    pub fn index_of(&self, value: &A) -> Option<usize> {

        self.edges.indices_of(value).map(|t| t.0)

    }

    /// Returns a range as the bin which contains the given `value`, or returns `None` otherwise.

    ///

    /// # Examples

    ///

    /// ```

    /// use ndarray_stats::histogram::{Edges, Bins};

    ///

    /// let edges = Edges::from(vec![0, 2, 4, 6]);

    /// let bins = Bins::new(edges);

    /// // [0, 2) contains `1`

    /// assert_eq!(

    ///     bins.range_of(&1),

    ///     Some(0..2)

    /// );

    /// // `10` is not in any interval

    /// assert_eq!(

    ///     bins.range_of(&10),

    ///     None

    /// );

    /// ```

    pub fn range_of(&self, value: &A) -> Option<Range<A>>

    where

        A: Clone,

    {

        let edges_indexes = self.edges.indices_of(value);

        edges_indexes.map(|(left, right)| Range {

            start: self.edges[left].clone(),

            end: self.edges[right].clone(),

        })

    }

    /// Returns a range as the bin at the given `index` position.

    ///

    /// # Panics

    ///

    /// Panics if `index` is out of bounds.

    ///

    /// # Examples

    ///

    /// ```

    /// use ndarray_stats::histogram::{Edges, Bins};

    ///

    /// let edges = Edges::from(vec![1, 5, 10, 20]);

    /// let bins = Bins::new(edges);

    /// assert_eq!(

    ///     bins.index(1),

    ///     5..10

    /// );

    /// ```

    #[must_use]

    pub fn index(&self, index: usize) -> Range<A>

    where

        A: Clone,

    {

        // It was not possible to implement this functionality

        // using the `Index` trait unless we were willing to

        // allocate a `Vec<Range<A>>` in the struct.

        // Index, in fact, forces you to return a reference.

        Range {

            start: self.edges[index].clone(),

            end: self.edges[index + 1].clone(),

        }

    }

}

#[cfg(test)]

mod edges_tests {

    use super::{Array1, Edges};

    use quickcheck_macros::quickcheck;

    use std::collections::BTreeSet;

    use std::iter::FromIterator;

    #[quickcheck]

    fn check_sorted_from_vec(v: Vec<i32>) -> bool {

        let edges = Edges::from(v);

        let n = edges.len();

        for i in 1..n {

            if edges[i - 1] > edges[i] {

                return false;

            }

        }

        true

    }

    #[quickcheck]

    fn check_sorted_from_array(v: Vec<i32>) -> bool {

        let a = Array1::from(v);

        let edges = Edges::from(a);

        let n = edges.len();

        for i in 1..n {

            if edges[i - 1] > edges[i] {

                return false;

            }

        }

        true

    }

    #[quickcheck]

    fn edges_are_right_open(v: Vec<i32>) -> bool {

        let edges = Edges::from(v);

        let view = edges.as_array_view();

        if view.is_empty() {

            true

        } else {

            let last = view[view.len() - 1];

            edges.indices_of(&last).is_none()

        }

    }

    #[quickcheck]

    fn edges_are_left_closed(v: Vec<i32>) -> bool {

        let edges = Edges::from(v);

        if let 1 = edges.len() {

            true

        } else {

            let view = edges.as_array_view();

            if view.is_empty() {

                true

            } else {

                let first = view[0];

                edges.indices_of(&first).is_some()

            }

        }

    }

    #[quickcheck]

    #[allow(clippy::needless_pass_by_value)]

    fn edges_are_deduped(v: Vec<i32>) -> bool {

        let unique_elements = BTreeSet::from_iter(v.iter());

        let edges = Edges::from(v.clone());

        let view = edges.as_array_view();

        let unique_edges = BTreeSet::from_iter(view.iter());

        unique_edges == unique_elements

    }

}

#[cfg(test)]

mod bins_tests {

    use super::{Bins, Edges};

    #[test]

    #[should_panic]

    #[allow(unused_must_use)]

    fn get_panics_for_out_of_bounds_indexes() {

        let edges = Edges::from(vec![0]);

        let bins = Bins::new(edges);

        // we need at least two edges to make a valid bin!

        bins.index(0);

    }

}