ATSLIB/libats/linmap_skiplist

This package implements a linear map based on the (randomized) skip-list structure.

While skip-lists are interesting, maps based on them are not as efficient as those based on balanced trees such as AVL-trees and red-black-trees. An often claimed advantage of skip-lists is that they are easier to implement than balanced trees. This, however, is not supported in ATS. With proper use of types, it seems on the contrary that correctly implementing balanced trees in ATS is significantly easier than skip-lists. So this package is largely for educational purpose, demonstrating a reasonable approach to handling inherently imperative structures like skip-list.

map

map_vtype

linmap_skiplist_initize

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_make_nil

Synopsis

fun{}
linmap_make_nil {key:t0p;itm:vt0p} ():<!wrt> 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_size

Synopsis

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

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

Description

This function searches for key [k0] in a given map [map]. If found, the item assciated with [k0] is put into [res], and the boolean value true is returned. Otherwise, the boolean value false is returned.

Return Value

The boolean value returned by this function indicates whether the key [k0] appears in the given map.

linmap_search_ref

Synopsis

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

Description

This function searches for key [k0] in a given map [map]. If found, a non-null pointer is returned which points to the location where the item associated with [k0] is stored. Otherwize, the null pointer is returned.

linmap_search_opt

Synopsis

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

Description

This function is the optional version of linmap_search.

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

Description

This function inserts a link from [k0] to [x0] into a given map [map]. In the case where the key [k0] is already associated with some item in the given map, this function replaces the item with [x0] and then stores the item into [res]. The returned value indicates wether replacement is actually performed.

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_insert_any

Synopsis

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

Description

This function inserts a link from [k0] to [x0] into a given map [map]. Note that it carries out insertion regardless whether the key [k0] is already associated with some item in the given map.

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

Description

If key k0 can be found in a given map, this function takes out the item associated with [k0] from the map, puts it into [res] and then returns the boolean value true. Otherwise, it simply returns the boolean value false.

linmap_takeout_opt

Synopsis

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

Description

This function is the optional version of linmap_takeout.

linmap_remove

Synopsis

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

Description

This function is similar to linmap_takeout except that it discards the item associated with [k0] if it is taken out. Note that the type for items stored in the map is assumed to be non-linear.

linmap_foreach

Synopsis

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

Description

This function traverses a given map, applying the function implemented by linmap_foreach$fwork to the key and item stored in each node.

linmap_foreach_env

Synopsis

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

Description

This function is similar to linmap_foreach except taking an environment as an extra argument.

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)

Description

What this function does is essentially to apply linmap_flistize$fopr to each pair in the list returned by linmap_listize. However, the actual implementation is more efficient.

linmap_flistize$fopr

Synopsis

fun
{key:t0p
;itm:vt0p}
{ki2:vt0p}
linmap_flistize$fopr (k: key, x: itm): ki2

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. Note that the items are assumed to be of a non-linear type.

linmap_skiplist_initize

Synopsis

fun linmap_skiplist_initize (): void

Description

This function is called to initialize the random number generator employed in the skip-list implementation.

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