sort
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 []void 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;
Functions
fn lbisect([]const void, size, const *void, *cmpfunc) size;
fn rbisect([]const void, size, const *void, *cmpfunc) size;
fn search([]const void, size, const *void, *cmpfunc) (size | void);
fn searchstrings([]const str, str) (size | void);
fn sort([]void, size, *cmpfunc) void;
fn sorted([]void, size, *cmpfunc) bool;
fn strings([]str) void;
fn strings_sorted([]str) bool;
Types
type cmpfunc
type cmpfunc = fn(a: const *void, b: const *void) 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
fn lbisect(in: []const void, sz: size, elem: const *void, 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
fn rbisect(in: []const void, sz: size, elem: const *void, 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
fn search(
in: []const void,
sz: size,
key: const *void,
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 searchstrings
fn searchstrings(in: []const str, key: str) (size | void);
Performs a binary search over a sorted slice of strings. Sorting is done with
respect to Unicode codepoints; see strings::compare. The index of the
matching item in the slice is returned if found, otherwise void is returned.
fn sort
fn sort(items: []void, itemsz: size, cmp: *cmpfunc) void;
Sorts a slice of items in place.
Note that this function may (temporarily) allocate, and will abort on
allocation failure.
fn sorted
fn sorted(items: []void, itemsz: size, cmp: *cmpfunc) bool;
Checks if all of the items in a slice are sorted.
fn strings
fn strings(items: []str) void;
Sorts a slice of strings in place. Sorting is done with respect to Unicode
codepoints; see strings::compare.
fn strings_sorted
fn strings_sorted(items: []str) bool;
Checks if all of the strings in a slice are sorted. Order is checked with
respect to Unicode codepoints; see strings::compare.