Module order

Ordering algorithms.

Structs

PiecewiseLinearConvexFn

Represents a maximum (upper envelope) of a collection of linear functions of one variable, evaluated using an online version of the convex hull trick. It combines the offline algorithm with square root decomposition, resulting in an asymptotically suboptimal but simple algorithm with good amortized performance: N inserts interleaved with Q queries yields O(N sqrt Q + Q log N) time complexity in general, or O((N + Q) log N) if all queries come after all inserts.

SparseIndex

A simple data structure for coordinate compression

Functions

asserting_cmp

A comparator on partially ordered elements, that panics if they are incomparable

merge_sort

A stable sort

merge_sorted

Stably merges two sorted and totally ordered collections into one

slice_lower_bound

Assuming slice is sorted and totally ordered, returns the minimum i for which slice[i] >= key, or slice.len() if no such i exists

slice_upper_bound

Assuming slice is sorted and totally ordered, returns the minimum i for which slice[i] > key, or slice.len() if no such i exists