PreviousUpNext

15.3.445  src/lib/src/typelocked-double-keyed-hashtable.api

## typelocked-double-keyed-hashtable.api
## AUTHOR:   John Reppy
##          AT&T Bell Laboratories
##          Murray Hill, NJ 07974
##          jhr@research.att.com

# Compiled by:
#     src/lib/std/standard.lib



# hashtables that are keyed by two keys (in different domains).



###                 IN THE NEOLITHIC AGE
###
###                 In the Neolithic Age savage warfare did I wage
###                 For food and fame and woolly horses' pelt;
###                 I was singer to my clan in that dim, red Dawn of Man,
###                 And I sang of all we fought and feared and felt.
###
###                 Yea, I sang as now I sing, when the Prehistoric spring
###                 Made the piled Biscayan ice-pack split and shove;
###                 And the troll and gnome and dwerg, and the Gods of Cliff and Berg
###                 Were about me and beneath me and above.
###
###                 But a rival, of Solutre', told the tribe my style was ~outré~ --
###                 'Neath a tomahawk of diorite he fell.
###                 And I left my views on Art, barbed and tangled, below the heart
###                 Of a mammothistic etcher at Grenelle.
###
###                 Then I stripped them, scalp from skull, and my hunting dogs fed full,
###                 And their teeth I threaded neatly on a thong;
###                 And I wiped my mouth and said, "It is well that they are dead,
###                 For I know my work is right and theirs was wrong."
###
###                 But my Totem saw the shame; from his ridgepole shrine he came,
###                 And he told me in a vision of the night:
###                 "There are nine and sixty ways of constructing tribal lays
###                  -- and every single one of them is right!"
###
###                     ...
###
###                                    -- Rudyard Kipling    (http://lrjjr.com/2005_11_01_archive.html)



api Typelocked_Double_Keyed_Hashtable {

    package key1:  Hash_Key;            # Hash_Key      is from   src/lib/src/hash-key.api
    package key2:  Hash_Key;            # Hash_Key      is from   src/lib/src/hash-key.api

    Hashtable(X);

    make_hashtable:  (Int, Exception) -> Hashtable(X);                          # The int is a size hint and the exception is to be raised by find.

    clear:  Hashtable(X) -> Void;                                               # Remove all elements from the table 

    set:  Hashtable(X) -> (key1::Hash_Key, key2::Hash_Key, X) -> Void;
        #
        # Insert an item.  If the key already has an item associated with it,
        # then the old item is discarded.


    in_domain1:  Hashtable(X) -> key1::Hash_Key -> Bool;
    in_domain2:  Hashtable(X) -> key2::Hash_Key -> Bool;
        #  return TRUE, if the key is in the domain of the table 

    get1:  Hashtable(X) -> key1::Hash_Key -> X;
    get2:  Hashtable(X) -> key2::Hash_Key -> X;
        #  Find an item, the table's exception is raised if the item doesn't exist 

    find1:  Hashtable(X) -> key1::Hash_Key -> Null_Or(X);
    find2:  Hashtable(X) -> key2::Hash_Key -> Null_Or(X);
        #  Look for an item, return NULL if the item doesn't exist 

    remove1:  Hashtable(X) -> key1::Hash_Key -> X;
    remove2:  Hashtable(X) -> key2::Hash_Key -> X;
        # Remove an item, returning the item.  The table's exception is raised if
        # the item doesn't exist.

    vals_count:  Hashtable(X) ->  Int;
        #  Return the number of items in the table 

    vals_list:   Hashtable(X) -> List(X);
    keyvals_list:  Hashtable(X) ->  List( (key1::Hash_Key, key2::Hash_Key, X) );
        #  Return a list of the items (and their keys) in the table 

    apply:   (X -> Void) -> Hashtable(X) -> Void;
    keyed_apply:  (((key1::Hash_Key, key2::Hash_Key, X)) -> Void) -> Hashtable(X)
                -> Void;
        #  Apply a function to the entries of the table 

    map:   (X -> Y) -> Hashtable(X) -> Hashtable(Y);
    keyed_map:  (((key1::Hash_Key, key2::Hash_Key, X)) -> Y) -> Hashtable(X)
                -> Hashtable(Y);
        #  Map a table to a new table that has the same keys 

    fold:   (((X, Y)) -> Y) -> Y -> Hashtable(X) -> Y;
    foldi:  (((key1::Hash_Key, key2::Hash_Key, X, Y)) -> Y) -> Y
                -> Hashtable(X) -> Y;

# * Also map'?? 
    filter:   (X -> Bool) -> Hashtable(X) -> Void;
    keyed_filter:  (((key1::Hash_Key, key2::Hash_Key, X)) -> Bool) -> Hashtable(X)
                -> Void;
        # remove any hashtable items that do not satisfy the given
        # predicate.

    copy:  Hashtable(X) -> Hashtable(X);
        #  Create a copy of a hashtable 

    bucket_sizes:  Hashtable(X) -> ((List( Int ), List( Int )) );
        # returns a list of the sizes of the various buckets.  This is to
        # allow users to gauge the quality of their hashing function.

}; #  Typelocked_Double_Keyed_Hashtable 


## COPYRIGHT (c) 1996 by AT&T Research.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.


Comments and suggestions to: bugs@mythryl.org

PreviousUpNext