ATSLIB/libats/linheap_binomial
This package implements a linear heap based on the binomial-heap
structure. The implementation is largely of functional style (with manual
memory management) and supports only mergeable-heap operations. In
particular, it does not support the decrease-key operation.
Synopsis
vtypedef heap (a:vt0p) = heap_vtype (a)
Description
The type constructor heap is a shorthand for
heap_vtype.
Synopsis
absvtype heap_vtype (a:vt@ype+) = ptr
Description
Given a viewtype T, the abstract viewtype heap_vtype(T) is
for a heap storing items of the viewtype T. Note that
heap_vtype is co-variant in its argument.
Synopsis
fun{a:vt0p}
compare_elt_elt (x1: &a, x2: &a):<> int
Description
This function is for comparing heap elements.
Synopsis
fun{} linheap_nil {a:vt0p} ():<> heap (a)
Description
This function creates an empty heap.
Synopsis
fun{
} linheap_is_nil{a:vt0p}(hp: !heap (INV(a))):<> bool
Description
This function tests whether a given heap is empty.
Synopsis
fun{
} linheap_isnot_nil{a:vt0p}(hp: !heap (INV(a))):<> bool
Description
This function tests whether a given heap is non-empty.
Synopsis
fun{a:vt0p}
linheap_size (hp: !heap (INV(a))):<> size_t
Description
This function computes the size of a given heap. It is time-complexity
O(1).
Synopsis
fun{a:vt0p}
linheap_insert (hp: &heap (INV(a)) >> _, x: a): void
Description
This function inserts an element into a given heap. It is of
time-complexity O(log(n)).
Synopsis
fun{a:vt0p}
linheap_merge
(hp1: heap (INV(a)), hp2: heap (a)): heap (a)
Description
This function merges two given heaps into one. It is of time-complexity
O(log(n)).
Synopsis
fun{a:t0p}
linheap_getmin
(
hp: !heap (INV(a)), res: &a? >> opt (a, b)
) : #[b:bool] bool (b)
Description
Given a heap [hp], this function copies the minimal element in [hp] into
[res] and returns true if [hp] is not empty. Otherwise, the function
returns false. For a heap of size n, the time-complexity of the function
is O(log(n)). Note that the type for the elements in the heap is assumed
to be non-linear. Return Value
The boolean value returned by this function indicates whether the given
heap is empty.
Synopsis
fun{a:vt0p}
linheap_getmin_ref (hp: !heap (INV(a))): cPtr0 (a)
Description
Given a heap [hp], this function returns the pointer to the location where
the minimal element in [hp] is stored if [hp] is not empty. Otherwise, the
function returns the null pointer.
Synopsis
fun{a:t0p}
linheap_getmin_opt (hp: !heap (INV(a))): Option_vt (a)
Description
This function is the optional version of linheap_getmin_opt.
Synopsis
fun{a:vt0p}
linheap_delmin
(
hp: &heap (INV(a)) >> _, res: &a? >> opt (a, b)
) : #[b:bool] bool b
Description
This function is similar to linheap_getmin except that it
removes the minimal element in [hp] if [hp] is not empty. For a heap of
size n, the time-complexity of the function in O(log(n)). Return Value
The boolean value returned by this function indicates whether the given
heap is empty.
Synopsis
fun{a:vt0p}
linheap_delmin_opt (hp: &heap (INV(a)) >> _): Option_vt (a)
Description
This function is the optional version of linheap_delmin_opt.
Synopsis
fun{a:t0p}
linheap_free (hp: heap (INV(a))):<!wrt> void
Description
This function is called to free a given linear heap [hp]. Note that the
elements contained in [hp] are assumed to be non-linear.
Synopsis
fun{a:vt0p}
linheap_freelin (hp: heap (INV(a))):<!wrt> void
Description
This function is called to free a given linear heap [hp]. It calls
linmap_freelin$clear to free the elements contained in [hp].
Synopsis
fun{x:vt0p}
linheap_freelin$clear
(x: &x >> x?):<!wrt> void
Synopsis
fun{a:vt0p}
linheap_free_ifnil
(hp: !heap (INV(a)) >> opt (heap (a), b)) :<> #[b:bool] bool(b)
Description
Given a heap [hp], this function frees [hp] and returns false if [hp] is
empty. Otherwise, the function keeps [hp] and returns true.