summaryrefslogtreecommitdiff
path: root/doc/api/libstd/datastruct.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/api/libstd/datastruct.txt')
-rw-r--r--doc/api/libstd/datastruct.txt181
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.