diff options
Diffstat (limited to 'doc/api/libstd/datastruct.txt')
| -rw-r--r-- | doc/api/libstd/datastruct.txt | 181 |
1 files changed, 181 insertions, 0 deletions
diff --git a/doc/api/libstd/datastruct.txt b/doc/api/libstd/datastruct.txt new file mode 100644 index 0000000..651cd0a --- /dev/null +++ b/doc/api/libstd/datastruct.txt @@ -0,0 +1,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. |