sort+x86_64 +linux

The sort module provides functions for sorting slices, as well as operations on sorted slices, such as binary search.

The functions sort and search are provided for working with generic slices. In order to work with a user-supplied slice of an arbitrary type, the slice must be cast to []opaque and the size of the member type passed alongside it (e.g. size(int)). The functions also take in a cmpfunc argument, which is called to determine how the slice items should be ordered.

Index

Types

type cmpfunc = fn(a: const *opaque, b: const *opaque) int;

Functions

fn lbisect(in: []const opaque, sz: size, elem: const *opaque, cmp: *cmpfunc) size;
fn rbisect(in: []const opaque, sz: size, elem: const *opaque, cmp: *cmpfunc) size;
fn search(in: []const opaque, sz: size, key: const *opaque, cmp: *cmpfunc) (size | void);
fn sort(items: []opaque, itemsz: size, cmp: *cmpfunc) void;
fn sorted(items: []opaque, itemsz: size, cmp: *cmpfunc) bool;

Types

type cmpfunc[link] 

type cmpfunc = fn(a: const *opaque, b: const *opaque) int;

This function type is used when sorting and searching. Given two pointers to values, a function of this type should return an integer less than, equal to, or greater than zero if the first argument is, respectively, less than, equal to, or greater than the second argument.

Functions

fn lbisect[link] 

fn lbisect(in: []const opaque, sz: size, elem: const *opaque, cmp: *cmpfunc) size;

Determines the index that 'elem' should be inserted into sorted slice 'in'. If 'elem' already appears in the slice, inserting to the returned index will insert immediately before the first occurance.

fn rbisect[link] 

fn rbisect(in: []const opaque, sz: size, elem: const *opaque, cmp: *cmpfunc) size;

Determines the index that 'elem' should be inserted into sorted slice 'in'. If 'elem' already appears in the slice, inserting to the returned index will insert immediately after the last occurance. 

fn search(in: []const opaque, sz: size, key: const *opaque, cmp: *cmpfunc) (size | void);

Performs a binary search over a sorted slice. If the key is found, index of the matching item in the slice is returned. Otherwise, void is returned.

fn sort[link] 

fn sort(items: []opaque, itemsz: size, cmp: *cmpfunc) void;

Sorts a slice of items in place. This function provides a stable sort - relative order of equal elements is preserved.

Note that this function may (temporarily) allocate, and will abort on allocation failure.

fn sorted[link] 

fn sorted(items: []opaque, itemsz: size, cmp: *cmpfunc) bool;

Checks if all of the items in a slice are sorted.