
Data Structure

This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.
A   set  is a collection of elements, without duplicates and without order.



Task

Show each of these set operations:

 Set creation
 Test m ∈ S -- "m is an element in set S"
 A ∪ B -- union; a set of all elements either in set A or in set B.
 A ∩ B -- intersection; a set of all elements in both set A and set B.
 A ∖ B -- difference; a set of all elements in set A, except those in set B.
 A ⊆ B -- subset; true if every element in set A is also in set B.
 A = B -- equality; true if every element of set A is in set B and vice versa.


As an option, show some other set operations.

(If A ⊆ B, but A ≠ B, then A is called a true or proper subset of B, written A ⊂ B or A ⊊ B.)

As another option, show how to modify a mutable set.



One might implement a set using an associative array (with set elements as array keys and some dummy value as the values).

One might also implement a set with a binary search tree, or with a hash table, or with an ordered array of binary bits (operated on with bit-wise binary operators).

The basic test, m ∈ S, is O(n) with a sequential list of elements, O(log n) with a balanced binary search tree, or (O(1) average-case, O(n) worst case) with a hash table.



See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


/*REXX program  demonstrates some  common   SET   functions.                            */
truth.0= 'false';            truth.1= "true"    /*two common names for a truth table.   */
set.=                                           /*the  order  of sets isn't important.  */
 
call setAdd 'prime',2 3 2 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
call setSay 'prime'                             /*a small set of some  prime numbers.   */
 
call setAdd 'emirp',97 97 89 83 79 73 71 67 61 59 53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2
call setSay 'emirp'                             /*a small set of  backward  primes.     */
 
call setAdd 'happy',1 7 10 13 19 23 28 31 32 44 49 68 70 79 82 86 91 100 94 97 97 97 97 97
call setSay 'happy'                             /*a small set of some  happy  numbers.  */
 
      do j=11  to 100  by 10                    /*see if  PRIME  contains some numbers. */
      call setHas  'prime', j
      say '             prime contains'     j":"     truth.result
      end   /*j*/
 
call setUnion  'prime','happy','eweion';  call setSay 'eweion'                /* (sic). */
call setCommon 'prime','happy','common';  call setSay 'common'
call setDiff   'prime','happy','diff'  ;  call setSay 'diff';        _=left('', 12)
call setSubset 'prime','happy'         ;  say _ 'prime is a subset of happy:' truth.result
call setEqual  'prime','emirp'         ;  say _ 'prime is  equal   to emirp:' truth.result
exit                                                   /*stick a fork in it, we're done.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
setHas:    procedure expose set.; arg _ .,! .; return wordpos(!, set._)\==0
setAdd:    return set$('add'    , arg(1), arg(2))
setDiff:   return set$('diff'   , arg(1), arg(2), arg(3))
setSay:    return set$('say'    , arg(1), arg(2))
setUnion:  return set$('union'  , arg(1), arg(2), arg(3))
setCommon: return set$('common' , arg(1), arg(2), arg(3))
setEqual:  return set$('equal'  , arg(1), arg(2))
setSubset: return set$('subSet' , arg(1), arg(2))
/*──────────────────────────────────────────────────────────────────────────────────────*/
set$: procedure expose set.;   arg $,_1,_2,_3;   set_=set._1;   t=_3;   s=t;   !=1
      if $=='SAY'    then do;   say "[set."_1']= 'set._1;   return set._1;   end
      if $=='UNION'  then do
                          call set$ 'add', _3, set._1
                          call set$ 'add', _3, set._2
                          return set._3
                          end
      add=$=='ADD';  common=$=='COMMON'; diff=$=='DIFF'; eq=$=='EQUAL'; subset=$=='SUBSET'
      if common | diff | eq | subset  then s=_2
      if add  then do;  set_=_2;  t=_1;  s=_1;  end
 
          do j=1  for words(set_);       _=word(set_, j);       has=wordpos(_, set.s)\==0
          if (add    & \has) |,
             (common &  has) |,
             (diff   & \has)       then set.t=space(set.t _)
          if (eq | subset) & \has  then return 0
          end    /*j*/
 
      if subset  then return 1
      if eq      then  if arg()>3  then return 1
                                   else return set$('equal', _2, _1, 1)
      return set.t