home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Moscow ML 1.42 / lib / Splaymap.sig < prev    next >
Encoding:
Text File  |  1997-08-18  |  2.6 KB  |  71 lines  |  [TEXT/Moml]
  1. (* Splaymap -- applicative maps implemented by splay-trees.
  2.  * 
  3.  * Modified for Moscow ML from SML/NJ library v. 0.2 which is 
  4.  * COPYRIGHT (c) 1993 by AT&T Bell Laboratories.  
  5.  * See file mosml/copyrght/copyrght.att for details.
  6.  *)
  7.  
  8. type ('key, 'a) dict
  9.  
  10. exception NotFound
  11.  
  12. val mkDict    : ('_key * '_key -> order) -> ('_key, '_a) dict
  13. val insert    : ('_key, '_a) dict * '_key * '_a -> ('_key, '_a) dict
  14. val find      : ('key, 'a) dict * 'key -> 'a
  15. val peek      : ('key, 'a) dict * 'key -> 'a option
  16. val remove    : ('_key, '_a) dict * '_key -> ('_key, '_a) dict * '_a
  17. val numItems  : ('key, 'a) dict -> int
  18. val listItems : ('key, 'a) dict -> ('key * 'a) list
  19. val app       : ('key * 'a -> unit) -> ('key,'a) dict -> unit
  20. val revapp    : ('key * 'a -> 'b) -> ('key,'a) dict -> unit
  21. val foldr     : ('key * 'a * 'b -> 'b)-> 'b -> ('key,'a) dict -> 'b
  22. val foldl     : ('key * 'a * 'b -> 'b) -> 'b -> ('key,'a) dict -> 'b
  23. val map       : ('_key * 'a -> '_b) -> ('_key,'a) dict -> ('_key, '_b) dict
  24. val transform : ('a -> '_b) -> ('_key,'a) dict -> ('_key, '_b) dict
  25.  
  26.  
  27. (* Type ('key, 'a) dict is the type of applicative maps from domain
  28.    type 'key to range type 'a, or equivalently, applicative
  29.    dictionaries with keys of type 'key and values of type 'a.  They
  30.    are implemented as ordered splay-trees (Sleator and Tarjan).
  31.  
  32.    [mkDict ordr] returns a new, empty map whose keys have ordering
  33.    ordr.
  34.  
  35.    [insert(m, i, v)] extends (or modifies) map m to map i to v.
  36.  
  37.    [find (m, k)] returns v if m maps k to v; otherwise raises NotFound.
  38.    
  39.    [peek(m, k)] returns SOME v if m maps k to v; otherwise returns NONE.
  40.  
  41.    [remove(m, k)] removes k from the domain of m and returns the
  42.    modified map and the element v corresponding to k.  Raises NotFound
  43.    if k is not in the domain of m.
  44.  
  45.    [numItems m] returns the number of entries in m (that is, the size
  46.    of the domain of m).
  47.  
  48.    [listItems m] returns a list of the entries (k, v) of keys k and
  49.    the corresponding values v in m.
  50.  
  51.    [app f m] applies function f to the entries (k, v) in m, in
  52.    increasing order of k (according to the ordering ordr used to
  53.    create the map or dictionary).
  54.  
  55.    [revapp f m] applies function f to the entries (k, v) in m, in
  56.    decreasing order of k.
  57.  
  58.    [foldl f e m] applies the folding function f to the entries (k, v)
  59.    in m, in increasing order of k.
  60.  
  61.    [foldr f e m] applies the folding function f to the entries (k, v)
  62.    in m, in decreasing order of k.
  63.  
  64.    [map f m] returns a new map whose entries have form (k, f(k,v)),
  65.    where (k, v) is an entry in m.
  66.  
  67.    [transform f m] returns a new map whose entries have form (k, f v),
  68.    where (k, v) is an entry in m.
  69.  
  70. *)
  71.