ATSLIB/libats/linmap_randbst

This package implements linear maps based on the randomized binary-search-tree (BST) structure.

Compared to balanced trees such as AVL-trees and red-black-trees, randomized binary-search-trees are relatively easier to implement. However, maps based on randomized BSTs are significantly less efficient than those based on balanced trees.

map

map_vtype

linmap_randbst_initize

linmap_randbst_random_m_n

map

Synopsis

stadef map = map_vtype

Description

The type constructor map is a shorthand for map_vtype.

map_vtype

Synopsis

absvtype
map_vtype (key:t@ype, itm:vt@ype+) = ptr

Description

Given a type K and a viewtype T, the abstract viewtype map_vtype(K, T) is for a map storing links from keys of the type K to items of the viewtype T. Note that map_vtype is co-variant in its second argument.

compare_key_key

Synopsis

fun{key:t0p}
compare_key_key (x1: key, x2: key):<> int

Description

This function is for comparing map keys.

linmap_nil

Synopsis

fun{}
linmap_nil {key:t0p;itm:vt0p} ():<> map (key, itm)

Description

This function creates an empty map.

linmap_is_nil

Synopsis

fun{
} linmap_is_nil
  {key:t0p;itm:vt0p} (map: !map (key, INV(itm))):<> bool

Description

This function tests whether a given map is empty.

linmap_isnot_nil

Synopsis

fun{
} linmap_isnot_nil
  {key:t0p;itm:vt0p} (map: !map (key, INV(itm))):<> bool

Description

This function tests whether a given map is non-empty.

linmap_search

Synopsis

fun{
key:t0p;itm:t0p
} linmap_search
(
  !map (key, INV(itm)), key, res: &itm? >> opt (itm, b)
) : #[b:bool] bool(b) (*found*) // endfun

linmap_search_ref

Synopsis

fun{
key:t0p;itm:vt0p
} linmap_search_ref
  (map: !map (key, INV(itm)), k0: key): cPtr0 (itm)

linmap_search_opt

Synopsis

fun{
key:t0p;itm:t0p
} linmap_search_opt
  (map: !map (key, INV(itm)), k0: key): Option_vt (itm)

linmap_insert

Synopsis

fun{
key:t0p;itm:vt0p
} linmap_insert
(
  &map (key, INV(itm)) >> _, key, itm, res: &itm? >> opt (itm, b)
) : #[b:bool] bool(b) // endfun

linmap_insert_opt

Synopsis

fun{
key:t0p;itm:vt0p
} linmap_insert_opt
  (map: &map (key, INV(itm)) >> _, k0: key, x0: itm): Option_vt (itm)

Description

This function is the optional version of linmap_insert.

linmap_takeout

Synopsis

fun{
key:t0p;itm:vt0p
} linmap_takeout
(
  &map (key, INV(itm)) >> _, key, res: &itm? >> opt (itm, b)
) : #[b:bool] bool(b) // endfun

linmap_takeout_opt

Synopsis

fun{
key:t0p;itm:vt0p
} linmap_takeout_opt
  (map: &map (key, INV(itm)) >> _, k0: key): Option_vt (itm)

linmap_remove

Synopsis

fun{
key:t0p;itm:t0p
} linmap_remove (
  map: &map (key, INV(itm)) >> _, k0: key): bool

linmap_foreach

Synopsis

fun{
key:t0p;itm:vt0p
} linmap_foreach (map: !map (key, INV(itm))): void

linmap_foreach_env

Synopsis

fun
{key:t0p
;itm:vt0p}
{env:vt0p}
linmap_foreach_env
  (map: !map (key, INV(itm)), env: &(env) >> _): void

linmap_foreach$fwork

Synopsis

fun
{key:t0p
;itm:vt0p}
{env:vt0p}
linmap_foreach$fwork
  (k: key, x: &itm >> _, env: &(env) >> _): void

linmap_free

Synopsis

fun{
key:t0p;itm:t0p
} linmap_free (map: map (key, INV(itm))):<!wrt> void

Description

This function frees a given map containing only non-linear items.

linmap_freelin

Synopsis

fun{
key:t0p;itm:vt0p
} linmap_freelin (map: map (key, INV(itm))):<!wrt> void

linmap_freelin$clear

Synopsis

fun{
itm:vt0p
} linmap_freelin$clear (x: &itm >> _?):<!wrt> void

linmap_free_ifnil

Synopsis

fun{
key:t0p;itm:vt0p
} linmap_free_ifnil
(
  map: !map (key, INV(itm)) >> opt (map (key, itm), b)
) :<!wrt> #[b:bool] bool(b) (*~freed*) // endfun

Description

Given a map, this function frees it and returns false if the map is empty. Otherwise, the function keeps the map and returns true.

linmap_listize

Synopsis

fun
{key:t0p
;itm:vt0p}
linmap_listize
  (map: map (key, INV(itm))):<!wrt> List_vt @(key, itm)

Description

This function returns a linear list of pairs consisting of keys and their associated items in a given map while freeing the map.

linmap_flistize

Synopsis

fun
{key:t0p
;itm:vt0p}
{ki2:vt0p}
linmap_flistize (map: map (key, INV(itm))): List_vt (ki2)

linmap_flistize$opr

Synopsis

Synopsis for [linmap_flistize$opr] is unavailable.

linmap_listize1

Synopsis

fun{
key,itm:t0p
} linmap_listize1
  (map: !map (key, INV(itm))):<!wrt> List_vt @(key, itm)

Description

This function returns a linear list of pairs consisting of keys and their associated items in a given map while keeping the map.

linmap_randbst_initize

Synopsis

fun{} linmap_randbst_initize (): void

Description

This function is called to initialize the random number generator employed in the implementation of randomized binary search trees.

linmap_randbst_random_m_n

Synopsis

fun{} linmap_randbst_random_m_n
  {m,n:nat} (m: int m, n: int n): natLt (2)

This page is created with ATS by Hongwei Xi and also maintained by Hongwei Xi.