ATSLIB/libats/funset_listord
This package implements functional sets based on lists ordered according to
some total ordering. The implementation should only be used for handling
sets that are relatively small. For large sets, an implementation based on
balanced trees may be considered.
Synopsis
typedef set (a:t0p) = set_type (a)
Description
The type constructor set is a shorthand for
set_t0ype_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{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_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(|xs|).
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(|xs|).
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(|xs|).
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(|xs|). 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(|xs|).Return Value
The function returns a boolean value indicating whether the element is
actually removed from the set xs.
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.
The time complexity of this function is O(|xs1|+|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. The time complexity of this function is O(|xs1|+|xs2|).
Synopsis
Synopsis for [funset_diff] is unavailable.
Description
Given sets xs1 and xs2, this function returns the difference of xs1 from
xs2. The time complexity of this function is O(|xs1|+|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. The time complexity of this function is
O(|xs1|+|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. The time
complexity of this function is O(|xs1|+|xs2|).
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 on set elements, which is implemented by
compare_elt_elt. The time complexity of this function is
O(|xs1|+|xs2|).
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.
The time complexity of this function is O(|xs1|+|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. The time complexity of this function is O(|xs1|+|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. The time complexity of this function is O(|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
castfn
funset2list{a:t0p} (xs: set(INV(a))):<> List0 (a)
Description
This function casts a set into a list in which elements are ordered
descendingly.