ndarray_stats/histogram/grid.rs
1#![warn(missing_docs, clippy::all, clippy::pedantic)]
2
3use super::{bins::Bins, errors::BinsBuildError, strategies::BinsBuildingStrategy};
4use itertools::izip;
5use ndarray::{ArrayRef, Axis, Ix1, Ix2};
6use std::ops::Range;
7
8/// An orthogonal partition of a rectangular region in an *n*-dimensional space, e.g.
9/// [*a*<sub>0</sub>, *b*<sub>0</sub>) × ⋯ × [*a*<sub>*n*−1</sub>, *b*<sub>*n*−1</sub>),
10/// represented as a collection of rectangular *n*-dimensional bins.
11///
12/// The grid is **solely determined by the Cartesian product of its projections** on each coordinate
13/// axis. Therefore, each element in the product set should correspond to a sub-region in the grid.
14///
15/// For example, this partition can be represented as a `Grid` struct:
16///
17/// ```text
18///
19/// g +---+-------+---+
20/// | 3 | 4 | 5 |
21/// f +---+-------+---+
22/// | | | |
23/// | 0 | 1 | 2 |
24/// | | | |
25/// e +---+-------+---+
26/// a b c d
27///
28/// R0: [a, b) × [e, f)
29/// R1: [b, c) × [e, f)
30/// R2: [c, d) × [e, f)
31/// R3: [a, b) × [f, g)
32/// R4: [b, d) × [f, g)
33/// R5: [c, d) × [f, g)
34/// Grid: { [a, b), [b, c), [c, d) } × { [e, f), [f, g) } == { R0, R1, R2, R3, R4, R5 }
35/// ```
36///
37/// while the next one can't:
38///
39/// ```text
40/// g +---+-----+---+
41/// | | 2 | 3 |
42/// (f) | +-----+---+
43/// | 0 | |
44/// | | 1 |
45/// | | |
46/// e +---+-----+---+
47/// a b c d
48///
49/// R0: [a, b) × [e, g)
50/// R1: [b, d) × [e, f)
51/// R2: [b, c) × [f, g)
52/// R3: [c, d) × [f, g)
53/// // 'f', as long as 'R1', 'R2', or 'R3', doesn't appear on LHS
54/// // [b, c) × [e, g), [c, d) × [e, g) doesn't appear on RHS
55/// Grid: { [a, b), [b, c), [c, d) } × { [e, g) } != { R0, R1, R2, R3 }
56/// ```
57///
58/// # Examples
59///
60/// Basic usage, building a `Grid` via [`GridBuilder`], with optimal grid layout determined by
61/// a given [`strategy`], and generating a [`histogram`]:
62///
63/// ```
64/// use ndarray::{Array, array};
65/// use ndarray_stats::{
66/// histogram::{strategies::Auto, Bins, Edges, Grid, GridBuilder},
67/// HistogramExt,
68/// };
69///
70/// // 1-dimensional observations, as a (n_observations, n_dimension) 2-d matrix
71/// let observations = Array::from_shape_vec(
72/// (12, 1),
73/// vec![1, 4, 5, 2, 100, 20, 50, 65, 27, 40, 45, 23],
74/// ).unwrap();
75///
76/// // The optimal grid layout is inferred from the data, given a chosen strategy, Auto in this case
77/// let grid = GridBuilder::<Auto<usize>>::from_array(&observations).unwrap().build();
78///
79/// let histogram = observations.histogram(grid);
80///
81/// let histogram_matrix = histogram.counts();
82/// // Bins are left-closed, right-open!
83/// let expected = array![4, 3, 3, 1, 0, 1];
84/// assert_eq!(histogram_matrix, expected.into_dyn());
85/// ```
86///
87/// [`histogram`]: trait.HistogramExt.html
88/// [`GridBuilder`]: struct.GridBuilder.html
89/// [`strategy`]: strategies/index.html
90#[derive(Clone, Debug, Eq, PartialEq)]
91pub struct Grid<A: Ord> {
92 projections: Vec<Bins<A>>,
93}
94
95impl<A: Ord> From<Vec<Bins<A>>> for Grid<A> {
96 /// Converts a `Vec<Bins<A>>` into a `Grid<A>`, consuming the vector of bins.
97 ///
98 /// The `i`-th element in `Vec<Bins<A>>` represents the projection of the bin grid onto the
99 /// `i`-th axis.
100 ///
101 /// Alternatively, a `Grid` can be built directly from data using a [`GridBuilder`].
102 ///
103 /// [`GridBuilder`]: struct.GridBuilder.html
104 fn from(projections: Vec<Bins<A>>) -> Self {
105 Grid { projections }
106 }
107}
108
109impl<A: Ord> Grid<A> {
110 /// Returns the number of dimensions of the region partitioned by the grid.
111 ///
112 /// # Examples
113 ///
114 /// ```
115 /// use ndarray_stats::histogram::{Edges, Bins, Grid};
116 ///
117 /// let edges = Edges::from(vec![0, 1]);
118 /// let bins = Bins::new(edges);
119 /// let square_grid = Grid::from(vec![bins.clone(), bins.clone()]);
120 ///
121 /// assert_eq!(square_grid.ndim(), 2usize)
122 /// ```
123 #[must_use]
124 pub fn ndim(&self) -> usize {
125 self.projections.len()
126 }
127
128 /// Returns the numbers of bins along each coordinate axis.
129 ///
130 /// # Examples
131 ///
132 /// ```
133 /// use ndarray_stats::histogram::{Edges, Bins, Grid};
134 ///
135 /// let edges_x = Edges::from(vec![0, 1]);
136 /// let edges_y = Edges::from(vec![-1, 0, 1]);
137 /// let bins_x = Bins::new(edges_x);
138 /// let bins_y = Bins::new(edges_y);
139 /// let square_grid = Grid::from(vec![bins_x, bins_y]);
140 ///
141 /// assert_eq!(square_grid.shape(), vec![1usize, 2usize]);
142 /// ```
143 #[must_use]
144 pub fn shape(&self) -> Vec<usize> {
145 self.projections.iter().map(Bins::len).collect()
146 }
147
148 /// Returns the grid projections on each coordinate axis as a slice of immutable references.
149 #[must_use]
150 pub fn projections(&self) -> &[Bins<A>] {
151 &self.projections
152 }
153
154 /// Returns an `n-dimensional` index, of bins along each axis that contains the point, if one
155 /// exists.
156 ///
157 /// Returns `None` if the point is outside the grid.
158 ///
159 /// # Panics
160 ///
161 /// Panics if dimensionality of the point doesn't equal the grid's.
162 ///
163 /// # Examples
164 ///
165 /// Basic usage:
166 ///
167 /// ```
168 /// use ndarray::array;
169 /// use ndarray_stats::histogram::{Edges, Bins, Grid};
170 /// use noisy_float::types::n64;
171 ///
172 /// let edges = Edges::from(vec![n64(-1.), n64(0.), n64(1.)]);
173 /// let bins = Bins::new(edges);
174 /// let square_grid = Grid::from(vec![bins.clone(), bins.clone()]);
175 ///
176 /// // (0., -0.7) falls in 1st and 0th bin respectively
177 /// assert_eq!(
178 /// square_grid.index_of(&array![n64(0.), n64(-0.7)]),
179 /// Some(vec![1, 0]),
180 /// );
181 /// // Returns `None`, as `1.` is outside the grid since bins are right-open
182 /// assert_eq!(
183 /// square_grid.index_of(&array![n64(0.), n64(1.)]),
184 /// None,
185 /// );
186 /// ```
187 ///
188 /// A panic upon dimensionality mismatch:
189 ///
190 /// ```should_panic
191 /// # use ndarray::array;
192 /// # use ndarray_stats::histogram::{Edges, Bins, Grid};
193 /// # use noisy_float::types::n64;
194 /// # let edges = Edges::from(vec![n64(-1.), n64(0.), n64(1.)]);
195 /// # let bins = Bins::new(edges);
196 /// # let square_grid = Grid::from(vec![bins.clone(), bins.clone()]);
197 /// // the point has 3 dimensions, the grid expected 2 dimensions
198 /// assert_eq!(
199 /// square_grid.index_of(&array![n64(0.), n64(-0.7), n64(0.5)]),
200 /// Some(vec![1, 0, 1]),
201 /// );
202 /// ```
203 pub fn index_of(&self, point: &ArrayRef<A, Ix1>) -> Option<Vec<usize>> {
204 assert_eq!(
205 point.len(),
206 self.ndim(),
207 "Dimension mismatch: the point has {:?} dimensions, the grid \
208 expected {:?} dimensions.",
209 point.len(),
210 self.ndim()
211 );
212 point
213 .iter()
214 .zip(self.projections.iter())
215 .map(|(v, e)| e.index_of(v))
216 .collect()
217 }
218}
219
220impl<A: Ord + Clone> Grid<A> {
221 /// Given an `n`-dimensional index, `i = (i_0, ..., i_{n-1})`, returns an `n`-dimensional bin,
222 /// `I_{i_0} x ... x I_{i_{n-1}}`, where `I_{i_j}` is the `i_j`-th interval on the `j`-th
223 /// projection of the grid on the coordinate axes.
224 ///
225 /// # Panics
226 ///
227 /// Panics if at least one in the index, `(i_0, ..., i_{n-1})`, is out of bounds on the
228 /// corresponding coordinate axis, i.e. if there exists `j` s.t.
229 /// `i_j >= self.projections[j].len()`.
230 ///
231 /// # Examples
232 ///
233 /// Basic usage:
234 ///
235 /// ```
236 /// use ndarray::array;
237 /// use ndarray_stats::histogram::{Edges, Bins, Grid};
238 ///
239 /// let edges_x = Edges::from(vec![0, 1]);
240 /// let edges_y = Edges::from(vec![2, 3, 4]);
241 /// let bins_x = Bins::new(edges_x);
242 /// let bins_y = Bins::new(edges_y);
243 /// let square_grid = Grid::from(vec![bins_x, bins_y]);
244 ///
245 /// // Query the 0-th bin on x-axis, and 1-st bin on y-axis
246 /// assert_eq!(
247 /// square_grid.index(&[0, 1]),
248 /// vec![0..1, 3..4],
249 /// );
250 /// ```
251 ///
252 /// A panic upon out-of-bounds:
253 ///
254 /// ```should_panic
255 /// # use ndarray::array;
256 /// # use ndarray_stats::histogram::{Edges, Bins, Grid};
257 /// # let edges_x = Edges::from(vec![0, 1]);
258 /// # let edges_y = Edges::from(vec![2, 3, 4]);
259 /// # let bins_x = Bins::new(edges_x);
260 /// # let bins_y = Bins::new(edges_y);
261 /// # let square_grid = Grid::from(vec![bins_x, bins_y]);
262 /// // out-of-bound on y-axis
263 /// assert_eq!(
264 /// square_grid.index(&[0, 2]),
265 /// vec![0..1, 3..4],
266 /// );
267 /// ```
268 #[must_use]
269 pub fn index(&self, index: &[usize]) -> Vec<Range<A>> {
270 assert_eq!(
271 index.len(),
272 self.ndim(),
273 "Dimension mismatch: the index has {0:?} dimensions, the grid \
274 expected {1:?} dimensions.",
275 index.len(),
276 self.ndim()
277 );
278 izip!(&self.projections, index)
279 .map(|(bins, &i)| bins.index(i))
280 .collect()
281 }
282}
283
284/// A builder used to create [`Grid`] instances for [`histogram`] computations.
285///
286/// # Examples
287///
288/// Basic usage, creating a `Grid` with some observations and a given [`strategy`]:
289///
290/// ```
291/// use ndarray::Array;
292/// use ndarray_stats::histogram::{strategies::Auto, Bins, Edges, Grid, GridBuilder};
293///
294/// // 1-dimensional observations, as a (n_observations, n_dimension) 2-d matrix
295/// let observations = Array::from_shape_vec(
296/// (12, 1),
297/// vec![1, 4, 5, 2, 100, 20, 50, 65, 27, 40, 45, 23],
298/// ).unwrap();
299///
300/// // The optimal grid layout is inferred from the data, given a chosen strategy, Auto in this case
301/// let grid = GridBuilder::<Auto<usize>>::from_array(&observations).unwrap().build();
302/// // Equivalently, build a Grid directly
303/// let expected_grid = Grid::from(vec![Bins::new(Edges::from(vec![1, 20, 39, 58, 77, 96, 115]))]);
304///
305/// assert_eq!(grid, expected_grid);
306/// ```
307///
308/// [`Grid`]: struct.Grid.html
309/// [`histogram`]: trait.HistogramExt.html
310/// [`strategy`]: strategies/index.html
311#[allow(clippy::module_name_repetitions)]
312pub struct GridBuilder<B: BinsBuildingStrategy> {
313 bin_builders: Vec<B>,
314}
315
316impl<A, B> GridBuilder<B>
317where
318 A: Ord,
319 B: BinsBuildingStrategy<Elem = A>,
320{
321 /// Returns a `GridBuilder` for building a [`Grid`] with a given [`strategy`] and some
322 /// observations in a 2-dimensionalarray with shape `(n_observations, n_dimension)`.
323 ///
324 /// # Errors
325 ///
326 /// It returns [`BinsBuildError`] if it is not possible to build a [`Grid`] given
327 /// the observed data according to the chosen [`strategy`].
328 ///
329 /// # Examples
330 ///
331 /// See [Trait-level examples] for basic usage.
332 ///
333 /// [`Grid`]: struct.Grid.html
334 /// [`strategy`]: strategies/index.html
335 /// [`BinsBuildError`]: errors/enum.BinsBuildError.html
336 /// [Trait-level examples]: struct.GridBuilder.html#examples
337 pub fn from_array(array: &ArrayRef<A, Ix2>) -> Result<Self, BinsBuildError> {
338 let bin_builders = array
339 .axis_iter(Axis(1))
340 .map(|data| B::from_array(&data))
341 .collect::<Result<Vec<B>, BinsBuildError>>()?;
342 Ok(Self { bin_builders })
343 }
344
345 /// Returns a [`Grid`] instance, with building parameters infered in [`from_array`], according
346 /// to the specified [`strategy`] and observations provided.
347 ///
348 /// # Examples
349 ///
350 /// See [Trait-level examples] for basic usage.
351 ///
352 /// [`Grid`]: struct.Grid.html
353 /// [`strategy`]: strategies/index.html
354 /// [`from_array`]: #method.from_array.html
355 #[must_use]
356 pub fn build(&self) -> Grid<A> {
357 let projections: Vec<_> = self.bin_builders.iter().map(|b| b.build()).collect();
358 Grid::from(projections)
359 }
360}