summaryrefslogtreecommitdiff
path: root/doc/api/libstd/algorithms.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/api/libstd/algorithms.txt')
-rw-r--r--doc/api/libstd/algorithms.txt129
1 files changed, 0 insertions, 129 deletions
diff --git a/doc/api/libstd/algorithms.txt b/doc/api/libstd/algorithms.txt
deleted file mode 100644
index 0787d43..0000000
--- a/doc/api/libstd/algorithms.txt
+++ /dev/null
@@ -1,129 +0,0 @@
-{
- title: Algorithms
- description: libstd: Algorithms
-}
-
-Algorithms
-----------
-
- 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::(integral,numeric)))
- generic bsearch : (sl : @t[:], val : @t, cmp : (a : @t, b : @t -> order) -> option(@idx::(integral,numeric)))
- generic swap : (a : @a#, b : @a# -> void)
-
- /* prepackaged comparisons */
- generic numcmp : (a : @a, b : @a -> order)
- const strcmp : (a : byte[:], b : byte[:] -> order)
- const strncmp : (a : byte[:], b : byte[:], n : size -> order)
-
- /* extrema and absolute values */
- generic min : (a : @a::numeric, b : @a::numeric -> @a::numeric)
- generic max : (a : @a::numeric, b : @a::numeric -> @a::numeric)
- generic clamp : (a : @a::numeric, min : @a::numeric, max : @a::numeric -> @a::numeric)
- generic abs : (a : @a::numeric -> @a::numeric)
- ;;
-
-Overview
---------
-
-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.
-
-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::numeric, b : @a::numeric -> 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::numeric, b : @a::numeric -> @a::numeric)
- generic max : (a : @a::numeric, b : @a::numeric -> @a::numeric)
-
-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::numeric, min : @a::numeric, max : @a::numeric -> @a::numeric)
-
-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::numeric -> @a::numeric)
-
-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.