home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Moscow ML 1.42 / lib / Binaryset.sig < prev    next >
Encoding:
Text File  |  1997-08-18  |  3.3 KB  |  92 lines  |  [TEXT/Moml]
  1. (* Binaryset -- sets, implemented by ordered balanced binary trees.
  2.  *
  3.  * Modified for Moscow ML 1995-04-22 from SML/NJ lib 0.2 file ordset-sig.sml.
  4.  * COPYRIGHT (c) 1993 by AT&T Bell Laboratories.  
  5.  * See file mosml/copyrght/copyrght.att for details.
  6.  * Original implementation due to Stephen Adams, Southampton, UK.
  7.  *)
  8.  
  9. type 'item set
  10.  
  11. exception NotFound
  12.  
  13. val empty        : ('item * 'item -> order) -> 'item set
  14. val singleton    : ('item * 'item -> order) -> 'item -> 'item set
  15. val add          : 'item set * 'item -> 'item set
  16. val addList      : 'item set * 'item list -> 'item set
  17. val retrieve     : 'item set * 'item -> 'item
  18. val peek         : 'item set * 'item -> 'item option
  19. val isEmpty      : 'item set -> bool
  20. val equal        : 'item set * 'item set -> bool
  21. val isSubset     : 'item set * 'item set -> bool
  22. val member       : 'item set * 'item -> bool
  23. val delete       : 'item set * 'item -> 'item set
  24. val numItems     : 'item set ->  int
  25. val union        : 'item set * 'item set -> 'item set
  26. val intersection : 'item set * 'item set -> 'item set
  27. val difference   : 'item set * 'item set -> 'item set
  28. val listItems    : 'item set -> 'item list
  29. val app          : ('item -> unit) -> 'item set -> unit
  30. val revapp       : ('item -> unit) -> 'item set -> unit
  31. val foldr        : ('item * 'b -> 'b) -> 'b -> 'item set -> 'b
  32. val foldl        : ('item * 'b -> 'b) -> 'b -> 'item set -> 'b
  33. val find         : ('item -> bool) -> 'item set -> 'item option
  34.  
  35. (* This unit implements sets of ordered elements.  Every set is
  36.    equipped with an ordering relation; the ordering relation is used
  37.    in the representation of the set.  The result of combining two sets
  38.    (of the same type but) with different ordering relations is undefined.
  39.    The implementation uses ordered balanced binary trees.
  40.  
  41.    [empty ordr] creates a new empty set with the given ordering
  42.    relation.  
  43.  
  44.    [singleton ordr i] creates the singleton set containing i, with the
  45.    given ordering relation.
  46.  
  47.    [add(s, i)] adds item i to set s.  
  48.  
  49.    [addList(s, xs)] adds all items from the list xs to the set s.
  50.  
  51.    [retrieve(s, i)] returns i if it is in s; raises NotFound otherwise.
  52.  
  53.    [peek(s, i)] returns SOME i if i is in s; returns NONE otherwise.
  54.  
  55.    [isEmpty s] returns true if and only if the set is empty.
  56.  
  57.    [equal(s1, s2)] returns true if and only if the two sets have the
  58.    same elements.
  59.  
  60.    [isSubset(s1, s2)] returns true if and only if s1 is a subset of s2.
  61.  
  62.    [member(s, i)] returns true if and only if i is in s.
  63.  
  64.    [delete(s, i)] removes item i from s.  Raises NotFound if i is not in s.
  65.    
  66.    [numItems s] returns the number of items in set s.
  67.  
  68.    [union(s1, s2)] returns the union of s1 and s2.  
  69.  
  70.    [intersection(s1, s2)] returns the intersectionof s1 and s2.
  71.  
  72.    [difference(s1, s2)] returns the difference between s1 and s2 (that
  73.    is, the set of elements in s1 but not in s2).
  74.  
  75.    [listItems s] returns a list of the items in set s.
  76.  
  77.    [app f s] applies function f to the elements of s, in increasing
  78.    order.
  79.  
  80.    [revapp f s] applies function f to the elements of s, in decreasing
  81.    order. 
  82.  
  83.    [foldl f e s] applies the folding function f to the entries of the
  84.    set in increasing order.
  85.  
  86.    [foldr f e s] applies the folding function f to the entries of the
  87.    set in decreasing order. 
  88.  
  89.    [find p s] returns SOME i, where i is an item in s which satisfies
  90.    p, if one exists; otherwise returns NONE.
  91. *)    
  92.