[m-rev.] diff: improve consistency of set module interfaces

[Julien Fischer]

Branches: main

Make the interfaces of the set modules more consistent.

library/set_ctree234.m:
library/set_ordlist.m:
library/set_tree234.m:
library/set_unordlist.m:
library/set_bbbtree.m:
 	Add the predicate non_empty/1 to the above modules.

 	Add the from_list/1 function to those set modules that
 	lack it.

library/set_bbbtree.m:
 	Add the predicate count/2 and the function count/1.

 	Deprecate the predicate size/2.

library/set_unordlist.m:
 	Add the predicate count/2 and the function count/1.

NEWS:
 	Announce the above.

Julien.

Index: NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.547
diff -u -r1.547 NEWS
--- NEWS	23 Nov 2010 04:37:15 -0000	1.547
+++ NEWS	30 Nov 2010 02:38:12 -0000
@@ -35,7 +35,21 @@
  * We have added the predicates divide/4 and divide_by_set/4 to the tree_bitset
    module of the standard library.

-* We have added the predicate set_ctree234.member/2.
+* We have added the predicates set_ctree234.member/2 and
+  set_ctree234.non_empty/1.  We have add the function
+  set_ctree234.from_list/1.
+
+* We have added the the predicate set_bbbtree.count/2 and the
+  function set_bbbtree.count/1.  These replace the predicate
+  set_bbbtree.size/2 which is now deprecated. 
+
+* We have added the predicate set_ordlist.non_empty/1.
+
+* We have added the predicate set_tree234.non_empty/1 and the
+  function set_tree234.from_list/1.
+
+* We have added the predicates set_unordlist.non_empty/1 and
+  set_unordlist.count/2, and the function set_unordlist.count/1.

  * All of the modules in the standard library that implement the set ADT,
    (set, set_ordlist, set_unordlist, set_bbbtree, set_tree234,
Index: library/set_bbbtree.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_bbbtree.m,v
retrieving revision 1.34
diff -u -r1.34 set_bbbtree.m
--- library/set_bbbtree.m	13 Nov 2010 16:49:27 -0000	1.34
+++ library/set_bbbtree.m	30 Nov 2010 02:38:12 -0000
@@ -34,11 +34,21 @@
      %
  :- pred set_bbbtree.empty(set_bbbtree(T)::in) is semidet.

+:- pred set_bbbtree.non_empty(set_bbbtree(T)::in) is semidet.
+
      % `set_bbbtree.size(Set, Size)' is true iff `Size' is the cardinality
      % of `Set'.
+    % This predicate is obsolete; use set_bbbtree.count/2 instead.
      %
+:- pragma obsolete(set_bbbtree.size/2).
  :- pred set_bbbtree.size(set_bbbtree(T)::in, int::out) is det.

+    % `set_bbbtree.count(Set, Count)' is true iff `Set' has `Count' elements.
+    % i.e. `Count' is the cardinality (size) of the set. 
+    %
+:- func set_bbbtree.count(set_bbbtree(T)) = int.
+:- pred set_bbbtree.count(set_bbbtree(T)::in, int::out) is det.
+
      % `set_bbbtree.member(X, Set)' is true iff `X' is a member of `Set'.
      % O(lg n) for (in, in) and O(1) for (out, in).
      %
@@ -441,11 +451,19 @@

  set_bbbtree.empty(empty).

+set_bbbtree.non_empty(tree(_, _, _, _)).
+
  %------------------------------------------------------------------------------%

  set_bbbtree.size(empty, 0).
  set_bbbtree.size(tree(_V, N, _L, _R), N).

+set_bbbtree.count(Set) = Count :-
+    set_bbbtree.count(Set, Count).
+
+set_bbbtree.count(empty, 0).
+set_bbbtree.count(tree(_V, N, _L, _R), N).
+
  %------------------------------------------------------------------------------%

  % set_bbbtree.member(X, empty) :- fail.
@@ -979,8 +997,8 @@
      set_bbbtree(T)::out) is det.

  set_bbbtree.build_node(X, L, R, Tree) :-
-    set_bbbtree.size(L, LSize),
-    set_bbbtree.size(R, RSize),
+    set_bbbtree.count(L, LSize),
+    set_bbbtree.count(R, RSize),
      N = 1 + LSize + RSize,
      Tree0 = tree(X, N, L, R),
      unsafe_promise_unique(Tree0, Tree).
@@ -1076,8 +1094,8 @@
      set_bbbtree(T)::out, int::in) is det.

  set_bbbtree.balance(V, L, R, Set, Ratio) :-
-    set_bbbtree.size(L, LSize),
-    set_bbbtree.size(R, RSize),
+    set_bbbtree.count(L, LSize),
+    set_bbbtree.count(R, RSize),
      (
          Val = LSize + RSize,
          Val < 2
@@ -1090,8 +1108,8 @@
      ->
          (
              R = tree(_V0, _N0, RL, RR),
-            set_bbbtree.size(RL, RLSize),  % Right side too big.
-            set_bbbtree.size(RR, RRSize),
+            set_bbbtree.count(RL, RLSize),  % Right side too big.
+            set_bbbtree.count(RR, RRSize),
              ( RLSize < RRSize ->
                  set_bbbtree.single_rot_l(V, L, R, Set)
              ;
@@ -1107,8 +1125,8 @@
      ->
          (
              L = tree(_V1, _N1, LL, LR),
-            set_bbbtree.size(LL, LLSize),  % Left side too big.
-            set_bbbtree.size(LR, LRSize),
+            set_bbbtree.count(LL, LLSize),  % Left side too big.
+            set_bbbtree.count(LR, LRSize),
              ( LRSize < LLSize ->
                  set_bbbtree.single_rot_r(V, L, R, Set)
              ;
@@ -1137,12 +1155,12 @@
      set_bbbtree(T)::out) is det.

  set_bbbtree.concat3(L, R, Set) :-
-    set_bbbtree.size(L, LSize),
+    set_bbbtree.count(L, LSize),
      ( LSize = 0 ->
          % Left tree empty so just return the right tree.
          Set = R
      ;
-        set_bbbtree.size(R, RSize),
+        set_bbbtree.count(R, RSize),
          ( RSize = 0 ->
              % Right tree empty so just return the left tree.
              Set = L
Index: library/set_ctree234.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_ctree234.m,v
retrieving revision 1.13
diff -u -r1.13 set_ctree234.m
--- library/set_ctree234.m	13 Nov 2010 16:49:27 -0000	1.13
+++ library/set_ctree234.m	30 Nov 2010 02:38:12 -0000
@@ -50,6 +50,8 @@
      %
  :- pred set_ctree234.empty(set_ctree234(_T)::in) is semidet.

+:- pred set_ctree234.non_empty(set_ctree234(T)::in) is semidet.
+
      % `set_ctree234.member(X, Set)' is true iff `X' is a member of `Set'.
      %
  :- pred set_ctree234.member(T, set_ctree234(T)).
@@ -75,6 +77,8 @@
      %
  :- func set_ctree234.list_to_set(list(T)) = set_ctree234(T).

+:- func set_ctree234.from_list(list(T)) = set_ctree234(T).
+
      % `set_ctree234.sorted_list_to_set(List) = Set' is true iff `Set' is
      % the set containing only the members of `List'. `List' must be sorted.
      %
@@ -416,6 +420,8 @@

  set_ctree234.empty(ct(0, _)).

+set_ctree234.non_empty(ct(N, _)) :- N \= 0.
+
  :- pragma promise_equivalent_clauses(set_ctree234.member/2).

  set_ctree234.member(E::in, Set::in) :-
@@ -573,6 +579,8 @@
      !:Size = !.Size + Incr,
      set_ctree234.do_list_to_set(Es, !Size, !Tree).

+set_ctree234.from_list(List) = set_ctree234.list_to_set(List).
+
  :- pred max_level_sizes(int::in, int::in, int::in,
      list(int)::in, list(int)::out) is det.

Index: library/set_ordlist.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_ordlist.m,v
retrieving revision 1.35
diff -u -r1.35 set_ordlist.m
--- library/set_ordlist.m	13 Nov 2010 16:49:27 -0000	1.35
+++ library/set_ordlist.m	30 Nov 2010 02:38:12 -0000
@@ -25,6 +25,11 @@
  %--------------------------------------------------------------------------%

  :- type set_ordlist(_T).
+ 
+    % `set_ordlist.init(Set)' is true iff `Set' is an empty set.
+    %
+:- pred set_ordlist.init(set_ordlist(_T)::uo) is det.
+:- func set_ordlist.init = set_ordlist(T).

      % `set_ordlist.list_to_set(List, Set)' is true iff `Set' is the set
      % containing only the members of `List'.
@@ -53,11 +58,6 @@
  :- pred set_ordlist.to_sorted_list(set_ordlist(T)::in, list(T)::out) is det.
  :- func set_ordlist.to_sorted_list(set_ordlist(T)) = list(T).

-    % `set_ordlist.init(Set)' is true iff `Set' is an empty set.
-    %
-:- pred set_ordlist.init(set_ordlist(_T)::uo) is det.
-:- func set_ordlist.init = set_ordlist(T).
-
      % `set_ordlist.singleton_set(Set, Elem)' is true iff `Set' is the set
      % containing just the single element `Elem'.
      %
@@ -76,6 +76,8 @@
      %
  :- pred set_ordlist.empty(set_ordlist(_T)::in) is semidet.

+:- pred set_ordlist.non_empty(set_ordlist(T)::in) is semidet.
+
      % `set_ordlist.subset(SetA, SetB)' is true iff `SetA' is a subset of
      % `SetB'.
      %
@@ -434,6 +436,8 @@

  set_ordlist.empty(sol([])).

+set_ordlist.non_empty(sol([_ | _])).
+
  set_ordlist.subset(Subset, Set) :-
      set_ordlist.intersect(Set, Subset, Subset).

Index: library/set_tree234.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_tree234.m,v
retrieving revision 1.15
diff -u -r1.15 set_tree234.m
--- library/set_tree234.m	13 Nov 2010 16:49:27 -0000	1.15
+++ library/set_tree234.m	30 Nov 2010 02:38:12 -0000
@@ -42,6 +42,8 @@
      %
  :- pred set_tree234.empty(set_tree234(_T)::in) is semidet.

+:- pred set_tree234.non_empty(set_tree234(T)::in) is semidet.
+
      % `set_tree234.member(X, Set)' is true iff `X' is a member of `Set'.
      %
  :- pred set_tree234.member(T, set_tree234(T)).
@@ -63,6 +65,8 @@
      %
  :- func set_tree234.list_to_set(list(T)) = set_tree234(T).

+:- func set_tree234.from_list(list(T)) = set_tree234(T).
+
      % `set_tree234.sorted_list_to_set(List) = Set' is true iff `Set' is
      % the set containing only the members of `List'. `List' must be sorted.
      %
@@ -398,6 +402,10 @@

  set_tree234.empty(empty).

+set_tree234.non_empty(two(_, _, _)).
+set_tree234.non_empty(three(_, _, _, _, _)).
+set_tree234.non_empty(four(_, _, _, _, _, _, _)).
+
  :- pragma promise_equivalent_clauses(set_tree234.member/2).

  set_tree234.member(Element::out, Set::in) :-
@@ -531,6 +539,8 @@
  set_tree234.list_to_set(List) = Tree :-
      set_tree234.list_to_set_2(List, empty, Tree).

+set_tree234.from_list(List) = set_tree234.list_to_set(List).
+
  set_tree234.sorted_list_to_set(List) = Tree :-
          % XXX We should exploit the sortedness of List.
      set_tree234.list_to_set_2(List, empty, Tree).
Index: library/set_unordlist.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/set_unordlist.m,v
retrieving revision 1.31
diff -u -r1.31 set_unordlist.m
--- library/set_unordlist.m	13 Nov 2010 16:49:27 -0000	1.31
+++ library/set_unordlist.m	30 Nov 2010 02:38:12 -0000
@@ -25,12 +25,17 @@
  %--------------------------------------------------------------------------%

  :- type set_unordlist(_T).
+ 
+    % `set_unordlist.init(Set)' is true iff `Set' is an empty set.
+    %
+:- func set_unordlist.init = set_unordlist(T).
+:- pred set_unordlist.init(set_unordlist(_T)::uo) is det.

      % `set_unordlist.list_to_set(List, Set)' is true iff `Set' is the set
      % containing only the members of `List'.
      %
-:- pred set_unordlist.list_to_set(list(T)::in, set_unordlist(T)::out) is det.
  :- func set_unordlist.list_to_set(list(T)) = set_unordlist(T).
+:- pred set_unordlist.list_to_set(list(T)::in, set_unordlist(T)::out) is det.

      % A synonym for set_unordlist.list_to_set/1.
      %
@@ -54,11 +59,6 @@
      is det.
  :- func set_unordlist.to_sorted_list(set_unordlist(T)) = list(T).

-    % `set_unordlist.init(Set)' is true iff `Set' is an empty set.
-    %
-:- pred set_unordlist.init(set_unordlist(_T)::uo) is det.
-:- func set_unordlist.init = set_unordlist(T).
-
      % `set_unordlist.singleton_set(Set, Elem)' is true iff `Set' is the set
      % containing just the single element `Elem'.
      %
@@ -78,6 +78,8 @@
      %
  :- pred set_unordlist.empty(set_unordlist(_T)::in) is semidet.

+:- pred set_unordlist.non_empty(set_unordlist(_T)::in) is semidet.
+
      % `set_unordlist.subset(SetA, SetB)' is true iff `SetA' is a subset of
      % `SetB'.
      %
@@ -226,6 +228,9 @@

  :- func set_unordlist.difference(set_unordlist(T), set_unordlist(T))
      = set_unordlist(T).
+ 
+:- func set_unordlist.count(set_unordlist(T)) = int.
+:- pred set_unordlist.count(set_unordlist(T)::in, int::out) is det.

  :- func set_unordlist.map(func(T1) = T2, set_unordlist(T1))
      = set_unordlist(T2).
@@ -384,6 +389,8 @@

  set_unordlist.empty([]).

+set_unordlist.non_empty([_ | _]).
+
  set_unordlist.subset([], _).
  set_unordlist.subset([E | S0], S1) :-
      set_unordlist.member(E, S1),
@@ -489,6 +496,15 @@

  %-----------------------------------------------------------------------------%

+set_unordlist.count(Set) = Count :-
+    set_unordlist.count(Set, Count).
+
+set_unordlist.count(Set, Count) :-
+    list.remove_dups(Set, Elems),
+    list.length(Elems, Count). 
+
+%-----------------------------------------------------------------------------%
+
  set_unordlist.fold(F, S, A) = B :-
      B = list.foldl(F, set_unordlist.to_sorted_list(S), A).



--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------