Containers.module
---------------------------------------------------------------
-- THIS FILE HAS BEEN CREATED FROM
-- --> Library/Containers/Containers.module.pp <--
-- DO NOT MODIFY IT
---------------------------------------------------------------
-- Copyright (C) International Computer Science Institute, 1994. COPYRIGHT --
-- NOTICE: This code is provided "AS IS" WITHOUT ANY WARRANTY and is subject --
-- to the terms of the SATHER LIBRARY GENERAL PUBLIC LICENSE contained in --
-- the file "Doc/License" of the Sather distribution. The license is also --
-- available from ICSI, 1947 Center St., Suite 600, Berkeley CA 94704, USA. --
--------> Please email comments to "sather-bugs@icsi.berkeley.edu". <----------
(*
CONTAINER CLASSES
These data types can hold other objects. They are all built up
out of more primitive Sather classes in Base.
The most important of these is ARRAY. It extends the built-in array
providing class AREF and provides facilities for sorting, printing,
interating, and so forth. The Sather language also allows a special
array-constructing literal syntax:
| a, b, c |
ARRAY2 and ARRAY3 provide multiple dimensions and are built using AREF
with multiplicative indexing.
The TUP classes make it convenient to construct tuples of other types.
The TUP classes are value classes, so they are efficient; there is no
heap management involved in their implementation. Because of Sathers
type inference, their construction can usually be acheived with:
#(first, second)
The TUP classes "do the right thing" automatically with respect to
equality and hash values.
There are three types of container classes
- abstract interfaces (such as $RO_SET{T} and $SET{T})
- concrete implementations (such as H_SET, LH_SET and SET)
- algorithm classes (collections of stateless algorithm functions)
Finally, we have the high-performance workhorse Sather classes,
FLIST, FMAP, FSET and FQSET which use amortised doubling. The "F"
prefix denotes fast. They have slightly awkward interfaces requiring
writebacks, i.e.
myset := myset.insert(foo);
Although this appears to be a value-oriented interface, the 'myset'
returned may actually be the same as the 'myset' on the right side (in
fact, it usually will be.) This is done for absolute speed (the 'F'
stands for 'fast'.) We suggest that they be avoided by novices and
should certainly not be used in class interfaces (i.e. their use
should be intra-class).
*)
-- Container Hierarchy
container.sa -has container.sa $CONTAINER -- Container abstraction
dispenser.sa -has dispenser.sa $DISPENSER -- Dispensers abstraction
-- for containers such as stacks
arr.sa -has arr.sa $ARR -has arr.sa $RO_ARR -- Array abstraction
-- Algorithm modules
member.sa -has member.sa MEMBER -- Membership funcs on a container
a_alg.sa -has a_alg.sa A_ALG -- Miscellaneous array algs
a_permute.sa -has a_permute.sa A_PERMUTE -- Permutations of arrays
a_sort.sa -has a_sort.sa A_SORT -- Sorting arrays
a_select.sa -has a_select.sa A_SELECT -- Selecting ith elt
a_search.sa -has a_search.sa A_SEARCH -- Binary searching.
-- Basic container classes ARRAY, TUP and NEXT
array.sa -has array.sa ARRAY
array2.sa -has array2.sa ARRAY2
array3.sa -has array3.sa ARRAY3
tup.sa -has tup.sa TUP
next.sa -has next.sa $NEXT NEXT
-- Standard container classes
list.sa -has list.sa $LIST -- Extensible arrays
a_list.sa -has a_list.sa A_LIST LIST
queue.sa -has queue.sa $QUEUE
a_queue.sa -has a_queue.sa A_QUEUE QUEUE
stack.sa -has stack.sa $STACK
nr_stack.sa -has nr_stack.sa $NR_STACK
a_stack.sa -has a_stack.sa A_STACK STACK
nr_a_stack.sa -has nr_a_stack.sa NR_A_STACK STACK
pq.sa -has pq.sa $PQ -- Priority queue
a_pq.sa -has a_pq.sa A_PQ PQMIN PQWT PQMINWT
bag.sa -has bag.sa $RO_BAG $BAG
bag_incl.sa -has bag_incl.sa BAG_INCL
h_bag.sa -has h_bag.sa H_BAG BAG
map.sa -has map.sa $RO_MAP $MAP
map_incl.sa -has map_incl.sa MAP_INCL MAP
h_map.sa -has h_map.sa H_MAP
multimap.sa -has multimap.sa $RO_MULTIMAP $MULTIMAP -- Multi-maps
multimap_incl.sa -has multimap_incl.sa RO_MULTIMAP_INCL MULTIMAP_INCL MULTIMAP
h_multimap.sa -has h_multimap.sa H_MULTIMAP -- Hash multi-map
set.sa -has set.sa $RO_SET $SET
set_incl.sa -has set_incl.sa RO_SET_INCL SET_INCL BINOP_SET_VIEW
h_set.sa -has h_set.sa SET H_SET -- Hash set
set_views.sa -has set_views.sa FILTER_SET_VIEW -- Filtered view of a set
llist.sa -has llist.sa LLIST LL_NODE -- Linked list class,
-- no abstraction as yet
btree.sa -has btree.sa B_TREE BT_NODE BT_NELEM
-- (a,b)-Trees
-- Fast workhorse container classes, to be used with care.
-- Try to only use locally within a routine or class - avoid
-- using them in interfaces. Many of these have no single abstraction
-- and contain all kinds of routines that may be useful in different
-- circumstances.
flist.sa -has flist.sa FLIST
fmap.sa -has fmap.sa FMAP
fset.sa -has fset.sa FSET -- Representation switching version of FSET
orig_fset.sa -has orig_fset.sa ORIG_FSET -- Original FSET
fqset.sa -has fqset.sa FQSET
fmultimap.sa -has fmultimap.sa FMULTIMAP
fgap_list.sa -has fgap_list.sa FGAP_LIST
-- Implementation classes
hashtab.sa -has hashtab.sa DYNAMIC_BUCKET_TABLE DYNAMIC_DATABUCKET_TABLE
BUCKET DATABUCKET
-- Test classes
tup_test.sa -has tup_test.sa TEST_TUP
array2_test.sa -has array2_test.sa TEST_ARRAY2
array3_test.sa -has array3_test.sa TEST_ARRAY3
arrays_test.sa -has arrays_test.sa TEST_ARR_ALG TEST_SORT
TEST_ARRAY TEST_LIST
flist_test.sa -has flist_test.sa TEST_FLIST
fset_test.sa -has fset_test.sa TEST_FSET
orig_fset_test.sa -has orig_fset_test.sa TEST_ORIG_FSET
fmap_test.sa -has fmap_test.sa TEST_FMAP
fmultimap_test.sa -has fmultimap_test.sa TEST_FMULTIMAP
fgap_list_test.sa -has fgap_list_test.sa TEST_FGAP_LIST
queue_test.sa -has queue_test.sa TEST_QUEUE
stack_test.sa -has stack_test.sa TEST_STACK
pq_test.sa -has pq_test.sa TEST_PQ
set_test.sa -has set_test.sa TEST_SET
map_test.sa -has map_test.sa TEST_MAP
bag_test.sa -has bag_test.sa TEST_BAG
multimap_test.sa -has multimap_test.sa TEST_MULTIMAP
llist_test.sa -has llist_test.sa TEST_LLIST -- Linked list test
btree_test.sa -has btree_test.sa TEST_BTREE BT_NODE_DBG B_TREE_DBG