Set Utilities (#29)

(an instance of Generic Utilities Package made by Hacker)

     This object is useful for operations that treat lists as sets (i.e.,
     without concern about order and assuming no duplication).
     
      union(set, set, ...) => union
      intersection(set, set, ...) => intersection
     
      diff*erence(set1, set2, ..., setn)
      => result of removing all elements of sets 2..n from set 1.
      exclusive_or(set, set, set, ...)
      => all elements that are contained in exactly one of the sets
     
      contains(set1, set2, ..., setn)
      => true if and only if all of sets 2..n are subsets of set 1
     
      equal(set1, set2)
      => true if and only if set1 and set2 are equal



VERB SOURCE CODE:

union: 
"Returns the set union of all of the lists provided as arguments.";
if (!args)
    return {};
endif
set = args[1];
for l in (listdelete(args, 1))
    for x in (l)
        set = setadd(set, x);
    endfor
endfor
return set;
.

intersection: 
"Returns the set intersection of all the lists provided as arguments.";
if (!args)
    return {};
endif
max = 0;
result = args[1];
for set in (listdelete(args, 1))
    if (length(result) < length(set))
        set1 = result;
        set2 = set;
    else
        set1 = set;
        set2 = result;
    endif
    for x in (set1)
        if (!(x in set2))
            set1 = setremove(set1, x);
        endif
    endfor
    result = set1;
endfor
return result;
.

diff*erence: 
"Usage:  diff(set 1, set 2, ..., set n)";
"Returns all elements of set 1 that are not in sets 2..n";
set = args[1];
for l in (listdelete(args, 1))
    for x in (l)
        set = setremove(set, x);
    endfor
endfor
return set;
.

contains: 
"True if the first list given is a superset of all subsequent lists.";
"False otherwise.  {} is a superset of {} and nothing else; anything is";
"a superset of {}.  If only one list is given, return true.";
super = args ? args[1] | {};
for l in (listdelete(args, 1))
    for x in (l)
        if (!(x in super))
            return 0;
        endif
    endfor
endfor
return 1;
.

exclusive_or xor: 
"Usage:  exclusive_or(set, set, ...)";
"Return the set of all elements that are in exactly one of the input sets";
"For two sets, this is the equivalent of (A u B) - (A n B).";
if (!args)
    return {};
endif
set = so_far = args[1];
for l in (listdelete(args, 1))
    for x in (l)
        if (x in so_far)
            set = setremove(set, x);
        else
            set = setadd(set, x);
        endif
    endfor
    so_far = {@so_far, @l};
endfor
return set;
.

difference_suspended diff_suspended: 
"Usage:  diff(set 1, set 2, ..., set n)";
"Returns all elements of set 1 that are not in sets 2..n";
set = args[1];
for l in (listdelete(args, 1))
    for x in (l)
        set = setremove(set, x);
        $command_utils:suspend_if_needed(0);
    endfor
endfor
return set;
.

equal: 
"True if the two lists given contain the same elements.";
"False otherwise.";
set1 = args[1];
set2 = args[2];
while (set1)
    elt = set1[1];
    set1 = listdelete(set1, 1);
    if (elt in set2)
        set2 = setremove(set2, elt);
        while (elt in set2)
            set2 = setremove(set2, elt);
        endwhile
        while (elt in set1)
            set1 = setremove(set1, elt);
        endwhile
    else
        return 0;
    endif
endwhile
if (set2)
    return 0;
else
    return 1;
endif
.


PROPERTY DATA: