Rust API reference

Every public function and type of the kwker crate, with its signature and description (Kwker 0.1.0). The functions are at the crate root (kwker::sort, kwker::top_k, ...); kwker::dist and kwker::arrow are modules.

Kwker: sorting, selection, top-k, argsort and key-value sorting of numeric slices, in place, with the fastest engine for the CPU chosen once at run time (AVX-512 or AVX2 on x86-64, NEON or SVE on ARM, portable elsewhere).

use kwker::Order;

let mut v = vec![3.5f64, 0.5, 2.0, 1.0];
kwker::sort(&mut v);
assert_eq!(v, [0.5, 1.0, 2.0, 3.5]);

let scores = [12, 7, 30, 18];
let (top, at): (Vec<i32>, Vec<usize>) = kwker::top_k(&scores, 2, Order::DESCENDING, true);
assert_eq!((top, at), (vec![30, 18], vec![2, 3]));

Key types: u8, i8, u16, i16, u32, i32, u64, i64, f32, f64, and the low-precision floats F16, Bf16, F8E5M2 and F8E4M3. Every engine returns the same result; isa names the one in use.

Sorting, selection and top-k

sort Page

pub fn sort<T: Sortable>(v: &mut [T])

Sorts v in place, smallest first.

Arguments

• v: the keys: integers, floats or the low-precision float types (any Sortable type).

Example

let mut v = vec![30, 10, 20];
kwker::sort(&mut v);
assert_eq!(v, [10, 20, 30]);

Notes

• Not stable: equal keys may change places (only NaNs with different bits can tell).
• Nearly sorted or duplicate-heavy input may use a side buffer of up to about v.len() / 4 keys.

Remarks: Not stable (rule 5): keys that are equal but can be told apart (NaNs with different bits) may change places. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

Examples: Quickstart: Kwker Core: Sort an array, Core concepts: In place or a copy, Runtime controls: Fallback switches, Sorting: Sort in place

sort_descending Page

pub fn sort_descending<T: Sortable>(v: &mut [T])

Sorts v in place, largest first.

Arguments

• v: the keys (any Sortable type).

Example

let mut v = vec![1.5f32, 3.0, 2.25];
kwker::sort_descending(&mut v);
assert_eq!(v, [3.0, 2.25, 1.5]);

Notes

• NaNs go last; +0.0 comes before -0.0.

Examples: Quickstart: Kwker Core: Largest first, or a sorted copy, Core concepts: Special float values, Sorting: Largest first, Sorting: Missing values (NaN)

sort_by_order Page

pub fn sort_by_order<T: Sortable>(v: &mut [T], order: Order)

Sorts v in place in the given order: ascending or descending, NaNs first or last.

Arguments

• v: the keys (any Sortable type).
• order: the direction and NaN placement, for example Order::DESCENDING.

Example

use kwker::{Direction, NanPlacement, Order};

let mut v = vec![2.0f64, f64::NAN, 1.0];
kwker::sort_by_order(&mut v, Order { direction: Direction::Ascending, nans: NanPlacement::First });
assert!(v[0].is_nan());
assert_eq!(v[1..], [1.0, 2.0]);

Notes

• Descending is the exact reverse of ascending for all keys but NaNs, which stay together at the chosen end.

Examples: Core concepts: Special float values, Sorting: Missing values (NaN)

select_nth Page

pub fn select_nth<T: Sortable>(v: &mut [T], k: usize)

Puts the key a full sort would put at position k into v[k], smaller or equal keys before it and larger or equal keys after it, like slice::select_nth_unstable.

Arguments

• v: the keys (any Sortable type).
• k: the position to fill, below v.len().

Example

let mut v = vec![50, 10, 40, 20, 30];
kwker::select_nth(&mut v, 2);
assert_eq!(v[2], 30); // the median

Panics

If k >= v.len().

Notes

• Only v[k] is in its sorted place; the keys on either side are in no particular order.

Examples: Quickstart: Kwker Core: The median, without a full sort, Top-k and selection: The median and other positions

select_nth_by_order Page

pub fn select_nth_by_order<T: Sortable>(v: &mut [T], k: usize, order: Order)

select_nth in the given order: with Order::DESCENDING, v[k] gets the (k+1)-th largest key.

Arguments

• v: the keys (any Sortable type).
• k: the position to fill, below v.len().
• order: the direction and NaN placement.

Panics

If k >= v.len().

partial_sort Page

pub fn partial_sort<T: Sortable>(v: &mut [T], k: usize)

Puts the k smallest keys of v, sorted, into v[..k].

Arguments

• v: the keys (any Sortable type).
• k: how many keys to sort; k >= v.len() sorts all of v.

Example

let mut v = vec![50, 10, 40, 20, 30];
kwker::partial_sort(&mut v, 2);
assert_eq!(v[..2], [10, 20]);

Notes

• The keys after v[..k] are in no particular order.

Remarks: The first k positions hold exactly what a full sort puts there; the rest hold the other keys in any order (rule 8). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

Examples: Top-k and selection: Sort only the beginning

partial_sort_by_order Page

pub fn partial_sort_by_order<T: Sortable>(v: &mut [T], k: usize, order: Order)

partial_sort in the given order: with Order::DESCENDING, the k largest keys, largest first.

Arguments

• v: the keys (any Sortable type).
• k: how many keys to sort; k >= v.len() sorts all of v.
• order: the direction and NaN placement.

argsort Page

pub fn argsort<T: Sortable, I: Index>(v: &[T], order: Order) -> Vec<I>

Returns the positions that sort v: v[p[0]], v[p[1]], ... is in order. Equal keys keep their input order.

Arguments

• v: the keys (any Sortable type); not changed.
• order: the direction and NaN placement, for example Order::ASCENDING.

Returns

One position per key, in the index type I you choose (u32, usize, ...; see Index).

Example

use kwker::Order;

let p: Vec<u32> = kwker::argsort(&[30, 10, 20], Order::ASCENDING);
assert_eq!(p, [1, 2, 0]);

Panics

If v.len() does not fit the index type I.

Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

Examples: Quickstart: Kwker Core: Get the order, not the sorted data, Order and ranking: The order of an array: argsort, Large data: Use several cores, Languages: The same calls in every language

argsort_into Page

pub fn argsort_into<T: Sortable>(v: &[T], order: Order, out: &mut [u64])

argsort into a buffer you provide, with no result vector.

Arguments

• v: the keys (any Sortable type); not changed.
• order: the direction and NaN placement.
• out: receives the positions; it must have v.len() entries.

Panics

If out.len() != v.len().

Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

argselect Page

pub fn argselect<T: Sortable, I: Index>(v: &[T], k: usize, order: Order) -> Vec<I>

Returns the positions of the k first keys of v in order, in no particular order: the positions of top_k's keys.

Arguments

• v: the keys (any Sortable type); not changed.
• k: how many positions; more than v.len() returns them all.
• order: the direction and NaN placement.

Returns

min(k, v.len()) positions in the index type I you choose.

Example

use kwker::Order;

let mut at: Vec<u32> = kwker::argselect(&[12, 7, 30, 18], 2, Order::ASCENDING);
at.sort();
assert_eq!(at, [0, 1]);

Panics

If v.len() does not fit the index type I.

Remarks: The positions of the stable order's first k keys, in any order (rule 6). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

Examples: Top-k and selection: Only the positions

top_k Page

pub fn top_k<T: Sortable, I: Index>(
    v: &[T],
    k: usize,
    order: Order,
    sorted: bool,
) -> (Vec<T>, Vec<I>)

Returns the k first keys of v in order and their positions: the k smallest with Order::ASCENDING, the k largest with Order::DESCENDING.

Arguments

• v: the keys (any Sortable type); not changed.
• k: how many keys; more than v.len() returns them all.
• order: the direction and NaN placement.
• sorted: true returns them in order; false returns the same keys in no particular order, which is faster.

Returns

(values, positions): min(k, v.len()) keys and their positions in v, in the index type I you choose (u32, usize, ...).

Example

use kwker::Order;

let (top, at): (Vec<i32>, Vec<usize>) = kwker::top_k(&[12, 7, 30, 18], 2, Order::DESCENDING, true);
assert_eq!(top, [30, 18]);
assert_eq!(at, [2, 3]);

Panics

If v.len() does not fit the index type I.

Notes

• Equal keys go to the earlier position first, so the result is the same on every run.

Remarks: The first k keys of the stable order and their positions; equal keys keep their input order (rule 9). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

Examples: Quickstart: Kwker Core: Find the top results, Use Kwker from Rust: The program, Top-k and selection: The k largest or smallest values, Languages: The same calls in every language

top_k_into Page

pub fn top_k_into<T: Sortable, I: Index>(
    v: &[T],
    order: Order,
    sorted: bool,
    values: &mut [T],
    indices: &mut [I],
) -> usize

top_k into buffers you provide, with no result vectors.

Arguments

• v: the keys (any Sortable type); not changed.
• order, sorted: as in top_k.
• values, indices: receive the keys and their positions; k is the shorter of the two, at most v.len().

Returns

k, the number of entries written.

Panics

If v.len() does not fit the index type I.

Notes

• The scratch buffers are kept per thread between calls; top_k_into_with uses a Workspace you own.

Remarks: The first k keys of the stable order and their positions; equal keys keep their input order (rule 9). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

top_k_indices_into Page

pub fn top_k_indices_into<T: Sortable>(
    v: &[T],
    order: Order,
    sorted: bool,
    out: &mut [u64],
) -> usize

The positions of top_k into a buffer you provide, with no result vectors.

Arguments

• v: the keys (any Sortable type); not changed.
• order, sorted: as in top_k.
• out: receives the positions; k is out.len(), at most v.len().

Returns

k, the number of positions written.

Sortable Page

pub trait Sortable: Copy + Sealed { }

Key types sort accepts: u32, i32, f32, u64, i64, f64 (the engines), and the 8- and 16-bit keys u8, i8, u16, i16, F16, Bf16, F8E5M2, F8E4M3 (counting sorts).

Direction Page

pub enum Direction {
    Ascending,
    Descending,
}

Sort direction.

Variants

• Ascending: Smallest first.
• Descending: Largest first.

NanPlacement Page

pub enum NanPlacement {
    Last,
    First,
}

Where NaN keys go (floating-point keys; ignored for integers), independent of the direction.

Variants

• Last: After every other key.
• First: Before every other key.

Order Page

pub struct Order {
    pub direction: Direction,
    pub nans: NanPlacement,
}

An ordering policy: direction and NaN placement. Order::default() is the order of sort.

Fields

• direction: Direction of the non-NaN keys.
• nans: Position of the NaN keys.

Order::ASCENDING Page

pub const ASCENDING: Order;

Ascending, NaNs last (the order of sort).

Order::DESCENDING Page

pub const DESCENDING: Order;

Descending, NaNs last.

Index Page

pub trait Index: Copy + Send + Sync + 'static { }

Index types of index-producing operations (u8, u16, u32, u64, usize). An index type of b bits needs len <= 2^b (lane-relative indices: the lane length).

Key-value sorts

sort_kv_stable Page

pub fn sort_kv_stable<K: Sortable, V: Copy>(keys: &mut [K], values: &mut [V])

Sorts keys in place, smallest first, and moves values with them. Equal keys keep their values in input order.

Arguments

• keys: the sort keys (any Sortable type).
• values: one value per key, of any Copy type.

Example

let mut keys = vec![2, 1, 2, 1];
let mut names = vec!["c", "a", "d", "b"];
kwker::sort_kv_stable(&mut keys, &mut names);
assert_eq!(keys, [1, 1, 2, 2]);
assert_eq!(names, ["a", "b", "c", "d"]);

Panics

If keys and values have different lengths.

Notes

• Uses buffers of about the input's size; sort_kv is faster when the order of equal keys does not matter.

Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

Examples: Sorting keys with values: Keep equal keys in order: the stable sort

sort_kv_stable_by_order Page

pub fn sort_kv_stable_by_order<K: Sortable, V: Copy>(keys: &mut [K], values: &mut [V], order: Order)

sort_kv_stable in the given order. Equal keys keep their values in input order in every order.

Arguments

• keys: the sort keys (any Sortable type).
• values: one value per key, of any Copy type.
• order: the direction and NaN placement, for example Order::DESCENDING.

Panics

If keys and values have different lengths.

sort_with_indices Page

pub fn sort_with_indices<K: Sortable, I: Index + Sortable + Ord>(
    keys: &mut [K],
    order: Order,
) -> Vec<I>

Sorts keys in place and returns where each sorted key came from: a sort and an argsort in one call. Use the positions to reorder other columns the same way.

Arguments

• keys: the keys (any Sortable type).
• order: the direction and NaN placement, for example Order::ASCENDING.

Returns

One input position per key, as u32 or u64. Equal keys keep their input order.

Example

use kwker::Order;

let mut keys = vec![30, 10, 20];
let from: Vec<u32> = kwker::sort_with_indices(&mut keys, Order::ASCENDING);
assert_eq!(keys, [10, 20, 30]);
assert_eq!(from, [1, 2, 0]);

Panics

If keys.len() does not fit the index type I.

sort_kv Page

pub fn sort_kv<K: Sortable, V: Copy>(keys: &mut [K], values: &mut [V])

Sorts keys in place, smallest first, and moves values with them: each value stays with its key.

Arguments

• keys: the sort keys (any Sortable type).
• values: one value per key, of any Copy type.

Example

let mut prices = vec![30, 10, 20];
let mut items = vec!['c', 'a', 'b'];
kwker::sort_kv(&mut prices, &mut items);
assert_eq!(prices, [10, 20, 30]);
assert_eq!(items, ['a', 'b', 'c']);

Panics

If keys and values have different lengths.

Notes

• Not stable: the values of equal keys may come out in any order (sort_kv_stable keeps their input order).
• 4- and 8-byte values on the AVX-512 and AVX2 engines sort without allocating; others use buffers of about the input's size (sort_kv_with takes a Workspace you own).

Remarks: Unless the stable form is asked for, pairs with equal keys may come out in any order; the stable form keeps their input order (rule 6). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

Examples: Core concepts: In place or a copy, Sorting keys with values: Sort keys and values together

sort_kv_by_order Page

pub fn sort_kv_by_order<K: Sortable, V: Copy>(keys: &mut [K], values: &mut [V], order: Order)

sort_kv in the given order.

Arguments

• keys: the sort keys (any Sortable type).
• values: one value per key, of any Copy type.
• order: the direction and NaN placement, for example Order::DESCENDING.

Panics

If keys and values have different lengths.

select_nth_kv Page

pub fn select_nth_kv<K: Sortable, V: Copy>(keys: &mut [K], values: &mut [V], k: usize)

select_nth on key-value pairs: the pair a full sort_kv would put at position k moves there, with smaller or equal keys before it and larger or equal keys after it.

Arguments

• keys: the keys (any Sortable type).
• values: one value per key, of any Copy type; each moves with its key.
• k: the position to fill, below keys.len().

Panics

If k >= keys.len() or keys and values have different lengths.

Notes

• Only position k is in its sorted place; the pairs on either side are in no particular order.

select_nth_kv_by_order Page

pub fn select_nth_kv_by_order<K: Sortable, V: Copy>(
    keys: &mut [K],
    values: &mut [V],
    k: usize,
    order: Order,
)

select_nth_kv in the given order.

Arguments

• keys, values, k: as in select_nth_kv.
• order: the direction and NaN placement, for example Order::DESCENDING.

Panics

If k >= keys.len() or keys and values have different lengths.

partial_sort_kv Page

pub fn partial_sort_kv<K: Sortable, V: Copy>(keys: &mut [K], values: &mut [V], k: usize)

partial_sort on key-value pairs: puts the k pairs with the smallest keys, sorted, at the front.

Arguments

• keys: the keys (any Sortable type).
• values: one value per key, of any Copy type; each moves with its key.
• k: how many pairs to sort; k >= keys.len() sorts them all.

Panics

If keys and values have different lengths.

Notes

• The pairs after the first k are in no particular order.

Remarks: The first k positions hold exactly what a full sort puts there; the rest hold the other keys in any order (rule 8). Unless the stable form is asked for, pairs with equal keys may come out in any order; the stable form keeps their input order (rule 6).

partial_sort_kv_by_order Page

pub fn partial_sort_kv_by_order<K: Sortable, V: Copy>(
    keys: &mut [K],
    values: &mut [V],
    k: usize,
    order: Order,
)

partial_sort_kv in the given order: with Order::DESCENDING, the k pairs with the largest keys.

Arguments

• keys, values, k: as in partial_sort_kv.
• order: the direction and NaN placement.

Panics

If keys and values have different lengths.

Examples: Sorting keys with values: Only the first k pairs

KeyValue Page

pub struct KeyValue<K, V> {
    pub key: K,
    pub value: V,
}

A key and its value in one record (#[repr(C)]: the key first). Sorted by the key only.

Fields

• key: The key the records are ordered by.
• value: The value carried along with it.

Key types

F16 Page

pub struct F16(pub u16);

IEEE 754 binary16 (half precision) bits. Ordered as a float; F16::to_f32 decodes exactly.

F16::to_f32 Page

pub fn to_f32(self) -> f32

The value as f32 (exact).

Bf16 Page

pub struct Bf16(pub u16);

bfloat16 bits (the top half of an f32). Ordered as a float; Bf16::to_f32 decodes exactly.

Bf16::to_f32 Page

pub fn to_f32(self) -> f32

The value as f32 (exact: the bits are its top half).

F8E5M2 Page

pub struct F8E5M2(pub u8);

OCP FP8 E5M2 bits (1 sign, 5 exponent, 2 mantissa bits; infinities and NaNs as in IEEE 754).

F8E5M2::to_f32 Page

pub fn to_f32(self) -> f32

The value as f32 (exact).

F8E4M3 Page

pub struct F8E4M3(pub u8);

OCP FP8 E4M3 bits, the "FN" variant (1 sign, 4 exponent, 3 mantissa bits; no infinities, NaN = S.1111.111).

F8E4M3::to_f32 Page

pub fn to_f32(self) -> f32

The value as f32 (exact).

128-bit keys

sort_u128 Page

pub fn sort_u128(v: &mut [u128], order: Order)

Sorts unsigned 128-bit keys in place.

Arguments

• v: the keys.
• order: the direction, for example Order::ASCENDING (128-bit integers have no NaNs).

Example

use kwker::Order;

let mut v = vec![3u128 << 100, 1, 2];
kwker::sort_u128(&mut v, Order::ASCENDING);
assert_eq!(v, [1, 2, 3u128 << 100]);

Notes

• Uses a buffer of v.len() keys; under a smaller set_scratch_limit it sorts in place, more slowly.

sort_i128 Page

pub fn sort_i128(v: &mut [i128], order: Order)

sort_u128 for signed 128-bit keys.

Arguments

• v: the keys.
• order: the direction, for example Order::ASCENDING.

select_nth_u128 Page

pub fn select_nth_u128(v: &mut [u128], k: usize, order: Order)

Puts the key a full sort would put at position k into v[k], the keys ordered before it in front of it and the others after it.

Arguments

• v: unsigned 128-bit keys.
• k: the position to fill, below v.len().
• order: the direction, for example Order::ASCENDING.

Panics

If k >= v.len().

select_nth_i128 Page

pub fn select_nth_i128(v: &mut [i128], k: usize, order: Order)

select_nth_u128 for signed 128-bit keys.

Arguments

• v, k, order: as in select_nth_u128.

Panics

If k >= v.len().

partial_sort_u128 Page

pub fn partial_sort_u128(v: &mut [u128], k: usize, order: Order)

Puts the k first keys of v in order, sorted, into v[..k].

Arguments

• v: unsigned 128-bit keys.
• k: how many keys to sort; k >= v.len() sorts all of v.
• order: the direction, for example Order::ASCENDING.

Notes

• The keys after v[..k] are in no particular order.

partial_sort_i128 Page

pub fn partial_sort_i128(v: &mut [i128], k: usize, order: Order)

partial_sort_u128 for signed 128-bit keys.

Arguments

• v, k, order: as in partial_sort_u128.

top_k_u128 Page

pub fn top_k_u128(v: &[u128], k: usize, order: Order) -> (Vec<u128>, Vec<u64>)

Returns the k first keys of v in order, sorted, and their positions.

Arguments

• v: unsigned 128-bit keys; not changed.
• k: how many keys; more than v.len() returns them all.
• order: the direction, for example Order::DESCENDING for the largest.

Returns

(values, positions), min(k, v.len()) of each. Equal keys go to the earlier position first.

top_k_i128 Page

pub fn top_k_i128(v: &[i128], k: usize, order: Order) -> (Vec<i128>, Vec<u64>)

top_k_u128 for signed 128-bit keys.

Arguments

• v, k, order: as in top_k_u128.

Returns

(values, positions), min(k, v.len()) of each.

argsort_u128 Page

pub fn argsort_u128(v: &[u128], order: Order) -> Vec<u64>

Returns the positions that sort v. Equal keys keep their input order.

Arguments

• v: unsigned 128-bit keys; not changed.
• order: the direction, for example Order::ASCENDING.

Returns

One position per key.

argsort_i128 Page

pub fn argsort_i128(v: &[i128], order: Order) -> Vec<u64>

argsort_u128 for signed 128-bit keys.

Arguments

• v, order: as in argsort_u128.

Returns

One position per key.

sort_kv_u128 Page

pub fn sort_kv_u128<V: Copy>(keys: &mut [u128], values: &mut [V], order: Order)

Sorts unsigned 128-bit keys in place and moves values with them. Equal keys keep their values in input order.

Arguments

• keys: the sort keys.
• values: one value per key, of any Copy type.
• order: the direction, for example Order::ASCENDING.

Panics

If keys and values have different lengths.

Notes

• Uses 16 bytes per key plus a copy of the values as scratch.

sort_kv_i128 Page

pub fn sort_kv_i128<V: Copy>(keys: &mut [i128], values: &mut [V], order: Order)

sort_kv_u128 for signed 128-bit keys.

Arguments

• keys, values, order: as in sort_kv_u128.

Panics

If keys and values have different lengths.

Permutations, partitions and streams

partition_by_threshold Page

pub fn partition_by_threshold<T: Sortable>(v: &mut [T], t: T, order: Order) -> usize

Moves the keys that come before t in order to the front of v and returns how many there are.

Arguments

• v: the keys (any Sortable type).
• t: the threshold; keys equal to it go to the back part.
• order: the direction and NaN placement, for example Order::ASCENDING (front = keys below t).

Returns

The size of the front part.

Example

use kwker::Order;

let mut v = vec![5, 1, 7, 3, 9];
let n = kwker::partition_by_threshold(&mut v, 5, Order::ASCENDING);
assert_eq!(n, 2);
assert!(v[..n].iter().all(|&x| x < 5));

Notes

• Neither part keeps its input order.

partition_by Page

pub fn partition_by<T, F: FnMut(&T) -> bool>(v: &mut [T], pred: F) -> usize

Moves the elements for which pred returns true to the front of v and returns how many there are.

Arguments

• v: the elements, of any type.
• pred: the test for the front part.

Returns

The size of the front part.

Notes

• Neither part keeps its input order; stable_partition_by keeps both.

stable_partition_by Page

pub fn stable_partition_by<T: Copy, F: FnMut(&T) -> bool>(v: &mut [T], pred: F) -> usize

partition_by that keeps both parts in their input order.

Arguments

• v: the elements, of any Copy type.
• pred: the test for the front part.

Returns

The size of the front part.

Notes

• Uses a buffer for the back part.

partition_multiway Page

pub fn partition_multiway<T: Sortable>(v: &mut [T], splitters: &[T], order: Order) -> Vec<usize>

Splits v into buckets by a list of splitters: bucket 0 holds the keys before splitters[0], bucket i the keys from splitters[i - 1] up to splitters[i], and the last bucket the keys from the last splitter on.

Arguments

• v: the keys (any Sortable type); reordered bucket by bucket.
• splitters: the bucket bounds, sorted in order.
• order: the direction and NaN placement, for example Order::ASCENDING.

Returns

The bucket boundaries: splitters.len() + 2 offsets from 0 to v.len(); bucket i is v[b[i]..b[i + 1]].

Example

use kwker::Order;

let mut v = vec![7, 1, 15, 3, 12, 8];
let b = kwker::partition_multiway(&mut v, &[5, 10], Order::ASCENDING);
assert_eq!(b, [0, 2, 4, 6]);

Panics

If splitters is not sorted in order.

Notes

• The keys inside a bucket are in no particular order.

is_valid Page

pub fn is_valid(validity: &[u8], i: usize) -> bool

Reads bit i of an Arrow-style validity bitmap: true for a value, false for a null.

Arguments

• validity: the bitmap, least significant bit first within each byte.
• i: the element's position.

argsort_nullable Page

pub fn argsort_nullable<T: Sortable>(
    values: &[T],
    validity: &[u8],
    order: Order,
    nulls_first: bool,
) -> Vec<usize>

Returns the positions that sort an array with nulls: the values in order, the nulls together first or last. Equal values and the nulls keep their input order.

Arguments

• values: the values (any Sortable type); not changed.
• validity: an Arrow-style bitmap, one bit per value (set = valid, clear = null).
• order: the direction and NaN placement, for example Order::ASCENDING.
• nulls_first: true puts the nulls first; false puts them last.

Returns

One position per value.

sort_nullable Page

pub fn sort_nullable<T: Sortable>(
    values: &mut [T],
    validity: &mut [u8],
    order: Order,
    nulls_first: bool,
) -> usize

Sorts an array with nulls in place: the values in order, the nulls together first or last. The bitmap is rewritten to match.

Arguments

• values: the values (any Sortable type).
• validity: an Arrow-style bitmap, one bit per value (set = valid, clear = null).
• order: the direction and NaN placement, for example Order::ASCENDING.
• nulls_first: true puts the nulls first; false puts them last.

Returns

The number of valid values.

sort_kv_nullable Page

pub fn sort_kv_nullable<K: Sortable, V: Copy>(
    keys: &mut [K],
    validity: &mut [u8],
    values: &mut [V],
    order: Order,
    nulls_first: bool,
) -> usize

Sorts keys with nulls and moves values with them: the valid keys in order (equal keys keep their input order), the null keys together first or last. The bitmap is rewritten to match.

Arguments

• keys: the keys (any Sortable type).
• validity: an Arrow-style bitmap, one bit per key (set = valid, clear = null).
• values: one value per key, of any Copy type.
• order: the direction and NaN placement, for example Order::ASCENDING.
• nulls_first: true puts the nulls first; false puts them last.

Returns

The number of valid keys.

Permutation Page

pub struct Permutation {
    /* private fields */
}

A reordering of n elements: element i of the result is element indices[i] of the input, the form crate::argsort returns. Use it to sort several columns by one key column: build it once with Permutation::sorting, then apply it to every column.

Example

use kwker::{Order, Permutation};

let ages = [41, 23, 35];
let mut names = ["Ana", "Bo", "Cy"];
let p = Permutation::sorting(&ages, Order::ASCENDING);
p.apply(&mut names);
assert_eq!(names, ["Bo", "Cy", "Ana"]);

Permutation::identity Page

pub fn identity(n: usize) -> Self

The permutation that leaves n elements in place.

Permutation::sorting Page

pub fn sorting<T: Sortable>(keys: &[T], order: Order) -> Self

The permutation that sorts keys in order. Equal keys keep their input order.

Arguments

• keys: the sort keys (any Sortable type).
• order: the direction and NaN placement, for example Order::ASCENDING.

Permutation::from_indices Page

pub fn from_indices(idx: Vec<usize>) -> Option<Self>

A permutation from its indices: element i of the result is element idx[i] of the input.

Returns

None unless every index of 0..idx.len() occurs exactly once.

Permutation::len Page

pub fn len(&self) -> usize

Number of elements.

Permutation::is_empty Page

pub fn is_empty(&self) -> bool

True for the permutation of nothing.

Permutation::as_slice Page

pub fn as_slice(&self) -> &[usize]

The gather indices.

Permutation::into_vec Page

pub fn into_vec(self) -> Vec<usize>

The gather indices, by value.

Permutation::is_identity Page

pub fn is_identity(&self) -> bool

True if every element stays in place.

Permutation::gather Page

pub fn gather<V: Copy>(&self, src: &[V]) -> Vec<V>

Returns src reordered: out[i] = src[indices[i]].

Permutation::gather_into Page

pub fn gather_into<V: Copy>(&self, src: &[V], out: &mut [V])

gather into out, which must have the permutation's length.

Permutation::scatter Page

pub fn scatter<V: Copy>(&self, src: &[V]) -> Vec<V>

Returns src with the reordering undone: out[indices[i]] = src[i].

Permutation::apply Page

pub fn apply<V>(&self, data: &mut [V])

Reorders data in place, as gather would, without copying it.

Notes

• Uses one bit of scratch per element.

Permutation::apply_inverse Page

pub fn apply_inverse<V>(&self, data: &mut [V])

Undoes apply in place, as scatter would.

Permutation::inverse Page

pub fn inverse(&self) -> Self

The inverse permutation: applying a permutation and then its inverse leaves data unchanged.

Permutation::then Page

pub fn then(&self, next: &Permutation) -> Permutation

The permutation that applies self, then next: x.apply(self); x.apply(next) equals x.apply(self.then(next)).

TopKStream Page

pub struct TopKStream<T: Sortable> {
    /* private fields */
}

The k first keys (in an Order) of data that arrives in chunks, without keeping the data. push each chunk, then read the result. Streams filled separately, for example one per thread with push_at, combine with merge.

Example

use kwker::{Order, TopKStream};

let mut s = TopKStream::new(2, Order::DESCENDING);
s.push(&[5, 1, 9]);
s.push(&[7, 3]);
let (top, at) = s.result(true);
assert_eq!(top, [9, 7]);
assert_eq!(at, [2, 3]);

Notes

• Positions count from 0 across the whole stream; equal keys go to the earlier position first.
• Keeps at most 2 * k candidates in memory.

TopKStream::new Page

pub fn new(k: usize, order: Order) -> Self

An empty stream that keeps the k first keys in order.

TopKStream::push Page

pub fn push(&mut self, chunk: &[T])

Adds the next chunk; its positions continue after the elements pushed so far.

TopKStream::push_at Page

pub fn push_at(&mut self, chunk: &[T], first: u64)

Adds a chunk whose first element has stream position first, so chunks can come in any order.

TopKStream::merge Page

pub fn merge(&mut self, other: &TopKStream<T>)

Adds the candidates of another stream with the same k and order.

TopKStream::seen Page

pub fn seen(&self) -> u64

The number of elements pushed so far: the position push gives the next element.

TopKStream::result Page

pub fn result(&self, sorted: bool) -> (Vec<T>, Vec<u64>)

Returns the k first keys (fewer if fewer were pushed) and their stream positions.

Arguments

• sorted: true returns them in order; false in no particular order.

Rows and segments

sort_rows Page

pub fn sort_rows<T: Sortable>(data: &mut [T], row_len: usize, order: Order)

Sorts every row of a row-major table in place.

Arguments

• data: the table, row after row (any Sortable type).
• row_len: the number of keys in a row.
• order: the direction and NaN placement, for example Order::ASCENDING.

Example

use kwker::Order;

let mut t = vec![3, 1, 2, 9, 7, 8];
kwker::sort_rows(&mut t, 3, Order::ASCENDING);
assert_eq!(t, [1, 2, 3, 7, 8, 9]);

Panics

If row_len does not divide data.len() (empty data takes any row_len).

Remarks: Not stable (rule 5): keys that are equal but can be told apart (NaNs with different bits) may change places. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

Examples: Sorting: Sort each row

sort_segments Page

pub fn sort_segments<T: Sortable, I: Index>(data: &mut [T], offsets: &[I], order: Order)

Sorts every segment data[offsets[i]..offsets[i + 1]] in place: segments of any length, one after another.

Arguments

• data: the keys (any Sortable type).
• offsets: the segment bounds, nondecreasing and at most data.len(); [0, end_0, end_1, ..., data.len()] covers all of data.
• order: the direction and NaN placement, for example Order::ASCENDING.

Example

use kwker::Order;

let mut v = vec![2, 1, 9, 8, 7];
kwker::sort_segments(&mut v, &[0u32, 2, 5], Order::ASCENDING);
assert_eq!(v, [1, 2, 7, 8, 9]);

Notes

• Keys outside the segments are left as they are.

Remarks: Not stable (rule 5): keys that are equal but can be told apart (NaNs with different bits) may change places. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

top_k_rows Page

pub fn top_k_rows<T: Sortable, I: Index>(
    data: &[T],
    row_len: usize,
    k: usize,
    order: Order,
    sorted: bool,
    values: &mut [T],
    indices: &mut [I],
)

The k first keys of every row and their positions within the row, as crate::top_k gives for one row.

Arguments

• data: the table, row after row (any Sortable type).
• row_len: the number of keys in a row.
• k: keys per row, at most row_len.
• order: the direction and NaN placement, for example Order::DESCENDING for the largest.
• sorted: true returns each row's keys in order; false in no particular order, which is faster.
• values, indices: receive k entries per row; row i's are at i * k..(i + 1) * k.

Example

use kwker::Order;

let scores = [0.1f32, 0.7, 0.2, 0.9, 0.3, 0.8];
let (mut top, mut at) = (vec![0.0f32; 2], vec![0u32; 2]);
kwker::top_k_rows(&scores, 3, 1, Order::DESCENDING, true, &mut top, &mut at);
assert_eq!(top, [0.7, 0.9]);
assert_eq!(at, [1, 0]);

Panics

If row_len does not divide data.len(), k > row_len, or an output does not hold rows x k entries.

Remarks: The first k keys of the stable order and their positions; equal keys keep their input order (rule 9). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

top_k_segments Page

pub fn top_k_segments<T: Sortable, I: Index, J: Index>(
    data: &[T],
    offsets: &[J],
    k: usize,
    order: Order,
    sorted: bool,
    values: &mut [T],
    indices: &mut [I],
)

The k first keys of every segment and their positions within the segment.

Arguments

• data: the keys (any Sortable type).
• offsets: the segment bounds, as in sort_segments.
• k: keys per segment.
• order: the direction and NaN placement.
• sorted: true returns each segment's keys in order; false in no particular order.
• values, indices: receive k slots per segment; segment i's are at i * k..(i + 1) * k.

Notes

• A segment shorter than k fills only its first slots; the others are left as they are.

Examples: Top-k and selection: Top-k per group

argsort_rows Page

pub fn argsort_rows<T: Sortable, I: Index>(
    data: &[T],
    row_len: usize,
    order: Order,
    indices: &mut [I],
)

The positions that sort every row, counted within the row, as crate::argsort gives for one row.

Arguments

• data: the table, row after row (any Sortable type); not changed.
• row_len: the number of keys in a row.
• order: the direction and NaN placement, for example Order::ASCENDING.
• indices: receives one position per key.

Panics

If row_len does not divide data.len() or indices.len() != data.len().

Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for.

sort_rows_indexed Page

pub fn sort_rows_indexed<T: Sortable>(
    data: &[T],
    row_len: usize,
    order: Order,
    values: &mut [T],
    indices: &mut [u64],
)

Sorts every row into values and writes where each sorted key came from into indices, like torch.sort(stable=True): a sort and an argsort in one call.

Arguments

• data: the table, row after row (any Sortable type); not changed.
• row_len: the number of keys in a row.
• order: the direction and NaN placement, for example Order::ASCENDING.
• values: receives the sorted rows.
• indices: receives the positions within each row; equal keys keep their input order.

Panics

If row_len does not divide data.len() or an output does not hold data.len() entries.

kth_rows Page

pub fn kth_rows<T: Sortable>(
    data: &[T],
    row_len: usize,
    k: usize,
    order: Order,
    nan_first: bool,
    values: &mut [T],
    indices: &mut [u64],
)

The key at position k of every sorted row and its position in the row, like torch.kthvalue. With k = (row_len - 1) / 2 this is each row's median.

Arguments

• data: the table, row after row (any Sortable type); not changed.
• row_len: the number of keys in a row.
• k: the sorted position, below row_len.
• order: the direction and NaN placement, for example Order::ASCENDING.
• nan_first: true returns a row's first NaN when it holds one, as torch.median does.
• values, indices: receive one entry per row.

Example

use kwker::Order;

let t = [5, 1, 3, 9, 7, 8];
let (mut med, mut at) = (vec![0; 2], vec![0u64; 2]);
kwker::kth_rows(&t, 3, 1, Order::ASCENDING, false, &mut med, &mut at);
assert_eq!(med, [3, 8]);
assert_eq!(at, [2, 2]);

Panics

If row_len does not divide data.len(), k >= row_len, or an output does not hold one entry per row.

Notes

• Among equal keys the earlier position counts first.

argsort_segments Page

pub fn argsort_segments<T: Sortable, I: Index, J: Index>(
    data: &[T],
    offsets: &[J],
    order: Order,
    indices: &mut [I],
)

The positions that sort every segment, counted within the segment, written at the segment's place in indices.

Arguments

• data: the keys (any Sortable type); not changed.
• offsets: the segment bounds, as in sort_segments.
• order: the direction and NaN placement.
• indices: one slot per key; slots outside the segments are left as they are.

argpartition_rows Page

pub fn argpartition_rows<T: Sortable, I: Index>(
    data: &[T],
    row_len: usize,
    kth: usize,
    order: Order,
    indices: &mut [I],
)

numpy.argpartition for every row: per row, the positions arranged so that slot kth holds the position of the row's key at sorted position kth, the slots before it the positions of smaller keys and the slots after it the others.

Arguments

• data: the table, row after row (any Sortable type); not changed.
• row_len: the number of keys in a row.
• kth: the sorted position, below row_len.
• order: the direction and NaN placement.
• indices: receives one position (within the row) per key.

Panics

If row_len does not divide data.len(), kth >= row_len, or indices.len() != data.len().

Notes

• The slots before kth are in no particular order; those after it are in increasing position order.

argpartition_segments Page

pub fn argpartition_segments<T: Sortable, I: Index, J: Index>(
    data: &[T],
    offsets: &[J],
    kth: usize,
    order: Order,
    indices: &mut [I],
)

argpartition_rows for segments of any length, written at each segment's place in indices.

Arguments

• data: the keys (any Sortable type); not changed.
• offsets: the segment bounds, as in sort_segments.
• kth: the sorted position.
• order: the direction and NaN placement.
• indices: one slot per key.

Notes

• A segment with kth + 1 keys or fewer gets its full argsort.

sort_rows_mt Page

pub fn sort_rows_mt<T: Sortable + Send + Sync>(
    data: &mut [T],
    row_len: usize,
    order: Order,
    threads: usize,
)

sort_rows on several threads; the result is the same.

Arguments

• data, row_len, order: as in sort_rows.
• threads: the number of threads; 0 uses the default (crate::default_threads).

Remarks: Not stable (rule 5): keys that are equal but can be told apart (NaNs with different bits) may change places. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for. Threads change only the speed: the result follows the same rules on any thread count (rule 10).

argsort_rows_mt Page

pub fn argsort_rows_mt<T: Sortable + Send + Sync, I: Index>(
    data: &[T],
    row_len: usize,
    order: Order,
    indices: &mut [I],
    threads: usize,
)

argsort_rows on several threads; the result is the same.

Arguments

• data, row_len, order, indices: as in argsort_rows.
• threads: the number of threads; 0 uses the default (crate::default_threads).

Remarks: Stable (rule 6): equal keys keep their input order, so the same input always gives the same positions. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for. Threads change only the speed: the result follows the same rules on any thread count (rule 10).

sort_rows_indexed_mt Page

pub fn sort_rows_indexed_mt<T: Sortable + Send + Sync>(
    data: &[T],
    row_len: usize,
    order: Order,
    values: &mut [T],
    indices: &mut [u64],
    threads: usize,
)

sort_rows_indexed on several threads; the result is the same.

Arguments

• data, row_len, order, values, indices: as in sort_rows_indexed.
• threads: the number of threads; 0 uses the default (crate::default_threads).

top_k_rows_mt Page

pub fn top_k_rows_mt<T: Sortable + Send + Sync, I: Index>(
    data: &[T],
    row_len: usize,
    k: usize,
    order: Order,
    sorted: bool,
    values: &mut [T],
    indices: &mut [I],
    threads: usize,
)

top_k_rows on several threads; the result is the same.

Arguments

• data, row_len, k, order, sorted, values, indices: as in top_k_rows.
• threads: the number of threads; 0 uses the default (crate::default_threads).

Remarks: The first k keys of the stable order and their positions; equal keys keep their input order (rule 9). Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for. Threads change only the speed: the result follows the same rules on any thread count (rule 10).

sort_segments_mt Page

pub fn sort_segments_mt<T: Sortable + Send + Sync, I: Index>(
    data: &mut [T],
    offsets: &[I],
    order: Order,
    threads: usize,
)

sort_segments on several threads; the result is the same.

Arguments

• data, offsets, order: as in sort_segments.
• threads: the number of threads; 0 uses the default (crate::default_threads).

Remarks: Not stable (rule 5): keys that are equal but can be told apart (NaNs with different bits) may change places. Keys follow the key order: -0.0 before +0.0, every NaN in one block, last unless NaNs-first is asked for. Threads change only the speed: the result follows the same rules on any thread count (rule 10).

Along an axis

sort_axis_strided Page

pub unsafe fn sort_axis_strided<T: Sortable>(
    base: *mut T,
    shape: &[usize],
    strides: &[isize],
    axis: usize,
    order: Order,
)

Sorts every lane along axis of a strided N-dimensional array in place, like numpy.sort(a, axis).

Arguments

• base: pointer to the array's first element (any Sortable type).
• shape: the array's dimensions.
• strides: the step between neighbours in each dimension, in elements (any sign).
• axis: the dimension to sort along.
• order: the direction and NaN placement, for example Order::ASCENDING.

Safety

Every element reachable through shape and strides from base must be valid and writable, and no two index tuples may address the same element (a stride of 0 along axis excepted).

sort_axis Page

pub fn sort_axis<T: Sortable>(data: &mut [T], shape: &[usize], axis: usize, order: Order)

Sorts every lane along axis of a row-major (C-order) array in place, like numpy.sort(a, axis).

Arguments

• data: the array's elements in row-major order (any Sortable type).
• shape: the array's dimensions; their product must be data.len().
• axis: the dimension to sort along.
• order: the direction and NaN placement, for example Order::ASCENDING.

Example

use kwker::Order;

// a 2 x 3 array sorted down its columns (axis 0)
let mut a = vec![4, 2, 9, 1, 5, 3];
kwker::sort_axis(&mut a, &[2, 3], 0, Order::ASCENDING);
assert_eq!(a, [1, 2, 3, 4, 5, 9]);

Panics

If the shape's product is not data.len() or axis >= shape.len().

argsort_axis_strided Page

pub unsafe fn argsort_axis_strided<T: Sortable, I: Index>(
    base: *const T,
    shape: &[usize],
    strides: &[isize],
    axis: usize,
    order: Order,
    out: *mut I,
    out_strides: &[isize],
)

The positions that sort every lane along axis of a strided array, counted within the lane, like numpy.argsort(a, axis). Equal keys keep their input order.

Arguments

• base, shape, strides, axis, order: the input, as in sort_axis_strided.
• out: pointer to the output array, of the same shape.
• out_strides: the output's strides, in elements.

Safety

Every element reachable through shape / strides from base must be readable, every element through shape / out_strides from out writable, and no two index tuples may address the same output element.

sort_axis_indexed_strided Page

pub unsafe fn sort_axis_indexed_strided<T: Sortable, I: Index>(
    base: *const T,
    shape: &[usize],
    strides: &[isize],
    axis: usize,
    order: Order,
    vals: *mut T,
    out: *mut I,
    out_strides: &[isize],
)

Sorts every lane along axis of a strided array into vals and writes each sorted key's position in its lane into out, like torch.sort(x, dim, stable=True), without a transposed copy.

Arguments

• base, shape, strides, axis, order: the input, as in sort_axis_strided.
• vals: pointer to the sorted-values output, of the input's shape.
• out: pointer to the positions output, of the same shape; null for the sorted values only.
• out_strides: the strides of both outputs, in elements.

Safety

Every element reachable through shape / strides from base must be readable, every element through shape / out_strides from vals and (unless null) out writable, no two index tuples may address the same output element, and the outputs may not overlap each other or the input.

kth_axis_strided Page

pub unsafe fn kth_axis_strided<T: Sortable>(
    base: *const T,
    shape: &[usize],
    strides: &[isize],
    axis: usize,
    k: usize,
    order: Order,
    nan_first: bool,
    vals: *mut T,
    out: *mut u64,
    out_strides: &[isize],
)

The key at sorted position k of every lane along axis of a strided array, and its position in the lane, like torch.kthvalue(x, k + 1, dim) or torch.median(x, dim).

Arguments

• base, shape, strides, axis, order: the input, as in sort_axis_strided.
• k: the sorted position, counted from 0.
• nan_first: true returns a lane's first NaN when it holds one, as torch.median does.
• vals, out: pointers to the value and position outputs, one entry per lane.
• out_strides: the outputs' strides for the input's shape; the entry for axis is not used.

Safety

Every element reachable through shape / strides from base must be readable, and every result slot through the other dimensions of out_strides from vals and out writable and distinct.

quantile_axis_strided Page

pub unsafe fn quantile_axis_strided<T: Sortable + Send + Sync>(
    base: *const T,
    shape: &[usize],
    strides: &[isize],
    axis: usize,
    qs: &[f64],
    ignore_nan: bool,
    interp: Interpolation,
    below: *mut T,
    above: *mut T,
    weight: *mut f64,
    out_strides: &[isize],
    threads: usize,
)

The order statistics behind torch.quantile(x, qs, dim) for every lane along axis of a strided array: for each quantile the two neighbouring keys and the weight between them (the result is below + weight * (above - below), as crate::quantile_lane gives for one lane).

Arguments

• base, shape, strides, axis: the input, as in sort_axis_strided.
• qs: the quantiles, each in [0, 1].
• ignore_nan: true skips NaNs, like torch.nanquantile.
• interp: the interpolation rule, as in torch.quantile.
• below, above, weight: pointers to the outputs; each lane gets a row of qs.len() entries.
• out_strides: the outputs' strides (in rows) for the input's shape; the entry for axis is not used.
• threads: the number of threads; 0 uses the default.

Safety

Every element reachable through shape / strides from base must be readable, and every output row writable.

quantile_axis_strided_ex Page

pub unsafe fn quantile_axis_strided_ex<T: Sortable + Send + Sync>(
    base: *const T,
    shape: &[usize],
    strides: &[isize],
    axis: usize,
    qs: &[f64],
    ignore_nan: bool,
    interp: Interpolation,
    f32_ranks: bool,
    below: *mut T,
    above: *mut T,
    weight: *mut f64,
    out_strides: &[isize],
    threads: usize,
)

quantile_axis_strided that can match older torch releases bit for bit on float32 input.

Arguments

• f32_ranks: true computes the ranks q * (n - 1) in float32, as torch 2.12 and earlier do for float32 input; the other arguments are as in quantile_axis_strided.

Safety

As quantile_axis_strided.

argsort_axis Page

pub fn argsort_axis<T: Sortable, I: Index>(
    data: &[T],
    shape: &[usize],
    axis: usize,
    order: Order,
    out: &mut [I],
)

The positions that sort every lane along axis of a row-major (C-order) array, counted within the lane, like numpy.argsort(a, axis). Equal keys keep their input order.

Arguments

• data: the array's elements in row-major order (any Sortable type); not changed.
• shape: the array's dimensions; their product must be data.len().
• axis: the dimension to sort along.
• order: the direction and NaN placement.
• out: receives the positions, row-major, same shape.

Panics

If data or out does not hold the shape's product of elements.

MAX_DIMS Page

pub const MAX_DIMS: usize = 64;

At most this many dimensions (NumPy's limit): the lane iteration keeps its state on the stack.

Searching

lower_bound Page

pub fn lower_bound<T: Sortable>(sorted: &[T], key: T, order: Order) -> usize

The first position in a sorted slice whose key does not come before key, like C++ std::lower_bound.

Arguments

• sorted: keys sorted in order (any Sortable type).
• key: the key to look for.
• order: the order sorted is in, for example Order::ASCENDING.

Example

use kwker::Order;

assert_eq!(kwker::lower_bound(&[10, 20, 20, 30], 20, Order::ASCENDING), 1);

upper_bound Page

pub fn upper_bound<T: Sortable>(sorted: &[T], key: T, order: Order) -> usize

The first position in a sorted slice whose key comes after key, like C++ std::upper_bound.

Arguments

• sorted: keys sorted in order (any Sortable type).
• key: the key to look for.
• order: the order sorted is in, for example Order::ASCENDING.

Example

use kwker::Order;

assert_eq!(kwker::upper_bound(&[10, 20, 20, 30], 20, Order::ASCENDING), 3);

equal_range Page

pub fn equal_range<T: Sortable>(sorted: &[T], key: T, order: Order) -> Range<usize>

The positions in a sorted slice that hold key.

Arguments

• sorted: keys sorted in order (any Sortable type).
• key: the key to look for.
• order: the order sorted is in, for example Order::ASCENDING.

Returns

The range from lower_bound to upper_bound; empty when key is not there.

Notes

• -0.0 and +0.0 count as equal, as in NumPy.

searchsorted_into Page

pub fn searchsorted_into<T: Sortable>(
    sorted: &[T],
    queries: &[T],
    side: Side,
    order: Order,
    out: &mut [u64],
)

Finds where each query would go in a sorted slice, like numpy.searchsorted and torch.searchsorted.

Arguments

• sorted: keys sorted in order (any Sortable type; the order is not checked).
• queries: the keys to look up.
• side: Side::Left gives each query's lower_bound; Side::Right its upper_bound.
• order: the order sorted is in.
• out: receives one position per query.

Panics

If out.len() != queries.len().

Remarks: -0.0 and +0.0 compare equal here, as in NumPy (rule 14).

searchsorted Page

pub fn searchsorted<T: Sortable>(sorted: &[T], queries: &[T], side: Side, order: Order) -> Vec<u64>

Finds where each query would go in a sorted slice, like numpy.searchsorted and torch.searchsorted.

Arguments

• sorted: keys sorted in order (any Sortable type; the order is not checked).
• queries: the keys to look up.
• side: Side::Left gives each query's lower_bound; Side::Right its upper_bound.
• order: the order sorted is in.

Returns

One position per query.

Example

use kwker::{Order, Side};

let at = kwker::searchsorted(&[10, 20, 30], &[5, 20, 35], Side::Left, Order::ASCENDING);
assert_eq!(at, [0, 1, 3]);

Remarks: -0.0 and +0.0 compare equal here, as in NumPy (rule 14).

Examples: Searching sorted data: Where does a value go? searchsorted

bucketize Page

pub fn bucketize<T: Sortable>(values: &[T], boundaries: &[T], right: bool, order: Order) -> Vec<u64>

The bucket of every value between sorted boundaries, like torch.bucketize.

Arguments

• values: the values to place (any Sortable type).
• boundaries: the bucket edges, sorted in order.
• right: false puts a value equal to an edge in the bucket below it; true in the bucket above it.
• order: the order boundaries is in, for example Order::ASCENDING.

Returns

One bucket number per value, from 0 to boundaries.len().

Example

use kwker::Order;

let b = kwker::bucketize(&[1, 5, 10], &[2, 6], false, Order::ASCENDING);
assert_eq!(b, [0, 1, 2]);

Remarks: -0.0 and +0.0 compare equal here, as in NumPy (rule 14).

Examples: Searching sorted data: Which bucket? bucketize

bucket_counts Page

pub fn bucket_counts<T: Sortable>(
    values: &[T],
    boundaries: &[T],
    right: bool,
    order: Order,
) -> Vec<u64>

Counts the values in each bucket of bucketize: a histogram with the edges you give.

Arguments

• values, boundaries, right, order: as in bucketize.

Returns

boundaries.len() + 1 counts.

Remarks: -0.0 and +0.0 compare equal here, as in NumPy (rule 14).

Examples: Searching sorted data: How many in each bucket? bucket_counts

bucket_counts_into Page

pub fn bucket_counts_into<T: Sortable>(
    values: &[T],
    boundaries: &[T],
    right: bool,
    order: Order,
    counts: &mut [u64],
)

bucket_counts into a buffer you provide.

Arguments

• values, boundaries, right, order: as in bucketize.
• counts: receives boundaries.len() + 1 counts (overwritten).

Panics

If counts.len() != boundaries.len() + 1.

Remarks: -0.0 and +0.0 compare equal here, as in NumPy (rule 14).

Side Page

pub enum Side {
    Left,
    Right,
}

Which end of a run of equal keys searchsorted reports: Left is the first position whose key does not come before the query (lower_bound); Right is the first position whose key comes after it (upper_bound).

Variants

• Left: The lower bound.
• Right: The upper bound.

Ranks

rank_into Page

pub fn rank_into<T: Sortable>(v: &[T], order: Order, ties: RankTies, out: &mut [u64])

rank into a buffer you provide.

Arguments

• v: the keys (any Sortable type); not changed.
• order: the direction and NaN placement, for example Order::ASCENDING.
• ties: how equal keys are ranked (see RankTies).
• out: receives one rank per key.

Panics

If out.len() != v.len().

Remarks: Ordinal ranks give equal keys increasing ranks in input order (rule 6). Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).

rank Page

pub fn rank<T: Sortable>(v: &[T], order: Order, ties: RankTies) -> Vec<u64>

The rank of every key, from 1, like SQL RANK() or pandas rank().

Arguments

• v: the keys (any Sortable type); not changed.
• order: the direction and NaN placement, for example Order::ASCENDING (rank 1 = the smallest).
• ties: how equal keys are ranked (see RankTies).

Returns

One rank per key, in input order.

Example

use kwker::{Order, RankTies};

let r = kwker::rank(&[30, 10, 20, 10], Order::ASCENDING, RankTies::Min);
assert_eq!(r, [4, 1, 3, 1]);

Notes

• Keys are equal when their values are: -0.0 equals +0.0, and all NaNs are one value.

Remarks: Ordinal ranks give equal keys increasing ranks in input order (rule 6). Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).

Examples: Order and ranking: Ranks

rank_average Page

pub fn rank_average<T: Sortable>(v: &[T], order: Order) -> Vec<f64>

Average ranks, from 1: equal keys share the mean of their group's ranks, like scipy.stats.rankdata and pandas rank(method="average"). Spearman's correlation uses these.

Arguments

• v: the keys (any Sortable type); not changed.
• order: the direction and NaN placement, for example Order::ASCENDING.

Returns

One rank per key, in input order.

Remarks: Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).

Examples: Order and ranking: Ranks

percent_rank Page

pub fn percent_rank<T: Sortable>(v: &[T], order: Order) -> Vec<f64>

SQL PERCENT_RANK(): (rank - 1) / (n - 1) for every key, between 0 and 1, with equal keys sharing their lowest rank.

Arguments

• v: the keys (any Sortable type); not changed.
• order: the direction and NaN placement, for example Order::ASCENDING.

Returns

One value per key, in input order; all 0 for fewer than two keys.

Remarks: Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).

Examples: Order and ranking: Ranks

inverse_ranks Page

pub fn inverse_ranks(ranks: &[u64]) -> Option<Vec<u64>>

Turns ranks back into a sort order: from ranks 1..=n (as rank with RankTies::Ordinal returns), the positions that sort the keys, as crate::argsort would give.

Arguments

• ranks: one rank per key, each of 1..=n exactly once.

Returns

The positions, or None if ranks is not a permutation of 1..=n.

rank_rows Page

pub fn rank_rows<T: Sortable>(
    data: &[T],
    row_len: usize,
    order: Order,
    ties: RankTies,
    out: &mut [u64],
)

rank within every row of a row-major table.

Arguments

• data: the table, row after row (any Sortable type); not changed.
• row_len: the number of keys in a row.
• order: the direction and NaN placement.
• ties: how equal keys are ranked (see RankTies).
• out: receives one rank per key.

Panics

If row_len does not divide data.len() or out.len() != data.len().

count_inversions Page

pub fn count_inversions<T: Sortable>(v: &[T], order: Order) -> u64

Counts the pairs of keys that are out of order: positions i < j whose keys come the other way round in order. This is the number of discordant pairs in Kendall's tau.

Arguments

• v: the keys (any Sortable type); not changed.
• order: the direction and NaN placement, for example Order::ASCENDING.

Example

use kwker::Order;

assert_eq!(kwker::count_inversions(&[3, 1, 2], Order::ASCENDING), 2);

Notes

• Equal keys are never an inversion; -0.0 equals +0.0, and all NaNs are one value.

RankTies Page

pub enum RankTies {
    Ordinal,
    Min,
    Max,
    Dense,
}

How rank ranks equal keys.

Variants

• Ordinal: Every key its own rank, equal keys in index order (the stable order): a permutation of 1..=n.
• Min: Equal keys share the lowest rank of their group (SQL RANK, pandas method="min").
• Max: Equal keys share the highest rank of their group (pandas method="max").
• Dense: Equal keys share one rank and the ranks have no gaps (SQL DENSE_RANK, pandas method="dense").

Quantiles

select_ranks Page

pub fn select_ranks<T: Sortable>(v: &mut [T], ranks: &[usize], order: Order)

Several crate::select_nth calls at once: afterwards v[r] holds the key a full sort would put there, for every r in ranks, and the keys between two selected positions lie between their keys.

Arguments

• v: the keys (any Sortable type).
• ranks: the positions to fill, each below v.len(); any order, repeats allowed.
• order: the direction and NaN placement, for example Order::ASCENDING.

Panics

If a rank is v.len() or more.

quantile_lane_mt Page

pub fn quantile_lane_mt<T: Sortable + Send + Sync>(
    v: &[T],
    qs: &[f64],
    ignore_nan: bool,
    interp: Interpolation,
    below: &mut [T],
    above: &mut [T],
    weight: &mut [f64],
    threads: usize,
)

quantile_lane of one large lane on several threads; v is not changed.

Arguments

• v: the values (any Sortable type).
• qs, ignore_nan, interp, below, above, weight: as in quantile_lane.
• threads: the number of threads; 0 uses the default.

quantile_lane Page

pub fn quantile_lane<T: Sortable>(
    v: &mut [T],
    qs: &[f64],
    ignore_nan: bool,
    interp: Interpolation,
    below: &mut [T],
    above: &mut [T],
    weight: &mut [f64],
    ranks: &mut Vec<usize>,
)

The order statistics behind torch.quantile for one lane of values: for each quantile, the two neighbouring keys and the weight between them. The quantile is below + weight * (above - below).

Arguments

• v: the values (any Sortable type); reordered.
• qs: the quantiles, each in [0, 1].
• ignore_nan: true skips NaNs, like torch.nanquantile.
• interp: the interpolation rule (see Interpolation).
• below, above, weight: receive one entry per quantile.
• ranks: scratch space, reused between calls.

Notes

• A lane holding a NaN (with ignore_nan: holding only NaNs) gives NaN for every quantile, as torch does.

quantiles Page

pub fn quantiles<T: Sortable>(v: &mut [T], qs: &[f64], order: Order) -> Vec<T>

The keys at the given quantiles: quantile q is the key at sorted position floor(q * (n - 1)).

Arguments

• v: the keys (any Sortable type); reordered as select_ranks does.
• qs: the quantiles, each in [0, 1].
• order: the direction and NaN placement, for example Order::ASCENDING.

Returns

One key per quantile.

Example

use kwker::Order;

let mut v: Vec<i32> = (1..=11).collect();
assert_eq!(kwker::quantiles(&mut v, &[0.0, 0.5, 1.0], Order::ASCENDING), [1, 6, 11]);

Panics

If v is empty or a quantile is outside [0, 1].

median Page

pub fn median<T: Sortable>(v: &mut [T], order: Order) -> T

The median of v; for an even count, the lower of the two middle keys.

Arguments

• v: the keys (any Sortable type); reordered as crate::select_nth does.
• order: the direction and NaN placement, for example Order::ASCENDING.

Example

use kwker::Order;

let mut v = vec![5, 1, 4, 2];
assert_eq!(kwker::median(&mut v, Order::ASCENDING), 2);

Panics

If v is empty.

Interpolation Page

pub enum Interpolation {
    Linear,
    Lower,
    Higher,
    Midpoint,
    Nearest,
}

How torch.quantile interpolates between the two keys around a quantile.

Variants

• Linear: lower + (higher - lower) x the fractional part of the rank
• Lower: the lower order statistic
• Higher: the higher order statistic
• Midpoint: their mean
• Nearest: the nearer one (ties to the even rank, as torch)

Unique values

unique_inverse Page

pub fn unique_inverse<T: Sortable + Send + Sync>(
    data: &[T],
    inverse: Option<&mut [u64]>,
    want_counts: bool,
    threads: usize,
) -> (Vec<T>, Vec<u64>)

The distinct keys of data, sorted, like numpy.unique and torch.unique, with optional group numbers and counts.

Arguments

• data: the keys (any Sortable type); not changed.
• inverse: if given, receives each key's position among the distinct keys (one entry per key).
• want_counts: true also counts each distinct key.
• threads: the number of threads; 1 uses the calling thread only.

Returns

(values, counts): the distinct keys, smallest first, and their counts (empty unless want_counts).

Example

let mut inv = vec![0u64; 4];
let (vals, counts) = kwker::unique_inverse(&[3, 1, 3, 2], Some(&mut inv), true, 1);
assert_eq!(vals, [1, 2, 3]);
assert_eq!(counts, [1, 1, 2]);
assert_eq!(inv, [2, 0, 2, 1]);

Panics

If inverse is given and its length differs from data.len().

Notes

• -0.0 and +0.0 are one key (given as the zero that comes first in the input); every NaN is a key of its own, listed last. Both follow torch.

unique_into Page

pub fn unique_into<T: Sortable + Send + Sync>(data: &[T], out: &mut [T], threads: usize) -> usize

The distinct keys of data, sorted, into a buffer you provide.

Arguments

• data: the keys (any Sortable type); not changed.
• out: as long as data; receives the distinct keys in out[..m].
• threads: the number of threads; 1 uses the calling thread only.

Returns

m, the number of distinct keys.

Panics

If out.len() != data.len().

Remarks: -0.0 and +0.0 are one value; every NaN is a value of its own, listed last (rule 15).

unique_inverse_into Page

pub fn unique_inverse_into<T: Sortable + Send + Sync>(
    data: &[T],
    values: &mut [T],
    inverse: Option<&mut [u64]>,
    counts: Option<&mut [u64]>,
    threads: usize,
) -> usize

unique_inverse into buffers you provide.

Arguments

• data: the keys (any Sortable type); not changed.
• values: as long as data; receives the distinct keys in values[..m].
• inverse: if given, receives each key's position among the distinct keys.
• counts: if given, as long as data; receives the counts in counts[..m].
• threads: the number of threads; 1 uses the calling thread only.

Returns

m, the number of distinct keys.

Panics

If a buffer given is not as long as data.

Sorted sets

set_op Page

pub fn set_op<T: Sortable>(a: &[T], b: &[T], op: SetOp, multiset: bool, order: Order) -> Vec<T>

A set operation on two sorted slices: intersection, union, difference or symmetric difference. The result is sorted too.

Arguments

• a, b: keys sorted in order (any Sortable type; the order is not checked).
• op: the operation (see SetOp).
• multiset: false treats each input as a set (every value at most once in the result); true counts copies, as C++ std::set_intersection and friends do: a value with ca copies in a and cb in b appears min(ca, cb) times in the intersection, max(ca, cb) in the union, max(ca - cb, 0) in the difference and |ca - cb| in the symmetric difference.
• order: the order both inputs are in, for example Order::ASCENDING.

Example

use kwker::{Order, SetOp};

let both = kwker::set_op(&[1, 2, 2, 3], &[2, 2, 4], SetOp::Intersection, false, Order::ASCENDING);
assert_eq!(both, [2]);
let both = kwker::set_op(&[1, 2, 2, 3], &[2, 2, 4], SetOp::Intersection, true, Order::ASCENDING);
assert_eq!(both, [2, 2]);

Notes

• Values compare as NumPy compares them: -0.0 equals +0.0, and all NaNs are one value.

Remarks: Equal values are one key here, as in NumPy: -0.0 and +0.0 are equal, and so are all NaNs (rule 13).

Examples: Groups, merges and sets: Set operations

set_intersection Page

pub fn set_intersection<T: Sortable>(a: &[T], b: &[T], multiset: bool, order: Order) -> Vec<T>

The keys in both a and b: set_op with SetOp::Intersection.

Arguments

• a, b, multiset, order: as in set_op.

set_union Page

pub fn set_union<T: Sortable>(a: &[T], b: &[T], multiset: bool, order: Order) -> Vec<T>

The keys in a or b: set_op with SetOp::Union.

Arguments

• a, b, multiset, order: as in set_op.

set_difference Page

pub fn set_difference<T: Sortable>(a: &[T], b: &[T], multiset: bool, order: Order) -> Vec<T>

The keys in a but not in b: set_op with SetOp::Difference.

Arguments

• a, b, multiset, order: as in set_op.

set_symmetric_difference Page

pub fn set_symmetric_difference<T: Sortable>(
    a: &[T],
    b: &[T],
    multiset: bool,
    order: Order,
) -> Vec<T>

The keys in exactly one of a and b: set_op with SetOp::SymmetricDifference.

Arguments

• a, b, multiset, order: as in set_op.

intersection_indices Page

pub fn intersection_indices<T: Sortable>(
    a: &[T],
    b: &[T],
    multiset: bool,
    order: Order,
) -> (Vec<u64>, Vec<u64>)

Where the common keys of two sorted slices are, in each of them, like numpy.intersect1d(return_indices=True). Use it to line up data that belongs to the keys.

Arguments

• a, b: keys sorted in order (any Sortable type).
• multiset: false gives each common value's first position in each input; true pairs up the first min(ca, cb) copies.
• order: the order both inputs are in.

Returns

(positions in a, positions in b), in increasing order.

row_intersect_count Page

pub fn row_intersect_count<T: Sortable>(a: &[T], ka: usize, b: &[T], kb: usize, out: &mut [u64])

For every row, how many keys two tables have in common: for example recall@k, retrieved ids against the true ones.

Arguments

• a: rows of ka keys each, row after row (any Sortable type).
• ka: the number of keys in a row of a.
• b: the same number of rows, of kb keys each.
• kb: the number of keys in a row of b.
• out: receives one count per row.

Panics

If the shapes do not agree.

Notes

• Counts are exact when the keys within each row are distinct; values compare as values (-0.0 equals +0.0, all NaNs are one value).

row_unique_count Page

pub fn row_unique_count<T: Sortable>(a: &[T], k: usize, out: &mut [u64])

The number of distinct values in every row of a row-major table.

Arguments

• a: the table, rows of k keys (any Sortable type).
• k: the number of keys in a row.
• out: receives one count per row.

Panics

If a.len() != out.len() * k.

Notes

• Values compare as values: -0.0 equals +0.0, and all NaNs are one value.

isin_into Page

pub fn isin_into<T: Sortable>(elements: &[T], test: &[T], invert: bool, out: &mut [bool])

Tests every element for membership in a set of keys, like numpy.isin and torch.isin.

Arguments

• elements: the keys to test (any Sortable type).
• test: the set, in any order.
• invert: true gives true for elements that are not in test.
• out: receives one answer per element.

Example

let mut hit = vec![false; 4];
kwker::isin_into(&[1, 5, 3, 7], &[3, 1], false, &mut hit);
assert_eq!(hit, [true, false, true, false]);

Panics

If out.len() != elements.len().

Notes

• -0.0 equals +0.0; a NaN equals nothing, as in torch and NumPy.

SetOp Page

pub enum SetOp {
    Intersection,
    Union,
    Difference,
    SymmetricDifference,
}

Which operation set_op computes.

Variants

• Intersection: Keys in both.
• Union: Keys in either.
• Difference: a minus b.
• SymmetricDifference: Keys in exactly one of them.

Merging

merge Page

pub fn merge<T: Sortable>(a: &[T], b: &[T], out: &mut [T], order: Order)

Merges two sorted slices into one sorted output. On equal keys, a's come first.

Arguments

• a, b: keys sorted in order (any Sortable type).
• out: receives the a.len() + b.len() merged keys.
• order: the order both inputs are in, for example Order::ASCENDING.

Example

use kwker::Order;

let mut out = vec![0; 5];
kwker::merge(&[1, 4, 6], &[2, 3], &mut out, Order::ASCENDING);
assert_eq!(out, [1, 2, 3, 4, 6]);

merge_kv Page

pub fn merge_kv<K: Sortable, V: Copy>(
    a_keys: &[K],
    a_values: &[V],
    b_keys: &[K],
    b_values: &[V],
    out_keys: &mut [K],
    out_values: &mut [V],
    order: Order,
)

Merges two sorted key-value sequences; each value moves with its key. On equal keys, a's come first.

Arguments

• a_keys, a_values: the first sequence, keys sorted in order.
• b_keys, b_values: the second sequence.
• out_keys, out_values: receive the merged pairs.
• order: the order both inputs are in.

merge_in_place Page

pub fn merge_in_place<T: Sortable>(v: &mut [T], mid: usize, order: Order)

Merges the sorted halves v[..mid] and v[mid..] in place. On equal keys, the first half's come first.

Arguments

• v: the keys (any Sortable type), both halves sorted in order.
• mid: where the second half starts.
• order: the order the halves are in.

Notes

• Uses a buffer the size of the smaller half.

kway_merge Page

pub fn kway_merge<T: Sortable>(runs: &[&[T]], out: &mut [T], order: Order)

Merges any number of sorted runs into one sorted output. Equal keys keep run order, then position.

Arguments

• runs: the runs, each sorted in order (any Sortable type).
• out: receives all the keys; its length is the runs' total.
• order: the order the runs are in, for example Order::ASCENDING.

Example

use kwker::Order;

let mut out = vec![0; 6];
kwker::kway_merge(&[&[1, 5], &[2, 6], &[3, 4]], &mut out, Order::ASCENDING);
assert_eq!(out, [1, 2, 3, 4, 5, 6]);

Examples: Groups, merges and sets: Merge sorted lists: kway_merge

kway_merge_kv Page

pub fn kway_merge_kv<K: Sortable, V: Copy>(
    keys: &[&[K]],
    values: &[&[V]],
    out_keys: &mut [K],
    out_values: &mut [V],
    order: Order,
)

kway_merge of key-value runs: each value moves with its key.

Arguments

• keys: the key runs, each sorted in order.
• values: one value run per key run, of the same lengths.
• out_keys, out_values: receive the merged pairs.
• order: the order the runs are in.

kway_merge_with Page

pub fn kway_merge_with<T: Sortable, F: FnMut(usize, usize)>(runs: &[&[T]], order: Order, emit: F)

The merged order of sorted runs, without moving anything: calls emit(run, index) for every element in merged order, so you can move records, rows or other data along.

Arguments

• runs: the runs, each sorted in order (any Sortable type).
• order: the order the runs are in.
• emit: called once per element with its run number and its position in that run.

Notes

• Equal keys come in run order, then position order, as in kway_merge.

merge_sorted_into Page

pub fn merge_sorted_into<T: Sortable>(sorted: &mut Vec<T>, new: &mut [T], order: Order)

Adds new keys to a sorted vector: sorts new and merges it in, without sorting sorted again.

Arguments

• sorted: keys already sorted in order; grows by new.len().
• new: the keys to add; sorted in place.
• order: the order, for example Order::ASCENDING.

Notes

• On equal keys, those already in sorted come first.

Several sort keys

lexsort Page

pub fn lexsort(keys: &[(&dyn KeyColumn, Order)]) -> Permutation

The order that sorts rows by several key columns: by the first column, ties by the second, and so on, each column in its own order. Apply the result to every column of the table with Permutation::apply.

Arguments

• keys: the key columns (slices or vectors of any Sortable type) with their orders, most significant first.

Returns

A Permutation; rows with equal keys in every column keep their input order.

Example

use kwker::Order;

let city = vec![2, 1, 2];
let age = vec![30, 40, 20];
let p = kwker::lexsort(&[(&city, Order::ASCENDING), (&age, Order::DESCENDING)]);
assert_eq!(p.as_slice(), [1, 0, 2]);

Panics

If the columns have different lengths.

Examples: Order and ranking: Sort by several columns

lexsort_mt Page

pub fn lexsort_mt(keys: &[(&dyn KeyColumn, Order)], threads: usize) -> Permutation

lexsort on several threads; the result is the same.

Arguments

• keys: as in lexsort.
• threads: the number of threads; 0 uses the default.

lexsort_into Page

pub fn lexsort_into(keys: &[(&dyn KeyColumn, Order)], threads: usize, out: &mut [u64])

lexsort into a buffer you provide, on several threads.

Arguments

• keys: as in lexsort.
• threads: the number of threads; 0 uses the default.
• out: receives one row position per row.

Panics

If a column's length differs from out.len().

lex_top_k Page

pub fn lex_top_k(keys: &[(&dyn KeyColumn, Order)], k: usize) -> Vec<usize>

The first k rows of lexsort's order without sorting every row, like SQL ORDER BY a, b LIMIT k.

Arguments

• keys: as in lexsort.
• k: how many rows.

Returns

The positions of the first k rows (fewer if there are fewer rows), in order.

Examples: Order and ranking: Sort by several columns

lex_select_nth Page

pub fn lex_select_nth(keys: &[(&dyn KeyColumn, Order)], k: usize) -> usize

The row at position k of lexsort's order, without sorting.

Arguments

• keys: as in lexsort.
• k: the position, below the number of rows.

Returns

The row's position in the input.

Panics

If k is not below the number of rows or the columns have different lengths.

KeyColumn Page

pub trait KeyColumn: Sync {
    fn rows(&self) -> usize;
}

A key column for lexsort: any slice or vector of a Sortable key type.

Records and fields

argsort_field Page

pub fn argsort_field<K: Sortable>(
    records: &[u8],
    n: usize,
    stride: usize,
    offset: usize,
    order: Order,
) -> Vec<u64>

The order of fixed-size binary records by one numeric field, without moving the records.

Arguments

• records: the records' bytes, one record after another.
• n: the number of records.
• stride: the size of a record, in bytes.
• offset: where the key field starts in a record, in bytes (it need not be aligned).
• order: the direction and NaN placement, for example Order::ASCENDING.

Returns

One record number per record: record p[0] has the first key. Equal keys keep their input order.

Example

// 3 records of 12 bytes: an id (u32) and a price (f64, unaligned at offset 4)
let mut bytes = Vec::new();
for (id, price) in [(7u32, 2.5f64), (8, -1.0), (9, 0.25)] {
    bytes.extend_from_slice(&id.to_ne_bytes());
    bytes.extend_from_slice(&price.to_ne_bytes());
}
let p = kwker::argsort_field::<f64>(&bytes, 3, 12, 4, kwker::Order::ASCENDING);
assert_eq!(p, vec![1, 2, 0]);

Panics

If n records of stride bytes do not fit in records.

argsort_field_into Page

pub fn argsort_field_into<K: Sortable>(
    records: &[u8],
    n: usize,
    stride: usize,
    offset: usize,
    order: Order,
    out: &mut [u64],
)

argsort_field into a buffer you provide.

Arguments

• records, n, stride, offset, order: as in argsort_field.
• out: receives n record numbers.

top_k_field Page

pub fn top_k_field<K: Sortable>(
    records: &[u8],
    n: usize,
    stride: usize,
    offset: usize,
    k: usize,
    order: Order,
) -> Vec<u64>

The first k records by one numeric field, without sorting them all: SQL ORDER BY field LIMIT k over records that stay where they are.

Arguments

• records, n, stride, offset: as in argsort_field.
• k: how many records.
• order: the direction and NaN placement, for example Order::DESCENDING for the largest.

Returns

The first min(k, n) record numbers, in order. Equal keys keep their input order.

argsort_by_key Page

pub fn argsort_by_key<T, K: Sortable>(v: &[T], order: Order, key: impl FnMut(&T) -> K) -> Vec<u64>

The order of any objects by a numeric key you extract, without moving the objects.

Arguments

• v: the objects, of any type.
• order: the direction and NaN placement, for example Order::ASCENDING.
• key: returns an object's key; called once per object.

Returns

One position per object; equal keys keep their input order. crate::sort_by_extracted_key moves the objects.

take_records Page

pub fn take_records(src: &[u8], record_size: usize, idx: &[u64], dst: &mut [u8])

Copies records by position: record j of dst becomes record idx[j] of src.

Arguments

• src: the source records' bytes.
• record_size: the size of a record, in bytes.
• idx: the source record of each output record; any positions, repeats allowed.
• dst: receives idx.len() records.

Panics

If a position is out of range or dst does not hold idx.len() records.

is_permutation Page

pub fn is_permutation(perm: &[u64]) -> bool

Whether perm holds every position of 0..perm.len() exactly once, as permute_in_place requires.

permute_in_place Page

pub fn permute_in_place<T>(v: &mut [T], perm: &[u64])

Reorders v in place so that position j gets the element that was at perm[j]: applies an argsort's result.

Arguments

• v: the elements, of any type.
• perm: a permutation of 0..v.len().

Example

let mut names = vec!["c", "a", "b"];
kwker::permute_in_place(&mut names, &[1, 2, 0]);
assert_eq!(names, ["a", "b", "c"]);

Panics

If perm is not a permutation of 0..v.len() (nothing is moved).

Notes

• Uses one bit of scratch per element; the elements are swapped, not copied.

Examples: Order and ranking: Reorder records in place

permute_records_in_place Page

pub fn permute_records_in_place(records: &mut [u8], record_size: usize, perm: &[u64])

permute_in_place for raw records of a fixed size.

Arguments

• records: perm.len() records of record_size bytes.
• record_size: the size of a record, in bytes.
• perm: a permutation of 0..perm.len().

Panics

If the sizes do not match or perm is not a permutation (nothing is moved).

sort_by_extracted_key Page

pub fn sort_by_extracted_key<T, K: Sortable>(
    v: &mut [T],
    order: Order,
    key: impl FnMut(&T) -> K,
    how: ObjectMove,
)

Sorts objects of any type by a numeric key you extract. Equal keys keep their input order.

Arguments

• v: the objects; they need not be Clone or Copy.
• order: the direction and NaN placement, for example Order::ASCENDING.
• key: returns an object's key; called once per object.
• how: how the objects move into place (see ObjectMove); ObjectMove::Auto picks.

Notes

• Objects are moved, never duplicated or dropped. sort_with_indices gives the sorting order alone.

sort_objects_by_key Page

pub fn sort_objects_by_key<T, K: Sortable>(v: &mut [T], order: Order, key: impl FnMut(&T) -> K)

Sorts objects of any type by a numeric key you extract. Equal keys keep their input order.

Arguments

• v: the objects; they need not be Clone or Copy.
• order: the direction and NaN placement, for example Order::ASCENDING.
• key: returns an object's key; called once per object.

Example

use kwker::Order;

let mut files = vec![("b.txt".to_string(), 300u64), ("a.txt".to_string(), 100)];
kwker::sort_objects_by_key(&mut files, Order::ASCENDING, |f| f.1);
assert_eq!(files[0].0, "a.txt");

sort_records_by_key Page

pub fn sort_records_by_key<T: Copy, K: Sortable>(
    v: &mut [T],
    order: Order,
    key: impl FnMut(&T) -> K,
)

Sorts Copy records of any size by a numeric key you extract. Equal keys keep their input order.

Arguments

• v: the records.
• order: the direction and NaN placement, for example Order::ASCENDING.
• key: returns a record's key; called once per record.

sort_records_stable Page

pub fn sort_records_stable<K: Sortable, V: Copy>(r: &mut [KeyValue<K, V>])

sort_records that keeps records with equal keys in input order.

Arguments

• r: the records.

Notes

• Uses buffers of about the input's size.

sort_records_stable_by_order Page

pub fn sort_records_stable_by_order<K: Sortable, V: Copy>(r: &mut [KeyValue<K, V>], order: Order)

sort_records_stable in the given order.

Arguments

• r: the records.
• order: the direction and NaN placement, for example Order::DESCENDING.

sort_records Page

pub fn sort_records<K: Sortable, V: Copy>(r: &mut [KeyValue<K, V>])

Sorts KeyValue records by key, smallest first.

Arguments

• r: the records.

Example

use kwker::KeyValue;

let mut r = vec![KeyValue { key: 3, value: 'c' }, KeyValue { key: 1, value: 'a' }];
kwker::sort_records(&mut r);
assert_eq!(r[0].value, 'a');

Notes

• Not stable: records with equal keys may come out in any order (sort_records_stable keeps their order).

sort_records_by_order Page

pub fn sort_records_by_order<K: Sortable, V: Copy>(r: &mut [KeyValue<K, V>], order: Order)

sort_records in the given order.

Arguments

• r: the records.
• order: the direction and NaN placement, for example Order::DESCENDING.

select_nth_records Page

pub fn select_nth_records<K: Sortable, V: Copy>(r: &mut [KeyValue<K, V>], k: usize, order: Order)

select_nth_kv on records: the record a full sort would put at position k moves there, with records of smaller or equal keys before it and the others after it.

Arguments

• r: the records.
• k: the position to fill, below r.len().
• order: the direction and NaN placement.

Panics

If k >= r.len().

partial_sort_records Page

pub fn partial_sort_records<K: Sortable, V: Copy>(r: &mut [KeyValue<K, V>], k: usize, order: Order)

partial_sort_kv on records: puts the k records with the first keys, sorted, at the front.

Arguments

• r: the records.
• k: how many records to sort; k >= r.len() sorts them all.
• order: the direction and NaN placement.

ObjectMove Page

pub enum ObjectMove {
    Auto,
    Gather,
    Cycles,
}

How sort_by_extracted_key moves the objects into their sorted places.

Variants

• Auto: Gather for objects up to 128 bytes, Cycles above (no n x size buffer for large objects).
• Gather: Each object moved once into a buffer in sorted order, then the buffer moved back (n x size bytes of scratch).
• Cycles: The permutation's cycles followed with swaps in place (one bit of scratch per object).

Masked and nullable data

top_k_masked Page

pub fn top_k_masked<T: Sortable>(
    v: &[T],
    mask: &[bool],
    k: usize,
    order: Order,
    sorted: bool,
) -> (Vec<T>, Vec<u64>)

The k first keys among the positions a mask selects, and their positions in v. No fill value or copy of the other keys is needed.

Arguments

• v: the keys (any Sortable type).
• mask: one flag per key; true keys take part.
• k: how many keys.
• order: the direction and NaN placement, for example Order::DESCENDING for the largest.
• sorted: true returns them in order; false in no particular order.

Returns

(values, positions). Equal keys go to the earlier position first.

Example

use kwker::Order;

let (top, at) = kwker::top_k_masked(&[5, 9, 7, 8], &[true, false, true, true], 2, Order::DESCENDING, true);
assert_eq!(top, [8, 7]);
assert_eq!(at, [3, 2]);

Panics

If mask.len() != v.len().

Examples: Top-k and selection: Top-k with a filter

top_k_mask_u8 Page

pub fn top_k_mask_u8<T: Sortable>(
    v: &[T],
    mask: &[u8],
    k: usize,
    order: Order,
    sorted: bool,
) -> (Vec<T>, Vec<u64>)

top_k_masked with one byte per key (nonzero takes part), as NumPy and PyTorch store bool arrays.

Arguments

• v, k, order, sorted: as in top_k_masked.
• mask: one byte per key.

top_k_valid Page

pub fn top_k_valid<T: Sortable>(
    v: &[T],
    validity: &[u8],
    k: usize,
    order: Order,
    sorted: bool,
) -> (Vec<T>, Vec<u64>)

top_k_masked with an Arrow-style validity bitmap (bit set = takes part).

Arguments

• v, k, order, sorted: as in top_k_masked.
• validity: one bit per key, least significant bit first.

argsort_masked Page

pub fn argsort_masked<T: Sortable>(v: &[T], mask: &[bool], order: Order) -> Vec<u64>

The positions that sort the keys a mask selects, without filling the others with a sentinel or copying the array. Equal keys keep their input order.

Arguments

• v: the keys (any Sortable type).
• mask: one flag per key; true keys take part.
• order: the direction and NaN placement, for example Order::ASCENDING.

Returns

One position (into v) per selected key.

argsort_mask_u8 Page

pub fn argsort_mask_u8<T: Sortable>(v: &[T], mask: &[u8], order: Order) -> Vec<u64>

argsort_masked with one byte per key (nonzero takes part).

Arguments

• v, order: as in argsort_masked.
• mask: one byte per key.

argsort_valid Page

pub fn argsort_valid<T: Sortable>(v: &[T], validity: &[u8], order: Order) -> Vec<u64>

argsort_masked with an Arrow-style validity bitmap (bit set = takes part).

Arguments

• v, order: as in argsort_masked.
• validity: one bit per key, least significant bit first.

argsort_where Page

pub fn argsort_where<T: Sortable>(v: &[T], order: Order, pred: impl Fn(&T) -> bool) -> Vec<u64>

argsort_masked of the keys for which pred returns true.

Arguments

• v, order: as in argsort_masked.
• pred: the test for taking part.

sort_masked Page

pub fn sort_masked<T: Sortable>(v: &mut [T], mask: &[bool], order: Order)

Sorts the keys at the positions a mask selects among those positions; the other positions are left as they are.

Arguments

• v: the keys (any Sortable type).
• mask: one flag per key; true positions take part.
• order: the direction and NaN placement, for example Order::ASCENDING.

Example

use kwker::Order;

let mut v = vec![9, 0, 3, 0, 1];
kwker::sort_masked(&mut v, &[true, false, true, false, true], Order::ASCENDING);
assert_eq!(v, [1, 0, 3, 0, 9]);

sort_mask_u8 Page

pub fn sort_mask_u8<T: Sortable>(v: &mut [T], mask: &[u8], order: Order)

sort_masked with one byte per key (nonzero takes part).

Arguments

• v, order: as in sort_masked.
• mask: one byte per key.

sort_valid Page

pub fn sort_valid<T: Sortable>(v: &mut [T], validity: &[u8], order: Order)

sort_masked with an Arrow-style validity bitmap (bit set = takes part).

Arguments

• v, order: as in sort_masked.
• validity: one bit per key, least significant bit first.

sort_where Page

pub fn sort_where<T: Sortable>(v: &mut [T], order: Order, pred: impl Fn(&T) -> bool)

sort_masked of the keys for which pred returns true.

Arguments

• v, order: as in sort_masked.
• pred: the test for taking part; called once per key, before the sort.

top_k_by_group Page

pub fn top_k_by_group<T: Sortable, G: Sortable>(
    v: &[T],
    groups: &[G],
    k: usize,
    order: Order,
) -> (Vec<G>, Vec<usize>, Vec<u64>)

The k first keys of every group, for group labels in any order: SQL ROW_NUMBER() OVER (PARTITION BY g ORDER BY v) <= k.

Arguments

• v: the keys (any Sortable type).
• groups: one group label per key, in any order.
• k: keys per group.
• order: the direction and NaN placement, for example Order::DESCENDING for the largest.

Returns

(labels, offsets, positions): the distinct labels, smallest first; group i's results are positions[offsets[i]..offsets[i + 1]], positions into v in order, at most k per group.

Example

use kwker::Order;

let (labels, offsets, at) = kwker::top_k_by_group(&[5, 9, 7, 8], &[1, 0, 1, 0], 1, Order::DESCENDING);
assert_eq!(labels, [0, 1]);
assert_eq!(offsets, [0, 1, 2]);
assert_eq!(at, [1, 2]);

Examples: Top-k and selection: Top-k per group

Group-by

group_codes Page

pub fn group_codes(keys: &[(&dyn KeyColumn, Order)], threads: usize) -> Groups

Numbers the groups of equal rows across one or more key columns, like pandas groupby or SQL GROUP BY. Group g is the g-th distinct key tuple in sorted order. Pass the codes to the group_* reductions.

Arguments

• keys: the key columns (slices or vectors of any Sortable type) with their orders, most significant first, as in crate::lexsort.
• threads: the number of threads; 1 uses the calling thread only.

Returns

A Groups: each row's group code, and each group's first row and size.

Example

use kwker::{GroupRows, Order};

let city = vec![2, 1, 2];
let sales = vec![10.0, 5.0, 2.5];
let g = kwker::group_codes(&[(&city, Order::ASCENDING)], 1);
assert_eq!(g.codes, [1, 0, 1]);
let (sum, count) = kwker::group_sum(&g.codes, g.len(), &sales, GroupRows { valid: None, skip_nan: false }, 1);
assert_eq!(sum, [5.0, 12.5]);
assert_eq!(count, [1, 2]);

Panics

If the columns have different lengths, or 2^32 rows or more.

Notes

• Keys group by value, as pandas and Polars do: -0.0 and +0.0 are one group, and all NaNs are one group.

Examples: Groups, merges and sets: Group several key columns: group_codes

group_codes_into Page

pub fn group_codes_into(
    keys: &[(&dyn KeyColumn, Order)],
    threads: usize,
    codes: &mut [u32],
    first: &mut [u64],
    sizes: &mut [u64],
) -> usize

group_codes into buffers you provide.

Arguments

• keys, threads: as in group_codes.
• codes: receives each row's group code; its length is the number of rows.
• first, sizes: as long as codes; receive each group's first row and size in their first groups entries.

Returns

The number of groups.

group_sum Page

pub fn group_sum<V: GroupValue>(
    codes: &[u32],
    groups: usize,
    values: &[V],
    rows: GroupRows<'_>,
    threads: usize,
) -> (Vec<V::Sum>, Vec<u64>)

The sum and the number of values in every group.

Arguments

• codes: each row's group, below groups or NO_GROUP (from group_codes).
• groups: the number of groups.
• values: one value per row (any integer or float type).
• rows: which rows have a value (see GroupRows).
• threads: the number of threads; 1 uses the calling thread only.

Returns

(sums, counts), one entry per group. Sums are f64 for floats, i64 or u64 (wrapping) for integers.

Notes

• A NaN value that is not skipped makes its group's sum NaN.

group_count Page

pub fn group_count<V: GroupValue>(
    codes: &[u32],
    groups: usize,
    values: &[V],
    rows: GroupRows<'_>,
    threads: usize,
) -> Vec<u64>

The number of rows with a value in every group.

Arguments

• codes, groups, values, rows, threads: as in group_sum.

group_min_max Page

pub fn group_min_max<V: GroupValue>(
    codes: &[u32],
    groups: usize,
    values: &[V],
    rows: GroupRows<'_>,
    max: bool,
    threads: usize,
) -> (Vec<V>, Vec<u64>)

The smallest or largest value in every group, and the number of values.

Arguments

• codes, groups, values, rows, threads: as in group_sum.
• max: false for the smallest, true for the largest.

Returns

(values, counts), one entry per group; the value of a group with count 0 is unspecified.

Notes

• NaN is passed over unless all of a group's values are NaN, as in Polars and Arrow.

group_end_rows Page

pub fn group_end_rows<V: GroupValue>(
    codes: &[u32],
    groups: usize,
    values: &[V],
    rows: GroupRows<'_>,
    last: bool,
    threads: usize,
) -> Vec<u64>

The first or last row with a value in every group.

Arguments

• codes, groups, values, rows, threads: as in group_sum.
• last: false for the first row, true for the last.

Returns

One row number per group; NO_ROW for a group without a value.

group_median Page

pub fn group_median<V: GroupValue>(
    codes: &[u32],
    groups: usize,
    values: &[V],
    rows: GroupRows<'_>,
    threads: usize,
) -> (Vec<f64>, Vec<u64>)

The exact median of every group: the middle value, or the mean of the two middle values.

Arguments

• codes, groups, values, rows, threads: as in group_sum.

Returns

(medians, counts), one entry per group; a group without values has median NaN.

group_quantile Page

pub fn group_quantile<V: GroupValue>(
    codes: &[u32],
    groups: usize,
    values: &[V],
    rows: GroupRows<'_>,
    q: f64,
    interp: Interpolation,
    threads: usize,
) -> (Vec<f64>, Vec<u64>)

The exact q quantile of every group, like pandas groupby().quantile(q, interpolation).

Arguments

• codes, groups, values, rows, threads: as in group_sum.
• q: the quantile, in [0, 1].
• interp: the interpolation rule (see Interpolation).

Returns

(quantiles, counts), one entry per group; a group without values gives NaN.

Panics

If q is outside [0, 1].

Notes

• Matches pandas bit for bit with rows.skip_nan set.

group_cumsum Page

pub fn group_cumsum<V: GroupValue>(
    codes: &[u32],
    groups: usize,
    values: &[V],
    rows: GroupRows<'_>,
    out: &mut [V::Sum],
)

Each row's running sum within its group, in row order, like pandas groupby().cumsum().

Arguments

• codes, groups, values, rows: as in group_sum.
• out: receives one running sum per row (f64 for floats, i64 or u64 for integers).

Panics

If out.len() != codes.len().

Notes

• A row without a group or a value gets NaN (integers: 0) and leaves its group's sum unchanged.

group_shift Page

pub fn group_shift<V: GroupValue>(
    codes: &[u32],
    groups: usize,
    values: &[V],
    periods: i64,
    out: &mut [f64],
)

Each row gets the value periods rows earlier in its group, like pandas groupby().shift(periods).

Arguments

• codes, groups, values: as in group_sum.
• periods: how many rows back; negative looks ahead.
• out: receives one f64 per row; NaN where there is no such row.

Panics

If out.len() != codes.len().

group_diff Page

pub fn group_diff<V: GroupValue>(
    codes: &[u32],
    groups: usize,
    values: &[V],
    periods: i64,
    out: &mut [f64],
)

Each row's value minus the value periods rows earlier in its group, like pandas groupby().diff(periods).

Arguments

• codes, groups, values: as in group_sum.
• periods: how many rows back; negative looks ahead.
• out: receives one f64 per row; NaN where there is no such row.

Panics

If out.len() != codes.len().

group_cumcount Page

pub fn group_cumcount(codes: &[u32], groups: usize, ascending: bool, out: &mut [u64])

Each row's position within its group, from 0, like pandas groupby().cumcount().

Arguments

• codes: each row's group, below groups or NO_GROUP.
• groups: the number of groups.
• ascending: true counts from the group's first row; false from its last.
• out: receives one position per row; u64::MAX for rows without a group.

Panics

If out.len() != codes.len() or a code is out of range.

group_rank Page

pub fn group_rank<V: GroupValue + Sortable>(
    codes: &[u32],
    groups: usize,
    values: &[V],
    rows: GroupRows<'_>,
    method: GroupRankMethod,
    pct: bool,
    order: Order,
    out: &mut [f64],
)

Each row's rank within its group, from 1, like pandas groupby().rank(method, ascending, pct).

Arguments

• codes, groups, values, rows: as in group_sum.
• method: how equal values are ranked (see GroupRankMethod).
• pct: true divides each rank by its group's number of values.
• order: Order::ASCENDING ranks the smallest first; Order::DESCENDING the largest.
• out: receives one f64 rank per row; NaN for rows without a value or a group.

Panics

If out.len() != codes.len().

Notes

• Matches pandas bit for bit; -0.0 equals +0.0.

group_stats Page

pub fn group_stats<V: GroupValue>(
    codes: &[u32],
    groups: usize,
    values: &[V],
    rows: GroupRows<'_>,
    threads: usize,
) -> GroupStats<V>

The sum, count, smallest and largest value of every group, in one pass over the data.

Arguments

• codes, groups, values, rows, threads: as in group_sum.

Returns

A GroupStats with one entry per group in each field.

run_lengths Page

pub fn run_lengths<T: Sortable>(v: &[T]) -> (Vec<T>, Vec<usize>)

Run-length encoding: each run of equal neighbouring keys and its length.

Arguments

• v: the keys (any Sortable type).

Returns

(keys, lengths), one entry per run.

Example

let (keys, lens) = kwker::run_lengths(&[7, 7, 3, 7]);
assert_eq!(keys, [7, 3, 7]);
assert_eq!(lens, [2, 1, 1]);

group_boundaries Page

pub fn group_boundaries<T: Sortable>(sorted: &[T]) -> Vec<usize>

Where each run of equal keys starts in a sorted slice.

Arguments

• sorted: the keys, sorted (any Sortable type).

Returns

The start of every run, then sorted.len(): group g is sorted[b[g]..b[g + 1]]. Empty for an empty slice.

unique_counts Page

pub fn unique_counts<T: Sortable>(v: &mut [T], order: Order) -> (Vec<T>, Vec<usize>)

Sorts v, then returns each distinct key and how often it occurs: a frequency table.

Arguments

• v: the keys (any Sortable type); sorted in place.
• order: the direction and NaN placement, for example Order::ASCENDING.

Returns

(keys, counts), the keys in order.

sort_unique Page

pub fn sort_unique<T: Sortable>(v: &mut [T], order: Order) -> usize

Sorts v and moves its distinct keys, in order, to the front.

Arguments

• v: the keys (any Sortable type).
• order: the direction and NaN placement, for example Order::ASCENDING.

Returns

The number of distinct keys, m; they are in v[..m].

Example

use kwker::Order;

let mut v = vec![3, 1, 3, 2, 1];
let m = kwker::sort_unique(&mut v, Order::ASCENDING);
assert_eq!(v[..m], [1, 2, 3]);

group_by_key Page

pub fn group_by_key<K: Sortable, V: Copy>(
    keys: &mut [K],
    values: &mut [V],
    order: Order,
) -> Vec<usize>

Groups key-value pairs by key: sorts them by key (values of equal keys keep their input order) and returns where each group starts.

Arguments

• keys: the keys (any Sortable type); sorted in place.
• values: one value per key, of any Copy type; moved with the keys.
• order: the direction and NaN placement, for example Order::ASCENDING.

Returns

The group boundaries, as group_boundaries gives them.

reduce_by_key Page

pub fn reduce_by_key<K: Sortable, V: Reducible>(
    keys: &[K],
    values: &[V],
    op: Reduction,
    order: Order,
) -> (Vec<K>, Vec<V>)

Aggregates the values of each distinct key: a group-by with sum, min, max, first or last.

Arguments

• keys: one key per value (any Sortable type); not changed.
• values: the values (integers or floats).
• op: the aggregation (see Reduction).
• order: the order of the result's keys, for example Order::ASCENDING.

Returns

(keys, results): each distinct key and its group's result.

Example

use kwker::{Order, Reduction};

let (keys, totals) = kwker::reduce_by_key(&[2, 1, 2], &[10, 5, 3], Reduction::Sum, Order::ASCENDING);
assert_eq!(keys, [1, 2]);
assert_eq!(totals, [5, 13]);

Panics

If keys and values have different lengths.

Notes

• Float sums add in input order; first and last are by input order.

Examples: Groups, merges and sets: Totals per key: reduce_by_key

mean_by_key Page

pub fn mean_by_key<K: Sortable, V: Reducible>(
    keys: &[K],
    values: &[V],
    order: Order,
) -> (Vec<K>, Vec<f64>)

The mean of the values of each distinct key.

Arguments

• keys: one key per value (any Sortable type).
• values: the values (integers or floats).
• order: the order of the result's keys.

Returns

(keys, means); each mean sums its values as f64 in input order.

count_by_key Page

pub fn count_by_key<K: Sortable>(keys: &[K], order: Order) -> (Vec<K>, Vec<u64>)

How often each distinct key occurs, without changing keys.

Arguments

• keys: the keys (any Sortable type).
• order: the order of the result's keys.

Returns

(keys, counts).

Examples: Groups, merges and sets: Totals per key: reduce_by_key

reduce_by_key_with Page

pub fn reduce_by_key_with<K: Sortable, V: Copy, A>(
    keys: &[K],
    values: &[V],
    order: Order,
    init: impl FnMut(&V) -> A,
    fold: impl FnMut(&mut A, &V),
) -> (Vec<K>, Vec<A>)

Your own aggregation per distinct key: init starts a group from its first value, fold adds the next ones, in input order.

Arguments

• keys: one key per value (any Sortable type).
• values: the values, of any Copy type; a struct or tuple carries several columns.
• order: the order of the result's keys.
• init: makes a group's starting accumulator from its first value.
• fold: adds a value to an accumulator.

Returns

(keys, accumulators).

Example

use kwker::Order;

// the largest value and the count, per key
let (keys, acc) = kwker::reduce_by_key_with(&[1, 2, 1], &[4, 9, 6], Order::ASCENDING,
    |&v| (v, 1), |a, &v| { a.0 = a.0.max(v); a.1 += 1; });
assert_eq!(keys, [1, 2]);
assert_eq!(acc, [(6, 2), (9, 1)]);

NO_GROUP Page

pub const NO_GROUP: u32 = u32::MAX;

The group code of a row that belongs to no group; reductions skip such rows.

NO_ROW Page

pub const NO_ROW: u64 = u64::MAX;

The row number group_end_rows gives a group without a row that has a value.

Groups Page