Myrddin: Algorithms

Summary: Algorithms

There are a number of algorithms that are pervasive through many programs. These include sorting, searching, and similar

We only cover sorting and searching here, although more would be a good addition. Maybe in a separate library.

``````pkg std =
/* the result of a comparison */
type order = union
`Before
`Equal
`After
;;

/* sorting and searching */
generic sort    : (sl:@a[:], cmp:(a:@a, b:@a -> order) -> @a[:])
generic lsearch : (sl : @t[:], val : @t, cmp : (a : @t, b : @t -> order) -> option(@idx)) :: numeric,integral @idx
generic bsearch : (sl : @t[:], val : @t, cmp : (a : @t, b : @t -> order) -> option(@idx)) :: numeric,integral @idx
generic swap    : (a : @a#, b : @a# -> void)

/* prepackaged comparisons */
generic numcmp  : (a : @a, b : @a -> order) :: numeric @a
const strcmp    : (a : byte[:], b : byte[:] -> order)
const strncmp   : (a : byte[:], b : byte[:], n : size -> order)

/* extrema and absolute values */
generic min : (a : @a, b : @a  -> @a) :: numeric @a
generic max : (a : @a, b : @a  -> @a) :: numeric @a
generic clamp   : (a : @a, min : @a, max : @a -> @a) :: numeric @a
generic abs : (a : @a -> @a) :: numeric @a
;;
``````

Types

``````type order = union
`Before
`Equal
`After
;;
``````

When comparing, it's useful to have an ordering between values. The order type is the result of a comparison, `a CMP b` describing whether the first value `a` comes before, after, or is equivalent to `b`.

Functions: Sorting and Searching

``````generic sort    : (sl:@a[:], cmp:(a:@a, b:@a -> order) -> @a[:])
``````

This function will sort a slice, modifying it in place. The comparison function `cmp` is used to decide how to order the slice. This comparison function must be transitive -- in otherwords, if A comes before B, and B comes before C, then A must come before C. This is true of most comparisons, but some care should be taken when attempting to provide "humanized" sorting.

Returns: the same slice it was pased. The slice will not be reallocated or moved.

``````generic lsearch : (sl : @t[:], val : @t, cmp : (a : @t, b : @t -> order) -> option(@idx::(integral,numeric)))
``````

Performs a linear search for a value using the comparison predicate `cmp`. The slice is walked in order until the first value where `cmp` returns ``Equal`.

Returns: ``Some idx`, or ``None` if the value is not present.

``````generic bsearch : (sl : @t[:], val : @t, cmp : (a : @t, b : @t -> order) -> option(@idx::(integral,numeric)))
``````

Performs a binary search for a value using the comparison predicate `cmp`. The input slice `sl` must be sorted according to the comparsion function `cmp` such that for a value at index `idx`, the comparison ```cmp(sl[idx - 1], sl[idx])``` must return either ``Before` or ``Equal`.

If there are multiple equal copies value within a list, the index retuned is not defined.

Returns: ``Some idx`, or ``None` if the value is not present.

``````generic swap    : (a : @a#, b : @a# -> void)
``````

Takes two pointers to two values, and switches them. If the pointers are equal, this is a no-op.

``````generic numcmp  : (a : @a, b : @a -> order)
const strcmp    : (a : byte[:], b : byte[:] -> order)
const strncmp   : (a : byte[:], b : byte[:], n : size -> order)
``````

These functions are helpers for comparing values. They will compare any two numeric values, and will return the ordering between the two.

Numcmp simply returns the result comparing whether `a` is less than `b`, relying on the behavior of the built in operators.

Strcmp and strncmp will do a lexicographical comparison, comparing strings byte by byte. This is a useful and correct behavior for both strings of arbitrary data, and utf8 encoded strings, where it is equivalent to doing a comparison by codepoint.

Functions: Extrema and Clamping

``````generic min : (a : @a, b : @a  -> @a)
generic max : (a : @a, b : @a  -> @a)
``````

Min and max return the larger or smaller of the two numeric values passed to them, respectively. They rely on the built in comparison functions.

``````generic clamp   : (a : @a, min : @a, max : @a -> @a)
``````

Clamp clamps the value `a` to the range [min, max], and returns it. This means that if `a` is lower than `min`, or greater than `max`, it is adjusted to those bounds and returned.

``````generic abs : (a : @a -> @a) :: numeric @a
``````

Abs returns the absolute value of a number. This means that if the number is less than 0, it is retuned with the sign inverted. If the type `@a` is unsigned, then this function is a no-op.