Crate runlength 

Generic run-length encoded sequences.

A run-length encoded sequence stores runs of repeated values once: a a a b b becomes runs [3, 2] with values [a, b]. This crate works with any value type, and is built around one idea: combining sequences is split into a plan, computed from run boundaries alone, and a separate step that computes values.

use runlength::prelude::*;

let a = Rle::from_runs(&[3, 2], vec![1, 2]).unwrap();
let b = Rle::from_runs(&[1, 4], vec![10, 20]).unwrap();

// The plan says which run of each input covers each output segment.
let p = a.plan_with(&b);
assert_eq!(p.ends, vec![1, 3, 5]);
assert_eq!(p.idx_a, vec![0, 0, 1]);
assert_eq!(p.idx_b, vec![0, 1, 1]);

// Any operation can be applied to any value types...
let labels = a.zip_with(&b, None, None, |x, y| format!("{x}/{y}")).unwrap();
assert_eq!(labels.get(0), Some(&"1/10".to_string()));

// ...and the usual operators pad the shorter side with zero.
let sum = &a + &b;
assert_eq!(sum.to_dense(), vec![11, 21, 21, 22, 22]);
assert_eq!(sum.runs(), vec![1, 2, 2]);

Main types

• Rle owns a sequence; RleRef borrows one. Their shared operations are on the RleLike trait.
• RleBatch stores many sequences under arbitrary keys in shared arrays, and combines batches key by key in parallel.
• Plan and MergePlan describe how runs combine without touching values, so callers can compute values any way they like.
• coverage_sum, coverage_count and their _by_key variants build sequences from intervals.

Conventions

• Positions and lengths are i64, and every sequence starts at 0.
• Intervals are half-open, [start, end).
• Neighbouring runs merge when their values are Identical: NaN merges with NaN, -0.0 does not merge with 0.0.
• Operations merge their result by default; _raw variants do not.

Modules

prelude

The types and traits needed for everyday use.

Structs

MergePlan

How runs are grouped by a merge mask, without any values involved.

OverlapPlan

Which intervals cover each segment, for aggregating interval values in any way.

Plan

How to combine two sequences, computed from their run ends alone.

PlanMany

How to combine k sequences, computed from their run ends alone: the k-input version of Plan.

Rle

A run-length encoded sequence that owns its data.

RleBatch

Many run-length encoded sequences, each identified by a key.

RleRef

A borrowed run-length encoded sequence, for example one entry of an RleBatch. It has the same invariants as Rle.

SliceView

A borrowed slice start..end of a sequence that is not copied, for reducing many slices cheaply. Positions are relative to start.

Enums

Error

Errors raised when input is invalid or an operation cannot be carried out.

How

Which keys a combination of two batches keeps, as in a DataFrame join.

Keep

Which value a merged group keeps when its runs hold different values.

Traits

Identical

The equality used to decide whether two neighbouring runs merge.

Num

Numeric value types that support length-weighted reductions and coverage.

RleLike

Read-only operations shared by Rle and RleRef.

Functions

concat

Joins sequences end to end. Identical neighbours are merged, including at the joins.

coverage_count

The number of intervals covering each position.

coverage_count_by_key

coverage_count per key, computed in parallel. Keys appear in order of first appearance; each sequence covers 0..max(end) of its intervals.

coverage_max

The largest of values over the intervals covering each position, or None where no interval covers it. Works for any ordered value type; NaN only wins where nothing else covers the position.

coverage_max_by_key

coverage_max per key, computed in parallel.

coverage_min

The smallest of values over the intervals covering each position; see coverage_max.

coverage_min_by_key

coverage_min per key, computed in parallel.

coverage_sum

The sum of values over the intervals covering each position.

coverage_sum_by_key

coverage_sum per key, computed in parallel. Keys appear in order of first appearance; each sequence covers 0..max(end) of its intervals.

coverage_sum_opt

Like coverage_sum, but uncovered positions are None instead of 0.

merge_plan

Groups runs with cumulative ends by a mask over neighbouring pairs. See MergePlan.

overlap_plan

Computes the OverlapPlan for intervals [start, end).

overlap_plan_by_key

overlap_plan per key, computed in parallel. Returns the keys in order of first appearance and one plan per key, covering 0..max(end) of that key’s intervals. Interval ids are positions in the input, not per key.

plan

Computes the Plan for combining sequences with run ends a and b.

plan_many

Computes the PlanMany for sequences with the given run ends.

zip_many

Combines several sequences position by position with f, which receives one value per input, and merges the result.

zip_with

Combines two sequences position by position with f, merging identical neighbours in the result.

zip_with_raw

Like zip_with but keeps one run per plan segment, without merging.

Type Aliases

Result