ATSLIB/libats/funmap_avltree
This package implements functional maps based on AVL-trees.
Synopsis
typedef map(key:t0p, itm:t0p) = map_type(key, itm)
Description
The type constructor map is a shorthand for
map_type.
Synopsis
abstype map_type (key:t@ype, itm:t@ype+) = ptr
Synopsis
fun{key:t0p}
compare_key_key (x1: key, x2: key):<> int
Description
This function is for comparing keys in maps.
Synopsis
fun{
} funmap_nil {key,itm:t0p}():<> map(key, itm)
Description
This function forms an empty map.
Synopsis
fun{
key,itm:t@ype
} funmap_size(map: map(key, INV(itm))):<> size_t
Description
This function returns the size of a given map. Its time complexity is
O(n).
Synopsis
fun{
key,itm:t0p
} funmap_search
(
map: map(key, INV(itm))
, key: key, res: &itm? >> opt(itm, b)
) : #[b:bool] bool(b)
Description
Given a map and a key, this function returns a boolean value to indicate
whether an item associated with the key has been found in the map. If found, the
item is stored in the third (call-by-reference) argument of the function.
The time complexity of funmap_search is O(log(n)).
Synopsis
fun{
key,itm:t0p
} funmap_search_opt
(map: map(key, INV(itm)), k0: key): Option_vt(itm)
Description
This function is the optional variant of the function funmap_search.
Synopsis
fun{
key,itm:t0p
} funmap_insert
(
map: &map(key, INV(itm)) >> _
, key: key, x0: itm, res: &itm? >> opt(itm, b)
) : #[b:bool] bool(b)
Description
Given a map, a key and an item, this function inserts the key-item pair
into the map. Note that the first argument of the function is
call-by-reference, and the updated map is stored in it after the function
returns. The boolean value returned by this function indicates whether the
given key is already associated with some item in the given map. If that is
the case, then the original item assciated with the given key is stored in
the third (call-by-reference) argument after the function returns.
The time complexity of funmap_insert is O(log(n)).
Synopsis
fun{
key,itm:t0p
} funmap_insert_opt
(
map: &map(key, INV(itm)) >> _, k0: key, x0: itm
) : Option_vt(itm)
Description
This function is the optional variant of the function funmap_insert.
Synopsis
fun{
key,itm:t0p
} funmap_insert_any
(map: &map(key, INV(itm)) >> _, k0: key, x0: itm): void
Description
Given a map, a key and an item, this function inserts the key-item pair
into the map. Note that the insertion is carried out even in the case where
the given key is already associated with some item in the map.
The time complexity of funmap_insert_any is O(log(n)).
Synopsis
fun{
key,itm:t0p
} funmap_takeout (
&map(key, INV(itm)) >> _, k0: key, res: &itm? >> opt (itm, b)
) : #[b:bool] bool (b)
Description
Given a map and a key, this function returns a boolean value to indicate
whether a key-item pair whose key equals the given key is removed from the
map. Note that the first argument of the function is call-by-reference, and
the updated map is stored in it after the function returns. In the case
where a key-item pair is removed, then the item in the pair is stored in
the third (call-by-reference) argument of the function.
Synopsis
fun{
key,itm:t0p
} funmap_takeout_opt
(map: &map(key, INV(itm)) >> _, k0: key) : Option_vt (itm)
Description
This function is the optional variant of the function funmap_takeout.
Synopsis
fun{
key,itm:t0p
} funmap_remove
(map: &map(key, INV(itm)) >> _, k0: key): bool
Description
This function is like funmap_takeout except that it does not
return of the removed item.
Synopsis
fun{
key,itm:t@ype
} fprint_funmap
(out: FILEref, map: map(key, INV(itm))): void
Description
This function prints out a given map.
Synopsis
fun{}
fprint_funmap$sep (out: FILEref): void
Description
This function is called by fprint_funmap to print out the
separator between key-item pairs.
Synopsis
fun{}
fprint_funmap$mapto (out: FILEref): void
Description
This function is called by fprint_funmap to print out the
separator between the key and the item in a key-item pair.
Synopsis
fun{
key,itm:t0p
} funmap_foreach(map: map(key, INV(itm))): void
Description
This function traverse a given map.
Synopsis
fun
{key:t0p
;itm:t0p}
{env:vt0p}
funmap_foreach_env
(map: map(key, INV(itm)), env: &(env) >> _): void
Synopsis
fun
{key:t0p
;itm:t0p}
{env:vt0p}
funmap_foreach$fwork
(k: key, x: itm, env: &(env) >> _): void
Synopsis
fun{
key,itm:t0p
} funmap_listize
(map: map(key, INV(itm))):<!wrt> List0_vt(@(key,itm))
Synopsis
fun
{key:t0p
;itm:t0p}
{ki2:t0p}
funmap_flistize(map: map(key, INV(itm))): List0_vt(ki2)
Synopsis
fun
{key:t0p
;itm:t0p}
{ki2:t0p}
funmap_flistize$fopr(key, itm): ki2
Synopsis
fun{
key:t0p;itm:t0p
} funmap_avltree_height (map: map (key, itm)):<> intGte(0)
Description
Given a map represented by some AVL-tree, this function returns the
height of the tree.