ndarray_histogram/histogram/

bins.rs

use ndarray::prelude::*;
use std::ops::{Index, Range};

#[cfg(feature = "rayon")]
use rayon::slice::ParallelSliceMut;

/// 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_histogram::{
/// 	histogram::{Bins, Edges},
/// 	o64,
/// };
///
/// let unit_edges = Edges::from(vec![o64(0.), o64(1.)]);
/// let unit_interval = Bins::new(unit_edges);
/// // left-closed
/// assert_eq!(unit_interval.range_of(&o64(0.)).unwrap(), o64(0.)..o64(1.),);
/// // right-open
/// assert_eq!(unit_interval.range_of(&o64(1.)), None);
/// ```
///
/// [`Bins`]: struct.Bins.html
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Edges<A: Ord + Send> {
	edges: Vec<A>,
}

impl<A: Ord + Send> 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_histogram::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
		#[cfg(feature = "rayon")]
		edges.par_sort_unstable();
		#[cfg(not(feature = "rayon"))]
		edges.sort_unstable();
		// remove duplicates
		edges.dedup();
		Edges { edges }
	}
}

impl<A: Ord + Send + 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_histogram::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 + Send> 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_histogram::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 + Send> Edges<A> {
	/// Returns the number of edges in `self`.
	///
	/// # Examples
	///
	/// ```
	/// use ndarray_histogram::{histogram::Edges, o64};
	///
	/// let edges = Edges::from(vec![o64(0.), o64(1.), o64(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_histogram::{O64, histogram::Edges, o64};
	///
	/// let edges = Edges::<O64>::from(vec![]);
	/// assert_eq!(edges.is_empty(), true);
	///
	/// let edges = Edges::from(vec![o64(0.), o64(2.), o64(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_histogram::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]` it returns
	///
	///   - `None`,
	///
	/// else otherwise.
	///
	/// # Examples
	///
	/// ```
	/// use ndarray_histogram::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_histogram::{
/// 	histogram::{Bins, Edges},
/// 	o64,
/// };
///
/// let edges = Edges::from(vec![o64(0.), o64(1.), o64(2.)]);
/// let bins = Bins::new(edges);
/// // first bin
/// assert_eq!(
/// 	bins.index(0),
/// 	o64(0.)..o64(1.) // o64(1.) is not included in the bin!
/// );
/// // second bin
/// assert_eq!(bins.index(1), o64(1.)..o64(2.));
/// ```
#[derive(Clone, Debug, Eq, PartialEq)]
pub struct Bins<A: Ord + Send> {
	edges: Edges<A>,
}

impl<A: Ord + Send> 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_histogram::{
	/// 	histogram::{Bins, Edges},
	/// 	o64,
	/// };
	///
	/// let edges = Edges::from(vec![o64(0.), o64(1.), o64(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_histogram::{
	/// 	O64,
	/// 	histogram::{Bins, Edges},
	/// 	o64,
	/// };
	///
	/// // At least 2 edges is needed to represent 1 interval
	/// let edges = Edges::from(vec![o64(0.), o64(1.), o64(3.)]);
	/// let bins = Bins::new(edges);
	/// assert_eq!(bins.is_empty(), false);
	///
	/// // No valid interval == Empty
	/// let edges = Edges::<O64>::from(vec![]);
	/// let bins = Bins::new(edges);
	/// assert_eq!(bins.is_empty(), true);
	/// let edges = Edges::from(vec![o64(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_histogram::histogram::{Bins, Edges};
	///
	/// 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_histogram::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_histogram::histogram::{Bins, Edges};
	///
	/// 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_histogram::histogram::{Bins, Edges};
	///
	/// 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;

	#[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 = v.iter().collect::<BTreeSet<&i32>>();
		let edges = Edges::from(v.clone());
		let view = edges.as_array_view();
		let unique_edges = view.iter().collect::<BTreeSet<&i32>>();
		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);
	}
}