# ndarray-slice
[![Build][]](https://github.com/qu1x/ndarray-slice/actions/workflows/build.yml)
[![Documentation][]](https://docs.rs/ndarray-slice)
[![Downloads][]](https://crates.io/crates/ndarray-slice)
[![Version][]](https://crates.io/crates/ndarray-slice)
[![Rust][]](https://www.rust-lang.org)
[![License][]](https://opensource.org/licenses)
[Build]: https://github.com/qu1x/ndarray-slice/actions/workflows/build.yml/badge.svg
[Documentation]: https://docs.rs/ndarray-slice/badge.svg
[Downloads]: https://img.shields.io/crates/d/ndarray-slice.svg
[Version]: https://img.shields.io/crates/v/ndarray-slice.svg
[Rust]: https://img.shields.io/badge/rust-v1.65.0-brightgreen.svg
[License]: https://img.shields.io/badge/License-MIT%20OR%20Apache--2.0-blue.svg
Fast and robust slice-based algorithms (e.g., [sorting], [selection], [search]) for
non-contiguous (sub)views into *n*-dimensional arrays. Reimplements algorithms in [`slice`] and
[`rayon::slice`] for [`ndarray`] with arbitrary memory layout (e.g., non-contiguous).
[`slice`]: https://doc.rust-lang.org/std/primitive.slice.html
[`rayon::slice`]: https://docs.rs/rayon/latest/rayon/slice/index.html
[`ndarray`]: https://docs.rs/ndarray
## Example
```rust
use ndarray_slice::{ndarray::arr2, Slice1Ext};
// 2-dimensional array of 4 rows and 5 columns.
let mut v = arr2(&[[-5, 4, 1, -3, 2], // row 0, axis 0
[ 8, 3, 2, 4, 8], // row 1, axis 0
[38, 9, 3, 0, 3], // row 2, axis 0
[ 4, 9, 0, 8, -1]]); // row 3, axis 0
// \ \ \
// column 0 \ column 4 axis 1
// column 2 axis 1
// Mutable subview into the last column.
let mut column = v.column_mut(4);
// Due to row-major memory layout, columns are non-contiguous
// and hence cannot be sorted by viewing them as mutable slices.
assert_eq!(column.as_slice_mut(), None);
// Instead, sorting is specifically implemented for non-contiguous
// mutable (sub)views.
column.sort_unstable();
assert!(v == arr2(&[[-5, 4, 1, -3, -1],
[ 8, 3, 2, 4, 2],
[38, 9, 3, 0, 3],
[ 4, 9, 0, 8, 8]]));
// \
// column 4 sorted, others untouched
```
## Current Implementation
Complexities where *n* is the length of the (sub)view and *m* the count of indices to select.
| Time | Best | *O*(*n*) | *O*(*n*) | *O*(*n*) | *O*(*n* log *m*) |
| Time | Average | *O*(*n* log *n*) | *O*(*n* log *n*) | *O*(*n*) | *O*(*n* log *m*) |
| Time | Worst | *O*(*n* log *n*) | *O*(*n* log *n*) | *O*(*n*) | *O*(*n* log *m*) |
| Space | Best | *O*(1) | *O*(1) | *O*(1) | *O*(*m*) |
| Space | Average | *O*(*n*/2) | *O*(log *n*) | *O*(1) | *O*(*m*+log *m*) |
| Space | Worst | *O*(*n*/2) | *O*(log *n*) | *O*(1) | *O*(*m*+log *m*) |
[sorting]: https://en.wikipedia.org/wiki/Sorting_algorithm
[selection]: https://en.wikipedia.org/wiki/Selection_algorithm
[search]: https://en.wikipedia.org/wiki/Search_algorithm
[`sort`]: Slice1Ext::sort
[`sort_unstable`]: Slice1Ext::sort_unstable
[`select_nth_unstable`]: Slice1Ext::select_nth_unstable
## Roadmap
* Add `SliceExt` trait for *n*-dimensional array or (sub)view with methods expecting `Axis` as
their first argument. Comparing methods will always be suffixed with `_by` or `_by_key`
defining how to compare multi-dimensional elements (e.g., rows) along the provided axis of
interest (e.g., columns).
See the [release history](RELEASES.md) to keep track of the development.
## Features
* `alloc` for stable `sort`/`sort_by`/`sort_by_key`. Enabled by `std`.
* `std` for stable `sort_by_cached_key`. Enabled by `default` or `rayon`.
* `stacker` for spilling recursion stack over to heap if necessary. Enabled by `default`.
* `rayon` for parallel `par_sort*`/`par_select_many_nth_unstable*`.
# License
Copyright © 2023 Rouven Spreckels <rs@qu1x.dev>
This project contains derivative works of [`rust`] and [`rayon`]. For full authorship information,
see their version control histories. Respective copyrights are retained by their contributors.
[`rust`]: https://github.com/rust-lang/rust
[`rayon`]: https://github.com/rayon-rs/rayon
Like the original works, this project is licensed under either of
* Apache License, Version 2.0, ([LICENSES/Apache-2.0](LICENSES/Apache-2.0) or
https://www.apache.org/licenses/LICENSE-2.0)
* MIT license ([LICENSES/MIT](LICENSES/MIT) or https://opensource.org/licenses/MIT)
at your option.
# Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted
for inclusion in this project by you, as defined in the Apache-2.0 license,
shall be dual licensed as above, without any additional terms or conditions.