home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Moscow ML 1.42 / lib / Polyhash.sig < prev    next >
Encoding:
Text File  |  1997-08-18  |  4.3 KB  |  98 lines  |  [TEXT/Moml]
  1. (* Polyhash -- polymorphic hashtables as in the SML/NJ Library, 1995-01-10 *)
  2.  
  3. type ('key, 'data) hash_table
  4.  
  5. val mkTable     : ('_key -> int) * ('_key * '_key -> bool) -> int * exn 
  6.                   -> ('_key, '_data) hash_table
  7. val numItems    : ('key, 'data) hash_table -> int
  8. val insert      : ('_key, '_data) hash_table -> '_key * '_data -> unit
  9. val peekinsert  : ('_key, '_data) hash_table -> '_key * '_data -> '_data option
  10. val find        : ('key, 'data) hash_table -> 'key -> 'data
  11. val peek        : ('key, 'data) hash_table -> 'key -> 'data option
  12. val remove      : ('key, 'data) hash_table -> 'key -> 'data
  13. val listItems   : ('key, 'data) hash_table -> ('key * 'data) list
  14. val apply       : ('key * 'data -> unit) -> ('key, 'data) hash_table -> unit
  15. val map         : ('_key * 'data -> '_res) -> ('_key, 'data) hash_table 
  16.                   -> ('_key, '_res) hash_table
  17. val filter      : ('key * 'data -> bool) -> ('key, 'data) hash_table -> unit
  18. val transform   : ('data -> '_res) -> ('_key, 'data) hash_table 
  19.                   -> ('_key, '_res) hash_table
  20. val copy        : ('_key, '_data) hash_table -> ('_key, '_data) hash_table
  21. val bucketSizes : ('key, 'data) hash_table -> int list
  22.  
  23. (*** Polymorphic hash primitives from Caml Light *)
  24.  
  25. val hash        : 'key -> int
  26. val hash_param  : int -> int -> 'key -> int
  27. val mkPolyTable : int * exn -> (''_key, '_data) hash_table
  28.  
  29.  
  30. (* [('key, 'data) hash_table] is the type of hashtables with keys of type
  31.    'key and data values of type 'data.
  32.  
  33.    [mkTable (hashVal, sameKey) (sz, exc)] returns a new hashtable,
  34.    using hash function hashVal and equality predicate sameKey.  The sz
  35.    is a size hint, and exc is the exception raised by function find.
  36.    It must be the case that sameKey(k1, k2) implies hashVal(k1) =
  37.    hashVal(k2) for all k1,k2.
  38.  
  39.    [numItems htbl] is the number of items in the hash table.
  40.  
  41.    [insert htbl (k, d)] inserts data d for key k.  If k already had an
  42.    item associated with it, then the old item is overwritten.
  43.  
  44.    [find htbl k] returns d, where d is the data item associated with key k, 
  45.    or raises the exception (given at creation of htbl) if there is no such d.
  46.  
  47.    [peek htbl k] returns SOME d, where d is the data item associated with 
  48.    key k, or NONE if there is no such d.
  49.  
  50.    [peekinsert htbl (k, d)] inserts data d for key k, if k is not
  51.    already in the table, returning NONE.  If k is already in the
  52.    table, and the associated data value is d', then returns SOME d'
  53.    and leaves the table unmodified.
  54.  
  55.    [remove htbl k] returns d, where d is the data item associated with key k, 
  56.    removing d from the table; or raises the exception if there is no such d.
  57.  
  58.    [listItems htbl] returns a list of the (key, data) pairs in the hashtable.
  59.  
  60.    [apply f htbl] applies function f to all (key, data) pairs in the 
  61.    hashtable, in some order.
  62.  
  63.    [map f htbl] returns a new hashtable, whose data items have been
  64.    obtained by applying f to the (key, data) pairs in htbl.  The new
  65.    tables have the same keys, hash function, equality predicate, and
  66.    exception, as htbl.
  67.  
  68.    [filter p htbl] deletes from htbl all data items which do not
  69.    satisfy predicate p.
  70.  
  71.    [transform f htbl] as map, but only the (old) data values are used
  72.    when computing the new data values.
  73.  
  74.    [copy htbl] returns a complete copy of htbl.
  75.  
  76.    [bucketSizes htbl] returns a list of the sizes of the buckets.
  77.    This is to allow users to gauge the quality of their hashing
  78.    function.  
  79.  
  80.    [hash k] returns a positive integer to key k. It holds that k1=k2
  81.    implies hash(k1) = hash(k2), so this function can be used when
  82.    creating hashtables.  The application hash(k) always terminates,
  83.    even on cyclic structures.  (From the Caml Light implementation).
  84.  
  85.    [hash_param n m k] computes a hash value for k with the same
  86.    properties as for hash. The parameters n and m give more precise
  87.    control over hashing.  Hashing performs a depth-first,
  88.    right-to-left traversal of the structure k, stopping after n
  89.    meaningful nodes were encountered, or m nodes, meaningful or not,
  90.    were encountered. Meaningful nodes are: integers, floating-point
  91.    numbers, strings, characters, booleans, references, and constant
  92.    constructors. 
  93.  
  94.    [mkPolyTable (sz, exc)] creates a new hashtable using the
  95.    polymorphic hash function (hash) and ML equality (op =); the integer 
  96.    sz is a size hint and the exception exc is to be raised by find.  
  97. *)
  98.