summaryrefslogtreecommitdiff
path: root/doc/api/libstd/datastruct.txt
blob: 651cd0a708201ad286f6561a3c0176a27e234e5f (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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
{
        title:  Data Structures
        description:  libstd: Data Structures
}


Data Structures
----------------

    pkg std =
            type htab(@k, @v) = struct
            ;;

            type bitset = struct
            ;;

            /* hash tables */
            generic mkht	: (h : (k : @k -> uint32), eq : (a : @k, b : @k -> bool) -> htab(@k, @v)#)
            generic htfree	: (ht : htab(@k, @v)# -> void)
            generic htput	: (ht : htab(@k, @v)#, k : @k, v : @v -> void)
            generic htdel	: (ht : htab(@k, @v)#, k : @k -> void)
            generic htget	: (ht : htab(@k, @v)#, k : @k -> option(@v))
            generic htgetv	: (ht : htab(@k, @v)#, k : @k, fallback : @v-> @v)
            generic hthas	: (ht : htab(@k, @v)#, k : @k -> bool)
            generic htkeys	: (ht : htab(@k, @v)# -> @k[:])

            /* bit sets */
            const mkbs	: (-> bitset#)
            const bsdup	: (bs : bitset# -> bitset#)
            const bsfree	: (bs : bitset# -> void)
            const bsmax	: (a : bitset# -> size)
            generic bsput	: (bs : bitset#, v : @a::(integral,numeric) -> bool)
            generic bsdel	: (bs : bitset#, v : @a::(integral,numeric) -> bool)
            generic bshas	: (bs : bitset#, v : @a::(integral,numeric) -> bool)
            const bsdiff	: (a : bitset#, b : bitset# -> void)
            const bsintersect	: (a : bitset#, b : bitset# -> void)
            const bsunion	: (a : bitset#, b : bitset# -> void)
            const bseq	: (a : bitset#, b : bitset# -> bool)
            const bsissubset	: (a : bitset#, b : bitset# -> bool)
            const bsclear	: (bs : bitset# -> bitset#)

            /* prepackaged hashing and equality tests */
            const strhash	: (s : byte[:]	-> uint32)
            const streq	: (a : byte[:], b : byte[:]	-> bool)
            generic ptrhash	: (p : @a#	-> uint32)
            generic ptreq	: (a : @a#, b : @a#	-> bool)
            generic inthash	: (v : @a::(integral,numeric)	-> uint32)
            generic inteq	: (a : @a::(integral,numeric), b : @a::(integral,numeric) -> bool)
            generic slhash	: (sl : @a[:] -> uint32)
    ;;

Hash Tables
-----------

The need for key value lookup shows up everywhere, so libstd contains an
implementation of hash tables.

    type htab(@k, @v) = struct
    ;;

The hash table is a generic type which contains any key and any value. The
key used is `@k`, and the value is `@v`.

    generic mkht	: (h : (k : @k -> uint32), eq : (a : @k, b : @k -> bool) -> htab(@k, @v)#)

Mkht creates a hash table on the heap. It accepts two functions, for hashing
and equality comparison. The hash table should be freed with `htfree`.

    generic htfree	: (ht : htab(@k, @v)# -> void)

Htfree frees a hash table and associated storage. The keys and values remain
untouched.

    generic htput	: (ht : htab(@k, @v)#, k : @k, v : @v -> void)

Inserts a key value pair into the hash table `ht`. If there is already a value
with the key `k`, then the key value pair will be replaced.

    generic htdel	: (ht : htab(@k, @v)#, k : @k -> void)

Removes a key value pair from the hash table `ht`.

    generic htget	: (ht : htab(@k, @v)#, k : @k -> option(@v))

Looks up a value from a hash table, returning `\`Some v` if the key is
present, or `\`None` if the value is not present.

    generic htgetv	: (ht : htab(@k, @v)#, k : @k, fallback : @v-> @v)

Looks up a value from a hash table, returning the value if the key is
present, or `fallback` if it is not present.

    generic hthas	: (ht : htab(@k, @v)#, k : @k -> bool)

Looks up a value from a hash table, returning `true` if the key is
present, or `falase` if the value is not present.

    generic htkeys	: (ht : htab(@k, @v)# -> @k[:])

Returns a list of all the keys present in the hash table. This list is
heap allocated, and must be freed with `slfree`.


Bit Sets
--------

The need for sets lookup shows up in many places, so libstd contains an
implementation of bit sets. Any numeric value can be put into the set,
and with the current API they may be freely intermixed [BUG?]

    type bitset = struct
    ;;

The bitset holds a set of integers. It works well for relatively dense, small
integers, as storage used is `O(max_value)`.

    const mkbs	: (-> bitset#)

Creates an empty bit set. The returned bit set should be freed with `bsfree`.

    const bsdup	: (bs : bitset# -> bitset#)

Duplicates an existing bit set. The returned bit set should be freed with
`bsfree`.

    const bsfree	: (bs : bitset# -> void)

Frees all resources associated with the bitset `bs`.

    const bsmax	: (a : bitset# -> size)

Returns the maximum value that the bitset contains. This is an approximation
of the capacity of the bitset, not a hard limit on the number of elements.

    const bscount	: (a : bitset# -> size)

Returns the total number of elements that the bitset contains. This is an
O(n) operation that involves iterating all of the bits.

    generic bsput	: (bs : bitset#, v : @a::(integral,numeric) -> bool)

Inserts the integer value `v` into the bit set `bs`. Returns `true` if this
operation changed the set, or `false` otherwise.

    generic bsdel	: (bs : bitset#, v : @a::(integral,numeric) -> bool)

Removes the integer value `v` from the bit set `bs`. Returns `true` if this
operation changed the set, or `false` otherwise.

    generic bshas	: (bs : bitset#, v : @a::(integral,numeric) -> bool)

Returns whether the bit set `bs` contains the value `v`.

    const bsdiff	: (a : bitset#, b : bitset# -> void)

Takes the set difference between `a` and `b`, storing the result back into
`a`.

    const bsintersect	: (a : bitset#, b : bitset# -> void)

Takes the set intersection between `a` and `b`, storing the result back into
`a`.

    const bsunion	: (a : bitset#, b : bitset# -> void)

Takes the set union between `a` and `b`, storing the result back into `a`.

    const bseq	: (a : bitset#, b : bitset# -> bool)

Tests whether the bitsets `a` and `b` contain the same elements, returning
`true` if they are equivalent and `false` otherwise.

    const bsissubset	: (a : bitset#, b : bitset# -> bool)

Tests whether every element of `b` is also within `a`, returning `true` if
`true` if `b` is a subset of `a`, and `false` otherwise.

    const bsclear	: (bs : bitset# -> bitset#)

Zeros every value within the bitset `bs`. This is equivalent to iterating
through it and deleting every element.