Trait NaturalArray

pub trait NaturalArray<K: ArrayKind>:
    OrdArray<K, K::I>
    + Sized
    + Sub<Self, Output = Self>
    + Add<Self, Output = Self>
    + AsRef<K::Index> {
    // Required methods
    fn max(&self) -> Option<K::I>;
    fn cumulative_sum(&self) -> Self;
    fn arange(start: &K::I, stop: &K::I) -> Self;
    fn repeat(&self, x: K::Slice<'_, K::I>) -> Self;
    fn quot_rem(&self, d: K::I) -> (Self, Self);
    fn mul_constant_add(&self, c: K::I, x: &Self) -> Self;
    fn connected_components(
        sources: &Self,
        targets: &Self,
        n: K::I,
    ) -> (Self, K::I);
    fn bincount(&self, size: K::I) -> K::Index;
    fn sparse_bincount(&self) -> (K::Index, K::Index);
    fn zero(&self) -> K::Index;
    fn scatter_sub_assign(&mut self, ixs: &K::Index, rhs: &K::Index);

    // Provided methods
    fn sum(&self) -> K::I { ... }
    fn segmented_sum(&self, x: &Self) -> Self { ... }
    fn segmented_arange(&self) -> Self { ... }
}

Arrays of natural numbers. This is used for computing with indexes and sizes.

Required Methods

fn max(&self) -> Option<K::I>

fn cumulative_sum(&self) -> Self

An inclusive-and-exclusive cumulative sum For an input of size N, returns an array x of size N+1 where x[0] = 0 and x[-1] = sum(x)

fn arange(start: &K::I, stop: &K::I) -> Self

Indices from start to stop

use open_hypergraphs::array::{*, vec::*};
let x0 = VecArray::arange(&0, &3);
assert_eq!(x0, VecArray(vec![0, 1, 2]));

let x1 = VecArray::arange(&0, &0);
assert_eq!(x1, VecArray(vec![]));

fn repeat(&self, x: K::Slice<'_, K::I>) -> Self

Repeat each element of the given slice. self and x must be equal lengths.

fn quot_rem(&self, d: K::I) -> (Self, Self)

Compute the arrays (self%denominator, self/denominator)

Panics

When d == 0.

fn mul_constant_add(&self, c: K::I, x: &Self) -> Self

Compute self * c + x, where c is a constant (scalar) and x is an array.

Panics

When self.len() != x.len().

fn connected_components(sources: &Self, targets: &Self, n: K::I) -> (Self, K::I)

Compute the connected components of a graph with n nodes. Edges are stored as a pair of arrays of nodes (sources, targets) meaning that for each i there is an edge sources[i] → targets[i].

Since n is the number of nodes in the graph, the values in sources and targets must be less than n.

Returns

Returns a pair (cc_ix, k), where cc_ix[i] is the connected component for the ith node, and k is the total number of components.

Panics

• Inequal lengths: sources.len() != targets.len()
• Indexes are out of bounds: sources[i] >= n or targets[i] >= n.

fn bincount(&self, size: K::I) -> K::Index

Count occurrences of each value in the range [0, size)

fn sparse_bincount(&self) -> (K::Index, K::Index)

Compute index of unique values and their counts

fn zero(&self) -> K::Index

Return indices of elements which are zero

fn scatter_sub_assign(&mut self, ixs: &K::Index, rhs: &K::Index)

Compute self[ixs] -= rhs

Provided Methods

fn sum(&self) -> K::I

fn segmented_sum(&self, x: &Self) -> Self

Segmented sum of input. For example, for self = [1 2 0], self.segmented_sum([1 | 2 3]) = [1 5 0].

Panics

When self.sum() != x.len()

fn segmented_arange(&self) -> Self

Given an array of sizes compute the concatenation of arange arrays of each size.

use open_hypergraphs::array::{*, vec::*};
let x = VecArray::<usize>(vec![2, 3, 0, 5]);
let y = VecArray::<usize>(vec![0, 1, 0, 1, 2, 0, 1, 2, 3, 4]);
assert_eq!(x.segmented_arange(), y)

Default implementation has time complexity:

• Sequential: O(n)
• PRAM CREW: O(log n)

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl NaturalArray<VecKind> for VecArray<usize>