ATSLIB/libats/funset_avltree
This package implements functional sets based on AVL-trees.
Synopsis
typedef set (a:t0p) = set_type (a)
Description
The type constructor set is a shorthand for
set_type.
Synopsis
abstype
set_type (a:t@ype+) = ptr
Synopsis
fun{a:t0p}
compare_elt_elt (x1: a, x2: a):<> int
Description
This function is for comparing elements in sets.
Synopsis
fun{}
funset_nil {a:t0p} ():<> set(a)
Description
This function forms an empty set.
Synopsis
fun{}
funset_make_nil {a:t0p} ():<> set(a)
Description
This function is the same as funset_nil.
Synopsis
fun{a:t0p}
funset_sing (x0: a):<> set(a)
Description
Given an element x, this function forms the singleton set
containing x.
Synopsis
fun{a:t0p}
funset_make_sing (x0: a):<> set(a)
Description
This function is the same as funset_sing.
Synopsis
fun{a:t0p}
funset_make_list (xs: List(INV(a))):<> set(a)
Description
Given a list xs, this function forms the set consisting of elements in
xs. Note that duplicated elements in xs are all removed in the formed set.
Synopsis
fun{}
funset_is_nil {a:t0p} (xs: set(INV(a))):<> bool
Synopsis
fun{}
funset_isnot_nil {a:t0p} (xs: set(INV(a))):<> bool
Synopsis
fun{a:t0p}
funset_size (xs: set(INV(a))):<> size_t
Description
This function returns the size of a given set xs. Its time complexity is
O(n).
Synopsis
fun{a:t0p}
funset_is_member (xs: set(INV(a)), x0: a):<> bool
Description
This function tests whether an element occurs in a given set xs. The time
complexity of this function is O(log(n)).
Synopsis
fun{a:t0p}
funset_isnot_member (xs: set(INV(a)), x0: a):<> bool
Description
This function tests whether an element does not occur in a given set xs. The
time complexity of this function is O(log(n)).
Synopsis
fun{a:t0p}
funset_insert
(xs: &set(INV(a)) >> _, x0: a):<!wrt> bool
Description
This function adds an element to a given set xs. The time complexity
of this function is O(log(n)). Return Value
The function returns a boolean value indicating whether the element is
already in the set xs.
Synopsis
fun{a:t0p}
funset_remove
(xs: &set(INV(a)) >> _, x0: a):<!wrt> bool
Description
This function removes an element from a given set xs. The time
complexity of this function is O(log(n)).Return Value
The function returns a boolean value indicating whether the element is
actually removed from the set xs.
Synopsis
fun{a:t0p}
funset_getmax
(
xs: set(INV(a)), x0: &a? >> opt(a, b)
) :<!wrt> #[b:bool] bool(b)
Synopsis
fun{a:t0p}
funset_getmax_opt (xs: set(INV(a))):<> Option_vt (a)
Synopsis
fun{a:t0p}
funset_getmin
(
xs: set(INV(a)), x0: &a? >> opt(a, b)
) :<!wrt> #[b:bool] bool(b)
Synopsis
fun{a:t0p}
funset_getmin_opt (xs: set(INV(a))):<> Option_vt (a)
Synopsis
fun{a:t0p}
funset_takeoutmax
(
xs: &set(INV(a)) >> _, x0: &a? >> opt(a, b)
) :<!wrt> #[b:bool] bool (b)
Synopsis
fun{a:t0p}
funset_takeoutmax_opt (xs: &set(INV(a)) >> _):<> Option_vt(a)
Synopsis
fun{a:t0p}
funset_takeoutmin
(
xs: &set(INV(a)) >> _, x0: &a? >> opt(a, b)
) :<!wrt> #[b:bool] bool (b)
Synopsis
fun{a:t0p}
funset_takeoutmin_opt (xs: &set(INV(a)) >> _):<> Option_vt(a)
Synopsis
fun{a:t0p}
funset_union (xs1: set(INV(a)), xs2: set(a)):<> set(a)
Description
Given sets xs1 and xs2, this function returns the union of xs1 and xs2.
Synopsis
fun{a:t0p}
funset_intersect (xs1: set(INV(a)), xs2: set(a)):<> set(a)
Description
Given sets xs1 and xs2, this function returns the intersection of xs1 and
xs2.
Synopsis
Synopsis for [funset_diff] is unavailable.
Description
Given sets xs1 and xs2, this function returns the difference of xs1 from
xs2.
Synopsis
fun{a:t0p}
funset_symdiff (xs1: set(INV(a)), xs2: set(a)):<> set(a)
Description
Given sets xs1 and xs2, this function returns the symmetric difference
between xs1 and xs2.
Synopsis
fun{a:t0p}
funset_equal (xs1: set(INV(a)), xs2: set(a)):<> bool
Description
This function tests whether two given sets xs1 and xs2 are equal.
Synopsis
fun{a:t0p}
funset_compare (xs1: set(INV(a)), xs2: set(a)):<> Sgn
Description
This function compares two given sets xs1 and xs2 based on the ordering
induced from the one (implemented by compare_elt_elt) on set
elements.
Synopsis
fun{a:t0p}
funset_is_subset (xs1: set(INV(a)), xs2: set(a)):<> bool
Description
Given sets xs1 and xs2, this function tests whether xs1 is a subset of xs2.
Synopsis
fun{a:t0p}
funset_is_supset (xs1: set(INV(a)), xs2: set(a)):<> bool
Description
Given sets xs1 and xs2, this function tests whether xs1 is a superset of
xs2.
Synopsis
fun{a:t0p}
fprint_funset
(out: FILEref, xs: set(INV(a))): void
Description
This function prints out the elements in a given set. It calls
fprint_funset$sep to print a separator between every two
consecutive elements.
Synopsis
fun{}
fprint_funset$sep
(out: FILEref): void
Description
This function template is called by fprint_funset. It
prints out the string ", " (a comma followed by a space character)
by default.
Synopsis
fun{a:t0p}
funset_foreach (set: set(INV(a))): void
Synopsis
fun{
a:t0p}{env:vt0p
} funset_foreach_env
(set: set(INV(a)), env: &(env) >> _): void
Synopsis
fun{
a:t0p}{env:vt0p
} funset_foreach$fwork
(x: a, env: &(env) >> _): void
Synopsis
fun{a:t0p}
funset_listize(xs: set(INV(a))):<!wrt> List0_vt(a)
Description
Given a set xs, this function returns a linear list consisting of all the
elements in xs.
Synopsis
fun{
a:t0p}{b:t0p
} funset_flistize (xs: set(INV(a))): List0_vt(b)
Description
Given a set xs, this function returns a linear list consisting of all the
elements returned by calling funset_flistize$fopr on elements
in xs.
Synopsis
fun{
a:t0p}{b:t0p
} funset_flistize$fopr(x: a): b
Synopsis
fun{a:t0p}
funset_avltree_height (xs: set (a)):<> intGte (0)
Description
Given a set represented by some AVL-tree, this function returns the
height of the tree.