std/order

11 exports, from std/order.vyrn.

Orders, the comparison under one, and the functions that sort by one. Asc, Desc, Then, Elem, Order and before are compiler-known: an order is a type, never a value, and only these three make one. The ascending order of T: by each named field in turn, or by T's own value with no field. Asc<Person, age> orders people by age. A key is an integer, a Bool or a String; Strings compare bytewise.

Dependencies

The import graph shows the whole library.

Imports: nothing else in std/
Imported by: no other std module

Asc type

type Asc<T> = Never

The ascending order of T: by each named field in turn, or by T's own value with no field. Asc<Person, age> orders people by age. A key is an integer, a Bool or a String; Strings compare bytewise.

Desc type

type Desc<O> = Never

The order O reversed.

Then type

type Then<A, B> = Never

The order A, then B among the values A ties. A and B order one type.

Elem type

type Elem<O> = Never

The type the order O compares: Elem<Asc<Person, age>> is Person.

Order protocol

protocol Order {}

The bound of a type parameter that stands for an order. Asc, Desc and Then satisfy it, and nothing else does.

before fn

fn before<O: Order>(a: Elem<O>, b: Elem<O>) -> Bool

Whether a is strictly before b under O. Two values tie under O when neither is before the other.

sort fn

fn sort<O: Order>(xs: consume Array<Elem<O>>) -> Array<Elem<O>> where sorted<O>(value)

xs sorted by O, stably: values that tie keep their order. An insertion sort, quadratic in the length.

insertSorted fn

fn insertSorted<O: Order>(
    xs: consume Array<Elem<O>> where sorted<O>(value),
    v: consume Elem<O>,
) -> Array<Elem<O>> where sorted<O>(value)

The sorted xs with v inserted after every value it is not before.

mergeSorted fn

fn mergeSorted<O: Order>(
    a: consume Array<Elem<O>> where sorted<O>(value),
    b: consume Array<Elem<O>> where sorted<O>(value),
) -> Array<Elem<O>> where sorted<O>(value)

The sorted a and b as one sorted array. Of two values that tie, a's comes first.

dedupSorted fn

fn dedupSorted<O: Order>(
    xs: consume Array<Elem<O>> where sorted<O>(value),
) -> Array<Elem<O>> where strict<O>(value)

The sorted xs with each run of values that tie under O cut to its first.

lowerBound fn

fn lowerBound<O: Order>(
    xs: Array<Elem<O>> where sorted<O>(value),
    v: Elem<O>,
) -> Int64 where value >= 0 && value <= xs.length

The first position in the sorted xs whose value v is not after: the count of values before v. Binary search.

Tests

3 test blocks in std/order.vyrn. CI runs all of them.

Test names

sort orders integers stably both ways
mergeSorted and dedupSorted keep the order
lowerBound finds the first value not before

Examples

1 program in examples/ import this module. Each runs as WebAssembly and as a native binary.

examples/knucleotide.vyrn