summaryrefslogtreecommitdiff
path: root/doc/api/libstd/algorithms.txt
blob: 0787d4333a2f3634c549c845e546cee7ee9acda1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
{
        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.