Sorted slices v0.1.0

IsSorted<T>

pub func IsSorted<T>(items: T[..]) -> bool

Whether items is in non-decreasing order. items is borrowed and read. An empty slice and a single element are sorted, there being no pair to be out of order. Equal neighbours are in order: this asks for non-decreasing, not strictly increasing. Requires < on the element type. Cannot fail. Runs in time proportional to the length, stopping at the first pair out of order, and allocates nothing.

Source

Type parameters

Parameters

Returns: whether the sequence is in non-descending order

IsSortedUntil<T>

pub func IsSortedUntil<T>(items: T[..]) -> uint

How far items is in non-decreasing order. items is borrowed and read. Returns the length of the longest sorted run starting at the front, which is the whole length when the slice is sorted, and the index of the first element smaller than the one before it otherwise. An empty slice gives zero and a single element gives one. Requires < on the element type. Cannot fail. Runs in time proportional to the answer and allocates nothing.

Source

Type parameters

Parameters

Returns: how many leading elements are in non-descending order

LowerBound<T>

pub func LowerBound<T>(items: T[..], value: T) -> uint

The first position where value could be inserted without breaking the order. items is borrowed and read; value is read by value. This is the index of the first element not less than value — the first equal one when there are equals, and where it would go when there are none. A value larger than everything gives the length. Requires < on the element type, and requires items to be sorted by that order. Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing.

Source

Type parameters

Parameters

Returns: the first index where value could be inserted and keep the order

UpperBound<T>

pub func UpperBound<T>(items: T[..], value: T) -> uint

The last position where value could be inserted without breaking the order. items is borrowed and read; value is read by value. This is the index of the first element greater than value — one past the last equal one when there are equals, and the same as LowerBound when there are none. Requires < on the element type, and requires items to be sorted by that order. Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing.

Source

Type parameters

Parameters

Returns: the last index where value could be inserted and keep the order

BinarySearch<T>

pub func BinarySearch<T>(items: T[..], value: T) -> uint?

The index of an element of items equal to value. items is borrowed and read; value is read by value. Reports none when no element is equal. When several are, the one reported is the first of them, which makes the answer depend on the sequence rather than on how the search happened to divide it. Requires < on the element type, and requires items to be sorted by that order. Equality is decided by the ordering rather than by ==: two elements neither of which is less than the other are equal here, whatever == would say about them. Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing.

Source

Type parameters

Parameters

Returns: the index of a matching element, or none; which one is unspecified when several match

EqualRange<T>

pub func EqualRange<T>(items: T[..], value: T) -> uint..uint

The range of positions in items holding elements equal to value. items is borrowed and read; value is read by value. The range runs from LowerBound to UpperBound, so it is empty when no element is equal — and its start is then where the value would be inserted, which is the answer a caller inserting into a sorted sequence wants. Requires < on the element type, and requires items to be sorted by that order. Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing.

Source

Type parameters

Parameters

Returns: the range of indices holding elements equal to value, empty when none does

IsSortedBy<T>

pub func IsSortedBy<T>(
    items: T[..],
    compare: func(T, T) -> Ordering
) -> bool

Whether items is in non-decreasing order under compare. items is borrowed and read; compare is called once per neighbouring pair until one is out of order. An empty slice and a single element are sorted, and equal neighbours are in order. Cannot fail. Runs in time proportional to the length and allocates nothing beyond whatever compare does.

Source

Type parameters

Parameters

Returns: whether the sequence is in non-descending order under compare

IsSortedUntilBy<T>

pub func IsSortedUntilBy<T>(
    items: T[..],
    compare: func(T, T) -> Ordering
) -> uint

How far items is in non-decreasing order under compare. items is borrowed and read. Returns the length of the longest sorted run starting at the front, exactly as IsSortedUntil does for the element type's own order. Cannot fail. Runs in time proportional to the answer and allocates nothing beyond whatever compare does.

Source

Type parameters

Parameters

Returns: how many leading elements are in non-descending order under compare

LowerBoundBy<T>

pub func LowerBoundBy<T>(
    items: T[..],
    value: T,
    compare: func(T, T) -> Ordering
) -> uint

The first position where value could be inserted into items under compare without breaking the order. items is borrowed and read; value is read by value. compare must be the order items was sorted by. Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing beyond whatever compare does.

Source

Type parameters

Parameters

Returns: the first index where value could be inserted and keep the order under compare

UpperBoundBy<T>

pub func UpperBoundBy<T>(
    items: T[..],
    value: T,
    compare: func(T, T) -> Ordering
) -> uint

The last position where value could be inserted into items under compare without breaking the order. items is borrowed and read; value is read by value. compare must be the order items was sorted by. Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing beyond whatever compare does.

Source

Type parameters

Parameters

Returns: the last index where value could be inserted and keep the order under compare

BinarySearchBy<T>

pub func BinarySearchBy<T>(
    items: T[..],
    value: T,
    compare: func(T, T) -> Ordering
) -> uint?

The index of an element of items that compare calls equal to value. items is borrowed and read; value is read by value. Reports none when no element is equal, and the first of them when several are. compare must be the order items was sorted by. Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing beyond whatever compare does.

Source

Type parameters

Parameters

Returns: the index of a matching element under compare, or none

EqualRangeBy<T>

pub func EqualRangeBy<T>(
    items: T[..],
    value: T,
    compare: func(T, T) -> Ordering
) -> uint..uint

The range of positions in items holding elements compare calls equal to value. items is borrowed and read; value is read by value. Empty when no element is equal, with its start at the position the value would be inserted. compare must be the order items was sorted by. Cannot fail. Runs in time proportional to the logarithm of the length and allocates nothing beyond whatever compare does.

Source

Type parameters

Parameters

Returns: the range of indices holding elements equal to value under compare