sort+x86_64 +linux

sort: sorting algorithms and support for sorted data structures

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.

Submodules

Index

Types

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

Functions

fn inplace(items: []opaque, itemsz: size, cmp: *cmpfunc) void;
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 | nomem);
fn sorted(items: []opaque, itemsz: size, cmp: *cmpfunc) bool;

Types

type cmpfunc[permalink] [source]

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.

sort::cmp:: provides convenience functions for some commonly sorted builtin types, such as integers and strings.

Functions

fn inplace[permalink] [source]

fn inplace(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.

The list is sorted in place, with no additional allocations. This is inefficient for large lists (see sort), but has the advantage of never returning nomem.

fn lbisect[permalink] [source]

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[permalink] [source]

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[permalink] [source]

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

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

In the event that sort returns nomem, the input is unchanged.

fn sorted[permalink] [source]

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

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